附加问题与算法.pptVIP

基于图的聚类01最小生成树聚类03Chameleon05基于SNN密度的聚类02OPOSSUM04Jarvis-Patrick聚类算法最小生成树聚类（minimumspanningtree，MST）最小生成树聚类可以看作用稀疏化找出簇的方法最小生成树聚类是一种基于分裂的层次聚类算法Until只剩下单个簇断开对应于最大相异度的边，创建一个新的簇Repeat计算相异度图的最小生成树EDCBAF基于图的聚类最小生成树聚类OPOSSUMChameleonJarvis-Patrick聚类算法基于SNN密度的聚类OPOSSUM：使用METIS的稀疏相似度最优划分使用METIS，将相似度图划分成k个不同的分支（簇）04计算稀疏化的相似度图03OPOSSUM（OptimalPartitioningofSparseSimilaritiesUsingMETIS）是一种专门为诸如文档或购物篮数据等稀疏、高维数据设计的聚类技术。与MST一样，它基于邻近度图的稀疏化进行聚类。然而，OPOSSUM使用METIS算法，该算法是专门为划分图设计的。01OPOSSUM聚类算法02所使用的相似性度量是适合于稀疏、高维数据的度量，如扩充的Jaccard度量或余弦度量。METIS图划分程序将稀疏图划分为k个不同的分支，其中k是用户指定的参数，旨在（1）最小化分支之间边的权值（2）实现平衡约束。OPOSSUM使用如下两种约束中的一种：（1）每个簇中的对象个数必须粗略相等，或（2）属性值的和必须粗略相等。优点与缺点OPOSSUM简单、速度快。01它将数据划分大小粗略相等的簇。根据聚类的目标这可能看作优点或缺点。02基于图的聚类最小生成树聚类OPOSSUMChameleonJarvis-Patrick聚类算法基于SNN密度的聚类这种层次聚类使用接近性和互连性概念以及簇的局部建模。关键思想是：仅当合并后的结果簇类似于原来的两个簇时，这两个簇才应当合并。02Chameleon是一种凝聚聚类技术，它解决前两段提到的问题。它将数据的初始划分与一种新颖的层次聚类方案相结合。01确定合并哪些簇相对接近度（relativecloseness，RC）：是被簇的内部接近度规范化的两个簇的绝对接近度。两个簇合并，仅当结果簇中的点之间的接近程度几乎与原来的每个簇一样。01mi和mj分别是簇ci和cj的大小。SEC（ci，cj）是连接簇ci和cj的边的平均值；SEC（ci）是二分簇ci的边的平均权值。021相对互连度（relativeinterconnectivity,RI）：是被簇的内部互连度规范化的两个簇的绝对互连度。如果结果簇中的点之间的连接几乎与原来的每个簇一样强，两个簇合并。2其中，EC（Ci，Cj）是连接簇Ci和Cj的边之和；EC(Ci)是二分簇Ci的割边的最小和；EC(Cj)是二分簇Cj的割边的最小和。3RI和RC可以用多种不同的方法组合，产生自相似性的总量。Chameleon使用的方法是合并最大化RI(Ci,Cj)*RC(Ci,Cj)a簇对。其中a值大于1.LimitationsofCurrentMergingSchemesRelativeClosenessschemeswillmerge(a)and(b)Relativeinterconnectivityschemeswillmerge(c)and(d)构造k-最近邻图使用多层图划分算法划分图Repeat合并关于相对互连性和相对接近性而言，最好地保持簇的自相似性的簇Until不再有可以合并的簇优点与局限性Chameleon能够有效地聚类空间数据，即便存在噪声和离群点，并且簇具有不同的形状、大小和密度。01Chameleon假定由稀疏化和图划分过程产生的对象组群是子簇，即一个划分中的大部分点属于同一个真正的簇。如果不是，则凝聚层次聚类将混合这些错误，因为它绝对不可能再将已经错误地放到一起的对象分开。这样，当划分过程未产生子簇时，chameleon就有问题，对于高维数据，常常出现这种情况。02共享最近邻相似性SNN（sharednearestneighbor）相似度计算：1找出所有点的k-近邻2If两个点x和y不是相互在对方的k-最近邻中then3similarity(x,y)?04Else5similarity(x,y)?共享的近邻个数6Endif7算法估计数据分布：确定分布：一般假设数据取自高斯混合分布。然后，对分