5.1 聚类概述及相似度测量
5.1 聚类概述及相似度测量
P2大家好，本次课我们学习聚类概述及相似度测量，聚类算法是数据挖掘算法中最重要的算法之一，应用十分广泛，相似度测量在多种数据挖掘算法中广泛应用。以下是本次要学习的内容：分类与聚类、聚类概述、相似度测量。
P3 分类与聚类
分类和聚类是两个容易混淆的概念，事实上它们具有显著区别。在分类中，为了建立分类模型而分析的数据对象的类别是已知的，即数据对象是已有标签的。然而，在聚类时处理的所有数据对象的类别都是未知的，即数据对象是没有标签的。因此，分类是有指导的，是通过例子（训练样本集）学习的过程，即有监督学习。而聚类是无指导的，是通过观察学习的过程，即无监督学习。
P4 聚类概述
聚类(clustering)是将数据对象的集合分成若干子集（或簇）的过程。使得同一个子集（簇）中的对象之间具有较高的相似性，而不同子集（簇）中的对象具有较高的相异性。如图所示，原来的若干个点经过聚类函数后划分为三个不同的簇，同个簇内的点间距离较其与不同簇内点的距离近，也就是说同簇内点的距离小，不同簇内的点的距离较远。
聚类的典型应用是什么?在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的分组，及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对Web上的文档进行分类，以发现信息。
P5 什么是聚类？
"物以类聚，人以群分"，在自然科学和社会科学中，存在着大量的分类问题。聚类分析又称群分析，它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学，但是聚类不等于分类。聚类与分类的不同在于，聚类所要求划分的类是未知的。聚类分析内容非常丰富，有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。
我们直接给出聚类的定义，由所示可见，聚类D可形式表示为n个对象的集合，对象之间的距离用sim()函数来表示，任意两个簇不同且没有交集，簇内任何对象的相似度均大于簇间任何对象的相似度。实际上聚类的定义是形式上表达上节所讲的聚类特性。
P6距离相似度
由上节知识我们知识可知判断一个点（数据）属于哪一个簇的判断依据就是通过计算该点与该簇内的所有点的距离要小于其与其他簇内点的距离来确定，所以这里需要用“距离相似度”。常见的距离相似度有：曼哈顿距离、欧几里得距、闵可夫斯基距离。这三种距离的计算公式如图所示。
P7欧几里得距离
欧几里得距离又称为“欧氏距离”，表示空间中两点间的直线距离。其定义如图所示，可知其计算方法是将X、Y两个点的对应属性值差的平方和，然后计算出其算术平方根，以此值为该两点的为欧氏距离。如图所示，当两点为平面上点时,即二维空间上的两个点，x =，y，则其欧氏距离即为勾股定理求得的两点距离。
P8曼哈顿距离
曼哈顿距离称为出租车距离，如图所示，对于一个具有正南正北、正东正西方向规则布局的城镇街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离。两点在南北方向上的距离加上在东西方向上的距离，即两点的曼哈顿距离
P9闵可夫斯基距离
闵可夫斯基距离是欧氏距离的一种推广，欧氏距离是闵可夫斯基距离的一种特殊情况。
由所示可知，当q=2时，闵可夫斯基距离即为欧氏距离；当q=1时，闵可夫斯基距离即为曼哈顿距离；当q→∞时，闵可夫斯基距离即为切比雪夫距离。
P10相似度计算
相似度通常相似度与距离成反比，在确定好距离函数后，相似度函数计算方法如图所示，即将距离加上1之和的倒数计为相似度，其取值范围为（0，1] ，相似度值越接近1，表明两点的距离很近，否则表明两点的距离较远。
P11密度相似性度量
密度是单位区域内的对象个数。密度相似性度量定义公式所示，由公式我们可知当密度相似性值越小，表示密度越相近，所以两点相似性越高。如图所示这样情况下，簇是对象的稠密区域，被低密度的区域环绕。
P12 连通性相似性度量
连通性相似性度量又是一种特殊的相似性度量方法。如图所示，数据集用图表示，图中结点是对象，而边代表对象之间的联系，这种情况下可以使用连通性相似性，将簇定义为图的连通分支，即图中互相连通但不与组外对象连通的对象组。也就是说，在同一连通分支中的对象之间的相似性度量大于不同连通分支之间对象的相似性度量。
P13概念相似性度量
概念相似性度量比较容易理解，如图所示狗、猫、鸡同于动物，其相似度接近，苹果、葡萄属于水果类，其相似度较近。
P14总结
好了，到此本次课就要结束了，我们做一个简短的回顾。聚类算法是数据挖掘的最重要算法之一，它是无指导的，是通过观察学习的过程，是无监督学习。相似度测量方法是计算空间两点的近似程度，相似度是通过两点间的距离计算取得。两点间的距离计算方法有曼哈顿距离、欧几里得距、闵可夫斯基距离。好，这次课到此结束，谢谢！