数据挖掘中聚类分析综述

・２２６・　价值工程　数据挖掘中聚类分析综述　Ｏｖｅｒｖｉｅｗ　ｏｆ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｎａｌｙｓｉｓ　ｉｎ　Ｄａｔａ　Ｍｉｎｉｎｇ　张静ＺＨＡＮＧ　Ｊｉｎｇ　（六安职业技术学院信息工程系，六安２３７０００）　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｌｕ，粕Ｖｏｃａｔｉｏｎａｌ　Ｔｅｃｈｎｉｃａｌ　Ｃｏｌｌｅｇｅ，Ｌｕ＇ａｎ　２３７０００，Ｃｈｉｎａ）　摘要：数据挖掘中的聚类技术是一种非监督分类技术。概述了聚类分析算法中的数据结构和数据类型，分析了聚类分析的意义　及研究现状，比较了几种聚类算法的优点及问题，并结合通信领域的应用指出了Ｋ—Ｍｅａｎｓ聚类技术的绝对优势。　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　ｔｅｃｈｎｏｌｏｇｙ　ｉｎ　ｄａｔａ　ｍｉｎｉｎｇ　ｉｓ　ａ　ｋｉｎｄ　ｏｆ　ｕｎｓｕｐｅｒｖｉｓｅｄ　ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ｔｅｃｈｎｉｑｕｅｓ．Ｔｈｅ　ｐａｐｅｒ　ａｎａｌｙｓｅｓ　ｔｈｅ　ｄａｔａ　ｓｔｒｕｃｔｕｒｅ　ａｎｄ　ｄａｔａ　ｔｙｐｅｓ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ａｎａｌｙｓｉｓ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｓｉｇｎｉｉｃａｆｎｃｅ　ａｎｄ　ｒｅｓｅｎｔ　ｒｅｓｅａｒｃｈ　ｏｆ　ｃｌｕｓｔｅｒ　ａｎａｌｙｓｉｓ，ｃｏｍｐａｒｅｓ　ｔｈｅ　ａｄｖａｎｔａｇｅｓ　ａｎｄ　ｄｉｓａｄｖａｎｔａｇｅｓ　ｏｆ　ｓｅｖｅｒａｌ　ｋｉｎｄｓ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ，ｐｏｉｎｔｓ　ｏｕｔ　ｔｈｅ　ａｂｓｏｌｕｔｅ　ａｄｖａｎｔａｇｅｓ　ｏｆ　Ｋ－ｎｅｓｌ１８　ｃｌｕｓｔｅｒｉｎｇ　ｔｅｃｈｎｏｌｏｇｙ　ｃｏｍｂｉｎｅｄ　ｗｉｔｈ　ｔｈｅ　ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｆｅｉｌｄ．　关键词：数据挖掘；聚类分析；Ｋ—Ｍｅａｎｓ算法　Ｋｅｙ　ｗｏｒｄｓ：ｄａｔａ　ｍｉｎｉｎｇ；ｃｌｕｓｔｅｒｉｎｇ　ａｎａｌｙｓｉｓ；Ｋ—Ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ　中图分类号：ＴＰ２７４　０引言　文献标识码：Ａ　文章编号：１００６—４３１１（２０１４）１５—０２２６—０２　数据挖掘，也称知识发现数据库（ＫＤＤ）ｒ”，就是从实际　的大量的、不完全的，含有噪声的数据中去提取出人们事　先不知道的、隐含在其中的对人们有用的知识和信息的过　程。数据挖掘经常被企业决策者利用，通过挖掘企业中存　储的大量数据中的潜在的有价值的信息，从而帮助企业经　营者做出正确的决策，为企业创造更多的利益。聚类技术　作为数据挖掘的的重要技术之一，也更多的为人们认识和　使用。本文分析了几种主要的聚类算法的优点及存在的问　作者简介：张静（１９８２一），女，安徽六安人，六安职业技术学院，硕　士，专业教师，研究方向为数据挖掘。　题，并指出Ｋ—Ｍｅａｎｓ￣聚类技术在通信领域的绝对优势。　１聚类的定义　聚类分析［３】仅根据在数据中发现的描述对象及其关系　的信息，将数据对象分组。其目标是，组内的对象相互之间　是相关的，而不同组的对象是不相关的，组内相似度越大，　组间差别度越大，聚内效果就越好。聚类分析技术作为强　大的辅助工具在科学研究、社会服务、市场营销等多个领　域发挥了巨大的作用。因此聚类分析技术研究也成为一个　热点课题。　２聚类分析算法中的数据结构和数据类型　２＿１数据结构一般聚类分析中的数据用以下两种数　据结构来表示：　能存在转载方式，与原网页内容一致，就容易误判为重复。　２．１网页预处理查重之前的工作是对网页中各种链　接、图片信息、广告信息删除，去掉所有噪声，只保留网页　的纯文本信息。下一步要对纯文本信息进行统一的归一化　处理，利用语法规则，对标点符号、英文字母、空格、回车符　等分隔符进行一致优化，保证对文本的信息提取时的准确　量化。为了提取网页指纹信息，运用信息检索技术，得到被　检测网页中关键词的频率集合Ｆ＝ｆＦ。，Ｆ２，Ｆ３…Ｆｍｌ，从中选　取前ｎ个（ｎ＜ｍ）频率大的关键词作为网页指纹的关键词　Ｆ：｛Ｆ１，Ｆ２…Ｆｎ）；下一步确定这ｎ个关键词的位置向量集合　Ｔ＝｛Ｔｌ，Ｔ２…Ｌ｝。关键词Ｆ及对应的向量Ｔ组成网页指纹　图２网页查重算法流程图　Ｋｉ（Ｑ），即：Ｋｉ（　｛Ｋ　。，Ｔ１），Ｋ２（Ｆ２，　ｒ２）…Ｋｏ（　，　｝。　本文提出的利用关键词及位置向量结合构成网页指　２．２网页指纹算法利用提取有特征的网页指纹Ｋ　（Ｑ）　纹的算法，避免了传统查重技术中只有关键词而造成的准　与特征库的指纹信息Ｋ（Ｄ）进行计算比较，利用公式（１）得　确率不高的情况发生，提升了查重效率，提高了用户浏览　到相似度ｓ，再与设定的阈值　比较，得出网页是否重复，　网页信息的准确度和效率。　提高网页查重的准确率。网页查重算法流程为：①第一步　参考文献：　对被检测网页预处理，对链接、广告、图片等噪声进行去噪　［１１＝１＝希杰．一种基于网页指纹的网页查重技术研究［Ｊ］．计算机　处理。得到纯文本信息。②对关键词及位置向量进行提取，　仿真，２０１１（９）：１５４—１５７．　构成网页指纹信息。③比较网页指纹信息，计算相似度。④　［２】马成前，毛许光．网页查重算法ｓｈｉｎｇｌｉｎｇ和ｓｉｍｈａｓｈ研究　与设定阈值　比较得出是否为重复网页。　［Ｊ】．计算机与数学工程，２００９，３７（１）：１５—１７．　网页查重算法流程如图２所示。　［３】白广慧，连浩，刘悦，程学旗．网页查重技术在企业数据仓库　３结束语　中的应Ｊ￣［Ｊ１．计算机应用，２００５（０７）．　・２２７・　①数据矩阵　对象一属性结构组成了数据矩阵。它由ｎ个对象组成，　例如：人；用Ｐ个属性来描述每个对象，例如：身高、体重、　出生日期等。可以使用ｎＸｐ矩阵或关系表的形式来表示数　据矩阵，如式（１）所示。　Ｘｌｌ…Ｘｌｆ…Ｘ【ｐ　Ｘｊ１…Ｘ　…Ｘｉｐ　变则须另当别论。在基于密度的聚类算法中，密度代替了　数据的相似性，根据数据对象的分布密度，将密度聚类分　析算法及应用足够大的区域相连结，从而发现任意形状的　簇。这类算法除了可以发现任意形状的簇，而且能有效地　起到消除噪声的作用。密度算法主要包括ＤＢＳＣＡＮ，　０Ｐ１１ＣＳ，ＤＥＮＣＬＵＥ等。　３．４基于网格的方法所谓基于网格的聚类算法就是　种把量化的网格空间进行聚类的算法。一方面，这种算　法可以提高计算效率ｉ但另一方面这种算法很难检测到斜　侧边界的聚类，只能针对垂直或水平的聚类。基于网格的　一ｘｎ１…　…ｘ“ｐ　聚类算法一般与数据集的大小不相关，而计算时间的复杂　②相异度矩阵　程度只决定于网格单元的数目，ＷａｖｅＣｌｕｓｔｅｒ、ＳＴＩＮＧ、　相异度矩阵是一个对象一对象结构。它包含ｎ个对象　ＣＬＩＱＵＥ等都是常见的基于网格的聚类算法。　互相之间差异。我们一般用ｎ　Ｘ　ｎ矩阵来表示相异度矩　３．５基于模型的方法所谓基于模型的算法就是一种　阵，如式（２）所示。　通过给每个聚类设定模型并在此基础上进行数据集选择　０　的计算方法。这类算法试图对给定数据和某些数学模型之　ｄ（２，１）０　间的拟合进行优化。基于模型的聚类计算方法是以数据符　ｄ（３，１）ｄ（３，２）０　合潜在的概率分布的假设前提为基础的，ＥＭ、神经网络、　：　：　：　（２）　概念聚类等都是常见的基于模型的算法。　ｄ（ｎ，１）ｄ（ｎ，２）……０　３．６聚类方法的比较目前，聚类算法包含很多种，它　２．２数据类型在实际应用中，数据挖掘任务面对的　们各不相同，有各自的特色：基于层次的算法适用于不同　更多的是非数值型数据对象以及复合数据类型，数据复杂　粒度上多层次的聚类结构；而基于密度的算法适用于形状　且多样化，布尔类型、有序数据类型、分段数值变量、标称　任意、数目不确定的聚类，而且还能起到消除噪声的作用；　型变量、二元、序数型以及混合型组合变量和比例型变量　基于模型的计算方法适用于已知数据分布的聚类；基于划　等都是在数据挖掘中常常会遇到的数据类型变量。　分的算法在处理聚类个数固定的聚类上有着明显优势，而　３主要的聚类算法　且它偏好球形的聚类；而基于网格的聚类有较强的计算优　目前，在数据挖掘中聚类的算法主要可分为以下几　势。因此，在进行数据挖掘中聚类分析时，人们可以根据具　种：划分算法、层次方法、基于密度的算法、基于模型的方　体应用场景和实际需求选择最佳聚类方法。　法以及基于网格的方法。下面将详细列出几种算法，并予　４总结与展望　以简单的介绍和分析。　随着科技的发展和信息量的成倍增长，聚类算法的研　３＿１划分方法所谓划分方法就是将包含有ｎ个数据　究和应用也越来越受到人们的关注。以通信企业为例，通　对象的数据集合分为ｍ个组，其中每个组都是一个聚类，　信企业的客户量大，拥有海量的通信数据，聚类算法中的　从定义可以看出，这种聚类要满足以下两点：①每个分组　Ｋ—Ｍｅａｎｓ算法恰恰是一种高效的可伸缩的算法，它在处理　至少要包含一个～个数据对象；②每个数据对象只能归属　大数据量尤其是海量数据时有着明显的优势，而且聚类的　在一个分组当中，不能出现一个数据对象同时归属几个分　质量相对较好。Ｋ—Ｍｅａｎｓ算法效果主要受下列几个因素的　组的情况，使用反复迭代的方法进行分组效果会更佳。最　影响：　终在计算时，使得每次改进后的分组方案较之前一次都更　①选择初始凝聚点；②聚类个数Ｋ的设定；③变量值　胜一筹，同一分组当中，各个数据对象越近越好，而一些部　的标准化及距离选择；④异常值处理；⑤变量的相关性；⑥　分的算法应用对于条件②的限制可以适当放宽一些。在聚　优化准则。　类算法中，ｋ一平均（ｋ—ｍｅａｎｓ）算法和ｋ一中心点（ｋ—ｍｅｄｏｉｄｓ）　参考文献：　算法是最重要的两种算法，除此之外的其他类型的划分方　［１】李丹丹．数据挖掘技术及其发展趋势［Ｊ］．电脑应用技术，　法都是在它们的基础上演化而来的。　２００７（６９）：３８—４１．　３．２层次方法层次聚类算法将数据集进行层次分　［２］ＣＬＩＩ￣ＴＯＮ　ＣＨＲＩＳＴＯＰＨＥＲ　Ｗ，ＭＵＬＬＩＧＡＮ　ＤＥＩＲＤＲＥ　Ｋ，　●　解。分为自下向上凝聚（ａｇｇｌｏｍｅｒａｔｉｖｅ）Ｐ＝次聚类和自上向　ＲＡＧＨＵ　ＲＡＭＡＫＲＩＳＨＮＡＮ．Ｄａｔａ　Ｍｉｎｉｎｇ　ａｎｄ　Ｐｒｉｖａｃｙ：Ａｎ　Ｏｖｅｒｖｉｅｗ　下的分裂法（ｄｉｖｉｓｉｖｅ）层次聚类两种。凝聚的层次聚类将每　［Ｍ】．Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．１９９６：１９３．　个数据对象单独分成一个组，再逐步合并分组达到终止函　【３】李兴森，李军．中小企业数据挖掘应用方案Ⅱ】．软件世界，　数的限制。分裂法层次聚类，先将所有数据对象放到一个　２００７（７１：６３—６４．　分组中，然后再渐渐划分为小的分组，直到达到了某个终　ｆ４１朱明擞据挖掘［Ｍ】．北京：中国科技出版社，２００２：３４＿４０．　『５】刘云生．数据库设计与分析［Ｍ】．武汉：华中理工大学出版　止条件。常用的层次聚类方法包括ＢＩＲＣＨ，ＣＵＲＥ，ＲＯＣＫ，　社，１９９３：５５—６０．　Ｃｈａｍｅｌｅｏｎ算法等ｏ　［６］ＰＨＡＭ　Ｄ　Ｔ，ＤＩＭＯＶ　Ｓ　Ｓ，ＮＧＵＹＥＮ　Ｃ　Ｄ．Ｓｅｌｅｃｔｉｏｎ　ｏｆ　Ｋ　ｉｎ　３．３基于密度的方法目前，对于非球形数据集的聚　Ｋ－ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ［Ｊ］．Ｍｅｃｈａｎｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｓｃｉｅｎｃｅ，２００４，２１９：　变来说，基于距离的算法是可行的，但对于其他类型的巨　】０３－１１９．