１２Ｏ 一种优化的Ｋ—Ｍｅａｎｓ聚类算法 一种优化的Ｋ—Ｍｅａｎｓ聚类算法 Ａｎ Ｏｐｔｉｍｉｚｅｄ Ｋ－Ｍｅａｎｓ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ 姚 奥 张 宇 （浙江理工大学信息学院，浙江杭州３１００１８） 摘要：聚类在数据挖掘领域应用广泛，但是传统的Ｋ—Ｍｅａｎｓ聚类算法存在对初始聚类中心点敏感以及需要人工设定 聚类个数Ｋ等问题。针对这些问题，在进行评论文本特征词聚类的过程中，提出了一种改进的Ｋ—Ｍｅａｎｓ聚类算法，综合利 用距离和密度来选择初始聚类中心点，并利用评测标准来确定聚类的个数Ｋ。此外，在聚类过程中，提出了利用基于知网的 相似度计算修正相似度矩阵，以及利用成对约束规则来提高聚类的准确度。实验证明，提出的方法是切实有效的。 关键词：距离，密度，初始聚类中心点 Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａｎ ｉｍｐｒｏｖｅｄ Ｋ－Ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ，ｔｈｅ ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｕｔｉｌｉｚａｔｉｏｎ ｏｆ ｄｉｓｔａｎｃｅ ａｎｄ ｄｅｎｓｉｔｙ ｔｏ ｓｅｌｅｃｔ ｔｈｅ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ，ａｎｄ ｕｓｅ ｍｅｔｒｉｃｓ ｔｏ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｐｏｌｙ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｃｌａｓｓｅｓ．Ｉｎ ａｄｄｉｔｉｏｎ，ｔｈｅ ＣｌＵＳ— ｔｅｒｉｎｇ ｐｒｏｃｅｓｓ．Ｔｈｅ ｐａｐｅｒ ａｌｓｏ ｐｒｏｐｏｓｅｓ ｔｈｅ ｕｓｅ ｏｆ ｔｈｅ ｃａｌｃｕｌａｔｉｏｎ ｏｆ ｃｏｒｒｅｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｓｉｍｉｌａｒｉｔｙ ＨｏｗＮｅｔ ｓｉｍｉｌａｒｉｔｙ ｍａｔｒｉｘ， ａｎｄ ｔｈｅ ｕｓｅ ｏｆ ｐａｉｒ ｗｉｓｅ ｃｏｎｓｔｒａｉｎｔ ｒｕｌｅｓ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｃｌｕｓｔｅｒｉｎｇ． Ｋｅｙｗｏｒｄｓ：ｄｉｓｔａｎｃｅ，ｄｅｎｓｉｔｙ，ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ
聚类分析是数据挖掘技术中一项重要的研究课题，在很多领 域都有具有广泛的应用，如模式识别、数据分析等。聚类分析的目 的是将数据对象分成若干个类或簇，使得在同一个簇中的对象之 间具有较高的相似度，而不同簇中的对象之间相似度较低＿１］。通过 聚类分析，人们能够识别出数据分布密集和稀疏的区域，发现全 局的分布模式以及数据属性之间一些意想不到的相互关系。 １ Ｋ—Ｍｅａｎｓ算法的改进 １．１初始聚类中心点选择 传统的Ｋ—Ｍｅａｎｓ聚类算法对选择的初始聚类中心点敏感， 选择不同的初始聚类中心点可能导致聚类结果的不同，从而导致 获得非全局最优解。如何选取一组最能反映数据对象的分布特征 的初始聚类中心点，最大程度的提高聚类算法的效率，本文针对 这个问题对传统的Ｋ—Ｍｅａｎｓ聚类算法进行了相应的改进。 在用欧氏距离作为相似度度量的Ｋ—Ｍｅａｎｓ聚类算法中，我 们希望选取的初始聚类中心点之间尽量的分散，相比较而言，相距 距离最远的Ｋ个数据对象更加具有代表性。但是在实际的应用 中，数据集中往往存在噪声点，这类边缘点、孤立点往往会被选取 作为聚类初始中心点，从而影响聚类的效果。而单纯的基于密度的 方法选择初始聚类中心点，则需要指定领域半径以及密度阈值，而 且忽略了距离因素。因此，本文综合考虑距离因素以及密度因素， 对Ｋ—Ｍｅａｎｓ聚类算法的初始聚类中心点选择进行了改进。 算法的基本思想是： Ｓｔｅｐ１：根据距离公式计算数据对象之间的距离，选取相距 最远的两个数据对象； Ｓｔｅｐ２：根据给定的半径ｄ与密度阈值ｍ，判断所选择的两 个点是否符合要求，若不符合，跳到Ｓｔｅｐ３；否则，跳到Ｓｔｅｐ４； Ｓｔｅｐ３：舍弃选中的两个点并标记其距离值，重新选择除标 记过的距离值以外的相距最远的两个点，并返回Ｓｔｅｐ２； Ｓｔｅｐ４：将最终符合条件的两个点以及它们的临近点作为两 个类的初始聚类，并计算其初始聚类中心； Ｓｔｅｐ５：在选取第Ｋ个初始聚类中心点时，计算其余的数据 对象到前Ｋ一１聚类中心的距离，选择距离已知分类最远的点； Ｓｔｅｐ６：根据给定的领域半径ｄ与密度阈值ｍ，判断所选的 点是否符合要求，若不是，舍弃该点并标记其距离值，重新选择 除了标记距离值以外与已知分类相距最远的点，不但重复 Ｓｔｅｐ６直到满足条件； Ｓｔｅｐ７：将满足条件的点与其临近点作为第Ｋ个初始分类， 并得到分类的初始聚类中心； Ｓｔｅｐ８：重复Ｓｔｅｐ５到Ｓｔｅｐ７，直到Ｋ不满足ＤＢＩ评估条件 为止。 在计算剩余数据对象与已知分类的距离时，我们采用如下 距离公式：
＝ｍｉｎ（ｄ（ｘ，Ｘ，），ｄ（ｘ，ｘ２），…，ｄ（ｘ。．）（Ｊ）） 换言之，数据对象到其他分类的距离是其到各个分类中心 点的距离的最小值。 １．２聚类个数的确定 传统的Ｋ—Ｍｅａｎｓ聚类算法中，聚类个数Ｋ是由用户预先 给定的。而对于非领域专家而言，聚类个数Ｋ是一个模糊的概 念。因此，我们需要一个评估指标，来确定何时的个数已达到最 佳。我们采用Ｄａｖｉｅｓ—Ｂｏｕｌｄｉｎ指数（ＤＢＩ） 来对聚类个数Ｋ进 行评估。 ＤＢＩ指标是一种评估聚类分散程度的度量标准，这是一种 内部评测方案，用分类内数据对象的紧密程度来对聚类结果进 行评测。Ｄａｖｉｅｓ—Ｂｏｕｌｄｉｎ指数实际上计算的是类内距离之和与 类间距离之和的比值［３］。 ＤＢＩ首先定义了一个分散度的值Ｓ，表示第ｉ个分类内部数 据对象的分散程度，计算公式如下： 三 一 Ｓ『＝÷ ｌｌ ｘｊ— ｌＩ
其中，Ｔ表示第ｉ个分类内数据对象的个数，Ｘｉ表示第１个分 类内的数据对象， 表示第｛个分类的质心。 其次，ＤＢＩ定义了一个距离值Ｍ，表示第ｉ个分类的质心和 第ｊ个分类的质心之间的欧氏距离，计算公式如下：
＝ＩＪ．）（『一 ｌｌ 此外，ＤＢＩ定义了相似度值Ｒ，用来表示两个分类ｉ，ｊ之间 的相似度，计算公式如下：
＝ 最后，通过计算每个分类与其他分类的最大相似度值，并得 《工业控制计算机｝２０１６年第２９卷第１ １期 １２１ 到所有分类的最大相似度值的均值，得到的便是ＤＢＩ值，计算公 式如下：
ＤＢ｛＝ Ｔ，ｍ ａｘ｜￣
在确定聚类个数Ｋ时，每当找到一个新的聚类中心点，便计 算当前的ＤＢＩ值，并与之前的ＤＢＩ值做比较，若新的ＤＢＩ参数 大于旧的ＤＢＩ，则接受当前形成的新的分类，否则，拒绝形成新 的分类，并停止聚类中心点的查找。 １．３知网相似度修正 由于共现分析的局限性，存在不合理性。例如：拿“手机的性 价比很高。”与“手机的分辨率很高。”这两句话看，“性价比”以及 “分辨率”的共现空间会十分的相似，因此这两个词的相似度会 非常高。然而“性价比”与“分辨率”在实际意义上却并不会有如 此之高的相似度。 在数据对象的相似度计算上，我们通过基于知网的词汇语 义相似度计算 ］，来改进原本单纯基于共现分析的相似度计算 结果。但是，由于网络评论文本的自由性与网络新兴词汇的流 通，知网的语义知识词典中不包含许多网络新词；再者很多词汇 的相似性具有领域相关性，比如“宝贝”和“手机”，语义上并不相 似，但是在评论中往往指的值同一个属性。因此，本文在计算数 据对象的相似度时，结合了共现分析得到的相似度与基于知网 的词汇语义相似度计算的结果，并以此来进行数据对象的聚类 分析。 １．４ ｍｕｓｔ—ｌｉｎｋ与ｃａｎｎｏｔ—ｌｉｎｋ成对约束 利用《知网》的词汇语义相似度计算修正相似度计算结果， 并不能完全解决基于共现分析的噪声问题。一方面是由于知网 的语义知识词典不能包罗所有的数据对象；另一方面是由于基 于《知网》的词汇语义相似度计算利用的是Ｈｏｗｎｅｔ中“义原”的 树状层次结构 ］，更多的是词语类别上的相似性。 因此，我们提出来利用ｃａｎｎ￣－Ｉｉｎｋ、ｍｕｓｔ—ｌｉｎｋ两项约束规 则加以辅助，以优化聚类结果。ｍｕｓｔ—ｌｉｎｋ约束规定：如果两个样 本属于ｍｕｓｔ—ｌｉｎｋ约束，那么这两个样本在聚类时必须被分配 到同一个聚类中。ｃａｎｎ￣一ｌｉｎｋ约束则相应地规定：如果两个样 本属于ｃａｎｎ￣一ｌｉｎｋ约束，那么这两个样本在聚类时必须被分配 到不同聚类之中［７］。 本文首先采用自然语言的知识来自动识别出部分ｍｕｓｔ— ｌｉｎｋ约束对，如果两个词语共享一个或几个字，例如“机子”和 “机器”，这两个词语共享“机”这个字，那么就认为这两个词语存 在ｍｕｓｔ—ｌｉｎｋ约束 ］。然后人工筛选出部分合适的ｍｕｓｔ—ｌｉｎｋ约 束对，以及人工指定部分ｃａｎｎ￣一ｌｉｎｋ约束对。最终形成的约束 对之间存在着传递性和对称性，例如“物流一快递”是一个 ｍｕｓｔ—ｌｉｎｋ约束对，那么“快递一物流”也一定是一个ｍｕｓｔ—ｌｉｎｋ 约束对，这就是ｍｕｓｔ—ｌｉｎｋ约束对的对称性，同理，ｃａｎｎｏｔ—ｌｉｎｋ 约束对也存在对称性；而若“物流一邮递”又是一个ｍｕｓｔ—ｌｉｎｋ约 束对，则“邮递一快递”也一定是一个ｍｕｓｔ—ｌｉｎｋ约束对，这就是 ｍｕｓｔ－ｌｉｎｋ约束的传递性；而若“物流一客服”是一个ｃａｎｎｏｔ—ｌｉｎｋ 约束对，那么“快递一客服”、“邮递一客服”也都是ｃａｎｎｏｔ—ｌｉｎｋ约 束对，这就是ｃａｎｎｏｔ—ｌｉｎｋ约束的传递性。 ２试验与分析 ２．１数据集及实验基础 实验所用数据集为淘宝评论集，包含共９８７７０条评论数 据。在针对在线评论文本的评价目标词的聚类工作中筛选出手 机分类的评价目标词以及其对应的特征向量，称手机分类的评 价目标词为手机类属性词，并对这些手机类属性词进行细粒度 的聚类分析。 ２＿２试验结果与分析 首先利用结合 密度、距离选择初始 聚类中心点以及通过 ＤＢＩ参数控制Ｋ值 的改进的Ｋ—Ｍｅａｎｓ 聚类算法，分别利用 属性词一属性词共现 矩阵和属性词一情感 词共现矩阵两个共 现矩阵来对手机类 的属性词进行相似 表１ 属性词一属性词共现矩阵细粒度聚类结果 初始聚类 聚类结果 手机东西机子货电池机器宝贝机 东西宝贝东东 电话通话东东手机壳屏保 待机散热 待机散热 收音机 拍照照相收音机手电筒 质量屏幕价格功能性价比声音系 统软件配件外观运行耳机信号手 感反应后盖像素字性能充电器价 声音音质 音质按键充电内存卡成色操作开 机外壳铃声字体键分辨率键盘款 式电板数据线音量设计ＧＰＳ天线 度计算，并以此实现对手机类属性词的细粒度聚类。结果分别如 表１、表２所示。 通过表１、表 ２所展示的聚类 结果我们可以看 到，利用不同的矩 阵进行聚类分析 时，Ｋ的数值会有 所不同，并且选择 的初始聚类簇也 会有差异。但是利 用不同的共现矩 阵对手机类属性 表２属性词一情藤词共现矩阵细粒度聚类结果 初始聚类 聚类结果 性价比分辨率 性价比像素分辨率 屏幕声音字 屏幕声音字按键铃声字体键盘音 按键字体键盘 量天线 音量 反应开机 运行反应操作开机ＧＰＳ 手机东西机子货电池质量机器宝 贝机价格功能系统软件配件外观 耳机信号手感电话后盖通话待机 手电简 性能充电器东东价音质充电内存 卡成色外壳拍照照相键款式电板 数据线收音机手机壳设计手电筒屏 保散热 词进行细粒度分类时，都存在分类不够细致的问题，即Ｋ的数值 偏小。在此基础上，我们在计算数据对象的相似度时添加知网相 似度的修正。然而，发现并不是每个共现矩阵都对知网的相似度 修正敏感。通过实验，发现除了属性词一属性词共现矩阵以外，其 另一个矩阵都对知网的相似度修正不敏感，即对聚类的结果几 乎没有影响。而属性 词一属性词共现矩阵 则对知网相似度修正 非常敏感，利用知网 相似度修正和ｍｕｓｔ— ｌｉｎｋ和ｃａｎｎｏｔ—ｌｉｎｋ 两类约束规则后其聚 类结果如表３所示。 通过知网的相似度修 正和规则之后，聚类 的个数Ｋ明显增加 了，分类更加细致。 ３结束语 表３添加规则处理细粒度聚类结果 初始聚类 聚类结果 功能后盖像素 质量功能外观信号后盖像素性能 性能操作电板 操作铃声键电板ＣＰＳ 电池价格性价 货电池屏幕机价格性价比系统软 比配件手感 件配件耳机手感充电器价按键 价按键内存卡 充电内存卡成色外壳款式数据线 外壳款式设计 设计天线 收音机手电筒 拍照照相收音机手电倚 分辨率 字字体分辨率键盘 机子机器 手机东西机子机器宝贝电话通话 东东 待机 待机散热 手机壳 手机壳屏保 声音音量 声音音质音量 运行反应开机 运行反应开机 实验表明，该方法是有效率的，能获得较好的细粒度分类结 果，在细粒度特征聚类上具有一定的探索价值。 参考文献 ［１］伍育红．聚类算法综述［Ｊ］．计算机科学，２０１５，４２（Ｓ１）：４９１—４９９， ５２４ ［２］Ｄａｖｉｅｓ Ｄ Ｌ．Ｂｏｕｌｄｉｎ Ｄ Ｗ，Ａ Ｃｌｕｓｔｅｒ Ｓｅｐａｒａｔｉｏｎ Ｍｅａｓｕｒｅ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ ｌｎｔｅｌｌｉ— ｇｅｎｃｅ，１ ９７９（２）：２２４—２２７ （下转１２４页）