1、聚类分析算法聚类分析算法 学习汇报学习汇报第1页，共31页。聚类分析概述聚类分析概述宁夏大学宁夏大学数学与计算机学院数学与计算机学院 1、什么是聚类？、什么是聚类？聚类（聚类（clustering）是将物理或抽象对象的集合分组成）是将物理或抽象对象的集合分组成为为多个多个类或簇（类或簇（cluster）的过程，使得在同一个簇中的对象之间具有较高）的过程，使得在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。的相似度，而不同簇中的对象差别较大。2、与分类的不同、与分类的不同 它要划分的类是未知的。即聚类是一种无指导学习，它不依赖它要划分的类是未知的。即聚类是一种无指导学习，它不依
2、赖预先定义的类和带类标号的训练实例。预先定义的类和带类标号的训练实例。第2页，共31页。聚类分析的应用聚类分析的应用 聚类分析已经广泛的用在许多应用中，包括模式识别、数据分析、图像处理以及聚类分析已经广泛的用在许多应用中，包括模式识别、数据分析、图像处理以及市场研究。典型的应用：市场研究。典型的应用：（1）商业：帮助市场分析人员从客户基本库中发现不同的客户群，并且用不同的购买模）商业：帮助市场分析人员从客户基本库中发现不同的客户群，并且用不同的购买模式描述不同客户群的特征。式描述不同客户群的特征。（2）生物学：推导植物或动物的分类，活的对种群固有结构的认识。）生物学：推导植物或动物的分类，活的
3、对种群固有结构的认识。（3）WEB文档分类文档分类 （4）其他：地球观测数据库中相似地区的确定各类保险投保人的分组，一个城市中不同）其他：地球观测数据库中相似地区的确定各类保险投保人的分组，一个城市中不同类型、价值、地理位置房子的分组等。类型、价值、地理位置房子的分组等。（5）作为其他数据挖掘算法的预处理：即先进行聚类，然后再进行分类等其）作为其他数据挖掘算法的预处理：即先进行聚类，然后再进行分类等其他数据挖掘他数据挖掘宁夏大学宁夏大学数学与计算机学院数学与计算机学院第3页，共31页。聚类分析的要求聚类分析的要求宁夏大学宁夏大学数学与计算机学院数学与计算机学院可伸缩性可伸缩性处理不同类型属性的
4、能力处理不同类型属性的能力 发现任意形状的聚类发现任意形状的聚类 用于决定输入参数的领域知识最小化用于决定输入参数的领域知识最小化 处理噪声数据的能力处理噪声数据的能力 对于输入记录的顺序不敏感对于输入记录的顺序不敏感 高维性高维性基于约束的聚类基于约束的聚类 可解释性和可用性可解释性和可用性第4页，共31页。聚类分析中的数据类型聚类分析中的数据类型宁夏大学宁夏大学数学与计算机学院数学与计算机学院 聚类分析中数据类型用于度量对象间的相异度，常聚类分析中数据类型用于度量对象间的相异度，常用的数据类型用的数据类型:区间标度变量区间标度变量二元变量二元变量标称型、序数型和比例标度型变量标称型、序数型
5、和比例标度型变量混合类型变量混合类型变量第5页，共31页。区间标度变量区间标度变量 宁夏大学宁夏大学数学与计算机学院数学与计算机学院 1 1、区间标度变量是一个粗略线性标度的连续度量。典型的例区间标度变量是一个粗略线性标度的连续度量。典型的例子包括重量和高度，经度和纬度坐标，以及大气温度。子包括重量和高度，经度和纬度坐标，以及大气温度。2 2、选择不同的度量单位（如选择不同的度量单位（如“米米”与英尺、与英尺、“千克千克”与与“磅磅”等）等）将直接影响聚类分析的结果。将直接影响聚类分析的结果。3 3、为了避免聚类分析对度量单位的依赖性，数据需要进行标为了避免聚类分析对度量单位的依赖性，数据需要
6、进行标准化。准化。4 4、怎样将一个变量的数据标准化呢？为了实现度量值的标准化，、怎样将一个变量的数据标准化呢？为了实现度量值的标准化，一种方法是将原来的度量值转换为无单位的值。一种方法是将原来的度量值转换为无单位的值。第6页，共31页。度量值的标准化度量值的标准化|)|.|(|121fnffffffmxmxmxns.).211nffffxx(xn m宁夏大学宁夏大学数学与计算机学院数学与计算机学院 （1）计算平均的绝对偏差（）计算平均的绝对偏差（mean absolute deviation）:其中：其中：（2）计算标准化的度量值，或（）计算标准化的度量值，或（z-score）:ffifif
7、smx z第7页，共31页。对象间的相异度计算对象间的相异度计算欧几里德距离：欧几里德距离：曼哈坦距离：曼哈坦距离：明考斯基距离：明考斯基距离：)|.|(|),(2222211ppjxixjxixjxixjid宁夏大学宁夏大学数学与计算机学院数学与计算机学院jpipjijixxxxxxjid2211),(qqppqqjxixjxixjxixjid)|.|(|),(2211第8页，共31页。聚类分析中的数据类型聚类分析中的数据类型宁夏大学宁夏大学数学与计算机学院数学与计算机学院 聚类分析中数据类型用于度量对象间的相异度，常用的聚类分析中数据类型用于度量对象间的相异度，常用的数据类型数据类型:区间
8、标度变量区间标度变量二元变量二元变量标称型、序数型和比例标度型变量标称型、序数型和比例标度型变量混合类型变量混合类型变量第9页，共31页。二元变量二元变量宁夏大学宁夏大学数学与计算机学院数学与计算机学院 一个二元变量只有两个状态：一个二元变量只有两个状态：0或者或者1，0表示该变量为空，表示该变量为空，1表示该变表示该变量存在。量存在。如果假设所有的二元变量有相同的权重，则得到一个两行两列的可如果假设所有的二元变量有相同的权重，则得到一个两行两列的可能性表。在下面这个表中，能性表。在下面这个表中，a是对于对象是对于对象i和和j值都为值都为1的变量的数目，的变量的数目，b是对于是对于对象对象I值
9、为值为1而对象而对象j的值为的值为0的变量数目，的变量数目，s是对于对象是对于对象c值为值为0而在对于对象而在对于对象j值值为为1的变量数目，的变量数目，d是对于对象是对于对象i和和j的值都为的值都为0的变量的数目。变量的总数是的变量的数目。变量的总数是p，p=a+b+c+d。pdbcasumdcdcbabasum0101Object jObject i第10页，共31页。基于对称二元变量的相似度称为恒定的相似度，即当一些基于对称二元变量的相似度称为恒定的相似度，即当一些或者全部二元变量编码改变时，计算结果不会发生变化。或者全部二元变量编码改变时，计算结果不会发生变化。如果二元变量的两个状态的
10、输出不是同样重要，则该二如果二元变量的两个状态的输出不是同样重要，则该二元变量是不对称的。基于这样变量的相似度被称为非恒定元变量是不对称的。基于这样变量的相似度被称为非恒定的相似度。的相似度。二元变量相似度的计算二元变量相似度的计算dcbacb jid),(宁夏大学宁夏大学数学与计算机学院数学与计算机学院cbacb jid),(第11页，共31页。聚类分析中的数据类型聚类分析中的数据类型宁夏大学宁夏大学数学与计算机学院数学与计算机学院 聚类分析中数据类型用于度量对象间的相异度，常聚类分析中数据类型用于度量对象间的相异度，常用的数据类型用的数据类型:区间标度变量区间标度变量二元变量二元变量标称型
11、、序数型和比例标度型变量标称型、序数型和比例标度型变量混合类型变量混合类型变量第12页，共31页。1、标称型变量、标称型变量 标称变量（标称变量（nominalnominal）是二元变量的推广，它可以具有多）是二元变量的推广，它可以具有多于两个的状态值。例如，于两个的状态值。例如，map-colormap-color是一个标称变量，它可是一个标称变量，它可能有五个状态：红色，黄色，绿色，粉红色和蓝色。两个对能有五个状态：红色，黄色，绿色，粉红色和蓝色。两个对象和象和j j之间的相异度可以用两种方法来计算：之间的相异度可以用两种方法来计算：（1）简单匹配方法）简单匹配方法 M是匹配的数目，是匹配
12、的数目，P是全部变量的数目是全部变量的数目 （2）使用二元变量）使用二元变量 为每一个状态创建一个新的二元变量，可以用非对称的二元变为每一个状态创建一个新的二元变量，可以用非对称的二元变量来编码标称变量。量来编码标称变量。标称型变量标称型变量宁夏大学宁夏大学数学与计算机学院数学与计算机学院pmpjid),(第13页，共31页。一个离散的序数（一个离散的序数（ordinal）型变量类似于标称变量，除了）型变量类似于标称变量，除了序数型变量的个状态是以有意义的序列排序的。在计算序数型变量的个状态是以有意义的序列排序的。在计算对象的相异度时，序数型变量的处理与区间标度变量非常对象的相异度时，序数型变
13、量的处理与区间标度变量非常类似。类似。（1）将）将xif 用它对应的秩代替。用它对应的秩代替。（2）将每个变量的值域映射到）将每个变量的值域映射到0.0，1.0上，使得每个变量都上，使得每个变量都有相同的权重。这通过用有相同的权重。这通过用zif来替代来替代rif来实现。来实现。（3）用前面所述的区间标度变量的任一种距离计算方法来计算。）用前面所述的区间标度变量的任一种距离计算方法来计算。序数型变量序数型变量,.,1fifMr 宁夏大学宁夏大学数学与计算机学院数学与计算机学院11fififMrz第14页，共31页。用比例标度型变量描述对象之间相异度有以下三种方法：用比例标度型变量描述对象之间相
14、异度有以下三种方法：（1）采用与处理区间标度变量相同的方法。）采用与处理区间标度变量相同的方法。（2）对比例标度型变量进行对数变换，如：）对比例标度型变量进行对数变换，如：yif=log(xif)然后再对变换得到的值按区间标度的值处理。然后再对变换得到的值按区间标度的值处理。（3）将其作为连续的序数型数据，将其秩作为区间标度的值来）将其作为连续的序数型数据，将其秩作为区间标度的值来对待。对待。比例标度型变量比例标度型变量宁夏大学宁夏大学数学与计算机学院数学与计算机学院第15页，共31页。聚类分析中的数据类型聚类分析中的数据类型宁夏大学宁夏大学数学与计算机学院数学与计算机学院 聚类分析中数据类型
15、用于度量对象间的相异度，常聚类分析中数据类型用于度量对象间的相异度，常用的数据类型用的数据类型:区间标度变量区间标度变量二元变量二元变量标称型、序数型和比例标度型变量标称型、序数型和比例标度型变量混合类型变量混合类型变量第16页，共31页。在许多现实的数据库中，对象是被混合类型的变量描述的。一般来说，一个数据在许多现实的数据库中，对象是被混合类型的变量描述的。一般来说，一个数据库可能包含上面列出的全部六种变量类型。用以下的公式计算库可能包含上面列出的全部六种变量类型。用以下的公式计算i和和j的相异度：的相异度：其中，其中，p为对象中的变量个数为对象中的变量个数 （1）如果）如果xif或或xjf
16、缺失（即对象缺失（即对象i或对象或对象j没有变量没有变量f的值），或者的值），或者xif=xjf=0，且变，且变量量f是不对称的二元变量，则指示项是不对称的二元变量，则指示项ij(f)=0；否则；否则ij(f)=1。（2）f 是二元变量或标称变量是二元变量或标称变量:if xif=xjf dij(f)=0,else dij(f)=1 （3）f是区间标度变量：是区间标度变量：dij(f)=|xif-xjf|/maxhxhf-minhxhf （4）f 是序数型或比例标度型：是序数型或比例标度型：计算秩计算秩rif 计算计算zif并将其作为区间标度变量值对待并将其作为区间标度变量值对待混合类型变量混
17、合类型变量宁夏大学宁夏大学数学与计算机学院数学与计算机学院)(1)()(1),(fijpffijfijpfdjid第17页，共31页。基于划分的方法基于划分的方法基于层次的方法基于层次的方法基于密度的方法基于密度的方法基于网格的方法基于网格的方法基于模型的方法基于模型的方法 主要聚类分析方法主要聚类分析方法宁夏大学宁夏大学数学与计算机学院数学与计算机学院第18页，共31页。划分方法（划分方法（partitioning method）的基本思想是：给定一个）的基本思想是：给定一个n个对象或元个对象或元组的数据库，一个划分方法构建数据的组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚
18、簇，个划分，每个划分表示一个聚簇，并且并且kn。也就是说，它将数据划分成为。也就是说，它将数据划分成为k个组，同时满足如下要求：个组，同时满足如下要求：每个组至少包括一个对象；每个组至少包括一个对象；每个对象必须属于且只属于一个组。每个对象必须属于且只属于一个组。基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以基于划分的聚类会要求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较流行的启发式方式：下两个比较流行的启发式方式：（1）k-平均算法。在该算法当中，每个簇用该簇中对象的平均值来表示。平均算法。在该算法当中，每个簇用该簇中对象的平均值来表示。（2）k-中心点算
19、法。在该算法中每个簇用接近聚类中心的一个对象来中心点算法。在该算法中每个簇用接近聚类中心的一个对象来表示。表示。基于划分的方法基于划分的方法宁夏大学宁夏大学数学与计算机学院数学与计算机学院第19页，共31页。层次方法（层次方法（hierarchical methodhierarchical method）的基本思想是：对给定）的基本思想是：对给定数据对象集合进行层次的分解。根据层次的分解如何形成，数据对象集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的。层次的方法可以分为凝聚的和分裂的。（1）凝聚的方法：又称为自底向上的方法，一开始将每个对）凝聚的方法：又称为自底向
20、上的方法，一开始将每个对象作为单独的一个组，然后根据一些规则相继地合并相近象作为单独的一个组，然后根据一些规则相继地合并相近的对象或者组，将它们聚合成越来越大的类，直到所有的的对象或者组，将它们聚合成越来越大的类，直到所有的组合并为一个，或者达到一个预先设定的终止条件。组合并为一个，或者达到一个预先设定的终止条件。基于层次的方法基于层次的方法宁夏大学宁夏大学数学与计算机学院数学与计算机学院第20页，共31页。（2）分裂的方法：又称为自顶向下的方法，是一个与凝聚的方式）分裂的方法：又称为自顶向下的方法，是一个与凝聚的方式相反的过程。即开始时将所有的对象置于一个簇中。在迭代相反的过程。即开始时将所
21、有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件（例如：类的数在单独的一个簇中，或者达到一个终止条件（例如：类的数目到了预定值，最近的两个类之间的最小距离大于设定值目到了预定值，最近的两个类之间的最小距离大于设定值等）。等）。基于层次的方法基于层次的方法宁夏大学宁夏大学数学与计算机学院数学与计算机学院第21页，共31页。绝大多数划分方法基于对象之间的距离进行聚类。这样的绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了方法只
22、能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的聚类方法（困难。随之提出了基于密度的聚类方法（density-based density-based methodmethod）。）。基本思想是：只要临近区域的密度（对象或数据点的数目）基本思想是：只要临近区域的密度（对象或数据点的数目）超过某个值，就继续聚类。也就是说，对给定类中的每个超过某个值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目数据点，在一个给定范围的区域中必须至少包含某个数目点。这样的方法可以用来过滤点。这样的方法可以用来过滤“噪声噪声”孤立点数据，发现孤立点数据，
23、发现任意形状的簇。任意形状的簇。基于密度的方法基于密度的方法宁夏大学宁夏大学数学与计算机学院数学与计算机学院第22页，共31页。基于网格的方法（基于网格的方法（grid-based method）的基本思想是：对象空）的基本思想是：对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构上进行。这种方法的主要优点是它的处理速度较都在这个网格结构上进行。这种方法的主要优点是它的处理速度较快，其处理时间独立于数据对象的数目，只与量化空间中每一维单快，其处理时间独立于数据对象的数目，只与量化空间中每一维单元数目有关。元
24、数目有关。基于网格的方法基于网格的方法宁夏大学宁夏大学数学与计算机学院数学与计算机学院第23页，共31页。基本思想是：为每个簇假定了一个模型，寻找数据对给定模基本思想是：为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也是基于标准的统计数字空间分布的密度函数来定位聚类。它也是基于标准的统计数字自动决定聚类的数目，考虑自动决定聚类的数目，考虑“噪声噪声”数据或孤立点，从而产生数据或孤立点，从而产生健壮的聚类方法。健壮的聚类方法。基于模型的方法基于模型的方法宁夏大学宁
25、夏大学数学与计算机学院数学与计算机学院第24页，共31页。k-means算法，也被称为算法，也被称为k-平均或平均或k-均值，是一种得到最广泛使均值，是一种得到最广泛使用的聚类算法。用的聚类算法。它是将各个聚类子集内的所有数据样本的均值作为它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。的每个聚类内紧凑，类间独立。k-means算法算法宁夏大
26、学宁夏大学数学与计算机学院数学与计算机学院第25页，共31页。（1）选定某种距离作为数据样本间的相似性度量）选定某种距离作为数据样本间的相似性度量 例如欧式距离：例如欧式距离：（2）选择评价聚类性能的准则函数）选择评价聚类性能的准则函数 误差平方和准则函数为：误差平方和准则函数为：（3）相似度的计算根据一个簇中对象的平均值来进行。）相似度的计算根据一个簇中对象的平均值来进行。k-means算法三个要点算法三个要点dkjijkikxxdxx12)(),(宁夏大学宁夏大学数学与计算机学院数学与计算机学院21ikiip XEpm第26页，共31页。输入：簇的数目输入：簇的数目k和包含和包含n个对象的
27、数据库。个对象的数据库。输出：输出：k个簇，使平方误差准则最小。个簇，使平方误差准则最小。算法步骤：算法步骤：1.为每个聚类确定一个初始聚类中心，这样就有为每个聚类确定一个初始聚类中心，这样就有K 个初始聚类中心。个初始聚类中心。2.将样本集中的样本按照最小距离原则分配到最邻近聚类将样本集中的样本按照最小距离原则分配到最邻近聚类 3.使用每个聚类中的样本均值作为新的聚类中心。使用每个聚类中的样本均值作为新的聚类中心。4.重复步骤重复步骤2.3步直到聚类中心不再变化。步直到聚类中心不再变化。5.结束，得到结束，得到K个聚类个聚类 k-means算法流程算法流程宁夏大学宁夏大学数学与计算机学院数学
28、与计算机学院第27页，共31页。主要优点：主要优点：是解决聚类问题的一种经典算法，简单、快速。是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。因为对处理大数据集，该算法是相对可伸缩和高效率的。因为它的复杂度是它的复杂度是0(n k t),其中其中,n 是所有对象的数目是所有对象的数目,k 是簇是簇的数目的数目,t 是迭代的次数。通常是迭代的次数。通常k n 且且t n。当结果簇是密集的，而簇与簇之间区别明显时当结果簇是密集的，而簇与簇之间区别明显时,它的效果较好。它的效果较好。k-means算法性能分析算法性能分析宁夏大学宁夏大学数学与计算机学院数学与计
29、算机学院第28页，共31页。主要缺点主要缺点在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数在簇的平均值被定义的情况下才能使用，这对于处理符号属性的数据不适用。据不适用。必须事先给出必须事先给出k（要生成的簇的数目），而且对初值敏感，对于（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。不同的初始值，可能会导致不同结果。它对于它对于“躁声躁声”和孤立点数据是敏感的，少量的该类数据能和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。够对平均值产生极大的影响。k-means算法性能分析算法性能分析宁夏大学宁夏大学数学与计算机学院数学与计算机学院第2
30、9页，共31页。k-means算法对某类簇中所有的样本点维度求平均值，即获得算法对某类簇中所有的样本点维度求平均值，即获得该类簇质点的维度。当聚类的样本点中有该类簇质点的维度。当聚类的样本点中有“噪声噪声”（离群点）（离群点）时，在计算类簇质点的过程中会受到噪声异常维度的干扰，时，在计算类簇质点的过程中会受到噪声异常维度的干扰，造成所得质点和实际质点位置偏差过大，从而使类簇发生造成所得质点和实际质点位置偏差过大，从而使类簇发生“畸变畸变”。为了解决该问题，为了解决该问题，K中心点算法（中心点算法（K-medoids）提出了新的质）提出了新的质点选取方式，而不是简单像点选取方式，而不是简单像k-
31、means算法采用均值计算法。算法采用均值计算法。在在K中心点算法中，每次迭代后的质点都是从聚类的样本点中心点算法中，每次迭代后的质点都是从聚类的样本点中选取，而选取的标准就是当该样本点成为新的质点后能提中选取，而选取的标准就是当该样本点成为新的质点后能提高类簇的聚类质量，使得类簇更紧凑。该算法使用绝对误差高类簇的聚类质量，使得类簇更紧凑。该算法使用绝对误差标准来定义一个类簇的紧凑程度。标准来定义一个类簇的紧凑程度。K-中心点算法中心点算法宁夏大学宁夏大学数学与计算机学院数学与计算机学院21ikiip XEpm第30页，共31页。输入：结果簇的数目输入：结果簇的数目K，包含，包含N个对象的数据
32、库。个对象的数据库。输出：输出：K个簇，使得所有对象与其最近中心点的相异度总和最小。个簇，使得所有对象与其最近中心点的相异度总和最小。方法：方法：随机选择随机选择K个对象作为初始的中心点。个对象作为初始的中心点。REPEAT指派每个剩余的对象给离它最近的中心点所代表的簇。指派每个剩余的对象给离它最近的中心点所代表的簇。随机地选择一个非中心点对象随机地选择一个非中心点对象Orandom；计算用计算用Orandom代替代替Oj的总代价的总代价S；if S0,then Orandom代替代替Oj,形成新的形成新的K个中心点的集合；个中心点的集合；until不发生变化；不发生变化；K-中心点算法中心点算法宁夏大学宁夏大学数学与计算机学院数学与计算机学院第31页，共31页。
