第３ｌ卷第６期 Ｖ０ｌ＿３１ Ｎｏ．６ 长春师范学院学报（自然科学版）
Ｊｏｕｒｎａｌ ｏｆ Ｃｈａｎｇｃｈｕｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ） ２０１２年６月
Ｊｕｎ．２０１２
聚类算法的研究 刘 洋 （大庆师范学院数学科学学院，黑龙江大庆１６３７１２）
【摘要】聚类算法是多元统计的一个重要分支，在理论和实际生活中都有重要的意义。本文对聚类算 法的发展历程以及近年来发展的一些聚类算法进行研究。 【关键词】聚类算法；算法优缺点；混合模型聚类算法 【中图分类号】Ｏ２１２ 【文献标识码】Ａ 【文章编号］１００８—１７８Ｘ（２０１２）０６—０００９—０３
聚类分析研究已有很长的历史，它不仅是多元统计中的一个重要分支，而且也是数据挖掘、模式识别 等研究方向的重要内容之一．通过聚类，可以给出数据稀疏和密集的区域，发现数据整体的分布模式，以及 数据彼此之间的相互关系等．聚类分析对较大数据集的分析处理也有重要应用． 不仅如此，聚类分析在其他领域也有重要的地位．例如，商业上聚类分析用于研究消费者行为；环境上 聚类分析是检验环境污染程度，对污染成分归类的有效工具；天文学中聚类分析用来对天体归类；生物学 中聚类分析被用来对动植物和基因进行分类，获取对种群固有结构的认识及发现新的基因；计算机中聚类 分析用来进行图像的分析处理等． １ 聚类及聚类的简单分类 迄今为止，聚类还没有一个被公认的定义．在此介绍应用多元统计分析ｌｌｌ中对聚类的描述：聚类分析又 称群分析，它是研究对样品或指示进行分类的一种多元统计方法．所谓的“类”，通俗地说，就是相似元素 的集合．分类有两种情形，一是对当前所研究的问题已知它的类别数目及类特征，只需将一些未知类的个 体，正确地归属于其中某一类；二是事先不知道研究的问题应分为几类，更不知道观测数据的具体分类情 况，需要对观测数据进行分析处理，选定一种度量数据接近程度的统计量，确定分类数目，建立一种分类 方法，并按接近程度对观、钡０对象给出合理的分类．聚类原则是使分到同一类间样本性质特征尽可能相似，不 同类间样本性质特征尽可能分开． 根据不同的分类标准，聚类算法有多种分类方式．根据对观测数据先验知识的有无，聚类被划分为无监 督聚类和有监督聚类．有监督聚类为上述的第一种情形，无监督聚类为上述的第二种情形．根据对观测数据内 在的概率框架的有无，聚类又可以分为基于模型和基于判断的聚类．根据实际问题的背景，观测数据类型， 又提出基于网格的聚类、基于最小生成树聚类、模糊聚类算、自组织映射聚类、蚁群聚类等． ２聚类算法 ２．１分层聚类算法 分层聚类算法是对于给定的观测样本或指标进行层次上的分解的一种聚类算法，可以分为凝聚算法和
【收稿日期】２０１２—０４—０５ 【作者简介】刘 洋（１９８５一），女，黑龙江大庆人，大庆师范学院数学科学学院助教，硕士，从事多元统计分析研究。
・９・ 分裂算法．分类的方法：一开始将所有的对象置于一个类中，计算每两个类间距离，把距离最小的两个类合 并为一个新类，如此下去，直到每个类只包含一个对象，或者达到一个终止条件为止． 分层聚类算法优点是可以得到各个数目的类；缺点是分到各个类问的观测样本不能自动调整，聚类计 算量太大，且在聚类时易忽略新类临时产生的信息，不能自动给出最优聚类数Ｅ１．此聚类算法适用于小型数 据． ２．２ Ｋ—ｍｅａｎｓ聚类算法 １９６７年，ＭａｃＱｕｅｅｎ首次提出了Ｋ—ｍｅａｎｓ聚类算法，大体思想是在最初的观测样本或指标中找出Ｋ个 观测样本作为始聚类中心，然后计算每一观测样本与每一个聚类中心的距离，把有最短距离的样本划分为
一类，重新计算（求平均值）每个有变化的聚类中心，则得到新的聚类中心，如此下去，直到每一类都不 再发生变化为止． Ｋ—ｍｅａｎｓ聚类算法的优点是思想直观，聚类速度较快；缺点是它太依赖于初始聚类中心的选取，不能 自动给出聚类数目，仅适用于数值型数据．为此，很多学者针对Ｋ—ｍｅａｎｓ算法的缺点给出改进算法：比如 Ｈｕａｎｇ为克服仅适用于数值型数据聚类的局限性提出Ｋ—ｍｏｄｅｓ—Ｈｕａｎｇ算法［２１，针对初始聚类中心的选择，谢 娟英等给出一种改进的全局Ｋ一均值聚类算法［３１等． ２．３基于密度的聚类 此聚类算法的主要思想是以观测样本的密度为依据，把拥有较大密度的观测样本聚成一类．观测样本的 整个样本空间被低密度的观测样本划分为若干区间．算法的优点是预先不需要知道聚类的数目；缺点是只能 处理数值型观测数据，但是基于网格的聚类算法解决了这一弊端． ２．４基于模型聚类算法 基于模型聚类算法是以概率数理理论为基础的聚类算法．可以解决无监督聚类对观测噪音不能恰当处 理、对观测样本不能自动给出最优的聚类数目的弊端．基于模型的聚类算法与ＥＭ算法结合，对聚类数目的 确定，转化为模型选择问题；对观测噪音的处理，通过添加一个或多个观测数据的不同成分来处理． ２．４．１ 聚类的混合模型 观测数据集记为Ｘ＝｛ｘ１，ｘ２，ｘ３，…，ｘｎ｝，设 （ＸＩ 是数据向量Ｘ所在第血个类的概率密度函数， 为参 Ｇ 数．设ｘ可分为Ｇ个类，令仃 为Ｘ来自第ｋ个类的权重（∑丌 １），则数据集ｘ模型的一般框架为，（ ＝
＝ｌ
Ｇ ∑订 Ｉ∞，假设ｘ。，Ｘ２，Ｘ３，…，ｘｎ彼此独立，９＝（８ 一，ｏａ，观测数据ｘ的联合模型为ｆ（ｘ。，Ｘ２， ，…， ； ＝
ｋ＝－ｌ
ｎ Ｇ 兀∑７ｒ （ＸＩ ．
：ｌｔ＝１
２．４．２混合模型聚类的理论
对观测数据集 ｛ｘｌ，ｘ２， ，…，ｘｎ｝建立一个有限维的混合模型，对给定数据集Ｘ，Ｌｏｇ一似然函数直接极 大化很困难．为此，引入ｘ最有可能的分类标签向量集Ｂ＝ｆＢ ，Ｂ２，Ｂ３，…， ，Ｘ的分类标签记为Ｂｉ＝（ｂｉ ， ，…， ｒ，若数据Ｘ来自第七（ｋ＝ｌ，２，…，Ｇ）个类，则 ＝１；否则 ＝０．通常情况下假定Ｂ ，Ｂ２，伤，…，Ｂｎ独立同分
布，以概率丌。，仃 ， ，…，丌Ｇ，（∑ ＝１）来自一个多维分布．则有 Ｇ Ｐ［ ＝１ Ｉ ］＝仃 ，Ｐ ｌＢ， ＝Ⅱ （ＸＩ∞ ． ’
ｒ＿Ｉ 利用分类标签向量集Ｂ，观测数据集的ｌｏｇ一似然函数可以表示成
ｎ Ｇ ｌｏｇＬ８（８）＝∑乏Ｊ（ｂ￣＝１）ｌｏｇ（７ｒ★ｆ Ｉ ，
・１０・ 其中Ｊ（ ＝１）为示性函数．把分类标签向量集Ｂ看成缺失向量集，利用ＥＭ算法估计式子中的参数０，使得似 然函数最大化．令参数０的极大似然估计为０，Ｘ来自第ｋ个类的后验概率为 ，表达式为 Ｐ［ ：１ Ｉｘ， ］＝ ）＿． ∑音ｆｆ （Ｘｌ ０ ）
Ｊ＝ｌ
根据后验概率 对样本进行聚类，将观测数据分类到有最大后验概率的类牙０用模型选择准则ＡＩＣ，
ＢＩＣ等给出观测数据集的聚类数目ｘ的最优选择． 基于模型的聚类算法，特别是基于混合模型的聚类算法应用广泛，但是对于非正态数据以及高维混合 数据集，此算法仍需进一步完善．ＷａｎｇＬ，ＲａｍｏｎｉＭＦ，ＳｅｂａｓｔｉａｎｉＰ ２００６ Ｅ￣提出了多项式混合模型聚类方法， 提供了一个自动选择有最大后验概率的聚类数目的方法，特别适用于有孤立点数据的聚类．Ｘｉａｏ ｆｅｎｇ Ｄａｉ等 （２００９）［６１建立了独立的Ｇａｕｓｓｉａｎ与Ｂｅｔａ分布数据的有限维混合联合模型，讨论了两种不同类型数据的混合模 型． ３结论 随着科学的不断进步．数据呈现维数大、分布复杂等特点，对聚类算法的要求也越来越严格．在今后的发 展中，如何聚类不同类型的数据集，特别是观测数据的分量问结构不统一，彼此不独立的数据集．为此，应 该融合不同聚类算法的思想，利用不同算法的优缺点构建新的、解释性更合理的聚类算法．
［参考文献】 【１］高惠璇．应用多元统计分析【Ｍ］．北京：ＩＬ京大学出版社，２００５． 【２］Ｈｕａｎｇ Ｚ．Ｅｘｔｅｎｓｉｏｎｓ ｔｏ ｔｈｅ Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｃｌｕｓｔｅｒｉｎｇ ｌａｒｇｅ ｄａｔａ ｓｅｔｓ ｗｉｔｈ ｃａｔｅｇｏｒｉｃａｌ ｖａｌｕｅｓ［Ｊ］．Ｄａｔａ Ｍｉｎｉｎｇ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ＩＩ，１９９８（２）：２８３—３０４． ［３】谢娟英，蒋帅，王春霞，等．一种改进的全局Ｋ一均值聚类算法［Ｊ］．陕西师范大学学报：自然科学版，２０１０（２）：１８，２２．
【４］Ｋｏｈｏｍｅｎ Ｔ．Ｔｈｅ ｓｅｌｆ－ｏｒｇａｎｉｚｉｎｇ ｍａｐ￣］．Ｐｒｏｃ ＩＥＥＥ，１９９０，７８（９）：１４６４－１４８０． 【５］Ｗａｎｇ Ｌ，Ｒａｍｏｎｉ Ｍ Ｆ，Ｓｅｂａｓｔｉａｎｉ Ｐ．Ｃｌｕｓｔｅｒｉｎｇ ｓｈｏｒｔ ｇｅｎｅ ｅｘｐｒｅｓｓｉｏｎ ｐｒｏｆｉｌｅｓ．Ｌｅｃｔｕｒｅ Ｎｏｔｅｓｉｎ ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ：Ｒｅｓｅａｃｈ ｉｎ ｃｏｍｐｕｔａｔｉｏｎａｌ Ｍｏｌｅｃｕｔａｒ Ｂｉｏｌｏｇｙ：ｌｏｔｈ Ａｎｎｕａｌ Ｉｎｔｅｒｎａｔｉｏｎａ１．ｃｏｎｆｅｒｅｎｃｅ［Ｊ］．ＲＥＣＯＭＢ，２００６（３９０９）：６０－６８． 【６】Ｘｉａｏ Ｆｅｎｇ Ｄ，Ｔｉｍｏ Ｅ，Ｏｌｌｉ Ｙ Ｈ，ｅｔ ａ１．Ａ ｊｏｉｎｔ ｆｉｎｉｔｅ ｍｉｘｔｕｒｅ ｍｏｄｅｌ ｆｏｒ ｃｌｕｓｔｅｒｉｎｇ ｇｅｎｅｓ ｆｒｏｍ ｉｎｄｅｐｅｎｄｅｎｔ Ｇａｕｓｓｉａｎ ａｎｄ ｂｅｔａ ｄｉｓｔｒｉｂｕｔｅｄ ｄａｔａＯ］．ＢＭＣ Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，２００９（１０）：１６５．
Ｒｅｓｅａｒｃｈ ｏｎ ｔｈｅ Ｃｌｕｓｔｅｒｉｎｇ Ａｌｇｏｒｉｔｈｍ ＬＩＵ Ｙａｎｇ （Ｓｃｉｅｎｃｅ ｏｆＭａｔｈｅｍａｔｉｃｓ Ｄｅｐａｒｔｍｅｎｔ ｏｆＤａｑｉｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｄａｑｉｎｇ １６３７１２，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈ ｉｓ ａｎ ｉｍｐｏ￣ａｎｔ ｂｒａｎｃｈ ｏｆ ｍｕｈｉｖａｒｉａｔｅ ｓｔａｔｉｓｔｉｃｓ ｐｌａｙｓ ａ ｓｉｇｎｉｆｉｃａｎｔ ｒｏｌｅ ｉｎ ｔｈｅ ｔｈｅｏｒｙ ａｎｄ ｒｅａｌｉｓｔｉｃ ｌｉｆｅ．Ｔｈｅ ｐａｐｅｒ ｓｔｕｄｉｅｓ ｔｈｅ Ｒａｃｋｓ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ’Ｓ ｄｅｖｅｌｏｐｍｅｎｔ ａｎｄ ｓｏｍｅ ｋｉｎｄ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｄｅｖｅｌｏｐｅｄ ｉｎ ｒｅｃｅｎｔ ｙｅａｒｓ． Ｋｅｙ ｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ；ｔｈｅ ａｄｖａｎｔａｇｅｓ ａｎｄ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ａｌｇｏｒｉｔｈｍ；ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｎ ｍｉｘｅｄ ｍｏｄｅｌ