数据挖掘(4)

《数据挖掘(4)》由会员分享，可在线阅读，更多相关《数据挖掘(4)（24页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章 聚类挖掘聚类挖掘东东北师师大软软件学院、理想信息技术术研究院 Email：Lixy_李 献 业Data Mining 数据挖掘一、聚类挖掘的相关概念1、聚类就是把整个数据分成不同的组，并使组与组之间的差异尽可能大，组内数据的差异尽可能小。2、聚类与分类的差别聚类开始时不知道要把数据分成几组，也没有分类的具体标准，聚类分析时数据集合的特征是未知的，也称无指导学习。分类开始时知道要把数据分成几组，分类将要处理的数据按照分类标准分入不同的类别，也称有指导学习。例如，聚类：婴儿区分动物；分类：成人区分动物。 2一、聚类挖掘的相关概念3、聚类问题的数学描述给定数据集合Vvi|i=1，2，n

2、，其中vi为数据对象，根据数据对象间的相似程度将数据集合分成k组，并满足如下条件：则该过程成为聚类。4、簇聚类中的组称为簇。其它关于簇的定义：一些相似成员的集合，不同簇中的成员是不相似的。簇中两点之间的距离要小于簇中一点与簇外任一点之间的距离。 3一、聚类挖掘的相关概念5、聚类分析方法的分类（1）按照聚类的标准，可分为两种：l 统计聚类方法基于对象之间的相似性度量进行聚类。包括：系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。此方法基于全局的比较，需要考察所有个体，因此，数据必须预先给定，不能动态增加新的数据对象。l 概念聚类方法基于对象具有的概念进行聚类。这里的

3、距离不是传统方法的集合距离，而是根据概念的描述来确定的。典型方法有：COBWEB、CLOC和基于列连的方法。 4一、聚类挖掘的相关概念（2）按照所处理的数据类型，可分为三种：l 数值型数据聚类方法所分析的数据是数值型数据，因此，可对所处理的数据直接比较大小。l 符号值数据聚类方法所分析的数据是符号型数据，因此，对所处理的数据不能直接比较大小。l 混合型数据聚类方法能同时处理数值数据和符号数据，此方法通常功能强大，但性能往往不尽如人意。5一、聚类挖掘的相关概念（3）按照聚类的尺度，可分为三种：l基于距离的聚类算法根据数据之间的距离进行聚类。此算法对噪声数据和孤立点较敏感。l基于密度的聚类算法此方

4、法认为簇是具有相同密度的联通区域。因此，需要扫描整个数据集，将数据划分为不同的小方格，并使用小方格的并来近似表示簇。因此可能不够精确。该方法对于噪声数据和孤立点不敏感。l基于互连性的聚类算法此类方法将聚类对象映射为图模型或超图模型，然后根据边寻找高连通度的结点集合。此方法能较好第反映数据之间的相关程度。 6一、聚类挖掘的相关概念（4）按照聚类分析算法的主要思路，可分为：l划分法：给定由n个对象或者元组的数据库，将数据划分为k（kn）组，每个组表示一个簇，每个组至少包含一个对象，每个对象必须属于且只属于一个组。l层次法：对给定的数据对象进行层次的分解。又分为凝聚法和分裂法 凝聚法：也称自底向上的

5、方法，一开始将每个对象单独作为一个簇，然后逐步合并相近的簇，直到每个簇满足特征性条件。 分裂法：也称自顶向下的方法，一开始将所有的对象置于一个簇中，然后逐步分裂成更小的簇，直到每个簇满足特征性条件。l基于模型的方法：给每个簇假定一个模型，然后去寻找能够很好地满足此模型的数据集。本章主要讨论基于划分的聚类算法和基于层次的聚类算法。 7一、聚类挖掘的相关概念6、距离与相似性度量 聚类分析的质量取决于度量标准的选择，下面是一些常用的度量标准 （1）距离函数 欧氏距离 明可夫斯基距离 二次性距离 余弦距离 二元特征样本的距离 （2）类间距离 最短距离法 最长距离法 中心法 类平均法 离差平方和8二、基

6、于划分的聚类方法1.主要思想给定一个有n个对象的数据集，划分聚类方法将构造数据的k（kn）个划分，每一个划分代表一个簇，即将数据划分为k个簇，且这k个划分满足下列条件： 每一个簇至少包含一个对象 每一个对象属于且仅属于一个簇。对于给定的k，算法首先给定一个初始的划分方法，以后通过反复迭代改变划分，使得每一次改进之后的划分方案都较前一次更好。即同一簇中的对象越近，不同簇中的对象越远。此类方法包括：k-平均、k-模、k-原型、k-中心点、PAM、CLARA以及ALARANS等。 9二、基于划分的聚类方法2、K-平均算法（1）算法介绍也称k-均值算法，是一种广泛使用的聚类算法。它以k为参数，把n个对

7、象分为k个簇，使簇内具有较高的相似度，而簇间的相似度较低。相似的计算根据簇中对象的平均值进行。（2）算法思想首先随机选择k个对象，每个对象初始代表一个簇的平均值或中心。对剩余的对象根据其与各个簇中心的距离，将其赋给最近的簇。然后重新计算每个簇的平均值。重复这个过程，直到准则函数收敛。准则函数如下：其中，E是数据库所有对象的平方误差的总和，x是空间中的点，表示给定的数据对象， 是簇的平均值。 10二、基于划分的聚类方法l第二次迭代：通过平均值调整对象所在的簇，重新聚类，即按离平均值点（1.5，1）和（3.5，3）最近的原则重新分配。得到两个新的簇1，2，3，4和5，6，7，8。重新计算簇平均值点

8、，得到新的平均值点为（1.5，1.5）和（4.5，3.5）。l第三次迭代：将所有点按离平均值（1.5，1.5）和（4.5，3.5）最近的原则重新分配，调整对象，得到两个新的簇1，2，3，4和5，6，7，8。发现没有出现重新分配，而且准则函数收敛，程序结束。（3）算法执行例子对右表的样本数据集，使用k-平均算法进行聚类。执行过程如下：l 第一次迭代：随机选择两个对象，如序号1和序号3当作初始点，分别找到离两点最近的对象，并产生两个簇1，2和3，4，5，6，7，8。对产生的簇分别计算平均值，得到平均值点：对于1，2，平均值点为（1.5，1）对于3，4，5，6，7，8，平均值点为（3.5，3） 序号

9、属性1属性211122131242254365374485411二、基于划分的聚类方法3、PAM（1）算法简介PAM是最早提出的k-中心点算法之一，他选择簇中位置最靠近中心的对象作为作为代表对象，对n个对象给出k个划分。（2）算法思想最初随机选择k个对象作为中心点，反复用非代表对象代替代表对象，试图找出更好的中心点以改进簇类的质量。在每次迭代中，所有可能的对象对（一个是中心点，另一个是非代表对象）被分析，对可能的各种组合，估计聚类结果的质量。PAM算法分为两个步骤：建立：随机寻找k个中心点作为初始的簇中心点。交换：对于所有可能的对象进行分析，找出交换后可以使平方-误差减少的对象，代替原中心点。

10、 12二、基于划分的聚类方法（3）算法执行例子假如空间中有五个点A，B，C，D，E，各点之间的距离关系如表，根据所给的数据用PAM算法进行实现划分聚类。样样本点 A B C D EA 0 1 2 2 3 B 1 0 2 4 3 C 2 2 0 1 5 D 2 4 1 0 3 E 3 3 5 3 0ABCDE算法执行步骤如下：第一步：建立阶段：从5个对象随机抽取2个中心点为A，B，则样本被划分为A，C，D和 B，E，如图： ABCDE13二、基于划分的聚类方法第二步，交换阶段：为了逐个检验三个非中心点C，D，E是否能够代替中心点A和B，需要计算6个距离代价的改变量：TCAC、TCAD、TCAE、

11、TCBC、TCBD、TCBE。下面以TCAC（A被C替换）为例说明计算过程：l 当A被C替换以后，A不再是中心点，因为A离B比A离C近，A被分配到B中心点代表的簇，CAAC=d（A，B）-d（A，A）=1。l B是一个中心点，当A被C替换后，B不受影响，CBAC=0l C原先属于A中心点所在的簇，当A被C替换后，C是新中心点，CCAC=d（C，C）-d（C，A）=0-2=-2。14二、基于划分的聚类方法lD原先属于A中心点所在的簇，当A被C替换以后，离D最近的中心点是C， CDAC=d（D，C）-d（D，A）=1-2=-1。lE原先属于B中心点所在的簇，当A被C替换后，离E最近的中心点仍是B，

12、CEAC=0.因此，TCAC=1+0-2-1+0=-2。同理，可以计算出：TCAD=-2，TCAE=-1，TCBC=-2，TCBD=-2，TCBE=-2选取一个最小的代价，如TCAC（C替换A），样本点被划分为B，A，E和C，D。至此完成第一次迭代，重复上述过程，直到代价不再减小。 15二、基于划分的聚类方法下图为6个距离代价的改变量ABCDEABCDEABCDEABCDEABCDEABCDE131 123113113122(a)开始：A和B为中心点(b)TCAC：变化-2；TCAD：变化-2(c)TCAE：变化-1(e)TCBE：变化-2(e)TCBD：变化-2(d)TCBC：变化-2223

13、16三、层次聚类方法层次聚类方法是对给定的数据集进行层次分解，直到满足某种条件为止。具体可分为凝聚的、分裂的两种方案。l凝聚的层次聚类是一种自底向上的策略，首先将每个对象作为一个簇，然后逐渐合并为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足。l分裂的层次聚类是一种自顶向下的策略，首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者某个终结条件被满足。 17三、层次聚类方法（1）AGNES算法是凝聚的层次聚类方法。算法最初将每个对象作为一个簇，然后根据某些准则将这些簇一步步合并。例如，如果C1中的一个对象和C2中的一个对象之间的相似度是所有不同簇

14、间最小的，则C1和C2被合并。两个簇间的相似度由这两个不同簇中距离最近的数据点对的欧氏距离确定。例，对右边的样本数据集，使用AGNES算法进行聚类（用户输入的终止条件为两个簇）。 序号属性1属性211122131242254365374485418三、层次聚类方法算法步骤如下： 初始簇1，2，3，4，5，6，7，8 第一步，根据初始簇计算每个簇间的距离，随即找出距离最小的两个簇，进行合 并，最小距离为1，合并后1、2点合并为一个点。 第二步，对上一次合并后的簇计算簇间的距离，找出距离最小的两个簇，进行合 并，合并后3、4点合并为一个点。 第三步，同上，5，6点成为一簇。 第四步，同上，7，8点

15、成为一簇。 第五步，合并1，2，3，4为一个簇。 第五步，合并5，6，7，8为一个簇。合并后簇的数目为2，达到终止条件程序 终止。 步骤骤最近的簇距离最近的两个簇合并后的新簇1 2 3 4 5 61 1 1 1 11，2 3，4 5，6 7，8 1，2，3，4 5，6，7，81，2，3，4，5，6，7，8 1，2，3，4，5，6，7，8 1，2，3，4，5，6，7，8 1，2，3，4，5，6，7，8 1，2，3，4，5，6，7，8 1，2，3，4，5，6，7，819三、层次聚类方法（2）DIANA算法是分裂的层次聚类。算法初始将所有对象都放在一个簇中，然后根据一些原则（如簇中最邻近对象的最大欧氏距离），将该簇分裂。分裂过程反复进行，直到达到终止条件。算法使用下面两种测度方法： 簇的直径：在一个簇中的任意两个数据点都有一个欧氏距离，这些距离中最大值是簇的直径。 平均相异度。例，对下面的样本数据集，使用DIANA算法进行聚类（用户输入的终止条件为两个簇）。 序号属性1属性2111221312422543