・４ ・ Ｃｏｍｐｕｔｅｒ Ｅｒａ Ｎｏ．８ ２０１０ 改进的聚类分析算法及其性能分析 郭书杰，吴小欣，黄杰 （９１５５０指控中心，辽宁大连１ １６０２３） 摘要：提出了一种改进的聚类分析算法，该算法采用类似中间聚类与最终聚类分布的思想，先对密集区域进行聚类， 形成了Ｋ个聚类，然后再对相对分散的自由数据进行Ｋ—ｍｅａｎｓ聚类，使聚类分析在迭代过程中始终沿着最优的方向进行， 减小了迭代次数，提高了收敛速度。该算法融合了网格聚类与Ｋ一均值聚类的优点，并且引入了一种新的划分网格的算法 和新的计算密度阀值的函数。理论分析以及实验证明，改进算法的聚类过程达到了令人满意的效果。 关键词：聚类分析；Ｋ一均值算法；网格聚类；融合聚类 Ｉｍｐｒｏｖｅｄ Ｃｌｕｓｔｅｒｉｎｇ Ａｎａｌｙｓｉｓ Ａｌｇｏｒｉｔｈｍ ａｎｄ Ｉｔｓ Ｐｅｒｆｏｒｍａｎｃｅ Ａｎａｌｙｓｉｓ ＧＵＯ Ｓｈｕ－ｊｉｅ，ＷＵ Ｘｉａｏ－ｘｉｎ，ＨＵＡＮＧ Ｊｉｅ （Ｃｏｍｍａｎｄ ａｎｄ Ｃｏｎｔｒｏｌ Ｃｅｎｔｅｒ ｏｆ Ａｒｍｙ ９１５５０，Ｄａｌｉａｎ，Ｌｉａｏｎｉｎｇ １１６０２３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｎ ｉｍｐｒｏｖｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｎａｌｙｓｉｓ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ．Ｕｓｉｎｇ ｔｈｅ ｉｄｅａ ｓｉｍｉｌａｒ ｔｏ ｈａｌｆ－ｆｉｎｉｓｈｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｎｄ ｆｉｎａｌ ｃｌｕｓｔｅｒｉｎｇ ｄｉｓｔｒｉｂｕｔｉｏｎ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｆｉｒｓｔｌｙ ｃｌｕｓｔｅｒｓ ｃｏｎｃｅｎｔｒａｔｅｄ ｒｅｇｉｏｎｓ ｔｏ ｇｅｔ Ｋ ｃｌｕｓｔｅｒｓ，ａｎｄ ｔｈｅｎ ｃｌｕｓｔｅｒｓ ｒｅｌａｔｉｖｅｌｙ ｓｃａｔｔｅｒｅｄ ｆｒｅｅ ｄａｔａ ｉｎ Ｋ—ｍｅａｎｓ，ｗｈｉｃｈ ｍａｋｅｓ ｃｌｕｓｔｅｒｉｎｇ ａｎａｌｙｓｉｓ ａｌｗａｙｓ ｆｏｌｌｏｗ ｏｐｔｉｍａｌ ｄｉｒｅｃｔｉｏｎ ｉｎ ｉｔｅｒａｔｉｖｅ ｐｒｏｃｅｓｓ，ｒｅｄｕｃｅｓ ｉｔｅｒａｔｉｏｎ ｔｉｍｅｓ ａｎｄ ｉｍｐｒｏｖｅｓ ｃｏｎｖｅｒｇｅｎｃｅ ｓｐｅｅｄ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｎｔｅｇｒａｔｅｓ ｔｈｅ ａｄｖａｎｔａｇｅｓ ｏｆ ｇｒｉｄ—ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｎｄ Ｋ ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ，ａｎｄ ｉｎｔｒｏｄｕｃｅｓ ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｏｆ ｐａｒｔｉｔｉｏｎｉｎｇ ｇｒｉｄ ａｎｄ ｎｅｗ ｆｕｎｃｔｉｏｎ ｏｆ ｃｏｍｐｕｔｉｎｇ ｄｅｎｓｉｔｙ ｔｈｒｅｓｈｏｌｄ．Ｔｈｅ ｔｈｅｏｒｅｔｉｃａｌ ａｎａｌｙｓｉｓ ａｎｄ ｅｘｐｅｒｉｍｅｎｔｓ ｐｒｏｖｅ ｔｈａｔ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｐｒｏｃｅｓｓ ｏｆ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ａｃｈｉｅｖｅｓ ｓａｔｉｓｆａｃｔｏｒｙ ｒｅｓｕｌｔｓ． Ｋｅｙ ｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ ａｎａｌｙｓｉｓ；Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ；ｇｒｉｄ—ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ；ｆｕｓｉｏｎ ｃｌｕｓｔｅｒｉｎｇ ０引言 聚类问题的经典算法，然而Ｋ＿均值具有人为确定ｋ值、过分依 Ｉ．，：ｌＩ．＋（卜惦，１．＋ｊ ６．Ｊ，ｊ＝１ ２”，Ｐ （１） Ｋ一均值是目前应用最为广泛的聚类分析算法之一，是解决 得出。 定义２网格单元密度：网格单元Ｃ。的密度Ｄｅｎ（Ｃ，）定义为 赖ｋ初始聚类中心点的缺点，而且运算量大，效率不高。目前对 该网格单元中的数据点的个数。 于Ｋ一均值算法的改进也有很多种，比如基于遗传算法的Ｋ一均 定义３密集单元与自由数据：设定密度阀值为Ｍｉｎｐｔｓ，将 值…、引入惩罚因子的Ｋ一均值 、ＰＢＫＰ算法 等。 密度大于密度阀值Ｍｉｎｐｔｓ的网格定义为密集单元，将密度小于 网格聚类算法的效率非常高，而且可以发现任意形状的 密度阀值的单元中的数据称为自由数据。 簇，但是网格聚类也存在种种的缺陷，比如依赖于密度阀值 定义４聚类重心：给定簇ｌ（ｊ＝（ｔｊＪ，ｔｌ 一，Ｌ ），则其均值即聚类 的选择等。目前对于网格聚类的改进算法也有很多，比如二分 重心定义为 网格聚类ｎ 、自适应网格聚类 、ＧＣＨＬ 等。 本文针对上述算法的缺点，结合他们的优点提出一种改进 的聚类分析算法——融合聚类分析算法。 其中ｎｌ为簇Ｉ（ｊ中对象的个数，ｘ，ｙ为簇 中的两两不同的对象。 定义５中间聚类：对样本空间进行划分，定义单元网格集， １融合聚类分析算法 １．１算法的基本概念 ｚ．＝ 设Ａ＝（Ｄ ，Ｄ ，…，Ｄ ）是ｎ个有界定义域，Ｓ＝Ｄ ×Ｄｚ×…×Ｄ 是一个ｎ维空间，我们将Ｄ ，Ｄ ，…，Ｄｎ看成是ｓ的维。算法的输 入则是一个ｎ维空间的点集，设为Ｖ＝｛ｖ ，ｖ。，…，ｖ ），其中ＶＩ＝｛Ｖ 计算网格单元的密度，将密度密集的单元进行网格聚类，这一 过程叫中间聚类。中间聚类只包含分布比较密集的点，并不包 含全部的聚集对象，中间聚类生成的簇叫中间聚类簇。 定义６后聚类：中间聚类结束后，计算每个中间聚类簇的 ｖ …，ｖ １代表第ｉ个点，ｖ Ｄｊ表示第ｉ个点的第ｊ维的分量。 定义１网格单元：不妨设第ｉ维上的分布点取值在区间［１１’ ｈｉ）中， ｌ ２一，ｎ，将每一维分成Ｐ个不相交的左闭右开的等长区 问，这些区间就称为网格单元。这样，数据空问被分割成Ｐ 个 ，ｈ；一１；、 中心作为初始中心点，然后对剩余的自由数据进行ｋ—ｍｅａｎｓ聚 类，这一过程叫做后聚类，所产生的簇叫做后聚类簇。 １．２算法的基本思想 首先基于网格聚类分析的思想，对样本空间进行划分定义 网格单元集，将对象映射到相应的网格单元中，计算网格单元 的数据，由邻近的密集单元合并形成“中间聚类簇”（中间聚 网格单元，网格单元在第ｉ维上的长度为８ｉ： ｐ ，第ｉ维上的 的密度，标记密度大于密度阀值ｔ的单元和密度小于密度ｌ酬直 第ｊ个区间段可由式（１） 计算机时代２０１０年第８期 ・ ５ ・ 类簇并不包含比较离散的自由数据）；计算中间聚类簇的重心 个数。在本算法中，由于已经对数据集进行了基于密度和网格 使得中间聚类中心与最终聚类中心分布类 作为初始聚类中心点，计算自由数据到每个聚类中心的距离， 的中间聚类处理，将自由数据分配到最近的中间聚类中，形成“后聚类簇”；重新 似，这样对于自由数据进行Ｋ一均值聚类，需要的迭代次数就会 计算每个后聚类的初始聚类中心，若无变化则算法终止，若有 很小，相对的时间也会大大缩短。从以上的分析来看融合算法 变化则重新进行聚类，直到满足条件完成聚类。 网格定义本身就是一个难题，网格大小与放置对于聚类的 总的时间复杂度最大时为０（ｎ）＋Ｏ（２ Ｘ ｍ’）＋０（ｋ Ｘ ｔ×ｎ），整个聚 类过程所需要的时问与数据集中的数据点数成线性关系，与维 ２．２试验结果对比 结果具有很大的影响，如何划分网格对于算法非常重要。在融 数成指数关系，总体来阱融合聚类在时间上是高效的。合算法中，引入了一种新的函数用于网格的划分： Ｏ＝一 实验的样本数据使用了著名的鸢尾花（Ｉｒｉｓ）数据集，该数据 式中，ｌ。为第ｉ分量的长度， １，２，…，ｎ。 “ 同时，基于网格的聚类非常依赖于密度阀值一ｒ的选择， 过大或者过小都会影响算法的性能。在融合算法中，对于密度 阀值的确定，提出了一种新的算法： ｌ Ｄｅｎ（Ｃ．） ｌ— Ｍｉｎｐｔｓ＝ 式中Ｄｅｎ（Ｃ ），ｉ＝ｌ，２，…，Ｎ为密度最高的Ｎ个密集单元的密度 值，Ｎ的值视具体的数据而定。一般情况下将Ｄｅｎ（Ｃ ）降序排 列，如果Ｄｅｎ（Ｃ．）与Ｄｅｎ（Ｃ ）发生明显跳变，则Ｎ＝ｉ。 １．３算法的步骤 根据】．２节算法基本思想的描述，算法的基本步骤如下。 ｓｔｅｐ ｌ：将数据空间划分为ｍ个不相交、等长的网格单元， 定义网格单元集； ｓｔｅｐ ２：将对象指派到合适的单元中； ｓｔｅｐ ３：计算每个单元的密度； ｓｔｅｐ ４：将密度大于密度阀值Ｍｉｎｐｔｓ的网格标记为“密集单 元”，将密度小于密度阀值的单元中的数据标记为“自由数据”； ｓｔｅｐ ５：反复任选一未被聚类的密集单元，将其和与之相邻 的密集单元合并为一簇，直至所有密集单元均被聚类，形成Ｋ 个“中问聚类”； ｓｔｅｐ ６：计算这Ｋ个中间聚类的重心ｚ．【ｌ“，作为初始聚类 中心； ｓｔｅｐ ７：反复任选一自由数据对象，计算其与ｋ个初始聚类 中心的距离ｄｉｓ（ｘ，Ｃ ），其中ｘ为自由数据对象，Ｃ 为第ｉ个类，若 ｄｉｓ（ｘ，Ｃ．）最小，则Ｘ Ｃ。，直至不再存在自由数据，形成“后聚类”； ｓｔｅｐ ８：重新计算后聚类的重心Ｚｌ｛ｌ’，若ｌＺ。 ’Ｚ， ”ｌ ０ 聚类结束，否则继续进行Ｋ一均值聚类，直到ｆＺ，“ ’Ｚ ’ ｌｓ完 成聚类。 ２融合聚类算法的性能检验与分析 ２．１时间复杂度分析 在本算法中，定义网格、将数据的对象映射到网格中并且 计算刚格密度，这一过程的时『日】复杂度为Ｏ（ｎ），ｎ为点的个数； 对于每个密集单元，检查所有与它相关联的密集单元生成簇， 假设密集单元的总个数为ｍ’，与一个密集单元相关联的单元数 最大值为２ ，则这个过程的时间复杂度为０（２“×ｍ’）。后聚类的 时间复杂度为Ｏ（ｋ×ｔ×ｎ ），其中ｔ是迭代次数，ｎ’是自由数据的 集可以从加州大学欧文分校的机器学习数据库中得到。该数 据集包括３类花的４个特性：萼片宽度、萼片长度、花瓣宽度、花 瓣长度，共１５０条纪录。 首先，对比融合算法与网格聚类算法的聚类结果。使用 ＧＢ算法对数据进行聚类，得到的结果如图１所示。 图１ ＧＢ的聚类结果 从 １我们可以看出，网格聚类的结果丢失了很多点，聚类 结果不能令人满意。这是由于基于 格的聚类只处理高密度 区域，低密度区域会被丢弃，造成簇的丢失。但是使用融合聚 类得到的结果（如图２所示）要比网格聚类的结果好很多。 图２融合的聚类结果 接下来，对比融合聚类算法的聚类结果与Ｋ一均值聚类算 法的聚类结果。利用融合聚类算法进行多次试验，聚类的过程 经历了中间聚类、后聚类、１次迭代后便结束聚类，共得到３ 类。每个类的初始中心在每个聚类阶段的值如表ｌ所示。 ・ ６ ・ Ｃｏｍｐｕｔｅｒ Ｅｒａ Ｎｏ．８ ２０１０ 表１融合聚类结果 中间聚类 类０ ６．６３３３３３３３３ ３ ｌ６６６６６６６７ ５ ４７９ ｐ９９５５ 找更优的初始聚类中心，总是不断变化着聚类中心，使得算法 最终聚类 ６．８５ ３．０７３６８４ ５．７４２１０５ 后聚类 ６．８４０５４１ ３．０７８３７８ ５．７５１３５１ 不能很陕收敛，算法的迭代次数也明显增加到１ １次。 ２．２３ Ｉ９９９７８ ２．１１３５１３ ２．０７１０５３ 类１ ４．９８１８１８１８８ ３．３８６３６３６４７ ｌ ４７４９９９９９７ ０．２４５４５４５５ ５．ｏｏ７８４３ ３．４ １．４９４１１８ Ｏ ２６Ｉ）７８４ ５．ｏ０６ ３．４１８ １．４６４ ０．２４４ 类２ ６．２７３３３３３２７ ２．６９３３３３３５６ ４．５３３３３３３６５ Ｌ４（）６６６６６４４ ５．９３５４８４ ２．７５４８３９ ４．４３２２５８ １．４２４１９４ ５．９０１６１３ ２．７４８３８７ ４．３９３５４８ １．４３３８７１ 图４ Ｋ—ｍｅａｎｓ的初始聚类中心 综上所述，我们可以看出，基于凝聚度和分离度的簇的性 图３给出了该次聚类过程中聚类中心变化的折线图。图中 能评估，融合算法要优于Ｋ－ｍｅａｎｓ算法。每个类的聚类中心在每个阶段变化都不大，且迅速地收敛，这 ３结束语 说明融合聚类算法得出的密集单元很好地模拟了数据集合中 本文所提出的融合聚类分析算法，取得了很好的实验结 密集区域的分布，很快地确定了Ｋ个初始聚类中心点，然后又 果。但算法仍然存在着不足之处，比如合适的密度阀值的选择 利用Ｋ一均值聚类将自由数据重新聚类，可以快速有效地完成 比较困难等，这些因素会影响到算法的性能，这也是今后需要 聚类。 我们继续研究和改进的地方。 参考文献： 【１】王敞，陈增强，袁著祉．基于遗传算法的Ｋ～均值聚娄分析【Ｊ】计算机科 学，２００３ ３０（２）：１６３—１６４ ｆ２Ｊ王红睿，赵黎明，裴剑．均衡化的改琏均值聚类法［ＪＪ．吉林大学学报（信 息科学版），２００６．２４（２）：１７１～１７６ 【３】Ｙａｎｊｕｎ Ｌｉ，Ｓｏｏｎ Ｍ．Ｃｈｕｎｇ．Ｐａｒａｌｌｅｌ ｂｉｓｅｃｔｉｎｇ ｋ－ｍｅａｎｓ ｗｉｔｈ ｐｒｅｄｉｃｔｉｏｎ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｇｒｉｄ Ｃｏｍｐｕｔｉｎｇ， ２００７．３９：１９－３７ 【４】岳士弘，王正友．二分网格聚粪方法及有效性【Ｊ】．计算机研究与发展， ２００５．４２（９）：１５０５－１５１０ 图３融合的初始聚类中心 １５】曾蒙福，马亨冰．一种自适应网格聚类算法的研究【Ｊ】．福建电脑， ２００６．３：１０５～１０６ 利用Ｋ＿均值聚类对Ｉｒｉｓ数据进行多次实验得到的结果，从 初始聚类中心到最终聚类中心变化都很大。如图４所示，在该 次聚类过程中，Ｋ－均值算法很随机地抽取了３个点作为初始聚 类中心，由于不能很好地捕获自然聚类的中心，算法不断地寻 【６１ Ｐｉｌｅｖａｒ，Ａ．Ｈ．Ｓｕｋｕｍａｒ．Ａ ｇｒｉｄ—ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｈｉｇｈ－ｄｉｍｅｎ— ｓｉｏｎａｌ ｖｅｒｙ ｌａｒｇｅ ｓｐａｔｉａｌ ｄａｔａ ｂａｓｅｓ［Ｊ１．Ｍ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ Ｌｅｔｔｅｒｓ，２００５．２６（７）：９９９～１０１１ （上接第３页） 以保证数据的一致眭，是数据库系统可靠性的基石。数据库的 一代混合型数据引擎的工作上，取得了令人欣慰的进展，并推 ０混合数据管理产品。 增删改都会通过事务方式来完成。在混合引擎中，应很好地将 出了ＣＧＲＳ６． 事务机制与倒排列表的修改融合起来，使得对文本倒排索引的 参考文献： Ｎａｖｉｎ Ｋａｂｒａ，Ｒａｇｈｕ Ｒａｍａｋｒｉｓｈｎａｎ，Ｖｕｋ Ｅｒｃｅｇｏｖａｃ．Ｔｈｅ ＱＵＩＱ 修改是可控的且结构化数据保持一致。对于关键任务的应用 ［１ｊ来说，容错与Ｉ炙复也是很重要的特性。这也对ＩＲ中倒排索引的 更新与修改提出了更高的要求。事务失败，索引状态应回滚到 Ｅｎｇｉｎｅ：Ａ Ｈｙｂｒｉｄ ＩＲＤＢ Ｓｙｓｔｅｍ［Ｒ］．科技报告．ＴＲ一１４４９．美国成斯 康辛州麦迪逊：威斯康星一麦迪逊大学，２００２ 【２１ Ｊｕｓｔｉｎ Ｚｏｂｅ１．Ａｎ Ｅｆｆｉｃｉｅｎｔ Ｉｎｄｅｘｉｎｇ Ｔｅｃｈｎｉｑｕｅ ｆｏｒ Ｆｕ１ｌ—ｔｅｘｔ 前一个与数据一致的状态。事务提交，查询用户才能检索到索 引的当前状态。 Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍｓ［ＡＪ．第１８次ＶＬＤＢ会议论文集ｆｑ．加拿大不列颠 哥伦比亚省温哥华，１９９２． 【３】Ｃｈｕｎ Ｚｈａｎｇ，Ｊｅｒｅｙ Ｆ．Ｎａｕｇｈｔｏｎ，Ｄａｖｉｄ Ｊ．ＤｅＷｉｔｔ，Ｑｉｏｎｇ Ｌｕｏ，Ｇｕｙ Ｍ．Ｌｏｈｍａｎ．，Ｏｎ ｓｕｐｐｏｒｔｉｎｇ ｃｏｎｔａｉｎｍｅｎｔ ｑｕｅｒｉｅｓ ｉｎ ｒｅｌａｔｉｏｎａｌ ４结束语 虽然内核级融合的方案存在着一些必须克服的技术困难， 但这应该是面对结构化数据和文本混合应用难题时最值得探 索和实践的方向。浙江天宇信息技术有限公司，已经在研究新 ｄａｔａｂａｓｅ ｍａｎａｇｅｍｅｎｔ ｓｙｓｔｅｍｓ［Ａ］．ＡＣＭ ＳＩＧＭＯＤ会议论文集【Ｃ】． 美国加州圣巴巴拉，２００１・ 潮
