数据挖掘 第8章 聚类分析：基本概念和算法
- 格式：ppt
- 大小：1.29 MB
- 文档页数：47
下载文档原格式
合集下载
完整版数据挖掘中的聚类分析方法
数据挖掘中的聚类分析方法随着计算机应用的普及，信息系统产生的数据量日益增大，如何有效地利用巨量的原始数据分析现状和预测未来，己经成为人类面临的一大挑战。
由此数据挖掘技术应运而生并得以迅猛发展，这是快速增长的数据量和日益贫乏的信息量之间矛盾运动的必然结果。
数据挖掘(DataMining),又称为数据库中的知识发现(简称KDD),是从大量数据中提取可信的、新颖的、有效的并能被人们理解的模式的处理过程。
数据挖掘是一门新兴的技术，它以数据库技术作为基础，把逻辑学、统计学、机器学习、模糊学、可视化计算等多门学科的成果综合在一起，进行如何从数据库中得到有用信息的研究。
数据挖掘技术得到了人们的普遍关注，广泛应用于银行金融、保险、公共设施、政府、教育、远程通讯、软件开发、运输等各个企事业单位及国防科研上。
聚类分析是数据挖掘中的一个重要研究领域。
所谓聚类，就是把没有类别标记的样本集按某种准则划分成若干类，使类内样本的相似性尽可能大，而类间样本的相似性尽量小，是一种无监督的学习方法。
聚类分析通常是在没有先验知识支持的前提下进行的，它所要解决的就是在这种前提下，实现满足要求的类的聚合。
聚类分析的研究主要集中在聚类算法上，产生性能好而且实用的聚类算法是其终极目的。
聚类是一个富有挑战性的研究领域，采用基于聚类分析方法的数据挖掘在实践中己取得了较好的效果，在实际操作中往往不是采用单一的手段，而是采用多种手段和方法相结合根据潜在的各项应用，数据挖掘对聚类的典型要求有以下9个方面：⑴可伸缩性可伸缩性是指算法不论对于小数据集还是对于大数据集，都应是有效的在很多聚类算法当中，对于数据对象小于200个的小数据集合性很好，而对于包含成千上万个数据对象的大规模数据库进行聚类时，将会导致有不同的偏差结果。
此外，可伸缩性算法应该随着数据库大小的变化，其运行时间应该线性变化。
(2)处理不同字段类型的能力算法不仅要能处理数值型数据，还要有处理其它类型字段的能力，包括分类标称类型(catalog流Viminal),序数型(ordinal),二元类型(binary),或者这些数据类型的混合。
聚类分析算法
聚类分析算法
聚类分析是一种数据挖掘技术，它可以从大量数据中发现联系，建立相似的类别，以便于进一步理解数据的结构和特征。
简而言之，聚类分析是将相似的数据分组，以便更详细地了解数据结构，以及数据之间的关系。
聚类分析技术可以帮助人们从数据中发现有趣的结构，或者发现数据之间的联系，可以用于许多不同的应用，比如市场分析，客户分析，社会网络分析，生物信息学，图像分析等等。
聚类分析的过程主要包括几个步骤：首先，选择数据集，然后为数据定义一个相似度函数，利用这个函数来确定数据之间的相似度；接着，使用聚类算法（如K-means或其他）将数据分成不同的类别；最后，进行结果评估，以确定聚类分析算法的有效性。
聚类分析技术对于许多不同的应用都有重要的作用，它可以帮助我们发现数据之间的联系，更好地理解数据，并让我们更加容易地发现有价值的信息。
因此，聚类分析技术是数据挖掘的一个重要工具，可以帮助我们更好地利用数据来解决实际问题。
数据挖掘方法聚类分析学习资料
* 距离越小，说明两个样本的性质越相似。 * 它的取值大小受量纲影响，不稳定。因此，
一般使用标准化的距离公式。
2、描述两个指标变量之间的相似程度：相似系数
令 Xs =(x 1 s … x i s … x n s )是第 s 个指标变 量， Xt =(x 1 t … x i t … x n t )是第 t 个指标变 量， 那么，指标变量 Xs和Xt之间的相关系数是：
A3
• 两点之间的距离：
A2
A1
– 欧氏距离(Euclidean distance)
– 欧氏距离的平方(squared Euclidean distance)
– 曼哈顿距离(Manhattan distance ; City-Block)
关于曼哈顿距离
曼哈顿距离——两点在南北方向上 的距离加上在东西方上的距离， 即D（I，J）=|XI-XJ|+|YI-YJ|。 对于一个具有正南正北、正东正 西方向规则布局的城镇街道，从 一点到达另一点的距离正是在南 北方向上旅行的距离加上在东西 方向上旅行的距离因此曼哈顿距 离又称为出租车距离。
聚类分析的统计量
数据
从几何学角度看，上面表中的每一行或每一列 都表示了空间中的一个点或一个向量。
1、描述两个样本之间的相似程度: 距离
令 Xi =(x i 1 … x i t … x i k )是第 i 个样本观察 值， Xj =(x j 1 … x j t … x j k )是第 j 个样本观 察值，那么，样本 Xi 和 Xj 之间的欧氏距离是：
• 1967年由学者J. B. MacQueen 所提出，也是最 早的组群化计算技术。
The K-Means Clustering Method
• Example
一般使用标准化的距离公式。
2、描述两个指标变量之间的相似程度：相似系数
令 Xs =(x 1 s … x i s … x n s )是第 s 个指标变 量， Xt =(x 1 t … x i t … x n t )是第 t 个指标变 量， 那么，指标变量 Xs和Xt之间的相关系数是：
A3
• 两点之间的距离：
A2
A1
– 欧氏距离(Euclidean distance)
– 欧氏距离的平方(squared Euclidean distance)
– 曼哈顿距离(Manhattan distance ; City-Block)
关于曼哈顿距离
曼哈顿距离——两点在南北方向上 的距离加上在东西方上的距离， 即D（I，J）=|XI-XJ|+|YI-YJ|。 对于一个具有正南正北、正东正 西方向规则布局的城镇街道，从 一点到达另一点的距离正是在南 北方向上旅行的距离加上在东西 方向上旅行的距离因此曼哈顿距 离又称为出租车距离。
聚类分析的统计量
数据
从几何学角度看，上面表中的每一行或每一列 都表示了空间中的一个点或一个向量。
1、描述两个样本之间的相似程度: 距离
令 Xi =(x i 1 … x i t … x i k )是第 i 个样本观察 值， Xj =(x j 1 … x j t … x j k )是第 j 个样本观 察值，那么，样本 Xi 和 Xj 之间的欧氏距离是：
• 1967年由学者J. B. MacQueen 所提出，也是最 早的组群化计算技术。
The K-Means Clustering Method
• Example
第8章聚类分析
第8 章聚类分析在自然与社会科学研究中,存在着大量分类研究的问题，如病虫害种群消长演替规律的研究中，需要从生态系统出发，构造其数量、时间和空间关系的分类模式，以此来研究病虫害的发生规律。
聚类分析就是其分类研究的方法之一。
聚类分析是根据事物本身的特性研究个体分类的方法。
聚类分析的原则是同一类中的个体有较大的相似性，不同类中的个体差异很大。
根据分类对象的不同可分为样品聚类和变量聚类。
1)样品聚类样品聚类在统计学中又称为 Q 型聚类。
用 SPSS 的术语来说就是对事件(Cases)进行聚类，或是说对观测量进行聚类。
是根据被观测的对象的各种特征，即反映被观测对象的特征的各变量值进行分类。
2)变量聚类变量聚类在统计学又称为 R 型聚类。
反映同一事物特点的变量有很多，我们往往根据所研究的问题选择部分变量对事物的某一方面进行研究。
由于人类对客观事物的认识是有限的，往往难以找出彼此独立的有代表性的变量，而影响对问题的进一步认识和研究。
例如在回归分析中，由于自变量的共线性导致偏回归系数不能真正反映自变量对因变量的影响等。
因此往往先要进行变量聚类，找出彼此独立且有代表性的自变量，而又不丢失大部分信息。
8.1 快速聚类过程（K-Means Cluster ）调用此过程可完成由用户指定类别数的大样本资料的逐步聚类分析。
所谓逐步聚类分析就是先把被聚对象进行初始分类，然后逐步调整，得到最终分类。
[例子8-1]根据1962 年至1988 年积累的三化螟有关资料进行聚类分析，研究三化螟种群消长规律。
数据见表8-1，其中发生期是指卵盛孵高峰期（2 代以5 月31 日和3 代7 月20 日为零计算天数），F2-F3 为2 代至3 代的增殖系数，F3-F4 为3 代至4 代的增殖系数。
对幼虫发生量和发生期数据进行快速聚类，分析各年的发生程度。
1098.1.1 操作方法1）数据准备在数据管理窗口，定义变量名：年份、幼虫 2、幼虫 3、发生期 2、发生期 3、增殖23、增殖34，分别代表年份、第2 代幼虫发生量、第3 代幼虫发生量、第2 代发生期、第3 代发生期、F2-F3 增殖系数、F3-F4 增殖系数。
数据挖掘中的聚类分析技术
数据挖掘中的聚类分析技术数据挖掘是指通过从大量数据中发现模式、关联和趋势等有价值的信息的过程。
而聚类分析则是数据挖掘中一种常用的技术，它能够将相似的数据对象归为一类，从而帮助我们理解数据集的结构和特征。
本文将介绍聚类分析的基本概念、常见算法和应用领域。
一、聚类分析的基本概念聚类分析是一种无监督学习的方法，它不需要依赖预先定义的标签或类别信息。
聚类分析的目标是将数据对象划分为若干个组，使得组内的数据对象相似度高，而组间的相似度较低。
聚类分析的结果可以帮助我们发现数据集中的潜在结构、发现异常值以及进行数据预处理。
在聚类分析中，我们需要选择合适的相似度度量方法和聚类算法。
常用的相似度度量方法有欧氏距离、曼哈顿距离和余弦相似度等。
而常见的聚类算法包括K均值算法、层次聚类算法和密度聚类算法等。
二、常见的聚类分析算法1. K均值算法K均值算法是一种迭代的聚类算法，它将数据对象划分为K个簇，其中K是用户指定的参数。
算法的核心思想是通过最小化簇内数据对象与簇中心的距离来确定簇的划分。
具体而言，算法首先随机选择K个初始簇中心，然后将每个数据对象分配到与其距离最近的簇中心所在的簇，接着更新簇中心为簇内数据对象的均值，重复以上步骤直到簇中心不再变化或达到最大迭代次数。
2. 层次聚类算法层次聚类算法是一种基于距离的聚类算法，它通过计算数据对象之间的相似度或距离来构建一个层次结构的聚类结果。
算法的基本思想是从每个数据对象开始，逐步合并相似度最高的簇，直到所有数据对象都被合并为一个大簇或达到预设的簇的个数。
3. 密度聚类算法密度聚类算法是一种基于密度的聚类算法，它将数据对象划分为高密度区域和低密度区域。
算法的核心思想是通过计算每个数据对象的邻域内的数据对象个数来确定数据对象的核心点、边界点和噪声点。
常用的密度聚类算法有DBSCAN算法和OPTICS算法等。
三、聚类分析的应用领域聚类分析在各个领域都有广泛的应用。
在市场营销中，聚类分析可以帮助企业发现潜在的消费者群体，从而制定个性化的营销策略。
聚类分析的基本概念与方法
聚类分析的基本概念与方法聚类分析（Cluster Analysis）是一种将数据分组或分类的统计学方法，通过将相似的对象归为同一组，使得组内的对象之间更加相似，而不同组之间的对象则差异较大。
它是数据挖掘和机器学习领域中常用的技术之一，被广泛应用于市场分析、生物信息学、图像处理等领域。
一、聚类分析的基本概念聚类分析基于相似性的概念，即认为具有相似特征的对象更有可能属于同一类别。
在聚类分析中，每个对象都被视为一个数据点，而聚类则是将这些数据点分组。
基本概念包括以下几点：1. 数据点：数据集中的每个样本或对象都被看作是一个数据点，它具有多个特征或属性。
2. 相似性度量：聚类分析的关键是如何计算数据点之间的相似性或距离。
常用的相似性度量包括欧氏距离、曼哈顿距离、闵可夫斯基距离等。
3. 簇/类别：将相似的数据点归为一组，这个组被称为簇或类别。
簇内的数据点相似度较高，而不同簇之间的数据点相似度较低。
4. 聚类算法：聚类分析依赖于具体的算法来实现数据点的分组。
常见的聚类算法有K均值聚类、层次聚类、密度聚类等。
二、聚类分析的方法1. K均值聚类（K-means Clustering）：K均值聚类是一种迭代的聚类方法，它将数据点分成K个簇，每个簇代表一个样本集。
算法的基本思想是通过最小化簇内数据点与簇中心之间的平方误差来确定最优的簇中心位置。
2. 层次聚类（Hierarchical Clustering）：层次聚类是一种基于树状结构的聚类算法，它根据数据点之间的相似性逐步合并或分割簇。
层次聚类分为凝聚型和分裂型两种方法，其中凝聚型方法从单个数据点开始，逐步合并最相似的簇；分裂型方法从所有数据点开始，逐步分割最不相似的簇。
3. 密度聚类（Density-Based Clustering）：密度聚类基于密度可达的概念，将具有足够高密度的数据点归为一簇。
核心思想是在数据空间中通过密度连通性来确定簇的边界，相对于K均值聚类和层次聚类，密度聚类能够有效处理不规则形状和噪声数据。
第八章-聚类分析
48
非恒定的相似度
➢ 如果一个二值变量的两个取值的重要性不同等重要，则该
二元变量就是不对称的。
▪ 如一个疾病disease的测试结果positive或negative，显然这两 个测试结果的重要性是不一样的：
➢ 通常将比较重要的输出结果，编码为1；而将另一结果编码 为0.
➢ 基于这样的二元变量的相似度被称为非恒定的相似度.
7
7.1 什么是聚类分析
聚类(Clustering)：
根据“物以类聚”的道理，对样品和指标进行分类的一种 多元统计分析方法； 聚类分析中“类”的特征：
➢ 聚类所说的类不是事先给定的，而是根据数据的相 似性和距离来划分；
➢ 聚类的数目和结构都没有事先假定。
9
聚类准则对聚类结果的影响
羊,狗,猫, 鲨鱼
蜥蜴,蛇, 麻雀，海鸥, 金鱼,青蛙
金鱼, 鲨鱼
羊,狗,猫,蜥蜴, 蛇,麻雀，海鸥, 青蛙
(a)繁衍后代的方式
羊,狗,猫,
金鱼,
蜥蜴,蛇,麻雀， 鲨鱼
海鸥,
青蛙
(c) 生存环境
(b) 肺的存在
蜥蜴,蛇,麻 雀，海鸥, 青蛙
金鱼
羊,狗, 猫,
鲨鱼
(d)繁衍后代的方式和是否存在肺
距离测度对聚类结果的影响
年龄 收入 家庭人口数
甲
30
3000
1
乙
40
3200
3
d ( 3 4 0 )2 0 ( 30 30 ) 2 2 0 ( 1 0 3 )2 0
示例：
另外，明氏距离的数值与指标的量纲有关。如，二维样本 （身高、体重），有三个样本：
a(180,50); b(190,50); c(180,60) 则a与b之间的明氏距离（欧氏距离、切比雪夫距离）等 于a与c之间的距离 ❖但问题是，身高的10cm真的等价于体重的10kg吗？ ❖因此，明氏距离无法消除量纲的影响，在衡量这类样本 的相似度时容易出现问题。
非恒定的相似度
➢ 如果一个二值变量的两个取值的重要性不同等重要，则该
二元变量就是不对称的。
▪ 如一个疾病disease的测试结果positive或negative，显然这两 个测试结果的重要性是不一样的：
➢ 通常将比较重要的输出结果，编码为1；而将另一结果编码 为0.
➢ 基于这样的二元变量的相似度被称为非恒定的相似度.
7
7.1 什么是聚类分析
聚类(Clustering)：
根据“物以类聚”的道理，对样品和指标进行分类的一种 多元统计分析方法； 聚类分析中“类”的特征：
➢ 聚类所说的类不是事先给定的，而是根据数据的相 似性和距离来划分；
➢ 聚类的数目和结构都没有事先假定。
9
聚类准则对聚类结果的影响
羊,狗,猫, 鲨鱼
蜥蜴,蛇, 麻雀，海鸥, 金鱼,青蛙
金鱼, 鲨鱼
羊,狗,猫,蜥蜴, 蛇,麻雀，海鸥, 青蛙
(a)繁衍后代的方式
羊,狗,猫,
金鱼,
蜥蜴,蛇,麻雀， 鲨鱼
海鸥,
青蛙
(c) 生存环境
(b) 肺的存在
蜥蜴,蛇,麻 雀，海鸥, 青蛙
金鱼
羊,狗, 猫,
鲨鱼
(d)繁衍后代的方式和是否存在肺
距离测度对聚类结果的影响
年龄 收入 家庭人口数
甲
30
3000
1
乙
40
3200
3
d ( 3 4 0 )2 0 ( 30 30 ) 2 2 0 ( 1 0 3 )2 0
示例：
另外，明氏距离的数值与指标的量纲有关。如，二维样本 （身高、体重），有三个样本：
a(180,50); b(190,50); c(180,60) 则a与b之间的明氏距离（欧氏距离、切比雪夫距离）等 于a与c之间的距离 ❖但问题是，身高的10cm真的等价于体重的10kg吗？ ❖因此，明氏距离无法消除量纲的影响，在衡量这类样本 的相似度时容易出现问题。
数据挖掘算法_聚类数据挖掘
10 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10
基于质心的 k－means聚类算法
坐标表示 5 个点｛ X1,X2,X3,X4,X5｝作为一个聚类分析的二维
样 本 ： X1＝（0,2），X2＝（0,0），X3＝（1.5,0），X4＝ （5,0），X5＝（5,2）。假设要求的簇的数量k=2。
聚类分析的应用实独立变量 数目增加时， 发现簇的难 度开始增加
美陆军委托他人研究如何重新设计女兵服装，目 的在于减少不同尺码制服的库存数，但必须保证 每个士兵都有合体的制服。 选取了3000名女性，每人有100多个度量尺寸。
常见的聚类方法--划分聚类方法
典型的应用
作为一个独立的分析工具，用于了解数据的分布； 作为其它算法的一个数据预处理步骤；
应用聚类分析的例子
市场销售: 帮助市场人员发现客户中的不同群体， 然后用这些知识来开展一个目标明确的市场计划； 土地使用: 在一个陆地观察数据库中标识那些土地 使用相似的地区；
保险: 对购买了汽车保险的客户，标识那些有较高 平均赔偿成本的客户；
第1步：由样本的随机分布形成两个簇： C ＝｛X1,X2,X4｝和C2＝｛X3,X5｝。 这两个簇的质心M1和M2是：
1
1 2
M ＝｛(0+0+5)/3,(2+0+0)/3｝＝｛1.66，0.66｝；
M ＝｛（1.5+5）/2，（0+2）/2｝＝｛3.25，1.00｝；
基于质心的 k－means聚类算法
﹒．· ．
﹒．┇ . .· · . . · · . · ﹒．﹒． ﹒．﹒．﹒．· ﹒． ﹒． ﹒． 类别3
数据挖掘--聚类方法
数据挖掘--聚类方法(1)聚类就是将数据对象分组成多个类或者簇，划分的原则是在同一个粗中的对象之间具有较高的相似度，而不同簇中的对象差别较大。
属于一种无指导的学习方法。
好的聚类算法应该满足以下几个方面：（1）可伸缩型：无论对小数据量还是大数据量应该都是有效的。
（2）具有处理不同类型属性的能力。
（3）能够发现任意形状的聚类。
（4）输入参数对领域知识的弱依赖性（5）对于输入记录顺序不敏感（6）能够处理很多维度的数据，而不止是对3维左右的数据有效（7）处理噪声数据的能力（8）基于约束的距离：既能找到满足特定的约束，又具有良好聚类特性的数据分组（9）挖掘出来的信息是可理解的和可用的。
聚类分析主要在以下几个方面应用：（1）可以作为其他算法的预处理步骤（2）可以作为一个独立的工具来获得数据的分布情况（3）可以完成孤立点挖掘，用来预示欺诈行为的存在。
基本概念聚类分析的输入可以用一组有序对（X,s）或(X,d)表示，这里X表示一组样本，s和d分别是度量样本间相似度或相异度(距离)的标准。
聚类系统的输出是一个分区C={C1,C2,…,Ck}，其中Ci是X的子集，成为类。
类的特征可以用如下几种方式表示： 通过类的中心或类的边界点表示一个类。
使用聚类树中的结点图形化地表示一个类。
使用样本属性的逻辑表达式表示类。
聚类分析的方法：聚类分析有很多大量的、经典的算法，比如k-平均、k-中心点、PAM、CLARANS, BIRTH,CURE,OPTICS,DBSCAN,STING,CLIQUE,WAVECLUSTER等。
度量标准：一个聚类分析过程的质量取决于对度量标准的选择，因此必须仔细选择度量标准。
（1）距离函数明可夫斯基距离：x, y 是相应的特征，n是特征的维数。
则明可夫斯基距离d(x,y)表示如下，r=2为欧式距离。
二次型距离：余弦距离二元特征样本的距离假定x和y分别是n维特征，xi和yi分别表示每维特征，且xi和yi的取值为二元类型数值{0，1}。
数据挖掘中的聚类分析
5
优秀的聚类算法标准： 一个能产生高质量聚类的算法必须满足下面 两个条件: (1) 类内(intra-class)数据或对象的相似性最 强； (2) 类间(inter-class)数据或对象的相似性最 弱。 聚类质量的高低通常取决于聚类算法所使 用的相似性测量的方法和实现方式，同时 也取决于该算法能否发现部分或全部隐藏 的模式。
22
算法：k-中心点。 输入：结果簇的数目k，包含n个对象的数据库 输出：k个簇，使得所有对象与其最近中心点的 相异度总和最小。 方法：1）随机选取k个对象作为初始的中心点 Oj, j=1,2,…,k； 2）repeat 3)指派每个剩余的对象给离它最近的中心点所代表的簇； 4）随机选择一个非中心点对象Orandom 5）计算Orandom代替Oj的总代价S 6）if S<0,then Orandom替换Oj，形成新的k中心点集合； 7）until 不发生变化。
区间标度变量是一个粗略线性标度的连续度量。 典型的例子则包括重量和高度，经度和纬度坐标， 以及大气温度等。为了将数据或对象集合划分成 不同类别，必须定义差异性或相似性的测度来度 量同一类别之间数据的相似性和不属于同一类别 数据的差异性。同时要考虑到数据的多个属性使 用的是不同的度量单位，这些将直接影响到聚类 分析的结果，所以在计算数据的相似性之前先要 进行数据的标准化。 对于一个给定的有n个对象的m维(属性)数据集， 主要有两种标准化方法：
9
§3聚类分析中的数据类型 聚类分析中的数据类型
聚类分析起源于统计学，传统的分析方法 大多是在数值类型数据的基础上研究的。 然而数据挖掘的对象复杂多样，要求聚类 分析的方法不仅能够对属性为数值类型的 数据进行，而且要适应数据类型的变化。 一般而言，在数据挖掘中，对象属性经常 以区间标度变量度量
优秀的聚类算法标准： 一个能产生高质量聚类的算法必须满足下面 两个条件: (1) 类内(intra-class)数据或对象的相似性最 强； (2) 类间(inter-class)数据或对象的相似性最 弱。 聚类质量的高低通常取决于聚类算法所使 用的相似性测量的方法和实现方式，同时 也取决于该算法能否发现部分或全部隐藏 的模式。
22
算法：k-中心点。 输入：结果簇的数目k，包含n个对象的数据库 输出：k个簇，使得所有对象与其最近中心点的 相异度总和最小。 方法：1）随机选取k个对象作为初始的中心点 Oj, j=1,2,…,k； 2）repeat 3)指派每个剩余的对象给离它最近的中心点所代表的簇； 4）随机选择一个非中心点对象Orandom 5）计算Orandom代替Oj的总代价S 6）if S<0,then Orandom替换Oj，形成新的k中心点集合； 7）until 不发生变化。
区间标度变量是一个粗略线性标度的连续度量。 典型的例子则包括重量和高度，经度和纬度坐标， 以及大气温度等。为了将数据或对象集合划分成 不同类别，必须定义差异性或相似性的测度来度 量同一类别之间数据的相似性和不属于同一类别 数据的差异性。同时要考虑到数据的多个属性使 用的是不同的度量单位，这些将直接影响到聚类 分析的结果，所以在计算数据的相似性之前先要 进行数据的标准化。 对于一个给定的有n个对象的m维(属性)数据集， 主要有两种标准化方法：
9
§3聚类分析中的数据类型 聚类分析中的数据类型
聚类分析起源于统计学，传统的分析方法 大多是在数值类型数据的基础上研究的。 然而数据挖掘的对象复杂多样，要求聚类 分析的方法不仅能够对属性为数值类型的 数据进行，而且要适应数据类型的变化。 一般而言，在数据挖掘中，对象属性经常 以区间标度变量度量
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1 0.5
0
Iteration 4
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
-2 -1.5 -1 -0.5
00.51Fra bibliotek1.5
2
x
Iteration 5
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
© 李春权 数据挖掘
哈尔滨医科大学
Non-traditional Dendrogram
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
聚类的类型：层次的与划分的
How many clusters?
Two Clusters
Four Clusters
Six Clusters
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
层次聚类（Hierarchical Clustering）
嵌套簇的集族，组织成一棵树。
p1 p2
p3 p4
Traditional Hierarchical Clustering
p1 p2 p3 p4
Traditional Dendrogram
p1 p2
p3 p4
p1 p2 p3 p4
Non-traditional Hierarchical Clustering
‹#›
聚类的类型：互斥的、重叠的、模糊的
互斥的（Exclusive）
– 每个对象都指派到单个簇.
重叠的（overlapping）或非互斥的（ non-exclusive）
– 聚类用来反映一个对象.同时属于多个组（类）这一 事实。
– 例如：在大学里，一个人可能既是学生，又是雇员
模糊聚类（Fuzzy clustering ）
聚类分析：基本概念和算法
第8章 聚类分析：基本概念和算法
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
目录
概述 K均值聚类（重点） 层次聚类（重点） DBSCAN（重点）
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
什么是聚类分析?
聚类分析将数据划分成有意义或有用的组（簇） 。
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
算法分解演示
y
Iteration 1
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
y
Iteration 2
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
y
Iteration 3
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
y
选择初始的质心
随机选择
从层次聚类中提取K个簇，并用这些簇 的质心作为初始质心
随机选择第一个点，或取所有点的质 心作为第一个点。然后，对于每个后继 初始质心，选择离已经选取过的初始质 心最远的点
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
优点与缺点
优点： 算法简单 适用于球形簇 二分k均值等变种算法运行良好，不受初始化问题 的影响。 缺点： 不能处理非球形簇、不同尺寸和不同密度的簇 对离群点、噪声敏感
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
K均值应用
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
Iteration 4
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
y
Iteration 5
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
y
Iteration 6
gene
带有病人生存期的样本
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
目录
概述 K均值聚类（重点） 层次聚类（重点） DBSCAN（重点）
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
层次聚类算法（重点）
计算邻近度矩阵 Repeat
合并最近的两个簇 更新邻近性矩阵，以反映新的簇与 原来的簇之间的邻近行 Until 仅剩下一个簇
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
层次聚类
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
各种相似度和相异度测量方法（重点）
简单属性之间的相似度和相异度 数据对象之间的相异度 – 欧氏距离. – 明可夫斯基距离. – 马氏距离 数据对象之间的相似度 – 简单匹配系数、雅卡尔系数. – 余弦相似度. – 相关性
生物信息科学与技术学院 2011
‹#›
聚类的复杂性
How many clusters?
Six Clusters
Two Clusters
Four Clusters
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
不同的聚类类型
划分聚类（Partitional Clustering） 层次聚类（Hierarchical Clustering） 互斥聚类（exclusive clustering） 非互斥（重叠）聚类（non-exclusive） 模糊聚类（fuzzy clustering） 完全聚类（complete clustering） 部分聚类（partial clustering）
选择了较差的初始质心的结果分解演示
y y
y y
y
Iteration 1
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
Iteration 2
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
Iteration 3
3 2.5
2 1.5
– 每个对象以一个0（绝对不属于）和1（绝对属于） 之间的隶属权值属于每个簇。换言之，簇被视为模糊 集。
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
聚类的类型：部分、完全
部分的（Partial） – 部分聚类中数据集某些对象可能不属于明确
定义的组。如：一些对象可能是离群点、噪 声。 完全的（complete） – 完全聚类将每个对象指派到一个簇。
该方法实现简单，但是点的密度依赖于指定的 半径。例如，如果半径足够大，则所有点的密 度都等于数据集中的点数m。类似地，如果半 径太小，则所有点的密度都是1。
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
生物信息科学与技术学院 2011
‹#›
簇类型:基于图的
如果数据用图表示，其中节点是对象，而边代 表对象之间的联系。 簇可以定义为连通分支（connected component）：互相连通但不与组外对象连通 的对象组。
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
簇类型: 基于密度的（Density-Based）
‹#›
二分k均值算法
初始化簇表，使之包含由所有的点组成的簇。
Repeat 从簇表中取出一个簇。 for i=1 to 实验次数 do 使用基本k均值，二分选定的簇。 end for 从二分实验中选择具有最小总sse的两个簇。 将这两个簇添加到簇表中。
Until 簇表中包含k个簇。
© 李春权 数据挖掘
.
2 Overlapping Circles
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
目录
概述 K均值聚类（重点） 层次聚类（重点） DBSCAN（重点）
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
基本K均值算法（重点）
1.选择k个点作为初始的质心 2.repeat 3.将每个点指派到最近的质心，形 成k个簇 4. 重新计算每个簇的质心 5.until 质心不发生变化
0
Iteration 4
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
-2 -1.5 -1 -0.5
00.51Fra bibliotek1.5
2
x
Iteration 5
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
© 李春权 数据挖掘
哈尔滨医科大学
Non-traditional Dendrogram
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
聚类的类型：层次的与划分的
How many clusters?
Two Clusters
Four Clusters
Six Clusters
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
层次聚类（Hierarchical Clustering）
嵌套簇的集族，组织成一棵树。
p1 p2
p3 p4
Traditional Hierarchical Clustering
p1 p2 p3 p4
Traditional Dendrogram
p1 p2
p3 p4
p1 p2 p3 p4
Non-traditional Hierarchical Clustering
‹#›
聚类的类型：互斥的、重叠的、模糊的
互斥的（Exclusive）
– 每个对象都指派到单个簇.
重叠的（overlapping）或非互斥的（ non-exclusive）
– 聚类用来反映一个对象.同时属于多个组（类）这一 事实。
– 例如：在大学里，一个人可能既是学生，又是雇员
模糊聚类（Fuzzy clustering ）
聚类分析：基本概念和算法
第8章 聚类分析：基本概念和算法
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
目录
概述 K均值聚类（重点） 层次聚类（重点） DBSCAN（重点）
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
什么是聚类分析?
聚类分析将数据划分成有意义或有用的组（簇） 。
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
算法分解演示
y
Iteration 1
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
y
Iteration 2
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
y
Iteration 3
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
y
选择初始的质心
随机选择
从层次聚类中提取K个簇，并用这些簇 的质心作为初始质心
随机选择第一个点，或取所有点的质 心作为第一个点。然后，对于每个后继 初始质心，选择离已经选取过的初始质 心最远的点
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
优点与缺点
优点： 算法简单 适用于球形簇 二分k均值等变种算法运行良好，不受初始化问题 的影响。 缺点： 不能处理非球形簇、不同尺寸和不同密度的簇 对离群点、噪声敏感
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
K均值应用
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
Iteration 4
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
y
Iteration 5
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
y
Iteration 6
gene
带有病人生存期的样本
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
目录
概述 K均值聚类（重点） 层次聚类（重点） DBSCAN（重点）
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
层次聚类算法（重点）
计算邻近度矩阵 Repeat
合并最近的两个簇 更新邻近性矩阵，以反映新的簇与 原来的簇之间的邻近行 Until 仅剩下一个簇
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
层次聚类
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
各种相似度和相异度测量方法（重点）
简单属性之间的相似度和相异度 数据对象之间的相异度 – 欧氏距离. – 明可夫斯基距离. – 马氏距离 数据对象之间的相似度 – 简单匹配系数、雅卡尔系数. – 余弦相似度. – 相关性
生物信息科学与技术学院 2011
‹#›
聚类的复杂性
How many clusters?
Six Clusters
Two Clusters
Four Clusters
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
不同的聚类类型
划分聚类（Partitional Clustering） 层次聚类（Hierarchical Clustering） 互斥聚类（exclusive clustering） 非互斥（重叠）聚类（non-exclusive） 模糊聚类（fuzzy clustering） 完全聚类（complete clustering） 部分聚类（partial clustering）
选择了较差的初始质心的结果分解演示
y y
y y
y
Iteration 1
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
Iteration 2
3 2.5
2 1.5
1 0.5
0
-2 -1.5 -1 -0.5
0
0.5
1
1.5
2
x
Iteration 3
3 2.5
2 1.5
– 每个对象以一个0（绝对不属于）和1（绝对属于） 之间的隶属权值属于每个簇。换言之，簇被视为模糊 集。
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
聚类的类型：部分、完全
部分的（Partial） – 部分聚类中数据集某些对象可能不属于明确
定义的组。如：一些对象可能是离群点、噪 声。 完全的（complete） – 完全聚类将每个对象指派到一个簇。
该方法实现简单，但是点的密度依赖于指定的 半径。例如，如果半径足够大，则所有点的密 度都等于数据集中的点数m。类似地，如果半 径太小，则所有点的密度都是1。
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
生物信息科学与技术学院 2011
‹#›
簇类型:基于图的
如果数据用图表示，其中节点是对象，而边代 表对象之间的联系。 簇可以定义为连通分支（connected component）：互相连通但不与组外对象连通 的对象组。
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
簇类型: 基于密度的（Density-Based）
‹#›
二分k均值算法
初始化簇表，使之包含由所有的点组成的簇。
Repeat 从簇表中取出一个簇。 for i=1 to 实验次数 do 使用基本k均值，二分选定的簇。 end for 从二分实验中选择具有最小总sse的两个簇。 将这两个簇添加到簇表中。
Until 簇表中包含k个簇。
© 李春权 数据挖掘
.
2 Overlapping Circles
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
目录
概述 K均值聚类（重点） 层次聚类（重点） DBSCAN（重点）
© 李春权 数据挖掘
哈尔滨医科大学
生物信息科学与技术学院 2011
‹#›
基本K均值算法（重点）
1.选择k个点作为初始的质心 2.repeat 3.将每个点指派到最近的质心，形 成k个簇 4. 重新计算每个簇的质心 5.until 质心不发生变化