《聚类方法Clustering周源06》由会员分享，可在线阅读，更多相关《聚类方法Clustering周源06（46页珍藏版）》请在金锄头文库上搜索。
1、聚类方法（Clustering） 周源2010.12.06钓衰馁柯虐苍狱眠抛纪铝油竿媒迄倍骸陇障伤苍凛峦埂扼梅吉侩倍绚揣腺聚类方法Clustering周源06聚类方法Clustering周源06什么是聚类聚类（Clustering）就是将数据分组成为多个类（Cluster）。在同一个类内对象之间具有较高的相似度，不同类之间的对象差别较大。纳珐团朋浊拧锰冒隙迷绣曹吮栓齿邯昌崭魂诧气刃黔姨全驳骑拈驹勒送下聚类方法Clustering周源06聚类方法Clustering周源06聚类分析聚类分析对于一个数据，人们既可以对变量（指标）进行分类(相当于对数据中的列分类)，也可以对观测值（事件，样品）来分类
2、（相当于对数据中的行分类）。比如学生成绩数据就可以对学生按照理科或文科成绩（或者综合考虑各科成绩）分类，当然，并不一定事先假定有多少类，完全可以按照数据本身的规律来分类。妒障姆印遁罪凑灿级曼钎哦卤渔肯胆倒江访漳工宾演暑抿雇邦潍渝绷经舌聚类方法Clustering周源06聚类方法Clustering周源06聚类的应用领域经济领域：帮助市场分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。谁喜欢打国际长途，在什么时间，打到那里？对住宅区进行聚类，确定自动提款机ATM的安放位置股票市场板块分析，找出最具活力的板块龙头股企业信用等级分类生物学领域推导植物和动物的分类；对基
3、因分类，获得对种群的认识数据挖掘领域作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步的研究镊婉各菌花驮败款摩貉哼步姆固劫癌烂厉屿戎募幅泊垂酱薪蝇鲤咽军属揉聚类方法Clustering周源06聚类方法Clustering周源06有贡献的研究领域数据挖掘聚类可伸缩性、各种各种复杂形状类的识别，高维聚类等统计学主要集中在基于距离的聚类分析，发现球状类机器学习无指导学习（聚类不依赖预先定义的类，不等同于分类）空间数据技术生物学市场营销学厕弟固珍玲胞铆辜谍惮香讣照菜淋盂恃尤蔡彬华页刺句甫厌蜗恿吗肃课喉聚类方法Clustering周源06聚类方法Clustering周源06聚类分析原
4、理介绍聚类分析中“类”的特征：聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分聚类的数目和结构都没有事先假定聚类方法的目的是寻找数据中：潜在的自然分组结构a structure of “natural” grouping感兴趣的关系relationship夏畸鬼高止亦选肺妨鼓洗冶扔值下秒薛梨镀门驯托傻檬食楼刽柏默姐摇淤聚类方法Clustering周源06聚类方法Clustering周源06聚类分析原理介绍什么是自然分组结构Natural grouping ?我们看看以下的例子：有16张牌如何将他们分为 一组一组的牌呢？AKQJ信试嚷浪捂把暂叔记土羽虞卸岗瓜哦篱载屑铅苞叶邀霄锭耿憎名
5、芒湍奠腹聚类方法Clustering周源06聚类方法Clustering周源06聚类分析原理介绍分成四组每组里花色相同组与组之间花色相异AKQJ花色相同的牌为一副花色相同的牌为一副Individual suits烽钞通裕嗅进综叙良帘阂枷基踌频源挖抱逸订洞范钦纂铬振荆总沦异转觅聚类方法Clustering周源06聚类方法Clustering周源06聚类分析原理介绍分成四组符号相同的牌为一组AKQJ符号相同的的牌符号相同的的牌Like face cards犀访涉祖戳唉姜藻指绒亥唁嚷裙厦偿唾撂沮柑园停傍铰谁益念藉煌魏典足聚类方法Clustering周源06聚类方法Clustering周源06聚类分析
6、原理介绍分成两组颜色相同的牌为一组AKQJ颜色相同的配对颜色相同的配对Black and red suits裹藉仕纠碑瞳碱提肮妻穆碰轰肤淫匠二危勤烁窝嗣车捞围跪读辊辽馒和陋聚类方法Clustering周源06聚类方法Clustering周源06聚类分析原理介绍本章要介绍的分类的方法称为聚类分析（cluster analysis）。对变量的聚类称为R型聚类，而对观测值聚类称为Q型聚类。这两种聚类在数学上是对称的(两个状态具有同等价值和相同的权重，例如性别的两个状态：男和女)，没有什么不同。相似性Similar的度量（统计学角度）距离Q型聚类主要用于对样本分类常用的距离有（只适用于具有间隔尺度变量
7、的聚类）：明考夫斯基距离（包括：绝对距离、欧式距离、切比雪夫距离）兰氏距离马氏距离斜交空间距离此不详述，有兴趣可参考应用多元分析（第二版）王学民相似系数R型聚类用于对变量分类，可以用变量之间的相似系数的变形如1rij定义距离这里不详细介绍这种聚类度量方法夕央壬届茵袍侣牌毖谱由迄表工遍棚画妥俱讯亦镀狡疮曲世辆塘啮侮富瞳聚类方法Clustering周源06聚类方法Clustering周源06聚类分析原理介绍变量按测量尺度（Measurement Level）分类间隔（Interval）尺度变量连续变量，如长度、重量、速度、温度等有序（Ordinal）尺度变量等级变量，不可加，但可比，如一等、二等、
8、三等奖学金名义（Nominal）尺度变量类别变量，不可加也不可比，如性别、职业等笺嚼生袄丝檀函禽帅漏炒奎滥程枝柏咋齿碴泡绽尸刃沉极钞艳蔼悸怨艺扣聚类方法Clustering周源06聚类方法Clustering周源06聚类分析原理介绍当对象是同时被各种类型的变量描述时，怎样描述对象之间的相异度呢？一种可取的办法是把所有变量一起处理，将不同类型的变量组合在单个相异矩阵中，把所有有意义的变量转换到【0，1】的区间上，只进行一次聚类分析。详见参考书滑怀产器彭惰乒诀绘碉拄魏昌间液蚊郑盐辊好虐牵酶纽座汁涝汕尽旦神焙聚类方法Clustering周源06聚类方法Clustering周源06主要聚类算法的分类划
9、分方法（划分方法（partitioning method）层次的方法（层次的方法（也称系统聚类法）（系统聚类法）（hierarchical method）基于密度的方法（基于密度的方法（density-based method）基于网格的方法（基于网格的方法（grid-based method）基于模型的聚类方法（基于模型的聚类方法（model-based method）聚类高维数据聚类高维数据基于约束的聚类分析基于约束的聚类分析离群点分析离群点分析其中，前两种算法是利用其中，前两种算法是利用统计学定义的距离统计学定义的距离进行度量进行度量彪弦留伺麻混诲响粮腕惠智咳吹尾歪纯邹拢嫂甲瘦吼弟噶赡幢
10、峙雅耽瓮苫聚类方法Clustering周源06聚类方法Clustering周源06划分方法划分方法1 典型的划分方法：k均值和k中心点2 大型数据库的划分方法：从k中心点到CLARANS思想：思想：随机选择k个对象，每个对象初始地代表一个类的平均平均值值或中心中心，对剩余每个对象，根据其到类中心的距离，被划分到最近的类；然后重新计算每个类的平均值。不断重复这个过程，直到所有的样本都不能再分配为止。辟他桐饺容其准队晃着怕弃矩学盂硷漳绒栋蝇椎瓮裙烙纲袒露袜卞犬购拧聚类方法Clustering周源06聚类方法Clustering周源06划分方法划分方法特点：特点：k事先定好事先定好创建一个初始划分，
11、再采用迭代的重定位技术创建一个初始划分，再采用迭代的重定位技术不必确定距离矩阵不必确定距离矩阵比系统聚类法运算量要小，适用于处理庞大的样本数据比系统聚类法运算量要小，适用于处理庞大的样本数据适用于发现球状类适用于发现球状类缺陷：缺陷：不同的初始值，结果可能不同不同的初始值，结果可能不同有些有些k均值算法的结果与数据输入顺序有关，如在线均值算法的结果与数据输入顺序有关，如在线k均值算法均值算法用爬山式技术（用爬山式技术（hill-climbing）来寻找最优解，容易陷入局部极）来寻找最优解，容易陷入局部极小值小值性站编城凭印拾靴诲奠送表误潜佃准辟埔邯扩纂火碌够惹稍洁览沫虐橱红聚类方法Cluste
12、ring周源06聚类方法Clustering周源06划分方法划分方法K-均值首先，随机地选择k个对象，每个对象代表一个簇的初始均值或中心。对剩余的每个对象，根据其与各个簇均值的距离，将它指派到最相似的簇。然后计算每个簇的新均值。这个过程不断重复，直到准则函数收敛。EM(Expectation-Maximization,期望最大化)算法与K均值算法将每个对象指派到一个簇相反。在EM算法中，每个对象按照权重指派到每个簇，其中权重表示对象的隶属概率。换句话说，在簇之间没有严格的边界。因此，新的均值基于加权的度量值来计算。法见赋灌以啼脾抄噬郝鹊辐伞坷捅秧补慰买淳阿铰鸽祁显郊社尹幽即絮蔗聚类方法Clus
13、tering周源06聚类方法Clustering周源06划分方法划分方法K-均值硬聚类计算每个类的中心EM算法 特点：1.我们从初始迭代直到收敛 2.是局部最优 3.K均值是用EM算法求解高斯混合分布的特例挑式洪熟践节羽婉林撇延督狸俩碰墨曹煽倒啤佑走糠偿商味借冶搪油阶浩聚类方法Clustering周源06聚类方法Clustering周源06K-均值将n个向量分到k个类别中去选择k个初始中心计算两项距离计算均值练鸥盖筒霸冀铺园似哩祷谓纤乳京式蛔函甜逊妥鸽抡雀落嚣当函路妈消绪聚类方法Clustering周源06聚类方法Clustering周源06印褒风吗瞥街颤叶崖驾煎丢棘颂卡灵谓运泡测葫岿砚诚糠帐
14、时犬养失病挛聚类方法Clustering周源06聚类方法Clustering周源06巫戌财瞬悔柯降黑安抄怠醋碎融坐筛迈犯恿笼沛丹细雄师搀岳界路不烯妇聚类方法Clustering周源06聚类方法Clustering周源06桩铀雹踢桐乔舀仙铸征砧江粕限话柑蓬曹玖禽脚殿网优鳞茧导康需淤龚孔聚类方法Clustering周源06聚类方法Clustering周源06迎樱鞍槽拷怯刃寇牌高仪挤溜匈漫栏爸遮豺竞柒款甜染竟拆忆臀熊遣就肚聚类方法Clustering周源06聚类方法Clustering周源06岳钮脐凄兵疮跋咆瓜钩照炕咽腥槐渊毗悦颊拓伺续戎镁楚竹果铝崭脯桩狂聚类方法Clustering周源06聚类方法
15、Clustering周源06埃散票秽蛙脑退屎治蓟甫阎闹捆桔扔做载仗网袒蹿瞒任蛆断熏生乏摸蔚江聚类方法Clustering周源06聚类方法Clustering周源06K-均值算法包脐浓叫推气斩促著们卢梭禁荔昼断铸峭绢招容问柒苞蒸鳖枉术会伦怂琵聚类方法Clustering周源06聚类方法Clustering周源06层次方法层次方法1 凝聚和分裂层次类聚2 BIRCH：利用层次方法的平衡迭代规约和聚类3 ROCK：分类属性的层次聚类算法4 Chameleon：利用动态建模的层次聚类算法煎钨诵粳球澜泉僵方鸦婴句渗缮奇愉绥凋渺唁官速猩橱垦柱粮椿茎骤御起聚类方法Clustering周源06聚类方法Clus
16、tering周源06层次的方法（层次的方法（也称系统聚系统聚类法）（类法）（hierarchical method）定义：对给定的数据进行层次的分解：定义：对给定的数据进行层次的分解：分类：分类：凝聚的（凝聚的（agglomerative）方法（自底向上）（案例介绍）方法（自底向上）（案例介绍）思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类思想：一开始将每个对象作为单独的一组，然后根据同类相近，异类相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止相异的原则，合并对象，直到所有的组合并成一个，或达到一个终止条件为止。条件为止。每一项自成一类迭代，将最近的两类合为一类分裂
17、的方法（分裂的方法（divisive）（自顶向下）（自顶向下）思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不思想：一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。止条件。将所有项看作一类找出最不相似的项分裂出去成为两类街枝燃铣激旭恫皆山奇瞪置返碍品爪窍孽罕私墒菇艺独晓抨揭缩蓉夷惠骚聚类方法Clustering周源06聚类方法Clustering周源06层次的方法（层次的方法（也称系统聚系统聚类法）（类法）（hierarchical method）特
18、点：特点：类的个数不需事先定好类的个数不需事先定好需确定距离矩阵需确定距离矩阵运算量要大，适用于处理小样本数据运算量要大，适用于处理小样本数据 层次的方法缺陷：层次的方法缺陷：一旦一个步骤（合并或分裂）完成，就不能被撤销或修正，因此产生了改进的层次聚类方法，如BRICH,BURE,ROCK,Chameleon。详见参考书 辩亨耸惶珊瘁高能侧秸痰苔匈秽冀剥习邯晃闪抬定例塌哺假花绢钡舀帝犊聚类方法Clustering周源06聚类方法Clustering周源06广泛采用的类间距离：广泛采用的类间距离：最小距离法（single linkage method）极小异常值在实际中不多出现，避免极大值的影响
19、 韩鹰壳街炳逸草娠粤铅着啼惺钵芍俯燥丫崔妻早平逛闻牵鹅癌金腊果胶仗聚类方法Clustering周源06聚类方法Clustering周源06广泛采用的类间距离：广泛采用的类间距离：最大距离法（complete linkage method）可能被极大值扭曲，删除这些值之后再聚类翔潭锌透嚣抖哑猫梳觅科差谬曾镭架蝎奶籽聘击皑宅啊税晦卫财缩惋离汛聚类方法Clustering周源06聚类方法Clustering周源06广泛采用的类间距离：广泛采用的类间距离：类平均距离法（average linkage method）类间所有样本点的平均距离该法利用了所有样本的信息，被认为是较好的系统聚类法妊厘樱超捶纪魁
20、用尊焊歼彝鲍为襄研踌氯袒崔嘲乓辟般澳乙抛扎戍穗糊脚聚类方法Clustering周源06聚类方法Clustering周源06广泛采用的类间距离：广泛采用的类间距离：重心法（重心法（centroid hierarchical method）类的重心之间的距离类的重心之间的距离对异常值不敏感，结果更稳定对异常值不敏感，结果更稳定 漓控耐殊县翻纯潦处橙咏中孕舞蔷扩询捶溉酚摊往篱牙姆顺遇墨洋刷条赐聚类方法Clustering周源06聚类方法Clustering周源06类的相似度度量我们可以知道两个项之间的相似度，但是聚类要求知道类与类之间的相似度三种方法：单连接方法全连接方法组平均方法抚蛀奢弓作蓄竟价炙
21、乍搪庭尖粪棵挟搓肝亭技术验答泞绢榷耐候鉴声轮乌聚类方法Clustering周源06聚类方法Clustering周源06类的相似度度量- 单连接方法：使用最小距离d(Ci,Cj)衡量簇间距离，有时称它为最近邻聚类算法。当最近的簇之间的距离超过某个任意的阀值时聚类过程就会终止。如果我们把数据点看作图的节点，图中的边构成簇内节点间的路径，由于连接簇的边总是从一个簇通向另一个簇，结果图将形成一颗树，使用最小距离度量的凝聚层次聚类算法也称为最小生成树算法。全连接方法: 使用最大距离d(Ci,Cj)度量簇间距离时，有时称为最远邻聚类算法。当最近的簇之间的最大距离超过某个任意的阀值时聚类过程就会终止，则称其
22、为全连接算法。通过把数据点看作图中的节点，用边来连接节点，我们可以把每个簇看成是一个完全图，也就是说，簇中所有的节点都有边来连接。组平均方法：最小和最大度量代表了簇间距离度量的两个极端。它们趋向对离群点或噪声数据过分敏感。使用均值距离或平均距离是对最小和最大距离之间的一种折中方法，而且可以克服离群点敏感性问题。哆套鳖喻缔理狞胀侗荚拓绍穆鹅棵穴档仁代籽浙绸碧搅装匣捍抑暴册湿盆聚类方法Clustering周源06聚类方法Clustering周源06欣始鞠敬疯去瞄钎邦械窃轩茎溃咏宇独便啸淄凶承琼彻模暑痪泛匿站晨剪聚类方法Clustering周源06聚类方法Clustering周源06屿爷万果呀俊戮驹
23、织鸟搔篷堕法催佬捍申征泡香座毡写九进刑侯孩作税冶聚类方法Clustering周源06聚类方法Clustering周源06音透俗钎润橱惨正贮弯较天朱镍照舟异搐林砰霞鉴坷玩场般镰夷幅惑策揣聚类方法Clustering周源06聚类方法Clustering周源06蕴埠栗婆龙预烽磊查吟鸥蜂甄椅恨态斗镑和讲淋和割非尼屑谐霓毫竭报措聚类方法Clustering周源06聚类方法Clustering周源06基于密度的方法基于密度的方法1 DBSCAN：一种基于高密度连通2 OPTICS：通过点排序识别聚类结构3 DENCLUE：通过密度分布函数的聚类思想：思想：只要临近区域的密度超过一定的阀值，就继续聚类特点：
24、特点：可以过滤噪声和孤立点outlier，发现任意形状的类邹瑞滞扰卢布捐映毅饱嚣凰沈氖穴鸦憋拳讯嘱宰媒讽遮惰员右拨刊俯职排聚类方法Clustering周源06聚类方法Clustering周源06基于网格的方法基于网格的方法1 STING：统计信息网格2 WaveCluster：利用小波变换聚类把样本空间量化为有限数目的单元，形成一个网络结构，聚类操作都在这个网格结构（即量化空间）上进行 。优点：处理速度很快，其处理时间通常独立于数据对象的数目，仅依赖于量化空间中每一维的单元书目。婚貉佃扣铜荡慢猴蒸户多啃险瓦濒甄暴叭湃屡考灵狂乔用胆油岗胯拓便丘聚类方法Clustering周源06聚类方法Clus
25、tering周源06基于模型的聚类方法基于模型的聚类方法1 期望最大化方法2 概念聚类3 神经网络方法为每个类假定一个模型，寻找数据对给定模型的最佳拟合。放访诛灰栗梭观戴挚芜婉艺忧彪梭踞素掐说璃驰庶侠胯身摄狰蠢嫩谜舷言聚类方法Clustering周源06聚类方法Clustering周源06聚类高维数据聚类高维数据1 CLIQUE：维增长子空间聚类方法2 PROCLUS：维归约子空间聚类方法3 基于频繁模式的聚类方法很多应用需要对包含大量特征项或者维数的对象进行分析。例如，文本文档可能包含成千上万个词条作为特征项，DNA微阵列数据可以在数以百计的条件下提供关于数以千计的基因表达水平信息。毗份爆规
26、逾谦肤卧被厄罐丸梅氓汪回汐岭垫萄启蟹尽弟淫男烬剪喝俄沙剥聚类方法Clustering周源06聚类方法Clustering周源06基于约束的聚类分析基于约束的聚类分析1 含有障碍物的对象聚类2 用户约束的聚类分析3 半监督聚类分析 是一种结合用户指定或面向应用的约束进行聚类的方法。约束表达了用户的期望，或者是描述了期望的聚类结果所具有的性质，并且提供与聚类过程通信的有效手段。可以指定各种各样的约束，或者由用户指定，或者作为应用需求来指定。窿僵蔓澜戚幻研劳仇冯鹃轨性配砌夷翌忻甩孵诺浙所叉搬天岸绒鸵货类瓦聚类方法Clustering周源06聚类方法Clustering周源06离群点分析1 基于统计分布的离群点分析2 基于距离的离群点检测3 基于密度的局部离群点检测4 基于偏差的离群点检测西谩衰肖始汞杏瘩渺挑乏据腐券位埋没砧楼秉余典姿汛廊扣逐裸起性赁耗聚类方法Clustering周源06聚类方法Clustering周源06Thank you!叼霍乃亭振厉苑版瓜掂码园揉扳授烬皖嫩仿勉邓妓颂谊釜汹斋道斋吼沥靠聚类方法Clustering周源06聚类方法Clustering周源06
