数据挖掘导论完整版中.ppt

基于图的聚类0102030405最小生成树聚类OPOSSUMChameleonJarvis-Patrick聚类算法基于SNN密度的聚类最小生成树聚类（minimumspanningtree，MST）计算相异度图的最小生成树01Repeat02断开对应于最大相异度的边，创建一个新的簇03Until只剩下单个簇04最小生成树聚类是一种基于分裂的层次聚类算法05最小生成树聚类可以看作用稀疏化找出簇的方法06基于图的聚类0102030405最小生成树聚类OPOSSUMChameleonJarvis-Patrick聚类算法基于SNN密度的聚类OPOSSUM：使用METIS的稀疏相似度最优划分OPOSSUM（OptimalPartitioningofSparseSimilaritiesUsingMETIS）是一种专门为诸如文档或购物篮数据等稀疏、高维数据设计的聚类技术。与MST一样，它基于邻近度图的稀疏化进行聚类。然而，OPOSSUM使用METIS算法，该算法是专门为划分图设计的。OPOSSUM聚类算法计算稀疏化的相似度图使用METIS，将相似度图划分成k个不同的分支（簇）所使用的相似性度量是适合于稀疏、高维数据的度量，如扩充的Jaccard度量或余弦度量。METIS图划分程序将稀疏图划分为k个不同的分支，其中k是用户指定的参数，旨在（1）最小化分支之间边的权值（2）实现平衡约束。OPOSSUM使用如下两种约束中的一种：（1）每个簇中的对象个数必须粗略相等，或（2）属性值的和必须粗略相等。12优点与缺点它将数据划分大小粗略相等的簇。根据聚类的目标这可能看作优点或缺点。02OPOSSUM简单、速度快。01基于图的聚类0102030405最小生成树聚类OPOSSUMChameleonJarvis-Patrick聚类算法基于SNN密度的聚类Chameleon是一种凝聚聚类技术，它解决前两段提到的问题。它将数据的初始划分与一种新颖的层次聚类方案相结合。这种层次聚类使用接近性和互连性概念以及簇的局部建模。关键思想是：仅当合并后的结果簇类似于原来的两个簇时，这两个簇才应当合并。确定合并哪些簇相对接近度（relativecloseness，RC）：是被簇的内部接近度规范化的两个簇的绝对接近度。两个簇合并，仅当结果簇中的点之间的接近程度几乎与原来的每个簇一样。mi和mj分别是簇ci和cj的大小。SEC（ci，cj）是连接簇ci和cj的边的平均值；SEC（ci）是二分簇ci的边的平均权值。相对互连度（relativeinterconnectivity,RI）：是被簇的内部互连度规范化的两个簇的绝对互连度。如果结果簇中的点之间的连接几乎与原来的每个簇一样强，两个簇合并。01其中，EC（Ci，Cj）是连接簇Ci和Cj的边之和；EC(Ci)是二分簇Ci的割边的最小和；EC(Cj)是二分簇Cj的割边的最小和。02RI和RC可以用多种不同的方法组合，产生自相似性的总量。Chameleon使用的方法是合并最大化RI(Ci,Cj)*RC(Ci,Cj)a簇对。其中a值大于1.03RelativeClosenessschemeswillmerge(a)and(b)Relativeinterconnectivityschemeswillmerge(c)and(d)构造k-最近邻图使用多层图划分算法划分图Repeat合并关于相对互连性和相对接近性而言，最好地保持簇的自相似性的簇Until不再有可以合并的簇算法估计数据分布：确定分布：一般假设数据取自高斯混合分布。然后，对分布的参数进行估计：利用EM算法进行最大似然估计利用直方图估计分布对分布进行划分、分离。每个分布对应于一个簇。12优点和缺点混合模型比k均值或模糊c均值更一般，因为它可以使用各种类型的分布。利用简单的估计分布的方法（如直方图）可能会错误估计数据的原始分布，导致结果不好。利用复杂的方法（如EM算法），计算复杂性会大大增加。基于原型的聚类01模糊聚类02使用混合模型的聚类03自组织映射自组织映射Kohonen自组织特征映射（SOFM或SOM）是一种基于神经网络观点的聚类和数据可视化技术。尽管SOM源于神经网络，但是它可以表示成一种基于原形的聚类的变形。与其他基于质心的聚类技术一样，SOM的目标是发现质心的集合，并将数据集中的每个对象指派到提供该对象最佳近似的质心。用神经网络的术语，每个质心都与一个神经元相关联。01