大数据技术及应用PPT课件(共10章)第6章-大数据分析挖掘-聚类.pptx

第6章大数据分析挖掘聚类 相似度计算010203主要内容聚类分析的步骤 聚类分析概述 聚类算法04 聚类结果评估05分类与聚类在日常生活中，人们不是孤立地看待每件事物，而是会根据观察到的事物属性对其进行分类在研究分类问题时，会面临两种情况：一种是预先已经划分好类别，要求根据研究对象的特征，确定它们所属的目标类；另一种是预先未定义类别，需要根据研究对象彼此间的相似程度，对它们进行分类前一种称为分类（classification）问题，后一种是本章将重点阐述的聚类（clustering）问题聚类分析概述1聚类分析是将物理或抽象对象的集合分成由相似对象组成的多个组（group）或簇（cluster）的过程簇具有“内部同质性、外部可分性”的特征常见簇的类型常见簇的类型明显分离的簇（well-separated clusters）每个点到同簇中任意点的距离比到不同簇中所有点的距离更近基于中心的簇（center-based clusters）每个点到所在簇中心的距离比到任何其他簇中心的距离更近，簇的中心通常被称为质心基于邻近的簇（contiguity-based clusters）每个点到同簇中至少一个点的距离比到不同簇中任意点的距离更近。

常见簇的类型基于密度的簇（density-based clusters）簇被视作由低密度区域分开的高密度区域概念簇（conceptual clusters）簇中的所有点具有某种共同的性质概念簇可以涵盖前面几种簇的定义簇的概念的模糊性，会导致同一数据集因为研究目的、数据输入方式、所选特征的不同，而最终形成不同的分簇结果聚类分析的步骤201020304数据预处理相似性度量聚类(分组)聚类结果评估通过特征选择和特征提取，确定聚类算法所使用的特征的数量、类型和取值范围的过程虽然聚类算法总是试图为数据集找到最佳的分簇方式，却无法保证聚类结果与数据集的真实结构相一致评估方法：外部准则、内部准则、相对准则相似性代表对象间的近似或相关程度，可作为聚类的依据，决定个体在不同簇之间的归属度量方法：距离，相似系数，建立目标函数，将聚类问题转化为对数据对象进行分割的优化问题，进而采用合适的解法求出聚类结果相似度计算3聚类分析的相似性度量分为两个方面：数据对象（个体）之间的相似关系和类（群体）之间的相似关系数据对象之间相似程度的描述把每个对象看作是多维空间中的一个点，通过距离大小反映对象之间的亲疏程度计算对象之间的相关系数（称为相似系数）类之间相似程度的描述通过对两类之间每个对象相似度的汇总来反映类之间的亲疏程度通过两个类的概括统计量之间的相似性描述类之间的亲疏程度对象之间的相似度数据对象是通过一组刻画其基本特征的属性表达的。

属性也称为特征、变量、特性或字段，它们是计算对象之间相似度的依据对象属性有连续型、离散型、混合型等，因此相似度的计算方法也不尽相同对象之间的相似度连续属性 对于连续属性，距离和相似系数都是度量对象之间相似程度的常用手段距离反映对象之间的相异性，相似系数反映对象之间的相似性假设数据集包含m个数据对象，每个对象用d个属性描述，第i个对象记为 对象之间的相似度(1)距离两个对象 和 之间的距离通过距离函数 计算，和 越相似，的值越小距离函数必须满足以下条件：对称性：非负性：自反性：三角不等式：对象之间的相似度欧氏距离全称是欧几里得距离，定义源于欧氏空间中两点间的距离公式，是一种最常用也最易于理解的距离度量方法欧氏距离的计算是基于各维度属性的绝对数值，只有当各个维度的数据值对欧氏距离的贡献同等的时候，才能获得良好的表达效果对象之间的相似度曼哈顿距离也称为城市街区距离或出租车距离，来源于从一个十字路口到另一个十字路口沿公路穿越曼哈顿街区的实际驾驶距离对象之间的相似度切比雪夫距离也称为棋盘距离（chessboard distance），起源于国际象棋中国王的走法，表示国王从当前位置走到某一格所需要的最少步数。

对象之间的相似度闵氏距离全称为闵可夫斯基距离，实际上是一组距离的定义可变参数 r 可以取任意正整数当 r=1 时，为曼哈顿距离；当 r=2时，为欧氏距离；当 r 时，为切比雪夫距离对象之间的相似度兰氏距离也称为堪培拉距离（Canberra distance），可以看作是曼哈顿距离的加权版本对象之间的相似度马氏距离表示数据的协方差距离当协方差矩阵 为单位阵时，马氏距离就简化为欧氏距离对象之间的相似度(2)相似系数 包括两种相似的表示方法：余弦相似度和狭义相关系数后者针对不同类型的属性，又有不同形式的定义，最常用的是皮尔逊相关系数对象之间的相似度余弦相似度 如果将数据对象 和 看作 d 维空间的向量，余弦相似度就是这两个向量之间夹角的余弦值余弦相似度的取值范围为-1，1，当两个向量的方向重合时，余弦相似度取最大值1；当两个向量的方向完全相反时，余弦相似度取最小值-1对象之间的相似度 在欧氏距离中，衡量相似度的标准是点之间的绝对距离在余弦相似度中，衡量相似度的标准是向量之间夹角的大小余弦相似度更加注重两个向量在方向上的差异，而与向量的长度无关，因此它的优点是不受坐标轴旋转、放大和缩小的影响对象之间的相似度皮尔逊相关系数用于衡量数据对象间的线性关系。

其中：对象之间的相似度 皮尔逊相关系数等于两个变量的协方差除以它们各自标准差的乘积，取值介于-1 和 1 之间表示 和 正相关，表示 和 负相关，表示 和 不相关根据皮尔逊相关系数，还可以定义皮尔逊距离：对象之间的相似度二值离散属性 二值离散属性只有两个值，通常取0和1二值属性需要采用特定的方法计算相似度，其中一类常用的方法是匹配距离（matching distance）假设两个数据对象 和 的每个属性都是二值离散型的，而且0和1两个取值的权重相同，这样可以得到一个22的列联表（contingency table）对象之间的相似度 a：在 和 中取值均为 1 的二值属性的个数 b：在 中取 0 在 中取 1 的二值属性的个数 c：在 中取 1 在 中取 0 的二值属性的个数 d：在 和 中取值均为 0 的二值属性的个数对象之间的相似度 基于a、b、c、d 这四个数值，定义 和 间的距离：欧氏距离：兰氏距离：对象之间的相似度 信息论中的汉明距离（Hamming distance）也可用于度量二值属性的相似性汉明距离是将一个数据对象变换为另一个数据对象所需要的最小替换次数例1 与 的汉明距离等于3。

在聚类分析中，还定义了一系列的相似系数来衡量二值属性的相似度对象之间的相似度对象之间的相似度 如果数据对象的属性都是对称的二值离散属性，则可以采用简单匹配系数或者Rogers and Tanimoto系数计算对象之间的相似度所谓对称，是指属性值取 0 或 1 所表示的内容同样重要Jaccard系数和Sneath and Sokal系数适用于计算非对称二值属性的相似度对象之间的相似度多值离散属性 多值离散属性是二值离散属性的推广，是状态数量大于2的离散属性度量多值属性相似度最常用的方法是简单匹配法对于给定的两个 d 维数据对象 和 ，如果每一维属性都是多值离散型的，则相似度为：其中 m是匹配数，即 和 中取值相同的属性个数对象之间的相似度 另一种计算 和 之间相似度的方法是先将多值离散属性转换成多个二值离散属性，然后利用二值离散属性的相似系数计算公式算出结果在对多值离散属性进行转换时，需要为每种状态创建一个相应的二值属性，当给定对象具有某个状态时，代表该状态的二值属性就置为 1，否则置为 0对象之间的相似度混合类型属性 实际中的数据集通常含有多种类型的属性，对于这种数据，有几种不同的方式来计算对象之间的距离。

方式一：把连续属性通过二分法进行离散化，然后利用二值离散属性的距离函数计算对象之间的距离方式二：将离散属性转化为连续属性，然后将对象的所有属性规范化到相同的区间上，最后利用连续属性的距离函数进行求解对象之间的相似度方式三：根据每种属性的类型，分别选择合适的距离函数，然后将所有属性计算出的距离值进行加权组合，得到最终结果例2 方式三的一种实现方案第1步：将连续属性通过规范化处理转换到相同的值域区间0.0，1.0上；第2步：将多值离散属性转换成多个二值离散属性；第3步：定义 d 维数据对象 和 之间的距离为：对象之间的相似度其中 表示 和 在第 k 个属性上的距离，它的计算方法如下：i.若属性k 为二值离散型，当 时，；否则，；ii.若属性k 为连续型，则其中 h 是属性 k 的所有非空缺对象对象之间的相似度其中 表示属性 k 对 和 之间距离的贡献，它的计算方法如下：i.如果 或 缺失，则 ；ii.如果 ，且属性 k 是不对称的二值离散属性，则 ；iii.除了上述 i 和 ii 之外的其他情况下，类之间的相似度将类之间的相似程度转化为个体之间的相似程度 假设有 和 两个类，x 和 y 分别是这两个类中的对象，和 之间的相似度可通过距离函数进行度量。

最远距离也称为全连接法（complete linkage），它将两个类之间的距离定义为这两个类两两对象之间的最远距离，即：类之间的相似度最近距离也称为单连接法（single linkage），它将两个类之间的距离定义为这两个类两两对象之间的最近距离，即：平均距离也称为平均连接法（average linkage），它将两个类之间的距离定义为这两个类两两对象之间的平均距离，即：代表类的基数类之间的相似度在上述距离函数中，对象x 和 y之间的距离 可以利用之前介绍过的各种距离公式计算得到，其中最常用的是欧氏距离类之间的相似度利用类的某种统计平均量计算类的相似程度重心距离 重心是类中所有对象在各个属性上的均值重心距离法的定义如下：其中 和 分别表示 和 的重心，类之间的相似度 对于由离散属性构成的数据对象，重心 对应的点可能会落在取值空间之外，在这种情况下，用均值中心或者中值中心来代表类将更加合适一个类的均值中心 是与类内其他对象的距离和最小的对象，即满足：类的中值中心 定义为：其中 表示数据集 T 的中位数类之间的相似度离差平方和 离差平方和法的思想来自于方差分析，也称为Ward法和 可以取 和 的重心、均值中心或者中值中心。

相似性度量方法的选择 相似性度量方法显著影响着聚类分析的效果一般说来，同一个数据集如果采用不同的相似性度量方法，就会得到不同的聚类结果究其原因，主要是因为不同的度量方法代表了不同意义上的相似性在实际应用中，需要根据属性类型、数据性质、聚类算法等因素来选择合适的度量方法相似性度量方法的选择属性类型不同类型的属性有各自的相似性度量方法，而具体到每种属性类型，又存在多种距离函数或相似系数的定义因此，在研究具体问题时，应当明确属性及其取值在实际应用中的意义，并据此选择合适的度量方法数据性质一方面，数据维度的差异会影响度量方法的有效性另一方面，在某些情况下，为了简化计算过程或者改善聚类效果，需要对数据属性的类型进行适当变换相似性度量方法的选择聚类算法相似性度量方法的选择受到聚类算法的影响，例如对于二维数据集，马氏距离在k-means算法中的效果最优，但是在k-medoids算法中却不是此外，选择相似性度量方法时，还应当考虑计算量大小、研究目标等因素聚类算法4 根据聚类原理的不同，现有聚类算法主要分为以下几类：基于划分的方法、基于层次的方法、基于密度的方法、基于模型的方法、基于网格的方法、基于图论的方法、基于模糊聚类的方法、基于分形理论的方法等，不少聚类算法是这些方法的综合。

聚类算法基于划分的方法 聚类分析中最简单、最基本的一类算法它的基本思想是：对一个具有 n 个对象的数据集 D，给定要生成的簇的个数 ，算法从某个初始的划分方式出发，通过反复迭代不断调整 k 个簇的成员，直到每个簇的成员稳定为止大多数基于划分的聚类算法通过距离衡量对象间的相似度k-means 算法k-。