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