5.1相似性度量方法和经典聚类算法

聚类分析主讲人：李侃数据相似性度量聚类分析的目标：使簇内数据之间具有高的相似性，不同簇数据之间具有高的差异性度量数据间的相似性数据相似性度量相似性度量方法欧氏距离切比雪夫距离闵可夫斯基距离标准化欧氏距离余弦距离马氏距离曼哈顿距离海明距离杰卡德距离相关距离信息熵基于核函数的度量相似性度量方法欧氏距离两个n维向量和之间的欧式距离（euclideandistance)为：

或向量运算：

相似性度量方法标准化欧氏距离根据数据各维分量的分布不同将各个分量都“标准化”到均值、方差相等。两个n维向量和之间的标准化欧氏距离为：

方差的倒数可以看作是一种权重，标准化欧氏距离本质上是一种加权欧氏距离。相似性度量方法曼哈顿距离两个n维向量和之间的曼哈顿距离为：

L1-距离、城市区块距离(cityblockdistance)在欧氏空间的直角坐标系上两点所形成的线段对轴产生的投影的距离总和。相似性度量方法切比雪夫距离两个n维向量和之间的切比雪夫距离为：

该公式等价为：

该等价性可以由放缩法和夹逼定理（squeezetheorem）证得由一致范数（uniformnorm）（或称为上确界范数）所衍生的度量，也是超凸度量（injectivemetricspace）的一种。

相似性度量方法闵可夫斯基距离两个n维向量和之间的闵可夫斯基距离：

当p分别取1，2，3时，会有什么样的效果呢？

相似性度量方法闵可夫斯基距离举例二维样本空间（身高，体重）中的三个样本：a(180,50)，b(190,50)，c(180,60)，其中a与b之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c之间的闵氏距离这意味什么？将各个分量的量纲，也就是“单位”当作相同看待没有考虑各个分量的分布（如期望、方差等）可能不同缺点相似性度量方法余弦距离向量的几何意义不只包含长度也包含方向，余弦距离（cosinedistance）是度量两个向量方向差异的一种方法。两个n维向量

和

之间的夹角余弦度量：

即：

相似性度量方法马氏距离马氏距离(mahalanobisdistance)是基于样本分布的一种距离，它是规范化的主成分空间中的欧氏距离。何谓规范化？规范化的主成分空间就是利用主成分分析对一些数据进行主成分分解，再对所有主成分分解轴做归一化，形成新的坐标轴，由这些坐标轴组成的空间就是规范化的主成分空间。相似性度量方法马氏距离设有M个向量，协方差矩阵记为S，均值记为向量μ

，则样本向量X到μ

的马氏距离：

向量Xi与Xj之间的马氏距离：若协方差矩阵是单位矩阵（各个样本向量之间独立同分布），则Xi与Xj之间的马氏距离等于它们的欧氏距离：若协方差矩阵是对角矩阵呢？标准化欧氏距离量纲无关，排除变量之间的相关性的干扰；马氏距离的计算是建立在总体样本的基础上；计算马氏距离过程中，要求总体样本数大于样本的维数。特点：相似性度量方法海明距离两个等长二进制串S1和S2将其中一个变换为另一个所需要的最小变换次数。例如：字符串“1111”与“1001”之间的汉明距离为2相似性度量方法杰卡德距离杰卡德相似系数(Jaccardsimilaritycoefficient)：两个集合A

和B的交集元素在A、B

的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号J(A,B)表示：杰卡德距离(JaccardDistance)：与杰卡德相似系数相反，用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度：相似性度量方法

相关距离相关系数：衡量随机变量X与Y

相关程度的一种方法，相关系数的取值范围是[-1,1]。相关系数的绝对值越大，则表明X

与Y

相关度越高。当X

与Y

线性相关时，相关系数取值为1（正线性相关）或-1（负线性相关）相关距离(correlationdistance)：相似性度量方法信息熵以上的距离度量方法度量皆为两个样本（向量）之间的距离信息熵(informationentropy)描述的是整个系统内部样本之间的一个距离，或者称之为系统内样本分布的集中程度（一致程度）、分散程度、混乱程度（不一致程度）。分布越分散信息熵越大分布越有序信息熵越小相似性度量方法信息熵计算给定的信息熵：其中，n为样本集X的分类数；

为X中第

i

类元素出现的概率。

相似性度量方法基于核函数的度量把原始样本空间中线性不可分的数据点采用核函数映射到高维空间中使其线性可分的一种度量方法。距离函数需满足：d(x,x)=0，即自身的距离为0d(x,y)>=0，即距离要非负；对称性，即d(x,y)=d(y,x)三角形法则(两个之和大于第三边）即d(x,k)+d(k,y)>=d(x,y)经典聚类算法经典聚类算法分类聚类方法往往学术界对聚类算法并没有一个公认的分类方法某一聚类方法会具有几种类别的特征聚类算法：划分方法层次方法基于密度方法基于网格方法基于模型方法经典聚类算法划分方法

典型方法：K-means及其变种、K-中心点、CLARA、CLARANS等经典聚类算法层次聚类树的建立策略：

自底向上的策略，把小的类别逐渐合并为大的类别，这种方法称为凝聚；

自顶向下的策略，把大的类别逐渐分裂为小的类别，这种方法称为分裂层次聚类方法将数据对象建立一棵聚类树。经典聚类算法层次聚类经典方法：BRICH方法、ROCK方法和Chameleon方法在层次聚类算法的实际应用中，聚类通常终止于某个预先设定的条件，比如簇的数目达到某个预定的值，或者每个簇的直径都在某个阈值之内。簇间距离度量方法：最小距离（最近邻聚类算法）最大距离（最远邻聚类算法）均值距离平均距离是簇

的均值是簇

中对象个数经典聚类算法基于密度的聚类基于密度的方法将簇看作数据空间中被低密度区域分割开的稠密的对象区域，有时也将这种低密度区域看作噪声。经典方法：DBSCAN、OPTICS、DENCLUE等基于密度的聚类DBSCAN具有噪声的基于密度的聚类应用算法定义：

q基于密度的聚类DBSCAN

密度可达是直接密度可达的传递闭包，它是非对称的，只有核心对象之间互相密度可达。密度相连则是一种对称的关系。基于密度的簇，是基于密度可达性的最大的密度相连对象的集合，不包含在任何簇中的对象被认为是噪声基于密度的聚类DBSCAN算法：1.检查数据集中的每个点的𝜺邻域

3.当没有新的点可以添加到任何簇时，聚类过程结束

计算复杂度为

，在使用空间索引的数据库中计算复杂度可降为。在参数𝜺和MinPts

设置恰当的情况下，DBSCAN算法可有效地找到任意形状的簇

对参数非常敏感真实的高维数据常具有非常倾斜的分布，全局密度参数不能刻画其内在的聚类结构评价：经典聚类算法基于网格的方法它采用一个多分辨率的网格数据结构，将空间量化为有限数目的单元，这些单元形成了网格结构，所有的聚类操