数据分析聚类分析

聚类分析：聚类分析(ClusterAnalysis)是一个将数据集中的所有数据，按照相似性划分为多簇是相似数据的集合。聚类分析是一种无监督分类方法：数据集中的数据没有预定义的类别标号(无训练集和训练的过程)。要求：聚类分析之后，应尽可能保证类别相同的数据之间具有较高的相似性，而类别不同的数据之间具有较低的相似性。聚类分析在数据挖掘中的作用：作为一个独立的工具来获得数据集中数据的分布情况；作为其他数据挖掘算法的预处理步骤。聚类分析的典型应用：图像处理——灰度图像的二值化(对灰度像素进行聚类)。对WEB日志数据进行聚类，以发现类似的用户访问模式。用户交易数据的聚类分析，以获得奇异点(异常交易)。常用的聚类分析方法：划分法：以距离作为数据集中不同数据间的相似性度量，将数据集划分成多个簇。层次法：对给定的数据集进行层次分解，形成一个树形的聚类结果。属于这样的聚类方法有：自顶向下法、自底向上法。相似性计算方法4特例：当两个样本之间的距离为零时，表示样本之间的距离是在样本的描述属性(特征)上进行计算的。连续性属性(如：重量、高度、年龄等)二值离散型属性(如：性别、考试是否通过等)多值离散型属性(如：收入分为高、中、低等)混合类型属性(上述类型的属性至少同时存在两种)q=1pointXYpl02p220p331p45pl0p22.8280p33.16202p45.0993.16220polntXYpl02p220p331p451pl pl0 p24 p34 p46p24024p34202p46420二值离散型属性只有0和1两个取值。1X■如果样本的属性都是对称的二值离散型属如果样本的属性都是不对称的二值离散型属性，则样本间的距离可用Jaccard系数计和aathenumberofatributeswacthenumberofattributesw多值离散型属性的相似性计算方法：多值离散型属性是指取值个数大于2的离散型属性。例如：成绩可以分为优、良、中、差。假设一个多值离散型属性的取值个数为N,给定数据集X={x;|i=1,2,..,total}。=(xj,x₂,.,xu),如何计算它们之间的距离?□方法二：先将多值离散型属性转换成多个二值离散型属性，然后再使用Jaccard系数计算样本距离计算公式如下：样本序号学历收入X高X2低X₃X老年本科以下中X4中年高ud(xj,x₄)=(3-2)/3≈0.3方法二：先将多值离散型属性转换成多个二值学历收入X高X₂X低X₃X本科以下中X中年高青中老年以下本科高中低X1001100X₂X1010001X₃X0100010X4010001100问题：对于包含混合类型属性的数据集，在聚类之前，对样本的属性值进行预处理：对连续型属性，将其各种取值进行规范化处理，使得属性值规范化到区间[0.0,1.0];其转换成多个二值离散型属性。预处理之后，样本中只包含连续型属性和二值离散型属性。典型的划分方法：□k-means(k-均值)□k-medoids(k-中心点)由处于簇中心区域的某个样本代表整个簇。序号属性1属性21序号属性1属性2123322455111 根据所给的数据通过对其实施k-means(设n=8,k=2),根据所给的数据通过对其实施k-means(设n=8,k=2),其主第一次迭代：假定随机选择的两个对象，如序2)和(3,4,5,6,7,8)。对于(1,2),平均值点为(1.5,1);对于[3,4,5,6,7,8},平均值点为(3.5,3)。即将所有点按离平均值点(1.5,1)、(3.5,3)最近的原则重新分配。得到两个新的簇：(1,2,3,4)和[5,6,7,8}.重新计算簇平均值点，得到新的平均值点为(1.5,1.5)和(4.5,3.5)。第三次迭代：将所有点按离平均值点(1.5,1.5)和(4.5,3.5)最近的原则重新分配，调整对象，簇仍然为[1,2,3,4)和[5,6,7,8},发现没有出现重新分配，而且准则函数选代次数平均值平均值产生的新族新平均值新平均值(簇1)(簇2)(簇1)(簇2)(1,1)(1,2)(1,2),[3,4,5,6,7,8(1.5,1)(3.5,3) 的类内龙我的零旋族而他宽龄类在间借可能分□对于同一个数据集，由于k-means算法对初始选取的聚类中心敏感，因此可用该准则评价聚类达到全局最优，只能达到局部最优。□可扩展性较好，算法复杂度为O(nkt)。□簇数目k需要事先给定，但非常难以选定；□初始聚类中心的选择对聚类结果有较大的影响；□对噪声和离群点数据敏感。□选取有代表性的样本(而不是均值)来表示整个簇，即：选取最靠近中心点(medoid)的那个样本来代表整个簇。□以降低聚类算法对离群点的敏感度。的划分)算法，于1987年提出。AlgorithmmedoidsPAMakmedoidsdlgorithmforpartitioni ■其中：n是数据集中样本的个数；Cpin表示中心点O,被非中心点O,替代后，样本点p的代价。·问题：如何计算每个样本点p产生的代价Cm?O0+p+p的隶属不发生变化，00p9p被重新分配给O假设空间中的五个点{A、B、C、D、E},如下图所示。各点之间的距离关系如下表所示，根据所给的数据对其运行k-medoids算法实现划分聚类(设k=2)。ABCDE33530A0122B1024C2201D2410E3353第一步建立阶段：假如从5个对象中第一步建立阶段：假如从5个对象中随机抽取的2个中心点为{A,B},则样本被划分为{A、C、D}和{B、E},如图所示。■第二步交换阶段：假定中心点A、根据PAM算法需要计算下列代价e)E原先属于B中心点所在的簇，当A被C替换以后，离E最近的中心仍然是B,根据PAM算法代价函数的第三种情况CEac=0。可按上述步骤依次计算代价TC、TC以及TCac、TCm、TCBE·当存在噪声和离群点时，k-medoids算法比k-means算法更加鲁棒(稳定)。k-medoids算法的执行代价比k-means算法要两种方法都需要事先指定簇的数目k。对给定的数据集进行层次分解：□自底向上方法(合并):开始时，将每个样本作为单独的一个组；然后，依次合并相近的样本或组，直至所有样本或组被合并为一个组或者达到终止条件为止。□自顶向下方法(分裂):开始时，将所有样本置于一个簇中；然后，执行迭代，在迭代的每一步中，一个簇被分裂为多个更小的簇，直至每个样本分别在一个单独的簇中或者达到终止条件为止。AGNES(AgglomerativeNesting)算法合并准则：每次找到距离最近的两个簇进行合并。AGNESAGNES算法(自底向上合并算法)AGNES算法在这个算法中，需要使用单链接(Single-Link)方法和相异度矩阵。□单链接方法用于确定任意两个簇之间的距离；□相异度矩阵用于记录任意两个簇之间的距离(它是一个下三角矩阵，即：主对角线及其上方表1数据集2空江0211.6705个样本之间的相异度矩阵015dy=13.80dμ=13,12d;sdydy2340河南与甘肃的距离最进，先将二者(3和4)合为一类G6=[G3.G4]——doi=d34₁=min{d,d₄)=13.12d₆₂=d₃zmin620河南、甘肃与青海并为一新类采用欧氏距离：d₇2=d₃45i₂=min(d2,dd700808AGNES算法AGNES算法的优、缺点：□算法简单，但有可能遇到合并点选择困难的情□在该种层次聚类算法中，也是以希望得到的簇的数目作为聚类的结束条件。同时，使用下面两种测度方法：簇的直径：在一个簇中，任意两个样本间距离的最大值。平均相异度(平均距离):输入：包含n个样本的数据集，终止条件簇的数目k。输出：k个簇，达到终止条件规定的簇的数目。例：有如下表所示的数据集，使用DIANA算法对该数据集进行分裂层次聚类。12345678属性1属性211223344第1步，首先找到具有最大直径的簇，然后计算该簇中每个样本的平均相异度(假定采用是欧式距2345678属性1112233441212454500第1步，首先找到具有最大直径的簇，然后计算第1步，首先找到具有最大直径的簇，然后计算该簇中每个样本的平均相异度(假定采用是欧式距样本5的平均距离为：2.18样本6的平均距离为：2.68大于该样本与oldparty中其他样本之间的最小距离，述条件的是样本2。group中的样本，并且此时达到算法的终止条件(k=2),算法结束。(如果没有达到算法的终止条件，应该从分裂出来的簇中再挑选一个具有直径最大的簇继续分裂。){2,3,4,5,6,7,8}{3,4,5,6.7,8}2,3,4,5,6,7,8]{1,2,3}[4,5,6,7.8}2,3,4,5,6,7,8]{1,2,3,4){5,6,7,8]2.3,4,5,6,7,8j(1