1、SEMINAR数据挖掘中的聚类分析算法研究数据挖掘中的聚类分析算法研究SEMINAR结构 一、聚类分析 二、聚类分析中的数据结构和数据类型 三、聚类分析算法分类SEMINAR1.1聚类分析聚类分析 聚类分析（聚类分析（ clustering analysis ） 聚类是把一组个体按照相似性划分成若干个类别，跟平常说的“物以类聚”相似。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。在许多应用中，可以将一个簇中的数据对象作为一个整体来对待。 SEMINAR1.2聚类分析与其他分类或预测的不同聚类分析与其他分类或预测的不同聚类与其他分类或预测的不同聚
2、类与其他分类或预测的不同（1）大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。（2）聚类分析是归纳的，不需要事先确定分类的准则来分析数据对象，不考虑己知的类标记。一般情况下，训练数据中不提供类标记，聚类的目标就是通过聚类算法产生这种标记。SEMINAR数据挖掘对聚类的典型要求数据挖掘对聚类的典型要求（1）可伸缩性）可伸缩性 可伸缩性是指算法不论对于小数据集还是对于大数据集,都应是有效的。（2）处理不同字段类型的能力）处理不同字段类型的能力 算法不
3、仅要能处理数值型数据，还要有处理其它类型字段的能力，包括分类/标称类型(categorical/nominal)，序数型(ordinal)，二元类型(binary)，或者这些数据类型的混合。1.3数据挖掘对聚类的典型要求数据挖掘对聚类的典型要求SEMINAR（3 3）能够发现任意形状的聚类）能够发现任意形状的聚类 有些簇具有规则的形状，如矩形和球形。但是，更一般地，簇可以具有任意形状。（4）用于决定输入参数的领域知识最小化）用于决定输入参数的领域知识最小化 在聚类分析当中，许多聚类算法要求用户输入一定的参数，如希望簇的数目。聚类结果对于输入参数很敏感，通常参数较难确定，尤其是对于含有高维对象的
4、数据集更是如此。（5）处理高维数据的能力）处理高维数据的能力 既可处理属性较少的数据，又能处理属性较多的数据。很多聚类算法擅长处理低维数据，一般只涉及两到三维，通常最多再加二维的情况下能够很好地判断聚类的质量。1.3数据挖掘对聚类的典型要求数据挖掘对聚类的典型要求SEMINAR（6）能够处理噪声数据）能够处理噪声数据 现实世界中的数据库常常包含了孤立点、空缺、未知 数据或有错误的数据。一些聚类算法对于这样的数据敏感,可能导致低质量的聚类结果。所以我们希望算法可以在聚类过程中检测代表噪声和离群的点，然后删除它们或者消除它们的负面影响。 （7）结果对于输入记录顺序不敏感）结果对于输入记录顺序不敏感
5、 一些聚类算法对于输入数据的顺序是敏感的。对于同一个数据集合，以不同的顺序提交给同一个算法时，可能产生差别很大的聚类结果，这是我们不希望的。 1.3数据挖掘对聚类的典型要求数据挖掘对聚类的典型要求SEMINAR（8）基于约束的聚类）基于约束的聚类 在实际应用当中可能需要在各种约束条件下进行聚类。找到既要满足特定的约束，又要具有良好聚类特性的数据分组是一项具有挑战性的任务。我们希望聚类算法可以在考虑这些限制的情况下，仍具有较好的表现。（9）可解释性和可用性）可解释性和可用性 聚类的结果最终都是要面向用户的，用户期望聚类得到的信息是可理解和可应用的。1.3数据挖掘对聚类的典型要求数据挖掘对聚类的典
6、型要求SEMINAR聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型（1）数据结构）数据结构 许多基于内存的少类算法选择如下两种有代表性的数据结构。1）数据矩阵（对象-变量结构） 数据矩阵是一张关系表的形式,每列代表对象的一个属性,每个元组代表一个数据对象。 具有p个属性的n个对象（例如，人可以用年龄，身高，体重，性别，种族等来描述）可以看成如下np(n个对象p个属性)的矩阵。2.聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型SEMINAR 2）相异度矩阵（对象-对象结构） 它存储n个对象两两之间的差异性，表现形式是nn维的矩阵。2.聚类分析中的数据结构和数据类型聚类
7、分析中的数据结构和数据类型SEMINAR 其中d(i，j)是对象i和对象j之间相异性的量化表示，通常为非负数，且d(i，j)=d(j，i)，d(i，i)=。对象i和对象j越相似，则d(i，j)越接近于0，对象i和对象j的差异越大，则d(i，j)越大。相异度矩阵通常用距离公式计算得到。2.聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型SEMINAR（2）数据类型）数据类型 聚类分析起源于统计学，传统的分析方法大多是在数值类型数据的基础上研究的。然而数据挖掘的对象复杂多样，要求聚类分析的方法不仅能够对属性为数值类型的数据进行，而且要适应数据类型的变化。1）区间标度变量 区间标度变量是
8、一个粗略线性标度的连续度量。典型的例子则包括重量和高度，经度和纬度坐标，以及摄氏或华氏温度等。 数据之间纯在差异性，同时多个属性肯那个有不同的度量单位，所以在计算数据相似性之前要进行数据的标准化。2.聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型SEMINAR 数据标准化处理以后就可以进行属性值的相似性测量，通常是计算对象间的距离。 对于n维向量xi和xj，有以下几种距离函数： 欧氏距离 曼哈顿距离2.聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型SEMINAR 概化的明考斯基（Minkowski）距离 当m=2时，明考斯基D2即为欧氏距离；当m=1时，明考斯基D1
9、即为曼哈顿距离。2.聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型SEMINAR2）二元变量 二元变量只有两个状态：0和1。其中二元变量又分为对称的二元变量和不对称的二元变量。前者是指变量的两个状态不具有优先权，后者对于不同的状态其重要性是不同的。 对于二元变量,度量两个变量的差异度可以由简单匹配系数(对称的情况)和Jaccard系数(非对称的情况)决定。设两个对象xi和xj，q是属性值在两个对象中都为1的属性个数，r是属性值在xi中为1而在xj中为0的属性个数，s是属性值在xi中为0而在xj中为1的属性个数，t是属性值在两个对象中都为0的属性个数。则2.聚类分析中的数据结构和数
10、据类型聚类分析中的数据结构和数据类型SEMINAR简单匹配系数：Jaccard系数2.聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型SEMINAR3）标称型变量 标称变量是二元变量的推广，它可以有多于两个状态值，状态之间是无序的。 两个对象i和j之间的差异度可用简单匹配法来计算: 其中，m是对象xi和xj中匹配的属性个数，而p是全部属性个数。2.聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型SEMINAR4）序数型变量 序数型变量类似于标称型变量，但它的各个状态是有意义的序列。 序数型变量值的相对顺序是必要的，而其实际的大小则不那么重要。一个序数型变量的值可以映射为
11、秩。假设一个变量f有m个状态，这些有序的状态定义了一个序列1，m，关于f的相异度计算步骤如下： 第i个对象的f值为xif，变量f有m个有序的状态，对应于序列1，m。用对应的秩rif代替xif，rif 1，m 每个序数型变量有不同数目的状态，为了使每个变量都有相同的权重,我们将每个变量的值域映射到0.0,1.0上:2.聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型SEMINAR 其中zif是rif映射后的值。 采用zif作为第i个对象的f值，计算相异度，可以采用任意一种距离度量方法。5）比例标度型变量 比例标度型变量就是在非线性的标度上所获得的正测量值。 对于此种类型的变量，一般采
12、用以下两种方法计算相异度。2.聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型SEMINAR2.聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型 对比例标度型变量进行对数变换，变换得到的值采用区间标度变量的方法来处理。 将比例标度型变量看做连续的序数型数据，将其秩作为区间标度的值来对待。6）混合类型的变量 以上讨论了各种数据类型和创门差异度的计算方法，在实际数据库中，数据对象是由混合类型的变量描述的。在实际聚类分析中，将不同的类型属性组合在同一个差异度矩阵中进行计算。设数据包含m个不同类型的属性,对象xi和xj之间的差异度定义为：SEMINAR 如果属性p是序数型或比例
13、标度型变量：将其转化为区间标度变量值对待。2.聚类分析中的数据结构和数据类型聚类分析中的数据结构和数据类型SEMINAR聚类分析算法分类聚类分析算法分类 聚类分析技术通常可分为五大类，分别是基于划分的聚类，基于层次的聚类，基于密度的聚类，基于网格的聚类以及基于模型的聚类。3.聚类分析算法分类聚类分析算法分类SEMINAR（1）基于划分的方法）基于划分的方法 划分算法的思想是，将给定待挖掘数据集中的数据对象划分成 K 组（k N，N代表数据集中对象数目），每一组表示一个聚类的簇。并且要满足任何一个数据对象仅可以属于一个聚类，每个聚类中至少具有一个数据对象。 K-medoids 和 K-means
14、 算法是划分算法中两个比较经典的算法。其他很多划分算法都是从这两个算法演变改进而来的。3.聚类分析算法分类聚类分析算法分类SEMINAR1.K-means（k均值）算法均值）算法 K-means算法的相似度计算根据一个簇中对象的平均值即簇的质心来进行，它的处理过程如下：首先，随机地选择k个对象作为初始的k个簇的质心；然后对剩余的每个对象，根据其与各个质心的距离，将它赋给最近的簇；再后重新计算每个簇的质心。这个过程不断重复，直到准则函数收敛。通常采用的准则函数为平方误差和准则函数,即SSE(sum of the squared error)，其定义如下： 这里的SSE是数据库中所有对象的平方误差
15、总和，p为数据对象，mi是簇Ci的平均值。这个准则函数使生成的结果尽可能的紧凑和独立。3.聚类分析算法分类聚类分析算法分类SEMINARK 均值算法的形式化描述如下：均值算法的形式化描述如下：K-means 算法：输入：具有 n 个数据对象的数据集，聚类结果中簇的个数 k。输出： 满足准则函数的 k 个聚类。处理过程：(1) 在数据集里任意选择 k 个对象，然后将每个数据对象代表初始聚类的中心；(2) 将剩下的数据划分到和数据本身相距最近的簇心的簇中；(3) 重新计算每个簇的均值得到新的簇心值(4) 重复(2)到(3)一直到每个簇不再发生变化或者目标函数收敛结束3.聚类分析算法分类聚类分析算法
16、分类SEMINAR 在该算法中，一次迭代中把每一个数据对象分到离它最近的聚类中心所在类，这个过程的时间复杂度为O(nkd)，这里的n指的是总的数据对象个数，k指定的聚类数，d是数据对象的维数；新的分类产生以后需要计算新的聚类中心,这个过程的时间复杂度为O(nd)。因此，这个算法一次迭代需要的总的时间复杂度为O(nkd)。例：假设给定如下要进行聚类的元组： 2,4,10,12,3,20,30,11,25 假设要求的簇的数量为k=2。 应用K一means算法： 第一步：初始时用前两个数值作为簇的质心，这两个簇的质心是：m1=2；m2=4；3.聚类分析算法分类聚类分析算法分类SEMINAR 第二步：
17、对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇，可得： K1=(2,3； K2=4,10,12,20,30,11,25； 数值3与两个均值的距离相等，所以任意的选择K1作为其所属的簇。 第三步：计算新的质心： m1=(2+3)/2=2.5； m2=(4+10+12+20+30+11+25)/7=16； 重新对簇中的成员进行分配可得K1 =2,3,4和K2 =10,12,20,30,11,25，3.聚类分析算法分类聚类分析算法分类SEMINAR不断重复这个过程可得: 注意在最后两步中簇的成员是一致的。由于均值不再变化，所以均值已经收敛了。因此，该问题的答案为K1=2,3,4,10,
18、11,12和K2 =20,30,25。3.聚类分析算法分类聚类分析算法分类SEMINARK-means优缺点：优缺点： 此聚类分析算法伸缩性良好，并且针对大型数据集效率很高。 初始的 K-means 算法缺点如下：(1)初始聚类中心选择的好与坏将会对聚类结果的质量产生很大影响；(2)算法很容易陷入局部最优解，有时会产生较差的结果；(3)算法开始时要求用户给出聚类簇的个数 k，而对于 K 值的选择还没有很好的准则可循；(4)对噪声敏感；(5)只能在可以定义聚类的平均值的条件下才可以应用，即适合处理数值属性的数据 (6)聚类的最终结果也许会出现不平衡现象，不适合发现那些非凸面形状的簇或者大小差别非
19、常大的簇。3.聚类分析算法分类聚类分析算法分类SEMINAR2.K-medoids（中心点）（中心点） 算法算法 K-means算法对于孤立点敏感，一个极大值的对象可能在相当大的程度上扭曲数据的分布。k中心点算法不采用簇中对象的平均值作为簇中心，而选用簇中离平均值最近的对象作为簇中心，此种方法具有很好的抗噪声的能力。以下是 K-medoids 算法的形式化描述：K-medoids 聚类算法：输入：具有 n 个对象的数据库，聚类的簇数目 k输出：满足目标函数的 k 个簇。3.聚类分析算法分类聚类分析算法分类SEMINAR处理过程：(1) 从输入的数据集中任意选择 k 个数据对象，并将每个数据对象
20、看做是初始簇的聚类中心；(2) 计算剩下的每个数据对象到每个簇中心点的距离，并将其指派到离它最近的中心点所代表的簇中；(3) 任意选择一个非中心点的数据对象 Or；(4) 计算用 Or代替 Oj形成新集合的总代价 s；(5) 如果 s0，则用 Or代替 Oj ，得到新的 k 个中心点的集合；(6) 重复(2)、(3)、(4)、(5)，直至 k 个中心点不再改变或目标函数收敛为止。 K-medoids 算法在抗噪声和孤立点的能力方面有了很大的提高，但是 K-medoids算法在处理起来花费时间比较长，并且依然需要用户输入目标聚类个数 k。 3.聚类分析算法分类聚类分析算法分类SEMINAR(2)
21、基于层次的聚类算法基于层次的聚类算法 层次的方法按数据分层建立簇,形成一棵以簇为节点的树。根据层次如何形成，层次的方法可以分为凝聚的和分裂的。 凝聚的方法，也称自底向上的方法，该方法从数据点作为个体簇开始，每一步合并两个最接近的簇，直到所有的簇合并为一个(层次的最上层)，或者达到一个终止的条件。 分裂的方法，也称为自顶向下的方法，它与凝聚的方法正好相反，该方法从包含所有点的一个簇开始，每一步分裂一个簇，最终每个对象在单独的一个簇中，或者达到一个终止条件，比如达到某个希望的簇数目，或者两个最近的簇之间的距离超过了某个闭值。3.聚类分析算法分类聚类分析算法分类SEMINAR 无论是凝聚算法还是分裂
22、算法都要采用一个划分准则,以便判定簇之间的相似性或相异性,五个广泛采用的簇间距离度量方法如下:（1）最小（单链）距离；（2）最大（全链）距离；（3）平均值（质心）距离；（4）平均（组平均）距离；（5）中心点距离。3.聚类分析算法分类聚类分析算法分类SEMINAR(3)基于密度的方法基于密度的方法 目前的研究发现基于密度的聚类方法在发现任意形状的数据集方面具有非常有力的效果。简单来说，基于密度的聚类算法就是将数据对象划分为成被低密度区分隔开的高密度区。基于密度的聚类应用本地集群准则，有非常优秀的抵抗噪声的效果，而且在挖掘任意形状的数据集方面的能力也非常优秀。虽然基于密度的聚类在发现任意形状的簇的
23、方面具有良好的效果，但是他依然需要用户输出必要的参数，并且其可扩展性也具有一定的局限性。 典型的基于密度的聚类方法包括DBSCAN和OPTICS。3.聚类分析算法分类聚类分析算法分类SEMINAR（4）基于网格的方法）基于网格的方法 基于网格算法的基本是思想是把数据空间的每个属性分割成有限个相邻的单元的网格结构，以单个单元为对象创见网格单元的集合，在此一切都是以划分的网格单元为对象进行操作。 基于网格的算法涉及到两方面参数的设定，其一是网格单元的设置，其二是网格单元密度的设定。3.聚类分析算法分类聚类分析算法分类SEMINAR（5）基于模型的聚类分析算法）基于模型的聚类分析算法 基于模型的聚类分析算法思想是把给定的数据集与某个相应数学模型相结合，寻找数据与模型之间的最佳拟合。在此种算法中，聚类结果的簇的数目也是通过统计数字自动所决定的，孤立点和噪声也是根据统计数字进而进行分析的。3.聚类分析算法分类聚类分析算法分类
