《数据挖掘原理与应用 第2版 》课件 7.1聚类分析-基本概念

第7章聚类分析基本概念聚类分析聚类是将物理或抽象对象的集合划分成为由类似的对象组成的多个属类的过程。比较相近比较相似比较相像如何衡量簇间最大化簇内最小化聚类分析聚类是将物理或抽象对象的集合划分成为由类似的对象组成的多个属类的过程。聚类分析按照一定的算法规则，将判定为较为相近和相似的对象，或具有相互依赖和关联关系的数据聚集为自相似的组群，构成不同的簇。物以类聚人以群分聚类分析将数据划分成有意义或有用的组群，在各种应用中，一个簇中的数据对象可以被作为一个整体来对待应用商务

-从客户信息库中发现不同的客户群，以购买模式来刻画不同的客户群的特征，进行有针对性的精准营销聚类分析将数据划分成有意义或有用的组群，在各种应用中，一个簇中的数据对象可以被作为一个整体来对待应用生物学-通过对基因进行类别划分，推导动植物的分类，获得对种群中固有结构的认识聚类分析将数据划分成有意义或有用的组群，在各种应用中，一个簇中的数据对象可以被作为一个整体来对待应用地理-从地球观测数据库中的数据确定地理上相似的地区房地产

-根据房屋的类型、价值和地理位置对商品房进行分组，区别处理聚类分析将数据划分成有意义或有用的组群，在各种应用中，一个簇中的数据对象可以被作为一个整体来对待应用信息-对Web上的文档进行处理分类，以便于进行分类检索和发现信息与分类相区别分类训练数据

产生规则（提取模型）

标注Supervised有监督的聚类数据

发现相似

簇Unsupervised无监督的聚类的复杂性簇类型明显分离的(Well-Separated)每个点到同簇中任一点的距离比到不同簇中所有点的距离更近。3个分离簇聚类的复杂性簇类型基于原型的每个对象到定义该簇的原型的距离比到其他簇的原型的距离更近。对于具有连续属性的数据，簇的原型通常是质心，即簇中所有点的平均值。当质心没有意义时，原型通常是中心点，即簇中最有代表性的点。基于中心的（Center-Based）的簇：每个点到其簇中心的距离比到任何其他簇中心的距离更近。4个基于中心的簇聚类的复杂性簇类型基于图的簇可以定义为连通分支（connectedcomponent）互相连通但不与组外对象连通的对象组。基于近邻的（Contiguity-Based）其中两个对象是相连的，仅当它们的距离在指定的范围内。这意味着，每个对象到该簇某个对象的距离比到不同簇中任意点的距离更近。8个“连通”簇图论的图！如果数据用图表示，其中节点是对象，而边代表对象之间的联系。聚类的复杂性簇类型基于密度的(Density-Based)簇是对象的稠密区域，被低密度的区域环绕。6个基于密度的簇聚类的复杂性簇类型基于密度的(Density-Based)簇是对象的稠密区域，被低密度的区域环绕。基于密度的簇聚类的复杂性簇类型概念簇(ConceptualClusters)可以把簇定义为有某种共同性质的对象的集合。例如：基于中心的聚类。还有一些簇的共同性质需要更复杂的算法才能识别出来。2个交叠簇聚类的复杂性分为几个簇?分为4个簇分为2个簇分为6个簇聚类算法分类聚类算法K均值，k-medoids及其扩展算法层次聚类算法基于密度的聚类基于网络的聚类其他聚类算法划分聚类算法CLARA，CLARANSCURE算法，ROCK算法BIRCH算法等DBSCAN算法GDBSCAN，DBCLASD算法OPTICS算法FDC算法BANG算法WaveCluster算法STING算法聚类算法分类按分类方法划分聚类聚类算法分类按分类方法划分聚类层次聚类聚类算法分类按分类方法划分聚类层次聚类基于密度的聚类聚类算法分类按划分方法分类互斥聚类聚类算法分类按划分方法分类互斥聚类非互斥聚类聚类算法分类按划分方法分类互斥聚类非互斥聚类模糊聚类聚类算法分类按划分范围分类完全聚类(completeClustering)部分聚类(partialClustering)“距离”度量聚类的实质是“近朱者赤近墨者黑”定义距离函数，基于属性值进行计算非负性对于任意x，y，两者之间的距离d(x，y)≥0，当x

=y时，等号成立。对称性对于任意x，y，两者之间的距离d(x，y)=d(y，x)，即距离是标量而不是向量。三角不等式对于任意x，y，z，有d(x，y)

≤d(x，z)+d(z，y)。即对象x到对象y的距离小于等于途经其他任何对象z的距离之和。？怎样才算近？也称为相似性“距离”度量欧几里得距离EuclideanDistance对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其欧几里得距离为在二维空间中的欧几里得距离就是平面中两点之间的实际距离。在三维空间中的欧几里得距离就是立体（三维）空间中两点之间的实际距离。“距离”度量曼哈顿距离对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其曼哈顿距离为(6,6)(2,2)欧几里得距离=5.66曼哈顿距离=(6-2)+(6-2)=844xy“距离”度量明可夫斯基距离MinkowskiDistance对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其明可夫斯基距离为相似系数余弦相似度对于n维数据

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，即对于x，y两个向量，有：cos(x,y)=(x·y)/‖x‖·‖y‖

余弦相似度【例如】分析以下两个句子的相似性：

句子A：我喜欢看电视，不喜欢看电影。句子B：我不喜欢看电视，也不喜欢看电影。1)可以将两个句子进行分词：句子A：我/喜欢/看电视/不/喜欢/看/电影句子B：我/不/喜欢/看/电视/也/不/喜欢/看/电影2)对所出现的各个词汇（我

喜欢

看

电视

电影

不

也），计算其词频：句子A：我1，喜欢2，看2，电视1，电影1，不1，也0句子B：我1，喜欢2，看2，电视1，电影1，不2，也1余弦相似度【例如】分析以下两个句子的相似性：

句子A：我喜欢看电视，不喜欢看电影。句子B：我不喜欢看电视，也不喜欢看电影。3)将词频转换为向量：句子A：x=(1221110)句子B：y=(1221121)4)计算其余弦相似度，有：余弦相似度由此，我们就得到了“找出相似文章”的一种算法：使用TF-IDF算法，找出两篇文章的关键词；每篇文章各取出若干个关键词（比如20个），合并成一个集合，计算每篇文章对于这个集合中的词的词频（为了避免文章长度的差异，可以使用相对词频）；生成两篇文章各自的词频向量；计算两个向量的余弦相似度，值越大就表示越相似。相似系数余弦相似度相关系数反映变量之间相关关系密切程度的统计指标相关系数按积差的方法计算，以两变量与各自平均值的离差为基础，通过两个离差相乘来反映两变量之间相关程度。x与y之间的协方差x,y的均方差相似系数余弦相似度相关系数Jaccard相似系数(JaccardSimilarityCoefficient)用于比较有限样本集之间的相似性与差异性A、B的相似性：Jaccard距离：余弦相似度TF-IDF算法TF-IDF通过统计方法，对字词对于语料库中的一份文件或文件集的重要程度进行评估。字词的重要性随其在文件中出现的次数正比增加，随其在语料库中出现的频率成反比下降，即如果某字在一篇文章中出现的频率TF高，而在其他文章中很少出现，则认为该字词具有很好的类别区分能力，适合用于分类。这里TF为词频(TermFrequency)，表示词条在文档d中出现的频率；IDF为逆向文件频率(InverseDocumentFrequency)，表示包含词条的文档的数量，值越大，表明词条具有很好的类别区分能力。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。除了TF-IDF以外，因特网上的搜索引擎还会使用基于链接分析的评级方法，以确定文件在搜寻结果中出现的顺序。误差平方和(SSE)在对两组数据的误差情况进行估计的时候，如原始数据和拟合数据之间的误差，或者是理论数据和观测数据之间的误差，会用其误差值取平方后求和来衡量误差的大小。计算公式为：

误差平方和(SSE）误差平方和（sumof