Chap53 聚类分析

1、武汉大学测绘学院 李英冰YB Li, SGG, Wuhan University5.3 聚类分析Cluster analysisNot Taking obstacles into accountTaking obstacles into account武汉大学 李英冰1.基本概念 2.划分方法（ K-均值， K-中心点） 3.层次方法 （BIRCH，CHAMELEON ）4.基于密度的方法 5.基于格网的方法 6.高级聚类分析7.聚类评估 目录2武汉大学 李英冰簇: 一个数据对象集合。簇中对象彼此相似; 与其他簇不相似聚类分析：将对象分为相对同质群组的统计分析技术分类与聚类的区别q分类：用已知

2、类别的样本训练集来设计分类器q聚类：事先不知样本类别，利用样本先验知识来构造分类器31. 基本概念AKQJAKQJAKQJAKQJ武汉大学 李英冰4聚类分析的基本思想样品号x1x2xp123nn个样品的p个指标样品聚类(Q)变量（指标）聚类(R)距离最近的原则相似系数最大的原则武汉大学 李英冰闵可夫斯基距离 欧氏距离(L2 norm) 曼哈顿距离(city block, L1 norm) 上确界距离(Lmax norm, L norm) 距离计算 222( , )1122d i jijijipjpxxxxxx|.|),(2211ppjxixjxixjxixjid( , )1122hhhhipj

3、pd i jijijxxxxxx1h1( , )maxlimphphifjfjfd i jifjfxxxx5武汉大学 李英冰单链接：两簇元素间的最小距离全链接：两簇元素间的最大距离平均距离：两簇元素间的平均距离中心点距离:两簇的中心点的距离6距离度量XXXXXXXX武汉大学 李英冰7簇的中心、半径和直径 ) 1(2)(11NNiqtiptNiNimDNmciptNimR2)(1中心 半径直径NtNiipmC)(1武汉大学 李英冰21),(iCpkicpdEi82. 划分方法 将包含n个对象的数据集 D 分配到k 个簇，所有对象Ci 和形心之间的误差平方和最小 给定 k，划分k簇的优化算法：qK

4、-均值（k-Means）: 一种基于形心的技术qK-中心点（k-Medoids or PAM） ：一种基于代表对象的技术武汉大学 李英冰基本步骤:1.取得k个初始初始中心点2.把每个点划分进相应的簇3.重新计算中心点4.迭代计算中心点5.收敛92.1 K-均值（K-Means ）算法武汉大学 李英冰10K-Means 算法示例K=2任意划分对象为k 组更新簇的形心更新簇的形心重新分 配对象Loop if needed初始数集nPartition objects into k nonempty subsetsnRepeatnCompute centroid (i.e., mean point)

5、for each partition nAssign each object to the cluster of its nearest centroid nUntil no change武汉大学 李英冰算法的复杂度为O(tkn), 注释: 经常终止于局部最优11K-Means 算法注释Input & centroidsMaxIterations & ConvergenceSelected kMeassures数据的采集和抽象初始的中心选择最大迭代次数收敛值 k值的选定 度量距离的手段factors？武汉大学 李英冰053-周垠驰-基于K均值聚类法的城市土地划分12K-Mean

6、s应用：图像分类武汉大学 李英冰对俄勒冈州波特兰市夜生活娱乐地点的聚类结果13K-Means应用：对地理坐标进行聚类武汉大学 李英冰如何修改K-均值算法，降低它对离群点的敏感性？k中心点算法不采用簇中对象的平均值作为簇中心，而选用簇中离平均值最近的对象作为簇中心142.2 K-中心点（K-Medoids ）算法012345678910012345678910012345678910012345678910武汉大学 李英冰15K-Medoids 步骤Total Cost = 20012345678910012345678910K=2任意选取k 个对象作为中心点分配每个剩余的对象到最近的中心点随机

7、选择一个非代表对象Oramdom计算代替对象的总代价012345678910012345678910Total Cost = 26如果质量改善，交换 O 和 Oramdom Do loopUntil no change012345678910012345678910武汉大学 李英冰层次聚类方法将数据对象组成一棵聚类树。163. 层次方法p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixC1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity MatrixC1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity Matr

8、ix武汉大学 李英冰根据层次分解是自底向上（合并）还是自顶向下（分裂），进一步分为凝聚的和分裂的。17层次方法的分类Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d eStep 4Step 3Step 2Step 1Step 0凝聚的层次聚类(AGNES)分裂的层次聚类(DIANA)武汉大学 李英冰使用概率模型度量簇之间的距离q把待聚类的数据对象看做要分析的基础数据生成机制的一个样本，或生成模型实践中，可以该数据的生成模型采用常见的分布函数（ 如高斯分布，或伯努利分布）它们由参数确定18概率层次聚类1-d Gaussian2-d Gau

9、ssian概率层次聚类的簇合并：合并C1和C2使总体聚类质量提高，但合并C3和C4不能武汉大学 李英冰凝聚层次聚类的主要弱点q不能撤销先前步骤所做的工作 q可伸缩性不好: 时间复杂度至少为 O(n2 ）层次&距离的结合 qBIRCH (1996)：使用聚类特征树的多阶段聚类qCHAMELEON (1999): hierarchical clustering using dynamic modeling19层次聚类的拓展武汉大学 李英冰BIRCH采用多阶段聚类技术：扫描产生一个基本的聚类，额外扫描进一步改进聚类质量BIRCH主要步骤：1.扫描数据库，建立一棵存放于内存的CF树 2.采用任

10、意的聚类算法对CF-tree 页节点进行聚类两个概念q聚类特征（CF）q聚类特征树（CF tree）203.1 BIRCH算法武汉大学 李英冰聚类特征（CF）：CF = (N, LS, SS)qN是簇的数据点qLS是线性和qSS平方和叠加性： CF1+CF2=(N1+N2, LS1+LS2, SS1+SS2)21聚类特征（CF）CF = (5, (16,30),(54,190)(3,4)(2,6)(4,5)(4,7)(3,8)21NiiXNiiX1武汉大学 李英冰CF tree 是一棵高度平衡的树 q非叶节点都有后代或子女qCF tree 两个参数:分支因子,阀值22聚类特征树（CF tree

11、）武汉大学 李英冰233.2 变色龙（CHAMELEON）算法用动态建模确定簇之间的相似度如果两个簇的互联性很高且又靠得很近，就将其合并相对互连度(RI) 相对近似度(RC)(,)(,)()(2ijijijEC C CRI C CEC CEC C(,)(,)()()ijijjiijijijSEC C CRC C CCCSEC CSEC CCCCC武汉大学 李英冰构造成一个K-最近邻图Gk 将图Gk 划分成大量的子图用层次聚类算法合并子簇找到真正的结果簇24变色龙算法的聚类步骤Partition the GraphMerge PartitionFinal ClustersConstruct (K

12、-NN)Sparse GraphData Set武汉大学 李英冰划分和层次方法旨在发现球状簇，但很难发现任意形状的簇基于密度的方法可以把簇看做数据空间中被稀疏区域分开的稠密区域，可以发现任意形状的聚类，代表性的方法有:qDBSCAN: Ester, et al. (KDD96)qOPTICS: Ankerst, et al (SIGMOD99).qDENCLUE: Hinneburg & D. Keim (KDD98)qCLIQUE: Agrawal, et al. (SIGMOD98) (more grid-based)254. 基于密度的聚类方法 武汉大学 李英冰DBSCAN: 一

13、种基于高密度连通区域的基于密度的聚类基于密度的簇: 密度相连点的最大数据集两个相关参数:qEps: 邻域的最大半径qMinPts: 指定稠密区域的密度阀值密度可达 VS 密度相连性264.1 DBSCANpqpqp1pqo密度可达密度相连性MinPts = 5;Eps = 1 cm武汉大学 李英冰核心点：在半径Eps 内含有超过MinPts数目的点边界点：在半径Eps 内含有小于MinPts，但是在核心点的邻居噪音点：任何不是核心点或者边界点的点27核心点、边界点、噪音点CoreBorderNoiseEps = 1cmMinPts = 5武汉大学 李英冰通过检查数据集中每点的Eps领域来搜索簇

14、，如果点p的Eps领域包含的多于MinPts个，则创建一个以p为核心对象的簇然后，DBSCAN迭代地聚集从这些核心对象直接可达的对象，这个过程可能涉及一些密度可达簇的合并当没有新的点添加的任何簇时，该过程结束。28DBSCAN算法原理武汉大学 李英冰优点：相对抗噪音，能发现任意形状的簇缺点： 当密度变化太大、或高维时，会有麻烦29DBSCAN的优缺点武汉大学 李英冰DBSCAN的参数设置依靠经验，参数的细微差别可能导致差别很大的聚类结果OPTICS不显示的产生数据集聚类，而是输出簇排序304.2 OPTICS: 通过点排序识别聚类结构武汉大学 李英冰核心距离：使得p的 -领域内至少有MinPt

15、s 对象可达距离： 使p从密度q可达的最小半径 31OPTICS需要两个信息Core Distance & Reachability Distance武汉大学 李英冰使用统计密度函数:主要特征q严格的数据基础q适用于有大量噪声的数据324.3 DENCLUE: 基于密度分布函数的聚类fx yeGaussiand x y( , )( , )222NixxdDGaussianiexf12),(22)(NixxdiiDGaussianiexxxxf12),(22)(),(influence of y on xtotal influence on xgradient of x in the d

16、irection of xi武汉大学 李英冰采用空间驱动的方法，把嵌入空间划分成独立于输入对象分布的单元使用一种多分辨率的网格数据结构。它将对象空间量化成有限数目目的单元，这些单元形成了网格结构，所有的聚类操作都在该结构上进行。 典型方法qSTING (STatistical INformation Grid）：统计信息网格 qCLIQUE：基于网格和密度的聚类方法335. 基于格网的聚类方法 武汉大学 李英冰将输入对象的空间区域划分成矩形单元多层矩形单元对应不同级别的分辨率每个高层单元被划分为多个低一层的单元，每个网格单元的属性的统计信息（如均值、最大值和最小值）优点:q基于网格的计算是独立

17、于计算的q网格结构有利于并行计算和增量更新q效率高345.1 STING：统计信息网格武汉大学 李英冰把每个维划分为不重叠的空间，从而把数据对象的整个嵌入空间划分成单元聚类步骤1.把d-维数据空间划分若干个互不重叠的重叠单位，并且从中识别出稠密单元2.使用每个子空间中的稠密单元来装配可能具有任意形状的簇 355.2 CLIQUE (Clustering In QUEst) 武汉大学 李英冰基于概率模型的聚类：每个对象都指派了一个属于簇的概率，广泛应用于文本挖掘等方面聚类高维数据聚类图和网络数据具有约束的聚类366. 高级聚类分析武汉大学 李英冰Cluster analysis is to fi

18、nd hidden categories.A mixture model assumes that a set of observed objects is a mixture of instances from multiple probabilistic clusters, and conceptually each observed object is generated independentlyFuzzy Clustering Using the EM Algorithm376.1 基于概率模型的聚类武汉大学 李英冰MethodsqSubspace-clustering: Searc

19、h for clusters existing in subspaces of the given high dimensional data spaceqDimensionality reduction approaches: Construct a much lower dimensional space and search for clusters there 386.2 聚类高维数据武汉大学 李英冰Similarity measuresqGeodesic distancesqDistance based on random walk (SimRank)Graph clustering

20、 methodsqMinimum cuts: FastModularity (Clauset, Newman & Moore, 2004)qDensity-based clustering: SCAN (Xu et al., KDD2007) 396.3聚类图和网络数据武汉大学 李英冰Clustering with ConstraintsqConstraints on instance objects, e.g., Must link vs. Cannot LinkqConstraint-based clustering algorithms406.4 具有约束的聚类Not Taking obstacles into accountTaking obstacles into account武汉大学 李英冰估计聚类趋势：确定给定的数据集是否具有可以导