聚类算法概要及相关知识准备

聚类的概念

聚类分析是在数据中发现数据对象之间的关系，将数据进行分组，组内的相似性越大，组间的差别越大，则聚类效果越好。
将物理或抽象对象的集合分成由类似对象组成的多个类或簇（cluster）的过程被称为聚类（Clustering）。由聚类所生成的簇是一组数据对象的集合，这些对象与同一簇中的对象相似度较高，与其他簇的对象的相似度较低。相似度是根据描述对象的属性值来度量的，距离是采用度量的方式。

相同点集的不同聚类方法

类的度量方法

常用的类的度量方法有2种，即距离和相似系数。距离用来度量样品之间的相似性，相似系数用来度量变量之间的相似性。

距离

欧式距离

定义在两个向量（两个点）上：点X和Y的欧式距离为：

闵可夫斯基距离

两个向量（点）的p阶距离：

当p=1 时就是曼哈顿距离，p=2 时就是欧式距离。

马氏距离

定义在2个向量（两个点）上，这2个点在同一分布里，点 x和 y的马氏距离为

海明威距离

定义：在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。即属性值相同，为0；属性值不同，为1。对应的分类属性 的海明威距离为：

混合距离

对于数据 和 的混合距离为：

其中，前p个为数值变量，后m-p个为分类变量。

相似度

两个n维向量X和Y，余弦相似性由点积和向量长度给出，如下所示：

余弦相似度

两个n维向量X和Y，余弦相似性由点积和向量长度给出，如下所示：

皮尔逊相关系数

假设有两个变量X、Y，那么两变量间的皮尔逊相关系数可通过以下公式计算：

斯皮尔曼相关系数

离散属性的相关性

假设有2个变量X,Y。则它们之间的相关系数为：