Clustering聚类分析

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Clustering聚类分析,2013.8.7,1,聚类,分类,相似的归为一类,不相似的归入不同类,未知类,仅依靠对象的相似度,2,应用,生物学,经济学,3,应用,文档分类,文档,向量,1、分量 表示第i个词条的频率,2、分量 为0或1，表示是否引用第i篇文档,4,应用,社交网络,5,对象间的比较,相似度,例：,距离（不相似度）,例：,欧几里得距离,6,距离函数的选择,根据数据的情况选择,例：将图中的点按连边情况分类,点表示成邻接矩阵的行,a=(0,1,0,1,0,1,),b=(0,1,1,0,1,0,),7,研究顾客的行为,D种商品,N个顾客,K种顾客类型，KN,每种类型的顾客购买物品的情况满足一种概率分布,8,研究顾客的行为,顾客1：2种蔬菜，3种水果，1种海鲜，0种零食，,顾客2：1种蔬菜，3种水果，1种海鲜，1种零食,顾客3：4种蔬菜，0种水果，3种海鲜，2种零食,顾客4：0种蔬菜，0种水果，0种海鲜，4种零食,顾客5：3种蔬菜，1种水果，5种海鲜，1种零食,可能的结果：,1,2 3,5 4,顾客1,( 2 , 3 , 1 , 0 ),蔬菜 水果 海鲜 零食,9,判断标准,每个类中，所有对象间的距离之和,每个类中，所有对象到“中心”的距离之和,k-median criterion,每个类中，所有对象到“中心”的距离平方之和,k-means criterion,通过最小化这些值得到最优的划分,10,判断标准的选择,根据分类的目标，依靠经验,例：距离的平方和,1、异常点的误差被放大，得到更多关注,2、数学计算上的优势,11,最优化判断标准,通常是NP-Hard,多项式算法,并非精确的最优解，而是相对优的解或者局部的最优解,12,算法一,判断标准：k-center criterion,最小化任意点到所分的类中心的最大距离,基本思想：,存在k个半径为r的球体覆盖所有点, 存在最大距离为r的划分,13,算法一,步骤,每次选取一个未被覆盖的,数据,点作为一个类的中心，作半径为r的球体，覆盖某些点。重复k次得到k个类。,14,算法一,不靠谱？有点,但是：,若存在最大距离为r/2的划分，这个算法一定能找到最大距离不超过r的划分。,证明：反证法,假设无法找到最大距离为r的划分,至少一个点不在k个半径为r的球体中,存在k+1个点两两的距离大于r,k个半径为r/2的球体无法覆盖这k+1个点,不存在最大距离为r/2的划分（矛盾）,15,类中心,要求类中心必须是数据点,类的划分有限，可穷举,类中心可以是空间中的任意点（使距离函数最小的点）,结果精确,某些判断标准下，类中心具有特殊性质,16,算法二,判断标准：k-means criterion,将d维的点集 划分到k个聚类 中，最小化所有点到所分的类中心（c）的距离平方之和。,minimize,17,算法二,最好的中心是类中所有点的重心,证明：,设x为一个类的中心，类中有 m个点。则距离的平方和可以表示为,定值,0,x=c时最小,18,算法二,初始情况：选取k个点作为k个类的中心,操作一：将每个数据点归入最近的中心所在类,操作二：对每个类，将类的中心更新为类中所有数据点的重心,终止条件：重复两个操作直到距离的平方和逼近局部最优,19,算法二,例子：,n=9,k=3,20,算法二,例子：,n=9,k=3,21,算法二,例子：,n=9,k=3,22,算法二,终止条件,算法一定会向局部最优解收敛，因为重复的两个操作都在不断优化距离平方和,操作一,操作二,设置误差标准以逼近局部最优解,23,算法二,初始情况,初始时对于k个点的选法不同，也会使收敛的结果不同，因此无法得到全局最优解。,但近似的最优解也能成为理想的划分。,24,参考材料,Computer Science Theory for the Information Age John Hopcroft，,Ravindran Kannan,25,谢谢！,26,