聚类分析大数据.ppt

《聚类分析大数据.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、21八月2021DataMining:ConceptsandTechniques1数据挖掘:概念与技术—第七章—21八月2021DataMining:ConceptsandTechniques2第七章聚类分析什么是聚类分析?数据类型及其相似性与非相似性计算算法复杂性及近似算法概念划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法单链接与全链接什么是聚类分析?“物以类聚，人以群分。”《战国策·齐策三》《周易·系辞上》聚类:一个数据对象的集合同一个聚类中的对象之间具有高度的相似性。不同聚类中的对象之间具有低的相似性。聚类分析把一组数

2、据划分成聚类。聚类是无监督分类:没有预先定义的类。21八月2021DataMining:ConceptsandTechniques4应用领域图像分割文档分类；消费市场分析；DNA与生物信息学；离群点（孤立点）分析；…21八月2021DataMining:ConceptsandTechniques5怎样度量聚类方法?一个好的聚类方法将会产生高质量的聚类:优化目标？高的聚类内相似性低的聚类间相似性聚类方法的质量依赖于它所使用的相似性的具体定义及具体实施.21八月2021DataMining:ConceptsandTechniques6对数据挖掘中的聚类方法的要求可扩

3、展性能够处理不同数据类型发现任意形状的聚类参数越少越好能够处理噪声和孤立点能够处理高维数据能够集成用户提出的各种约束21八月2021DataMining:ConceptsandTechniques7第七章聚类分析什么是聚类分析?数据类型及其相似性与非相似性计算算法复杂性及近似算法概念划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法单链接与全链接21八月2021DataMining:ConceptsandTechniques8数据结构数据矩阵(2模)区分矩阵(1模)21八月2021DataMining:ConceptsandT

4、echniques9数据类型及其相似性与非相似性计算相似性与非相似性区间值变量:二元变量:标称性,序数性,和比例标度型变量:混合类型的变量:21八月2021DataMining:ConceptsandTechniques10区间值变量标准化数据标准化计算平均绝对偏差:其中计算标准化的度量差(z-score)计算相似性或非相似性时，使用zif.。考虑：一是没有量纲；二是使用这个平均绝对偏差sf比使用标准差f对于孤立点具有更好的鲁棒性。21八月2021DataMining:ConceptsandTechniques11距离：常用的非相似性度量常见的距离有:Mink

5、owski距离:如果q=1,d是Manhattan距离若q=2,d是Euclidean距离:21八月2021DataMining:ConceptsandTechniques12二元变量非相似性二元变量的可能性表简单匹配系数(如果二元变量是对称的):Jaccard系数(若二元变量是不对称的):对象i对象j21八月2021DataMining:ConceptsandTechniques13标称型变量非相似性二元变量的推广，它可以有超过2的状态数，如Map_Color,可以有red,yellow,blue,green方法1:简单匹配m:匹配的数目,p:全部变量的数目方

6、法2:使用一组二元变量对标称型变量的每一个状态设置一个二元变量21八月2021DataMining:ConceptsandTechniques14序数型变量非相似性一个序数型变量可以离散化或连续化。可以象区间标度变量一样处理用它们的秩rif替换xif,将每一个变量的范围映射到[0,1]用计算区间值变量同样的方法计算非相似性21八月2021DataMining:ConceptsandTechniques15向量对象间的余弦相似性对于两个向量对象x,y，余弦度量是一种常用的（特别是在信息检索领域）相似性度量：21八月2021DataMining:Conceptsan

7、dTechniques16第七章聚类分析什么是聚类分析?数据类型及其相似性与非相似性计算算法复杂性及近似算法概念划分方法k-center、k-cluster、k-means、谱聚类NCut层次方法单链接与全链接21八月202117问题的分类P与NP的通俗解释P问题：在多项式时间内能解决的问题。NP问题：在多项式时间内能验证的问题。21八月2021DataMining:ConceptsandTechniques18NPC与NP－HardNPC问题：所有NP问题能在多项式时间内规约到该问题且该问题本身属于NP问题。NP-Hard问题：所有NP问题能在多项式时间内规约

8、到该问题。21八月202