集成聚类的算法

❶ 聚类算法有哪几种

聚类分析计算方法主要有： 层次的方法(hierarchical method)、划分方法(partitioning method)、基于密度的方法(density-based method)、基于网格的方法(grid-based method)、基于模型的方法(model-based method)等。其中，前两种算法是利用统计学定义的距离进行度量。
k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象，则根据它们与这些聚类中心的相似度(距离)，分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然 后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
其流程如下：
(1)从 n个数据对象任意选择 k 个对象作为初始聚类中心;
(2)根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;
(3)重新计算每个(有变化)聚类的均值(中心对象);
(4)循环(2)、(3)直到每个聚类不再发生变化为止(标准测量函数收敛)。
优点： 本算法确定的K个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果较好。对于处理大数据集，这个算法是相对可伸缩和高效的，计算的复杂度为 O(NKt)，其中N是数据对象的数目，t是迭代的次数。
缺点：
1. K 是事先给定的，但非常难以选定;
2. 初始聚类中心的选择对聚类结果有较大的影响。

❷ 聚类算法的具体方法

k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
k-means 算法的工作过程说明如下：
首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；
然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。
一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 K-MEANS有其缺点：产生类的大小相差不会很大，对于脏数据很敏感。
改进的算法：k—medoids 方法。这儿选取一个对象叫做mediod来代替上面的中心的作用，这样的一个medoid就标识了这个类。K-medoids和K-means不一样的地方在于中心点的选取，在K-means中，我们将中心点取为当前cluster中所有数据点的平均值，在 K-medoids算法中，我们将从当前cluster 中选取这样一个点——它到其他所有（当前cluster中的）点的距离之和最小——作为中心点。
步骤：
1，任意选取K个对象作为medoids（O1,O2,…Oi…Ok）。
以下是循环的：
2，将余下的对象分到各个类中去（根据与medoid最相近的原则）；
3，对于每个类（Oi）中，顺序选取一个Or，计算用Or代替Oi后的消耗—E（Or）。选择E最小的那个Or来代替Oi。这样K个medoids就改变了，下面就再转到2。
4，这样循环直到K个medoids固定下来。
这种算法对于脏数据和异常数据不敏感，但计算量显然要比K均值要大，一般只适合小数据量。 上面提到K-medoids算法不适合于大数据量的计算。Clara算法，这是一种基于采样的方法，它能够处理大量的数据。
Clara算法的思想就是用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用K-medoids算法得到最佳的medoids。Clara算法从实际数据中抽取多个采样，在每个采样上都用K-medoids算法得到相应的（O1, O2 … Oi … Ok），然后在这当中选取E最小的一个作为最终的结果。 Clara算法的效率取决于采样的大小，一般不太可能得到最佳的结果。
在Clara算法的基础上，又提出了Clarans的算法，与Clara算法不同的是：在Clara算法寻找最佳的medoids的过程中，采样都是不变的。而Clarans算法在每一次循环的过程中所采用的采样都是不一样的。
与上面所讲的寻找最佳medoids的过程不同的是，必须人为地来限定循环的次数。

❸ 聚类算法有哪些

聚类方法分为以下几类：
分割方法：K-means
分层次方法：ROCK 、 Chemeleon
基于密度的方法：DBSCAN
基于网格的方法：STING 、 WaveCluster
等等

❹ 16种常用的数据分析方法-聚类分析

聚类（Clustering）就是一种寻找数据之间内在结构的技术。聚类把全体数据实例组织成一些相似组，而这些相似组被称作簇。处于相同簇中的数据实例彼此相同，处于不同簇中的实例彼此不同。

聚类分析定义

聚类分析是根据在数据中发现的描述对象及其关系的信息，将数据对象分组。目的是，组内的对象相互之间是相似的（相关的），而不同组中的对象是不同的（不相关的）。组内相似性越大，组间差距越大，说明聚类效果越好。

聚类效果的好坏依赖于两个因素：1.衡量距离的方法（distance measurement） 2.聚类算法（algorithm）

聚类分析常见算法

K-均值聚类也称为快速聚类法，在最小化误差函数的基础上将数据划分为预定的类数K。该算法原理简单并便于处理大量数据。

K-均值算法对孤立点的敏感性，K-中心点算法不采用簇中对象的平均值作为簇中心，而选用簇中离平均值最近的对象作为簇中心。

也称为层次聚类，分类的单位由高到低呈树形结构，且所处的位置越低，其所包含的对象就越少，但这些对象间的共同特征越多。该聚类方法只适合在小数据量的时候使用，数据量大的时候速度会非常慢。

案例

有20种12盎司啤酒成分和价格的数据，变量包括啤酒名称、热量、钠含量、酒精含量、价格。

问题一：选择那些变量进行聚类？——采用“R 型聚类”

现在我们有4个变量用来对啤酒分类，是否有必要将4个变量都纳入作为分类变量呢？热量、钠含量、酒精含量这3个指标是要通过化验员的辛苦努力来测定，而且还有花费不少成本。

所以，有必要对4个变量进行降维处理，这里采用spss R型聚类（变量聚类），对4个变量进行降维处理。输出“相似性矩阵”有助于我们理解降维的过程。

4个分类变量各自不同，这一次我们先用相似性来测度，度量标准选用pearson系数，聚类方法选最远元素，此时，涉及到相关，4个变量可不用标准化处理，将来的相似性矩阵里的数字为相关系数。若果有某两个变量的相关系数接近1或-1，说明两个变量可互相替代。

只输出“树状图”就可以了,从proximity matrix表中可以看出热量和酒精含量两个变量相关系数0.903，最大，二者选其一即可，没有必要都作为聚类变量，导致成本增加。

至于热量和酒精含量选择哪一个作为典型指标来代替原来的两个变量，可以根据专业知识或测定的难易程度决定。（与因子分析不同，是完全踢掉其中一个变量以达到降维的目的。）这里选用酒精含量，至此，确定出用于聚类的变量为：酒精含量，钠含量，价格。

问题二：20 中啤酒能分为几类？—— 采用“Q 型聚类”

现在开始对20中啤酒进行聚类。开始不确定应该分为几类，暂时用一个3-5类范围来试探。Q型聚类要求量纲相同，所以我们需要对数据标准化，这一回用欧式距离平方进行测度。

主要通过树状图和冰柱图来理解类别。最终是分为4类还是3类，这是个复杂的过程，需要专业知识和最初的目的来识别。

这里试着确定分为4类。选择“保存”，则在数据区域内会自动生成聚类结果。

问题三：用于聚类的变量对聚类过程、结果又贡献么，有用么？——采用“单因素方差分析”

聚类分析除了对类别的确定需讨论外，还有一个比较关键的问题就是分类变量到底对聚类有没有作用有没有贡献，如果有个别变量对分类没有作用的话，应该剔除。

这个过程一般用单因素方差分析来判断。注意此时，因子变量选择聚为4类的结果，而将三个聚类变量作为因变量处理。方差分析结果显示，三个聚类变量sig值均极显着，我们用于分类的3个变量对分类有作用，可以使用，作为聚类变量是比较合理的。

问题四：聚类结果的解释？——采用”均值比较描述统计“

聚类分析最后一步，也是最为困难的就是对分出的各类进行定义解释，描述各类的特征，即各类别特征描述。这需要专业知识作为基础并结合分析目的才能得出。

我们可以采用spss的means均值比较过程，或者excel的透视表功能对各类的各个指标进行描述。其中，report报表用于描述聚类结果。对各类指标的比较来初步定义类别，主要根据专业知识来判定。这里到此为止。

以上过程涉及到spss层次聚类中的Q型聚类和R型聚类，单因素方差分析，means过程等，是一个很不错的多种分析方法联合使用的案例。

聚类分析的应用

聚类分析是细分市场的有效工具，被用来发现不同的客户群，并且它通过对不同的客户群的特征的刻画，被用于研究消费者行为，寻找新的潜在市场。

聚类分析被用来对动植物和基因进行分类，以获取对种群固有结构的认识。

聚类分析可以通过平均消费来鉴定汽车保险单持有者的分组，同时可以根据住宅类型、价值、地理位置来鉴定城市的房产分组。

聚类分析被用来在网上进行文档归类。

聚类分析通过分组聚类出具有相似浏览行为的客户，并分析客户的共同特征，从而帮助电子商务企业了解自己的客户，向客户提供更合适的服务。

❺ 聚类的计算方法

传统的聚类分析计算方法主要有如下几种：
1、划分方法(partitioning methods)
给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。而且这K个分组满足下列条件：（1） 每一个分组至少包含一个数据纪录；（2）每一个数据纪录属于且仅属于一个分组（注意：这个要求在某些模糊聚类算法中可以放宽）；对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。使用这个基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法；
大部分划分方法是基于距离的。给定要构建的分区数k，划分方法首先创建一个初始化划分。然后，它采用一种迭代的重定位技术，通过把对象从一个组移动到另一个组来进行划分。一个好的划分的一般准备是：同一个簇中的对象尽可能相互接近或相关，而不同的簇中的对象尽可能远离或不同。还有许多评判划分质量的其他准则。传统的划分方法可以扩展到子空间聚类，而不是搜索整个数据空间。当存在很多属性并且数据稀疏时，这是有用的。为了达到全局最优，基于划分的聚类可能需要穷举所有可能的划分，计算量极大。实际上，大多数应用都采用了流行的启发式方法，如k-均值和k-中心算法，渐近的提高聚类质量，逼近局部最优解。这些启发式聚类方法很适合发现中小规模的数据库中小规模的数据库中的球状簇。为了发现具有复杂形状的簇和对超大型数据集进行聚类，需要进一步扩展基于划分的方法。
2、层次方法(hierarchical methods)
这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。例如在“自底向上”方案中，初始时每一个数据纪录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者某个条件满足为止。代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等；
层次聚类方法可以是基于距离的或基于密度或连通性的。层次聚类方法的一些扩展也考虑了子空间聚类。层次方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤销。这个严格规定是有用的，因为不用担心不同选择的组合数目，它将产生较小的计算开销。然而这种技术不能更正错误的决定。已经提出了一些提高层次聚类质量的方法。
3、基于密度的方法(density-based methods)
基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。这个方法的指导思想就是，只要一个区域中的点的密度大过某个阀值，就把它加到与之相近的聚类中去。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等；
4、基于网格的方法(grid-based methods)
这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快，通常这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；
很多空间数据挖掘问题，使用网格通常都是一种有效的方法。因此，基于网格的方法可以和其他聚类方法集成。
5、基于模型的方法(model-based methods)
基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。通常有两种尝试方向：统计的方案和神经网络的方案。
当然聚类方法还有：传递闭包法，布尔矩阵法，直接聚类法，相关性分析聚类，基于统计的聚类方法等。

❻ 有哪些常用的聚类算法

【聚类】聚类分析是直接比较各对象之间的性质，根据在对象属性中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相似的（相关的），而不同组中的对象是不同的（不相关的）。组内的相似性（同质性）越大，组间差别越大，聚类就越好。

聚类的目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，是无监督学习过程。在无监督学习中，训练样本标记信息是未知的。聚类试图将数据集中的样本划分为若干个通常不相交的子集，每个子集称为一个“簇”，每个簇可能对应于一些潜在的类别，这些类别概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇所对应的概念语义需要由使用者来把握和命名。

❼ 常用的聚类方法有哪几种

聚类分析的算法可以分为划分法、层次法、基于密度的方法、基于网格的方法、基于模型的方法。

1、划分法，给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。

2、层次法，这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。

3、基于密度的方法，基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。

4、图论聚类方法解决的第一步是建立与问题相适应的图，图的节点对应于被分析数据的最小单元，图的边（或弧）对应于最小处理单元数据之间的相似性度量。

5、基于网格的方法，这种方法首先将数据空间划分成为有限个单元的网格结构,所有的处理都是以单个的单元为对象的。

6、基于模型的方法，基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。

(7)集成聚类的算法扩展阅读：

在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯。

它作为数据挖掘中的一个模块，可以作为一个单独的工具以发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；并且，聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。

许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进行聚类可能会导致有偏的结果。

许多聚类算法在聚类分析中要求用户输入一定的参数，例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担，也使得聚类的质量难以控制。

❽ 一种面向高维数据的集成聚类算法

一种面向高维数据的集成聚类算法
聚类集成已经成为机器学习的研究热点，它对原始数据集的多个聚类结果进行学习和集成，得到一个能较好地反映数据集内在结构的数据划分。很多学者的研究证明聚类集成能有效地提高聚类结果的准确性、鲁棒性和稳定性。本文提出了一种面向高维数据的聚类集成算法。该方法针对高维数据的特点，先用分层抽样的方法结合信息增益对每个特征簇选择合适数量比较重要的特征的生成新的具代表意义的数据子集，然后用基于链接的方法对数据子集上生成的聚类结果进行集成．最后在文本、图像、基因数据集上进行实验，结果表明，与集成前的K均值聚类算法及基于链接的聚类集成算法相比，该方法能有效的改善聚类结果。
引 言
聚类分析又称群分析，是根据“物以类聚”的道理对样品或指标进行分类的一种多元统计分析方法。它是一个将数据分到不同类或者簇的过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。聚类分析是机器学习、模式识别的一个最重要的研究方向之一，它是了解数据集的结构的一种最重要的手段，并已经成功的应用于数据挖掘、信息检索、语音识别、推荐系统等领域。
现实世界中的数据集具有各种形状和结构，不存在哪一种单一的算法对任何数据集都表现的很好[3]，没有一种聚类算法能准确揭示各种数据集所呈现出来的多种多样的形状和簇结构，每一种聚类算法都有其优缺点，对于任何给定的数据集，使用不同的算法都会有不同的结果，甚至对于同一种算法给定不同的参数都会有不同的聚类结果，自然分组概念内在的不明确性决定了没有一个通用的聚类算法能适用于任何数据集的聚类问题。此外，类存在多样性的特点，类具有不同的形状、大小、密度，而且类之间往往是相互重叠的，这样的问题在高维数据中更加明显，因为不相关的或者冗余的特征会使类的结构更加不明显。K均值算法[5]是一种应用广泛的最经典的聚类算法之一，它的特点之一就是随机选取初始的聚类中心，如果选取的中心点不同，聚类结果就可能产生很大的差异。K均值聚类算法对初始中心点的依赖性，导致K均值算法的聚类结果不稳定。在这种情况下，聚类集成应运而生，许多学者在这个领域进行了深入的研究。
聚类集成的目的在于结合不同聚类算法的结果得到比单个聚类算法更优的聚类。对聚类集体中的成员聚类的问题成为一致性函数问题，或叫做集成问题。很多学者证实通过聚类集成可以有效的提高像K均值聚类这些单一聚类算法的准确性、鲁棒性和稳定性.在现有的研究中，产生基聚类结果的方法有:
(1)使用同一种聚类算法，每次运行使用不同的参数和随机初始化；
(2)使用不同的聚类算法，如K均值产生多个不同的聚类;
(3)对数据集的子集聚类，子集通过不同采样像bagging、Sub-sampling等方法获得；
(4)在数据集的不同特征子集或在数据集的不同子空间的投影上聚类得到不同聚类结果构成聚类集体。我们的方法主要是对第四种聚类集成问题进行了深入研究，在数据集的不同子集上进行集成分析。对于高维数据来说，数据点为单位划分仍存在维数灾难的问题，维数灾难可能会引发这种现象，一个给定数据点与离它最近点的距离比与离它最远的数据点的距离近，所以我们引入同样的数据点但基于不同的特征子集就可能会避免这种问题。生成基聚类结果以后就是设计一致性函数对聚类结果集成，就是将聚类成员进行合并，得到一个统一的聚类结果。目前存在很多一致性函数，常用的有投票法、超图划分、基于共协矩阵的证据积累、概率积累等等，我们在文章中用了文献[1]中的方法，它是一种基于链接的方法。常规的集成方法往往基于一个由基聚类结果即这些数据基聚类结果内部的关系生成，忽略了这些结果之间的关系，所以Iam-on等利用簇之间的相似度来精炼集成信息矩阵。在高维数据中，我们将数据集的局部特征子集用作聚类成员与基于链接的集成聚类方法有效结合，解决了高维数据进行集成聚类的问题。
本文组织如下：第2节对聚类集成做了一个概述，并针对于高维数据这一特殊数据集提出了自己的集成聚类方法。第3节是本文的核心部分，它讲述了对特征进行分层抽样，并基于信息增益抽取出比较重要的具有代表意义的局部特征子集的过程，此外对传统的K均值算法的具体过程进行了简要的描述，然后引出了分层抽样的概念，用分层抽样的思想确定我们选择的特征的数目，最后给出了信息增益的定义，通过这个指标最终确定我们在每一个聚类簇中选择的特征；最后把我们前面的工作抽取局部特征子集与基于链接的方法结合起来形成了自己的算法描述；第4节首先对8个实际数据集包括文本、图像、基因数据进行描述，然后在这八个数据集上比较和分析了我们的方法(SSLB)和传统K均值算法和基于链接的聚类集成算法(LB)在四个聚类评价标准上的聚类性能；第5节是对全文的总结。
相关工作
聚类集成概述
聚类分析是按照某种相似性测度将多维数据分割成自然分组或簇的过程。聚类算法很多，但是没有一个万能的聚类算法能用于任何聚类问题，其原因在自然分组概念的内在不明确性以及类可以有不同的形状、大小、密度等，这个在高维数据中的问题更为明显，那些不相关的特征和冗余的特征会使类结构更加模糊。单个聚类存在的这些问题，引发了学者们对聚类集成的研究。首先由Strehl[12]等人提出”聚类集成”的概念，而后Gionis[13]等人也给出该问题的描述。杨草原等给聚类集成下了一个定义，认为聚类集成就是利用经过选择的多个聚类结果找到一个新的数据(或对象)划分，这个划分在最大程度上共享了所有输入的聚类结果对数据或对象集的聚类信息。
聚类集成的符号化形式为：假设数据集X有n个实例，X={x1,x2,…,xn},首先对数据集X使用M次聚类算法，得到M个聚类，?={?1,?2,…,?M}(下面称为聚类成员)，其中?i(i=1,2,…,M)为第i次聚类算法得到的聚类结果。然后用一致性函数T对?的聚类结果进行集成得到一个新的数据划分?’[1].
摘 要

图1聚类集成的基本过程。首先对数据集使用不同的聚类算法得到不同的划分，然后对这些划分用一致性函数合并为一个聚类结果P’
由上面的聚类集成过程可知，对一个数据集进行聚类集成，主要有两个阶段，第一个阶段是基聚类器对原始数据进行聚类，得到基聚类结果。第二个阶段是基聚类结果集成，根据聚类集成算法对前一个阶段采集的基聚类结果进行处理，使之能够最大限度地分享这些结果，从而得到一个对原始数据最好的聚类集成结果。
面向高维数据的集成聚类
信息时代互联网成为最大的信息聚集地，像Web文档、交易数据、基因表达数据、用户评分数据等等，这些成为聚类分析的主要研究对象，而这些数据的维度成千上万，甚至更高，这给聚类分析带来了极大的挑战。高维数据的聚类集成面临更多的问题。
传统的集成学习的第一步是产生多个基聚类结果，这一阶段是对数据集或者其子集反复进行聚类算法。现有的方法主要有：使用一个聚类算法，每次运行设置不同的参数和随机初始化；使用不同的聚类算法；对数据集的子集进行聚类；将数据集的特征空间投影到数据子空间。基聚类结果生成以后就开始对基聚类结果进行集成。一致性函数是一个函数或者是一个方法，它将聚类成员进行集成，得到一个统一的聚类结果。目前存在许多一致性函数，它大致可以分为:
(1)基于成对相似性的方法，它主要考虑的是所有的数据点对的关系的重现、
(2)基于超图划分的方法和(3)基于特征的方法，它是把聚类的集成转换为类标的集成。
针对高维数据的特点，我们选择基于相似性的方法对聚类结果进行集成，凝聚层次聚类算法是最经典的基于相似性方法，我们用了文献中的方法，他把SL凝聚聚类算法用来生成最终的划分。但是基于成对相似度的集成的过程都是一个比较粗糙的过程，集成的结果往往基于一个由基聚类结果即这些数据划分内部的关系生成，忽略了这些划分结果之间的关系，所以它使用了Iam-on[17]等利用簇之间的相似度来精炼集成信息矩阵，实验证明这种方法在很多数据集上表现很好，不仅增强了聚类稳定性也改善了聚类性能。由于我们研究的对象是高维数据，考虑到需要聚类的对象的维度很大，对完整的对象聚类一定会增加聚类算法的运行开销。这对基于链接的方法性能有所影响，因此，我们考虑对特征空间的局部特征子集进行聚类得到结果。经过上面的分析，我们引出自己的方法。我们对其中的基本步骤进行细化，我们的方法示意图如下：

我们方法的示意图，对聚类集成的过程进行了细化，描述了每一个过程的输入和输出
我们的方法就是针对高维数据的特点，对传统的聚类集成进行了一些改进，我们首先用前面提到的K均值算法对特征进行聚类，然后用信息增益来衡量不同簇中的特征的重要程度，而每个特征簇中的所抽取特征的数目nh由上面stratifiedsampling[18]的方法得到，最后利用信息增益选择top(nh)的特征。根据上述方法对特征进行降维，得到了最具代表的数据子集。数据子集的生成，变换K均值算法的k值，取k=2,3…√N(N为数据点的数目)生成不同的具有差异的数据子集，然后沿用[1]中的方法进行聚类集成，最后把这√N-2次的聚类结果进行最后一次集成得到我们最终的聚类结果。基于局部特征子集的生成方法内容在下一章详细讲述。
基于局部特征的数据子集生成方法
集成时使用哪种方法产生聚类成员一般从两个方面来考虑，一个是集成者的目的，一个是数据集的结构。在机器学习的实际应用中，我们面对的绝大多数都是高维数据。数据集的特征数量往往较多，可能存在不相关的特征，特征之间可能存在相互依赖，容易导致分析特征、训练模型的时间变长，甚至引发“维度灾难”，模型复杂推广能力下降。所以我们采用基于局部特征的数据子集生成方法。图3是我们生成局部特征的数据子集的示意图：

Fig. 3 The basic process of the generation of feature subset
首先我们用传统的K均值算法对数据集的特征进行聚类，然后对于不同的特征簇我们用信息增益来衡量它的重要性，不同的特征簇中我们应该筛选多少特征簇呢？分层抽样很好的解决了这个问题，分层抽样的思想是计算每个实例之间的相关性(用标准差、方差来衡量)，它认为类中的实例相关性比较大的可以选择较多的样本来代替当前类，类中相关性较小的就少选择一些实例来代替当前类的样本，根据分层抽样中计算出的特征簇的数目再利用信息增益这种衡量重要性的标准进行筛选后就得到了局部的特征子集。下面具体论述基于局部特征的数据子集生成方法中的关键技术。
k均值算法
K均值算法[5]是MacDueen提出的一个着名的聚类学习算法。它根据相似度距离迭代的更新向量集的聚类中心，当聚类中心不再变化或者满足某些停止条件，则停止迭代过程得到最终的聚类结果。K均值算法的具体步骤为：
(1) 随机选择k个数据项作为聚类中心；
(2) 根据相似度距离公式，将数据集中的每一项数据分配到离他最近的聚类中去；
(3) 计算新的聚类中心；
(4) 如果聚类中心没有发生改变，算法结束；否则跳转到第(2)步.
我们使用K均值算法对数据集的特征进行聚类，我们通过选取不同的k值进行特征聚类，然后用后面的分层抽样进行选择得到差异度比较明显的局部特征的数据子集作为后面的聚类集成的输入。
信息增益
对特征进行聚类后得到多个特征团，如何对它们进行特征选择，如何度量特征团中的特征的重要程度是我们面临的问题。信息增益是信息论中的一个重要概念，它被广泛应用在机器学习、数据挖掘领域，计算信息增益是针对一个特征项而言的，它通过统计某一个特征项t在类别C中出现与否的实例数来计算特征项t对类别C的信息增益，定义为：

其中P(ci)表示ci类实例在数据集中出现的概率，p(t)表示数据集中包含特征项t的实例数，p(ci|t)表示实例包含特征项t时属于ci类的条件概率，p(t ? )表示数据集中不包含特征项t的实例数，p(c_i |t ? )表示实例不包含特征项t时属于ci类的概率，m为类别数。信息增益考虑特征与类别信息的相关程度，认为信息增益值越大，其贡献越大。我们的方法采用信息增益来度量特征簇中的特征的重要程度。
分层抽样（Stratified sampling）
在对特征进行聚类后对特征进行选择，我们采用信息增益来度量每个特征簇中的特征的重要程度。但是每个特征簇我们选择多少个特征比较合适，这是分层抽样解决的问题。抽样的目的是在不影响聚类效果的情况下在已经分好或者聚好类的实例中，从每个类中抽取部分的样本来代替整个类。Stratifiedsampling[18]方法遵循的原则是：计算每个实例之间的相关性(用标准差、方差来衡量)，我们认为类中的实例相关性比较大的可以选择较小的样本来代替当前类，类中相关性较小的就多选择一些实例来代替当前类的样本。这个方法就是确定每个类中筛选的实例的数目。此方法中每个类的样本数目为：

其中nh是第h类应该抽取的实例数。n是预计抽取的总样本数，Nh是在总体样本中第h类的实例数，?h是第h类的标准差。通过(1)式我们就可以得到每个类中应该选择的实例数目。提出这中抽样方法的学者还对它的精确度、置信区间进行了分析，证明了它在不影响学习效果的情况下对可以对数据降维，提高学习效率。
在本文的方法中，我们先用前面提到的k均值算法对特征进行聚类，然后用信息增益来衡量不同簇中的特征的重要程度，而每个特征簇中的所抽取特征的数目nh由上面stratifiedsampling的方法得到，最后利用信息增益选择top(nh)的特征。根据上述方法对特征进行降维，得到了最具代表的数据子集，进行后面的数据集的聚类集成。
实验结果与分析
实验数据集
本文选用了8个数据集，包括文献[1]中的两个数据集：一个人工数据集Four-Gaussian[19]和一个被用来做基因数据聚类的真实数据集Leukemiadataset[20],另外就是六个真实数据集包括两个文本数据集，两个图像数据集，两个基因数据。表1给出了这些数据集的名称以及数据的样本、属性、类别数量。
Table 1 Number of instance, features and classes of datasets

实验分析
实验中，本文对比了三种分类算法包括传统的k-means算法，文献[1]中的LB算法以及我们实现的算法SSLB。聚类性能通过下面四个评价指标来衡量，表2给出了这四个评价指标[1]的具体描述：
Table 2 Name of measures, formulas

K为聚类结果中簇的数目，nk是属于第k个簇的数据点数目，d(xi,xj)是数据点xi和xj的距离，N是数据集中数据点的总数。n11是指在两个划分?’(正确的划分)和?中出现在相同簇中的数据线对的个数，n00是指在两个划分?’、?中中出现在不同簇中的数据点对的个数，n01表示在划分?中属于不同簇在另一个划分?’ 中属于同一个簇的数据点对数目，n10表示在划分?’中属于不同簇在另一个划分?中属于同一个簇的数据点对数目。
其中CP衡量的是在同一个簇中，所有数据点的数据点对的平均距离，越小越好。CA衡量的是与已经的类标相比，聚类正确的数据点数目，CA的范围是从0到1，越大越好。RI这个指标衡量存在于相同和不同簇中的点对数目，RI的值从0到1，越大越好，AR也是越大越好。
本文对这8个数据集进行聚类集成，聚类成员由k均值对特征聚类然后分层抽样产生的局部特征子集获得，聚类中心的个数为数据集的类别数。为了增加实验的可靠性，所有的实验结果为10次结果的平均值。对比试验采用原始的K均值聚类算法、基于链接(LB)的方法，与我们实现的方法(SSLB)进行比较。在表3中，我们把关键值都突出的表现出来，在这8个数据集上，SSLB有在四个评价指标上都表现出比较大的优势。
根据表四，比较集成前的K均值算法、LB方法和SSLB方法，可以看出，在数据集Four-Gaussian上，SSLB在四种评价指标上都可以看出，其聚类性能明显优于集成前的K均值算法和LB聚类集成算法。在两种文本数据集Tr31和Tr41上，我们的方法优势不是很明显，但是在前两个指标CP和CA上还是明显好于集成前的K均值聚类，与LB算法在这两个指标上性能相当，而且在这两个文本数据上，在RI和AR上集成前的K均值算法与LB和SSLB方法相比都存在优势。在两个图像数据集上，SSLB方法在CP这个评价指标上都远远好于集成前的K均值聚类算法和LB算法，但是在第二个评价指标和第三个评价指标上就比LB算法差一点。在基因数据Colon上SSLB再第一个聚类评价指标上仍然存在很大的优势，在聚类的准确率上，我们的方法与LB方法相当，但是明显优于集成前的K均值算法。在基因数据TOX-171上，我们的方法获得了最好的聚类集成性能，在四个聚类评价指标上，都远远好于集成前的K均值算法和LB算法。
下面我们逐一在这四个聚类评价标准比较集成前的K均值算法、SSLB算法和LB算法。图四、图五、图六、以及图七分别描述了集成前的K均值聚类、LB以及我们的方法SSLB在CP、CA、RI、AR上的表现。

聚类评价指标CP衡量的是在同一个簇中，所有数据点的数据点对的平均距离，越小越好。通过图四可以看出，在所有数据集上，我们的算法SSLB都存在很大的优势，比集成前的K-means算法以及LB算法在CP这个指标上都好，此外还能看出CP在不同的数据集上的差异还是比较大的，在Four-Gaussian上明显比其他数据集上差。

聚类评价指标CA衡量的是与已知的类标相比，聚类正确的数据点数目占总的数据点数目的比例，CA的范围是从0到1，越大越好。从图五可以看出我们的算法在数据集Four-Gaussian、Tr41、Colon和TOX-171上的聚类精度比集成前的K均值算法以及LB算法都要好，但是在Tr31以及两个图像数据集上的优势不大，这这个现象值得我们关注，也是我们接下来会研究的工作。

聚类评价指标RI衡量的是存在于相同和不同簇中的点对数目，RI的值从0到1，越大越好。从图六可以看出我们的算法在人工数据集Four-Gaussian以及几个基因数据集上的表现比较突出、但是在其他数据集上就处于弱势，而且可以看出集成前的K均值算法在所有的数据集在RI上的表现都比较好。

聚类评价指标AR衡量的也是存在于相同和不同簇中的点对数目，AR的值从0到1，越大越好。从图七可以看出我们的算法SSLB在大多数数据集上存在着优势，但是在数据集Leukemia、Tr41、Colon上的超过了集成前的K均值算法和我们的算法。这些现象和结果都是我们接下来的研究的重点。

综上所述，在几乎所有数据集上，在所有的聚类评价指标上我们的聚类集成算法SSLB好于集成前K均值算法的聚类效果，而且在大多数数据集上，我们的算法比LB算法存在一定的优势，尤其是在基因数据上的表现较为突出。但是在有的数据集上优势也不够明显，我们要继续分析这些数据结构上的特点和我们的算法可能存在的问题，这也是我们接下来研究的方向。
结 论
本文提出了一种面向高维数据的集成聚类方法。针对高维数据的特点，对传统的聚类集成进行了一些改进，首先对特征聚类然后基于分层抽样抽取特征子集，抽取到最具代表性的特征子集后用基于链接的方法进行聚类集成。并在8个实际数据集包括文本、图像、基因数据上进行实验，在这8个数据集上分析和比较了我们的方法和集成前的K均值算法以及基于链接的聚类集成算法在四个评价标准上的聚类性能，能够看出我们的算法在聚类性能上有一定改善。

❾ 聚类算法有哪几种

聚类算法有：聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k均值、k中心点等算法的聚类分析工具已被加入到许多着名的统计分析软件包中，如SPSS、SAS等。

❿ 有哪些常用的聚类算法

聚类分析计算方法主要有如下几种：
1.
划分法(partitioning
methods)
给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K
评论
0
0
0
加载更多