一种改进的基于局部密度的聚类算法
- 格式：pdf
- 大小：389.25 KB
- 文档页数：6
迄今为止 ，国内外研究人员相继提出很多聚类算法。 主要分为基于层次的聚类、基于划分 的聚类、基于密度的 聚类、基于网格的聚类、基于模型的聚类等嗍。基于层次的聚 类是指对样本集合进行合并或者分裂，直到满足某一个终
收 稿 日期 ：２０１５—０６—０８；修 回 日期 ：２０１５—１１—０２
· ５５ ·
Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒｉｎｇ ａｎａｌｙｓｉｓ ｉｓ ａｎ ｉｍ ｐｏｒｔａｎｔ ａｎｄ ｃｈａｌｌｅｎｇｉｎｇ ｒｅｓｅａｒｃｈ ｆ ｉｅｌｄ ｉｎ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ａｎｄ ｄａｔａ ｍｉｎｉｎｇ．Ａ ｆａｓｔ ａｎｄ ｅｆｅｃｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｉｄｅａ ｏｆ ｌｏｃａｌ ｄｅｎｓｉｔｙ ｗａｓ ｐｒｏｐｏｓｅｄ ｂｙ Ａｌｅｘ．Ｂｕｔ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ａｎｄ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ ｉｎ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｗｅｒｅ ｄｅｔｅｒ ｍ ｉｎｅｄ ｂｙ ｈａｎｄ．Ｔｈｅｒｅｆｏｒｅ，ｔ ｈｅ ｃａｎｄｉｄａｔｅｓ ｏｆ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ ｂａｓｅｄ ｏｎ ｌｏｃａｌ ｄｅｎｓｉｔｙ ｗｅｒｅ ｆ ｉｒ ｓｔｌｙ ｓｅｌｅｃｔｅｄ ａｎｄ ｔｈｅｎ ｄｅｎｓｉｔｙ ｃｏｎｎｅｃｔｉｖｉｔｙ ｍｅｔｈｏｄ ｗａｓ ｕｓｅｄ ｔｏ ｏｐｔｉｍｉｚｅ ｔｈｅ ｃａｎｄｉｄａｔｅｓ．Ｔ ｈ ｅ ｃｌａｓｓｅｓ ｏｆ ｓａｍｐｌｅｓ ａｒｅ ｔｈｅ ｓａｍｅ ａｓ ｔ ｈｅ ｎｅａｒｅｓｔ ｃｅｎｔｅｒ ｗｉｔ ｈ ｂｉｇｇｅｒ ｌｏｃａ ｌ ｄｅｎｓｉｔｙ．Ｅｘｐｅｒ ｉｍｅｎｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｈａｓ ａ ｂｅｔｔｅｒ ｃｌｕｓｔｅｒ ｅｆｆｉｃｉｅｎｃｙ ａｎｄ ｃａｎ ｈａｎｄｌｅ ｔｈｅ ｐｒｏｂｌｅｍｓ ｏｆ ｕｎｃｅｒｔａｉｎ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ａｎｄ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ． Ｋ ｅｙ ｗｏｒｄｓ：ｌｏｃａｌ ｄｅｎｓｉｔｙ，ｃｌｕｓｔｅｒ ｃｅｎｔｅｒ，ｅｖａｌｕａｔｉｏｎ ｃｒｉｔｅｒ ｉｏｎ
１．Ｃｏｌｌｅｇｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒ ｉｎｇ ａｎｄ Ａｒｔ Ｄｅｓｉｇｎ，Ｚｈ￣ｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ
Ｗａｔｅｒ Ｒｅｓｏｕｒｃｅｓ ａｎｄ Ｅｌｅｃｔｒ ｉｃ Ｐｏｗｅｒ，Ｈａｎｇｚｈｏｕ ３１００１８，Ｃｈｉｎａ
２．Ｃｏｌｌｅｇｅ ｏｆ Ｓｃｉｅｎｃｅ，Ｚｈｅｊｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｎｇｚｈｏｕ ３ １００２３，Ｃｈｉｎａ
于 局 部 密 度 的 聚 类 算 法 是 一 种 快 速 、有 效 的 聚 类 方 法 ，但 该 方 法 通 过 手 工 选 取 确 定 聚 类 个 数 和 聚 类 中 心 。 为
此 ．对 原 算 法 进 行 改 进 ．在 初 步 选 取 候 选 聚类 中 心 的基 础 上 ，使 用 基 于 密 度 连 通 的算 法 优 化 选 取 聚类 中心 ，然
１ 引 言
聚类是指在没有任何先验知识的情况下 。根据数据特 征的相似性将同类数据聚集在一起的过程 ，属于无监督分 类的范畴。聚类的目标是使得同一类簇内对象的相似性尽 可能大，不同类簇之间对象的相似性尽可能小。聚类作为
一 种重要的数据分析和挖掘手段，已被广泛应用于语音识 别、字符识别、图像处理、信息安全、金融等领域。
后 使 用 大 密 度 最 近 邻 方 法 确 定 样 本 类 别 。实 验 证 明 ，该 方 法 能 有 效 解 决 聚 类 个 数 和 聚 类 中心 无 法 确 定 的 问标 上 显 示 出较 好 的 聚类 效 果 和性 能 。
关 键 词 ：局 部 密 度 ；类 簇 中心 ；评 价 指 标
研究与开发
一 种改进 的基 于局 部密度 的聚类算法
关 晓 惠 ’，钱 亚冠 ，孙 欣欣 ’ （１．浙 江水利 水 电 学院 ，浙 江 杭 州 ３１００１８；２．浙 江科 技 学院理 学 院 ，浙 江 杭 州 ３１００２３）
摘 要 ：聚 类 分 析 一 直 是 机 器 学 习 和 数 据 挖 掘 领 域 一 个 比 较 活跃 而 且 极 具 挑 战性 的 研 究 方 向 。 Ａｌｅｘ提 出 的 基
止条件，代表算法有 ＢＩＲＣＨ算法、ＣＵＲＥ算法１７２］。优点是能 得到不同粒度的聚类结构，缺点是很难确定合并和分裂的 准则。基于划分的聚类是指首先将所有数据粗略地划分为
个类 ，然后通过迭代算法使某个准则达到最优来对划分 进行修正。代表算法有 ｋ－ｍｅａｎｓ算法、ｋ中心点方法及其改 进 】。优点是算法简单、速度快 ，缺点是 值需要事先指 定，而且只能发现圆形类簇。基于密度 的聚类算法是指 根据数据对象 的分布密度 ，将密度足够大的数据对象聚 类在一起 ，样本空间被低密度区间划分开 。代表算法有 ＤＢＳＣＡＮ算法、０ ＩＣＳ算法、ＤＥＮＣＬＵＥ算法［７４。优点是可 以发现任意形状的类簇，缺点是参数的设置对聚类结果影 响较大。基于网格的聚类是指将数据空间量化为有限单元． 构成一个可以聚类的网格结构 ，代表算法有 ＳＴＩＮＧ算法、 ＣＬＩＱＵＥ算法 。优点是运算速度快 ，缺点是存在量化尺度 问题。基于模型的聚类是指寻找给定数据与某种数据模型 的最佳拟合 ，代表方法有 ＣＯＢＷＥＢ算法、ＡｕｔｏＣｌａｓｓ算法、 ＳＯＭ算法 １４１。
中图 分 类 号 ：ＴＮ９２９．５
文 献 标 识 码 ：Ａ
ｄｏｉ：１０．１ １９５９／ｊ．ｉｓｓｎ．１０００—０８０１．２０１６００８
Ａ ｎ ｉ￣ｍ ．ｐｒｏｖｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉ ｔｈ‘ ｍ ｂａｓｅｄ ｏｎ ｌｏｃａ ｌ ｄｅｎｓｉｔｙ
ＧＵＡＮ Ｘｉａｏｈｕｉ ，ＱＩＡＮ Ｙａｇｕａｎ ，ＳＵＮ Ｘｉｎｘｉｎ
收 稿 日期 ：２０１５—０６—０８；修 回 日期 ：２０１５—１１—０２
· ５５ ·
Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒｉｎｇ ａｎａｌｙｓｉｓ ｉｓ ａｎ ｉｍ ｐｏｒｔａｎｔ ａｎｄ ｃｈａｌｌｅｎｇｉｎｇ ｒｅｓｅａｒｃｈ ｆ ｉｅｌｄ ｉｎ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ａｎｄ ｄａｔａ ｍｉｎｉｎｇ．Ａ ｆａｓｔ ａｎｄ ｅｆｅｃｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｉｄｅａ ｏｆ ｌｏｃａｌ ｄｅｎｓｉｔｙ ｗａｓ ｐｒｏｐｏｓｅｄ ｂｙ Ａｌｅｘ．Ｂｕｔ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌｕｓｔｅｒｓ ａｎｄ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ ｉｎ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｗｅｒｅ ｄｅｔｅｒ ｍ ｉｎｅｄ ｂｙ ｈａｎｄ．Ｔｈｅｒｅｆｏｒｅ，ｔ ｈｅ ｃａｎｄｉｄａｔｅｓ ｏｆ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ ｂａｓｅｄ ｏｎ ｌｏｃａｌ ｄｅｎｓｉｔｙ ｗｅｒｅ ｆ ｉｒ ｓｔｌｙ ｓｅｌｅｃｔｅｄ ａｎｄ ｔｈｅｎ ｄｅｎｓｉｔｙ ｃｏｎｎｅｃｔｉｖｉｔｙ ｍｅｔｈｏｄ ｗａｓ ｕｓｅｄ ｔｏ ｏｐｔｉｍｉｚｅ ｔｈｅ ｃａｎｄｉｄａｔｅｓ．Ｔ ｈ ｅ ｃｌａｓｓｅｓ ｏｆ ｓａｍｐｌｅｓ ａｒｅ ｔｈｅ ｓａｍｅ ａｓ ｔ ｈｅ ｎｅａｒｅｓｔ ｃｅｎｔｅｒ ｗｉｔ ｈ ｂｉｇｇｅｒ ｌｏｃａ ｌ ｄｅｎｓｉｔｙ．Ｅｘｐｅｒ ｉｍｅｎｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｈａｓ ａ ｂｅｔｔｅｒ ｃｌｕｓｔｅｒ ｅｆｆｉｃｉｅｎｃｙ ａｎｄ ｃａｎ ｈａｎｄｌｅ ｔｈｅ ｐｒｏｂｌｅｍｓ ｏｆ ｕｎｃｅｒｔａｉｎ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ａｎｄ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ． Ｋ ｅｙ ｗｏｒｄｓ：ｌｏｃａｌ ｄｅｎｓｉｔｙ，ｃｌｕｓｔｅｒ ｃｅｎｔｅｒ，ｅｖａｌｕａｔｉｏｎ ｃｒｉｔｅｒ ｉｏｎ
１．Ｃｏｌｌｅｇｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒ ｉｎｇ ａｎｄ Ａｒｔ Ｄｅｓｉｇｎ，Ｚｈ￣ｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ
Ｗａｔｅｒ Ｒｅｓｏｕｒｃｅｓ ａｎｄ Ｅｌｅｃｔｒ ｉｃ Ｐｏｗｅｒ，Ｈａｎｇｚｈｏｕ ３１００１８，Ｃｈｉｎａ
２．Ｃｏｌｌｅｇｅ ｏｆ Ｓｃｉｅｎｃｅ，Ｚｈｅｊｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｎｇｚｈｏｕ ３ １００２３，Ｃｈｉｎａ
于 局 部 密 度 的 聚 类 算 法 是 一 种 快 速 、有 效 的 聚 类 方 法 ，但 该 方 法 通 过 手 工 选 取 确 定 聚 类 个 数 和 聚 类 中 心 。 为
此 ．对 原 算 法 进 行 改 进 ．在 初 步 选 取 候 选 聚类 中 心 的基 础 上 ，使 用 基 于 密 度 连 通 的算 法 优 化 选 取 聚类 中心 ，然
１ 引 言
聚类是指在没有任何先验知识的情况下 。根据数据特 征的相似性将同类数据聚集在一起的过程 ，属于无监督分 类的范畴。聚类的目标是使得同一类簇内对象的相似性尽 可能大，不同类簇之间对象的相似性尽可能小。聚类作为
一 种重要的数据分析和挖掘手段，已被广泛应用于语音识 别、字符识别、图像处理、信息安全、金融等领域。
后 使 用 大 密 度 最 近 邻 方 法 确 定 样 本 类 别 。实 验 证 明 ，该 方 法 能 有 效 解 决 聚 类 个 数 和 聚 类 中心 无 法 确 定 的 问标 上 显 示 出较 好 的 聚类 效 果 和性 能 。
关 键 词 ：局 部 密 度 ；类 簇 中心 ；评 价 指 标
研究与开发
一 种改进 的基 于局 部密度 的聚类算法
关 晓 惠 ’，钱 亚冠 ，孙 欣欣 ’ （１．浙 江水利 水 电 学院 ，浙 江 杭 州 ３１００１８；２．浙 江科 技 学院理 学 院 ，浙 江 杭 州 ３１００２３）
摘 要 ：聚 类 分 析 一 直 是 机 器 学 习 和 数 据 挖 掘 领 域 一 个 比 较 活跃 而 且 极 具 挑 战性 的 研 究 方 向 。 Ａｌｅｘ提 出 的 基
止条件，代表算法有 ＢＩＲＣＨ算法、ＣＵＲＥ算法１７２］。优点是能 得到不同粒度的聚类结构，缺点是很难确定合并和分裂的 准则。基于划分的聚类是指首先将所有数据粗略地划分为
个类 ，然后通过迭代算法使某个准则达到最优来对划分 进行修正。代表算法有 ｋ－ｍｅａｎｓ算法、ｋ中心点方法及其改 进 】。优点是算法简单、速度快 ，缺点是 值需要事先指 定，而且只能发现圆形类簇。基于密度 的聚类算法是指 根据数据对象 的分布密度 ，将密度足够大的数据对象聚 类在一起 ，样本空间被低密度区间划分开 。代表算法有 ＤＢＳＣＡＮ算法、０ ＩＣＳ算法、ＤＥＮＣＬＵＥ算法［７４。优点是可 以发现任意形状的类簇，缺点是参数的设置对聚类结果影 响较大。基于网格的聚类是指将数据空间量化为有限单元． 构成一个可以聚类的网格结构 ，代表算法有 ＳＴＩＮＧ算法、 ＣＬＩＱＵＥ算法 。优点是运算速度快 ，缺点是存在量化尺度 问题。基于模型的聚类是指寻找给定数据与某种数据模型 的最佳拟合 ，代表方法有 ＣＯＢＷＥＢ算法、ＡｕｔｏＣｌａｓｓ算法、 ＳＯＭ算法 １４１。
中图 分 类 号 ：ＴＮ９２９．５
文 献 标 识 码 ：Ａ
ｄｏｉ：１０．１ １９５９／ｊ．ｉｓｓｎ．１０００—０８０１．２０１６００８
Ａ ｎ ｉ￣ｍ ．ｐｒｏｖｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉ ｔｈ‘ ｍ ｂａｓｅｄ ｏｎ ｌｏｃａ ｌ ｄｅｎｓｉｔｙ
ＧＵＡＮ Ｘｉａｏｈｕｉ ，ＱＩＡＮ Ｙａｇｕａｎ ，ＳＵＮ Ｘｉｎｘｉｎ
