凝聚聚类算法

凝聚聚类算法（通用7篇）

凝聚聚类算法 篇1

简单来说, 聚类处理的核心就在于:将数据集当中, 数据所表现出特征的不同为依据, 将其划分为差异性的数据簇。在所形成的数据簇当中, 样本与样本之间的相似度极高。而即便是对于同一数据集而言, 不同数据簇与数据簇相互之间样本的相异度水平也相当高。更加关键的一点是:由于在对数据集进行聚类处理的过程当中, 没有涉及到以类别、标签为载体的监督信息与数据, 因而其学习方式表现出了突出的无监督性特征, 仅仅建立在无标签样本的基础之上完成学习。而对于所提出的建立在成对约束基础之上的半监督凝聚层次聚类算法而言, 其优越性就体现在:能够在学习过程当中同时应用有标签样本以及无标签样本进行辅助。在确保聚类性能得到显著提升的前提条件下, 能够兼顾对监督信息的灵活使用。而成对约束在其中无疑也发挥着关键性的作用。

1 成对约束的基本概念

在半监督聚类处理算法下, 成对约束表示的是:两个样本一定会被划分至同一个数据簇当中, 或者是两个样本一定被划分到不同的数据簇当中。现阶段, 应用最为广泛的成对约束概念为:建立在must link以及cannot link基础之上的约束关系。其中, 前者所表述的是:两个样本一定会被划分至同一个数据簇当中, 而后者所表述的则是:两个样本一定被划分到不同的数据簇当中。对于样本m, 样本n而言, 以Con (m, n) 的方式对两个样本之间的成对约束关系加以表述, 则有以下关系:

当Con (m, n) 取值为1的情况下, 则就有Con (n, m) 取值为1;当Con (m, n) 取值为-1的情况下, 则就有Con (n, m) 取值为-1。

2 实施过程

2.1 对邻近度标准的应用

在所研究的建立在成对约束基础之上的半监督凝聚层次聚类算法而言, 算法实施过程当中最具创新性价值的当属近邻度这一概念。近邻度这一概念是在近邻分类算法基础之上所生成的。其所指的主要是:以待分类样本为标准, 寻求与其距离间隔最小的标记样本, 将所寻求的标记样本数量定义为k。在此基础之上, 研究k集合当中, 样本类别所述情况, 通过判定所占数目最多标记样本类别的方式, 将与之相对应的待分类样本划作该类型样本。将样本定义为x, 则对于任意x取值而言, 均对应有一个独立的邻近度参数 (通常将其定义为α) 。α始终取值为0以上的系数, 其与样本x, 以及既定参数k之间的对应关系如下:

α=1/既定参数k∑||样本x-距离样本最近的标记样本k||;

在基于成对约束基础之上的半监督凝聚层次聚类算法实施的过程当中, 近邻度的应用价值主要体现在:假定存在xa、xb、以及xc这3个不同的样本, 以其为中心做圆, 则圆的半径就能够充分呈现以上3个不同样本所对应的近邻度标准。若xa、xb、xc周边样本的分布相对比较密集, 则意味着与之相对应的邻近度标准数值较小;反过来说, 若xa、xb、xc周边样本的分布相对比较稀疏, 则意味着与之相对应的邻近度标准数值较大。

2.2 对成对约束的应用

在算法具体实施的过程当中, 通过对成对约束的合理应用, 能够使聚类簇相互之间的距离得到有效的改变。在此过程当中, 需要按照如下步骤加以实施:

第一步:需要分别定义两个集合:将集合一定义为ML (A;x) 。该集合主要描述的是:在A聚类簇当中, 与样本x关系始终保持在must link状态下的样本集合。同时, 需要将集合二定义为CL (A;x) 。该集合主要描述的是:在A聚类簇当中, 与样本x关系始终保持在cannot link状态下的样本集合。以上两个集合的取值具体表述方式如下所示:

以以上数据为基础, 可定义用以表述第二步中所确定集合以及的近邻度差水平。具体的表达方式应当为:为聚类簇A相对于在must link状态下的约束度水平-聚类簇A相对于在cannot link状态下的约束度水平。按照以上方式, 根据所计算结果的分析, 可以得出聚类簇A与之间的对应关系。当计算结果取值为负的情况下, 对于聚类簇A而言, 其与之间的关系表现为canno link约束关系;当计算结果取值为正的情况下, 对于聚类簇A而言, 其与之间的关系表现为must link约束关系。在整个算法实施的过程当中, 还需要特别注意的一点问题在于:在整个基于成对约束的半监督凝聚层聚类算法实施过程当中, 并不具有对称性方面的特征。换句话来说, 的取值与的取值并不一致。

3 准确率验证

为进一步针对所提出基于成对约束的半监督凝聚层次聚类算法的准确度情况进行综合分析, 选取常规AHC算法作为对比算法, 分别选取haberman、balance-scale、iris、tae, 以及pid这5个数据集作为原始数据进行计算。数据集当中按照随机方式抽取样本, 生成建立在must link以及cannot link基础之上的约束关系。算法均运行20次, 取平均值进行综合对比。首先, 对于常规AHC算法而言, haberman数据集对应的聚类准确率为72.5%;balance-scale数据集对应的聚类准确率为62.5%;iris数据集对应的聚类准确率为92.5%;tae数据集对应的聚类准确率为36.5%;pid数据集对应的聚类准确率为65.0%;其次, 对于基于成对约束的半监督凝聚层次聚类算法而言, haberman数据集对应的聚类准确率为85.5%;balancescale数据集对应的聚类准确率为92.0%;iris数据集对应的聚类准确率为99.5%;tae数据集对应的聚类准确率为80.0%;pid数据集对应的聚类准确率为88.5%。

4 结语

主要针对基于成对约束的半监督凝聚层次聚类算法实施展开了详细的分析与研究, 并对比常规意义上AHC聚类算法, 就不同的数据集进行了聚类准确度的比较。比较结果表明:基于成对约束的半监督凝聚层次聚类算法准确度高, 对不同数据集适应性高, 所提出的近邻度概念与价值均十分有效, 值得进一步的应用。

参考文献

[1]李娜, 钟诚.基于划分和凝聚层次聚类的无监督异常检测[J].计算机工程, 2008, 34 (2) :120-123, 126.

[2]丁彦, 李永忠.基于PCA和半监督聚类的入侵检测算法研究[J].山东大学学报:工学版, 2012, 42 (5) :41-46.

[3]陈志民, 杨敬锋, 陈其昌, 等.融合监督学习与凝聚层次聚类的土地评价方法[J].计算机工程与应用, 2007, 43 (18) :188-190.

[4]王娜, 李霞.基于监督信息特性的主动半监督谱聚类算法[J].电子学报, 2010, 38 (1) :172-176.

凝聚聚类算法 篇2

随着互联网的快速发展和普及应用,网络入侵行为日益增多,网络安全成为人们广泛关注的话题。入侵检测系统IDS作为一种重要的网络安全防范技术,显得尤为重要。设计快速、有效的网络入侵检测模型,确保网络系统的安全具有十分重要的意义[1]。

为了提高网络入侵的检测能力,许多学者和专家对网络入侵问题进行相应研究,提出许多有效的检测算法[2]。网络入侵检测实质上是模式识别中的分类问题,首先收集网络状态数据,然后对网络行为进行分析,最后将网络行为分为异常和正常,并根据检测结果采取相应安全措施。网络入侵检测主要包括两个关键步骤: ①网络特征提取和选择; ②分类器设计及参数优化。当前网络入侵分类器主要采用支持向量机算法SVM、贝叶斯网络和神经网络等机器学习进行构建,神经网络基于经验风险最大化原理,而SVM是一种专门针对高维分类问题的机器学习算法,泛化能力优异,避免了传统机器学习的局限性,大量研究表明,通常情况下SVM分类性能要优于神经网络[4,5,6]。这些入侵检测算法要求样本大,不能对一些新的、变异的入侵行为进行检测,存在漏检、误检率高的难题。为了克服机器学习算法存在的不足,有学者提出基于聚类算法的网络入侵检测模型,该类方法只能够描述凸数据的分类问题,无法正确描述非凸数据的聚类,而在网络入侵检测过程中,由于受到多因素的综合影响,原数据不能保证是凸性,入侵检测率有待进一步提高,应用范围受限。为了解决传统聚算法存在的不足,文献[7]提出一种基于 α 核心集的多层凝聚算法( Mul CA) ,其无须训练数据,通过对入侵检测进行多层次的 α 核心集提取得到最顶层的核心集( 称为凝聚粗化阶段) ,然后利用数据间的高斯相似性自上而下对各层的核心集进行聚类( 称为凝聚细化阶段) ,实验结果表明,Mul CA提高网络入侵检测率。但是Mul CA算法存在一些自身难以克服的缺陷,如一旦不能成功选取顶层的核心集,聚类就失败,而且计算复杂性增加。

为了提高网络入侵的检测率,以降低误报率和误检率,提出一种基于改进Mul CA算法的网络入侵检测模型。首先采用KMeans聚类中心替代Mul CA算法的原顶层核心集,提高顶层的核心集选取成功率,在没有增加算法计算复杂性条件,提高算法鲁棒性,最后采用KDD CUP 99 数据集进行仿真实验。结果表明,本模型可以提高网络入侵检测的正确率和检测效率,获得更加理想的网络入侵效果。

1 KM-Mul CA算法

1. 1 Mul CA算法

多层聚类中心( 称为核心集) 的凝聚聚类算法Mul CA( multilevel core-sets based aggregation) 利用多层次的 α 核心集的提取过程,随着细化过程的推进,算法的聚类中心不断增加,有利于提高算法的聚类效果。

( 1) 数据间的相似性

数据xi与xj的相似性定义如下:

其中,σ = σ0d,d为数据集直径。

( 2) 首要核心点

对于任意数据集X,首要核心点x*满足条件为:

( 3) α - 核心集

设x*1为任意X的首要核心点,x*2为除x*1外的X{x*1}的首要核心点,以此类推,x*k+1为数据集X{x*1,…,x*k}的首要核心点,X的α-核心集定义为:

式中,1 =[α* | X| ],| X| 为数据集X的数量,α 核心集规模控制参数。

( 4) 凝聚矩阵

其中,Px - xα体现的是数据集合X与其核心集Xα的相关程度。

1. 2 K-Means和KM-Mul CA算法的融合

Mul CA算法的步骤如图1 所示。Mul CA算法与以往的聚类算法的不同点在于其采用多层的核心集方式,将聚类数据分为多个层次进行分别聚类,这样在自上而下的聚类过程中,聚类中心的数目也在不断增加。这种方式提高了算法的聚类精度,并且适用于非凸性的数据集分类识别,是一种新颖而高效的分类识别方法。

从图1 可知,Mul CA算法一旦不能成功选取顶层的核心集,聚类就失败,就会导致网络入侵检测的正确率低,误检率和漏检率升高。为了解决这个问题,首先结合入侵检测数据的特点,将数据集分类为入侵数据和非入侵数据,然后利用K-Means快速准确得到数据集的两个聚类中心,以此代替顶层核心集,以保证顶层核心集的鲁棒性和正确性,降低算法的时间复杂度。KMMul CA算法步骤:

( 1) 输入待分类的数据集X及所需要聚类的个数K。

( 2) 利用K-Means方法提前确定待分类数据集的聚类中心Y( K)。

( 3) 计算并输出数据集X的各层 α 核心集及相似性矩阵。

( 4) 利用Y( K)替换Xαm,并参照Mul CA算法细化阶段对数据集进行分类。

2 KM-Mul CA算法性能测试

为了测试KM-Mul CA算法的性能,利用高斯分布生成数据对聚类算法进行对比实验,具体的数据生成算法描详细参见文献[11]。分别产生2 个聚类区( 二类) 、数据区间为[- 1 4]; 3个聚类区( 三类) ,数据区间为[- 3 2]; 4 个聚类区( 四类) ,数据区间[- 4 4]人工数据集。选取三种类别的测试数据集的数据规模为100,Mul CA算法控制参数为 αMul CA= 0. 6,KM-Mul CA算法的 αIMul CA= 0. 3。对比结果如图2 - 图4 所示。

图中“□”表示该算法的聚类中心。可以直观看出KMMul CA凝聚算法的聚类效果要优于所对比的Mul CA算法和KMean算法,特别是当顶层核心集过于靠近两组数据的边界时容易出现错误的分类结果。

3 KM-Mul CA的网络入侵检测模型

3. 1 网络入侵检测基本流程

入侵检测是属于模式识别的一个学科领域,其基本工作流程如图5 所示。网络入侵检测的最基本的问题是如何对入侵行为进行正确的分类和识别,核心内容是入侵特征提取和分类器的构建。

原始入侵数据主要来源于应用程序、审计日志以及网络上的数据包等,其包含大量的冗余信息,如果直接采用原始数据建立入侵检测模型,那么特征的维度过高,造成维度灾难,并且冗余特征会对入侵检测结果产生不利影响,导致计算复杂度高。因此对网络入侵特征进行提取和选择,消除冗余特征,对提高网络入侵检测效果、缩短入侵检测建模时间具有重要意义。本文采用多层凝聚算法提高入侵检测检测效果。

3. 2 KM-Mul CA算法的入侵检测建模步骤

( 1) 原始数据中的各特征取值范围不同,会对网络入侵检测建模过程产生的不利影响,为此,本文先要对网络入侵的特征向量进行归一化预处理,以提高网络入侵的检测效率,具体归一化公式为:

式中,xstd为标准差; n为特征数量。

( 2) 得到归一化后的入侵特征向量集,并确定聚类个数K,凝聚算法层级m。

( 3) 对入侵模板进行特征的提取、特征向量的构造及数据预处理,进而得到归一化的入侵模板特征向量集Y,并利用KMeans方法确定聚类中心Y( k)。

( 4) 计算并输出特征向量集X的各层 α 核心集及其相似性矩阵。

( 5) 利用Y( k)替换Xαm,并参照Mul CA算法细化阶段对数据集进行分类。

( 6) 根据入侵的特征向量集合,确定并输出所相应入侵检测结果。

4 网络入侵检测仿真实验

4. 1 数据来源

实验数据来自KDD99 数据集,该数据集包括4 种入侵类型: Probe( 扫描与探测) 、Do S( 拒绝服务攻击) 、U2R( 对本地超级用户的非法访问) 和R2L ( 未经授权的远程访问) ,数据集中每条连接记录共有41 个属性: 9 个离散属性和32 个连续属性。选取的各类别样本分布如表1 所示。

4. 2 对比模型及评价指标

为了使KM-Mul CA结果具有可比性,采用Mul CA和KMeans的入侵检测模型进行对比实验,模型的性能评价指标为:检测率和误检率。检测率和误检率分别义如下:

4. 3 结果与分析

各模型的检测结果如表2 所示。可以看到,相对于KMeans算法,Mul CA算法的检测率更高; 相对于Mul CA和KMeans入侵检测模型,KM-Mul CA提高了网络入侵检测率,大幅度降低了误检率。对比结果表明,KM-Mul CA获得更加理想的入侵检测效果,验证了本文算法是有效的和优越的。

表3 为不同算法网络入侵检测建模时间。可以看到,相对于Mul CA算法,由于K-Means算法入侵检测建模时间最短,但是检测率最低; 相对于Mul CA算法,KM-Mul CA算法的入侵检测建模时间相对较短,网络入侵检测的效率得以提高,这主要是采用K-Means算法确定顶层核心集,可以获得更加合理的行聚类,计算复杂度降低,加快网络入侵检测建模时间。

为进一步验证验证KM-Mul CA网络入侵检测算法的优越性,选择当前两种典型的两种入侵检测算法进行对比仿真实验,它们分别为PRIDE[9]和DIDS[10]的算法。它们的网络入侵检测仿真结果如图6、图7 所示。对图6 进行分析知,相对于对比算法,KM-Mul CA算法提高了网络入侵检测率,同时从7 可知,相对于对比算法,KM-Mul CA算法的入侵检测错误率更低。

综合上述可知,KM-Mul CA算法是一种检测率高、速度快的网络入侵检测算法,可以满足网络入侵检测的实时和在线检测要求。

5 结语

为了提高入侵检测检测率,针对多层次核心集凝聚算法存在的不足,提出一种均值分析和多层次核心集凝聚算法相融合的入侵检测模型,并通过仿真测试了本文模型的优越性和可行性。下一步将继续对多层次凝聚算法进行深入研究,进一步提高聚类的准确性,提高网络入侵检测效率。

摘要：为了提高网络入侵的检测率,以降低误检率,提出一种基于均值聚类分析和多层核心集凝聚算法相融合的网络入侵检测模型。利用K-Means算法获取多层核心集凝聚算法的核心集,用其替代原粗化过程得到的顶层核心集,实现顶层核心集的快速准确定位,简化算法的计算复杂性。将KM-Mul CA算法应用到入侵检测模型,采用KDD CUP 99数据集进行仿真实验。结果表明,该模型可以获得理想的网络入侵检测率和误检率。

关键词：网络入侵检测,多层凝聚算法,K均值聚类算法,支持向量机

参考文献

[1]卿斯汉,蒋建春,马恒太,等.入侵检测技术研究综述[J].通信学报,2004,25(7):19-29.

[2]Chirag Modi,Dhiren Patel,Bhavesh Borisaniya.A survey of intrusion detection techniques in cloud[J].Journal of Network and Computer Applications,2013,36(1):42-57.

[3]饶鲜,董春曦,杨绍全.基于支持向量机的入侵检测系统[J].软件学报,2003,14(4):789-803.

[4]Ghosh A K,Michael C,Schatz M.Areal-time intrusion system based on learning program behavior[C]//Debar H,Wu S F(eds).Recent Advances in Intrusion Detection(RAID 2000).Toulouse:Spinger-Verlag,2000:93-109.

[5]Faraoun K M,Boukelif A.International Journal of Computational Intelligence[J].Neural Networks Learning Improvement using the Clustering Algorithm to Detect Network Intrusions,2007,3(2):161-168.

[6]Richhariya Vineet,Sharma Nupur.Optimized Intrusion Detection by CACC Discretization Via Nave Bayes and Clustering[J].International Journal of Computer Science&Network Security,2014,14(1):54-58.

[7]马儒宁,王秀丽,丁军娣.多层核心集凝聚算法[J].软件学报,2013,24(3):490-505.

[8]肖国荣.改进蚁群算法和支持向量机的网络入侵检测[J].计算机工程与应用,2014,50(3):75-78.

[9]Amin Hassanzadeh,Zhaoyan Xu,Radu Stoleru,et al.PRIDE:Practical Intrusion Detection in Resource Constrained Wireless Mesh Networks[J].Information and Communications Security,2013,8233:213-228.

[10]Krupa Brahmkstri,Devasia Thomas,S T Sawant,et al.Kshirsagar.Ontology Based Multi-Agent Intrusion Detection System for Web Service Attacks Using Self Learning[J].Networks and Communications(NetC om2013),2014,284:265-274.

一种基于层次聚类的双聚类算法 篇3

随着DNA芯片技术的不断发展, 基因表达数据实验得到极大地发展, 实验要求也相应提高, 使得传统聚类方法存在的缺陷日益明显。传统聚类仅在整个数据矩阵的单个方向聚类, 或者行方向或者列方向, 无法发现列集合下行的局部信息, 无法适应生物理论下数据的多功能特点。此外聚类经常会分散相互表达的数据块产生错误决策, 使得基因信息简单化。为了克服传统聚类方法存在的缺陷, Cheng和Church[1]首先提出双聚类并应用于基因表达数据挖掘中。双聚类被定义为一个具有统一标准的基因表达数据子集, 即分别通过交换矩阵的行和列, 将数值相似的数据聚合在一起形成子矩阵。为了评价该子矩阵的相似程度Cheng和Church [1]提出了均方残值的概念, 均方残值越低表明子矩阵的数据相似性越强, 即表达相关性越强, 集合捕获基因数据中有生物意义的基因信息越强。图1表示双聚类与聚类的区别。从图1中可以看出, 行方向为基因, 列方向为实验条件, 整个基因表达数据表达的是基因在不同的实验条件下表现出的不同数值。双聚类是数据矩阵中数据相似块, 双聚类与双聚类之间可以重叠。

Cheng和Church[1]运用贪心策略移动行和列来搜索双聚类。Yang et al [2]在Cheng和Church[1]算法的基础上, 提出了概率算法 (FLOC) , 该算法能够同时发现k个具有可重叠性的双聚类集合。Zhang et al [3]提出DBF算法即运用频繁模式挖掘确定双聚类, 该算法在第一阶段频繁模式下产生较高质量的双聚类集合, 在第二阶段迭代过程中, 通过进一步增加行和列扩大双聚类。

本文使用均方残值策略为双聚类的表达水平打分。为了避免随机值干扰并实现可重叠双聚类, 我们采用自底向上的思想。首先对基因表达数据的行和列分别使用层次聚类生成行集合和列集合, 行集合和列集合再分别组合成数据子矩阵, 并作为双聚类初始种子;然后采用启发式策略对种子分别添加行和列, 用全局优化找出均方残值最低的双聚类;并使用生成双聚类种子的热核图, 也叫做伪彩色图, 在伪彩色图中, 不同的数据表示不同的颜色, 数据相似度越大, 颜色也就越接近。最后将算法的结果与其他流行的算法结果进行比较。

2 双聚类模型

在基因表达数据矩阵中, A为表达矩阵, 行集合为基因集合X, 列集合为条件集合Y, aIJ为表达矩阵A的元素值, 表示在第j列条件下第i行基因的表达值。 (I, J) 对表示子矩阵AIJ, 其中I为基因集合的子集I⊆X, J为条件集合的子集J⊆Y。

双聚类的一致性表现在行和列的数据分别具有相似性。在理想状态下, 每行或者每列的值可以通过其他行和列减去一个值产生。这时, 双聚类中每个元素值根据它的行均值aiJ, 列均值aIj, 矩阵均值aIj确定。差值aIj-aiJ为第J列关于该双聚类中其他列的相对偏差;对行差值亦然。因而, 双聚类的元素值aij可以定义为行均值加上列均值减去矩阵均值。

aij=aiJ+aIj-aIJ (1)

然而基因数据中存在噪声, 双聚类并不一定是理想的, 因此定义残差量化一个元素的真实值与相关的行均值、列均值、矩阵均值的期望。非理想状态下元素值的残差定义为:

RSIJ (i, j) =aij-aiJ-aIj+aIJ (2)

为了评价双聚类在噪声影响下的质量, Cheng 和Church[1]在残差的基础上定义了Hscore (均方残值) 为双聚类行与列的相关性打分。均方残值公式如下:

其中, 存在当δ≥0, 如果满足H (I, J) ≤δ的条件, 则子矩阵AIJ叫做δ-双聚类。

3 双聚类算法

3.1 层次聚类算法生成种子

本节首先介绍层次聚类的基本概念, 再介绍层次聚类的算法, 并阐明该算法计算公式。一个层次聚类算法将数据组织成一棵聚类的树, 根据层次是自底向上还是自顶向下形成, 可以进一步将层次聚类算法分为凝聚型和分裂型聚类算法。根据所采用的计算类间距离方法的不同, 层次聚类算法主要有单连接SL ( Single- Link) , 全连接CL (Complete-Link) 和平均连接AL (Average- Link) 三种。单连接也叫做最近邻居, 就是求两个类之间的最短距离。本文采用分裂型、单连接算法, 分别对矩阵的行和列方向上进行聚类。在行方向进行层次算法时, 将所有行归于同一个类, 采用欧式距离计算每个行之间的距离, 并采用单连接的方法计算每个类之间的相似度, 当两个类之间的距离小于等于阈值, 则合并这两个类。然后将该层类分裂成两个下层的类, 重复计算, 直至达到符合条件为止。列方向方法同样。在matlab中实现的代码如下:

本文对数据矩阵的行和列分别使用层次聚类算法生成m, n聚类, 整个数据集就划分成m×n数据块, 将所有的数据块作为我们双聚类起始的种子。

3.2 启发式更新种子生成初始双聚类

采用启发式方法更新前面生成的种子。先添加列, 计算Hscore值是否超过设定的阈值, 没有则将该列添加到数据矩阵中;对行做同样的操作直到Hscore值达到设定的阈值。

3.3 全局优化生成最终的双聚类

生成种子的质量会影响双聚类的质量, 因此, 我们不是取Hscore值最小的前100个作为我们双聚类起始的种子, 而是使用所有的种子并进行分组更新优化。优化步骤如下:

(1) 初始化双聚类, 设定种子数为n ;

(2) 计算每个种子的行均值, 列均值, 矩阵均值, 和Hscore值, 启发式更新种子 ;

(3) 对于每个种子, 将自己的Hscore值与所经历过的最好Hscore值进行比较, 如果较好, 则将其作为当前的最好的Hscore值;

(3) 对于每组种子, 将该组Hscore值与所有组经历过的最好的Hscore值进行比较, 如果较好, 则将其作为当前的所有种子集合的最好Hscore值;

(4) 根据式子 (1) 、 (2) 扩张种子;判断是否达到终止条件, 如果达到则跳出, 否则转 (2) 。

4 实验结果比较

4.1 算法可行性验证

我们采用理想状态下无噪声干扰的模拟数据矩阵。矩阵大小为50×20, 取值为0或1。图2为模拟数据的热核图, 图3为模拟数据双聚类的热核图, 通过图2和图3可验证本算法的正确性。

4.2 植物数据的实验结果

植物数据包含三种类型植物叫做Setosa、Versicolour、Virginica, 每一种植物约有50个样本。列描述植物的属性分别为萼片长、宽, 花瓣长、宽。

从图4和图5的热核图可看出, 本文方法在四种属性条件下可以找出三种不同类型的植物。

4.3 酵母数据实验结果

进行测试使用的第三个数据集是酵母细胞表达数据。我们采用Cheng 和Church[1]使用的酵母数据集, 目的是比较双聚类的结果。该基因数据集包含2884个基因, 17个条件, 数据取值在[0, 600]之间, 其中缺失的数据用-1来替代。

种子好坏决定双聚类聚类最终结果, 使用层次聚类算法先将酵母细胞数据划分为1000个种子, 并全部用于双聚类的搜索中。

图6、图7两组图一个是原始酵母数据集热核图, 另一个是所有种子组合的热核图, 图7的热核图是通过层次聚类得到的结果, 从中可以看出, 颜色一致的部分是均方残值相似种子组合成, 双聚类在此基础上进行优化搜索, 既能减少搜索偶然性, 又能提高双聚类的搜索速度。

Cheng和Church[1]算法采用阈值为300, 在本算法中设定同样的阈值300, 双聚类的结果比较如表1所示。

4.4 算法存在的一些问题以及改进

对于层次聚类算法生成种子过程, 我们发现该算法对数据大小设定很敏感, 不当的设置会分裂好的双聚类, 并对最后双聚类的生成影响很大, 因此采用分裂层次聚类算法还有很多待改进的地方。

5 结束语

各种聚类算法及改进算法的研究 篇4

随着经济社会和科学技术的高速发展,各行各业积累的数据量急剧增长,如何从海量的数据中提取有用的信息成为当务之急。聚类是将数据划分成群组的过程,即把数据对象分成多个类或簇,在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类,能够识别密集和稀疏的区域,发现全局的分布模式,以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法,一般可分为基于层次的,基于划分的,基于密度的,基于网格的和基于模型的五大类。

2 数据挖掘对聚类算法的要求

(1)可兼容性:要求聚类算法能够适应并处理属性不同类型的数据。(2)可伸缩性:要求聚类算法对大型数据集和小数据集都适用。(3)对用户专业知识要求最小化。(4)对数据类别簇的包容性:即聚类算法不仅能在用基本几何形式表达的数据上运行得很好,还要在以其他更高维度形式表现的数据上同样也能实现。(5)能有效识别并处理数据库的大量数据中普遍包含的异常值,空缺值或错误的不符合现实的数据。(6)聚类结果既要满足特定约束条件,又要具有良好聚类特性,且不丢失数据的真实信息。(7)可读性和可视性:能利用各种属性如颜色等以直观形式向用户显示数据挖掘的结果。(8)处理噪声数据的能力。(9)算法能否与输入顺序无关。

3 各种聚类算法介绍

随着人们对数据挖掘的深入研究和了解,各种聚类算法的改进算法也相继提出,很多新算法在前人提出的算法中做了某些方面的提高和改进,且很多算法是有针对性地为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性,但对其它类型的数据或在其他领域应用中则不一定还有优势。所以,我们必须清楚地了解各种算法的优缺点和应用范围,根据实际问题选择合适的算法。

3.1 基于层次的聚类算法

基于层次的聚类算法对给定数据对象进行层次上的分解,可分为凝聚算法和分裂算法。

(1)自底向上的凝聚聚类方法。这种策略是以数据对象作为原子类,然后将这些原子类进行聚合。逐步聚合成越来越大的类,直到满足终止条件。凝聚算法的过程为:在初始时,每一个成员都组成一个单独的簇,在以后的迭代过程中,再把那些相互邻近的簇合并成一个簇,直到所有的成员组成一个簇为止。其时间和空间复杂性均为O(n2)。通过凝聚式的方法将两簇合并后,无法再将其分离到之前的状态。在凝聚聚类时,选择合适的类的个数和画出原始数据的图像很重要。

(2)自顶向下分裂聚类方法。与凝聚法相反,该法先将所有对象置于一个簇中,然后逐渐细分为越来越小的簇,直到每个对象自成一簇,或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。跟凝聚式方法的方向相反,从一个簇出发,一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂型方法,因为在较高的层很难进行正确的拆分。

3.2 基于密度的聚类算法

很多算法都使用距离来描述数据之间的相似性,但对于非凸数据集,只用距离来描述是不够的。此时可用密度来取代距离描述相似性,即基于密度的聚类算法。它不是基于各种各样的距离,所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是:只要一个区域中的点的密度(对象或数据点的数目)大过某个阈值,就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发,把密度足够大的区域连接起来,从而可发现任意形状的簇,并可用来过滤“噪声”数据。常见算法有DBSCAN,DENCLUE等。

3.3 基于划分的聚类算法

给定一个N个对象的元组或数据库,根据给定要创建的划分的数目k,将数据划分为k个组,每个组表示一个簇类(<=N)时满足如下两点:(1)每个组至少包含一个对象;(2)每个对象必须属于且只属于一个组。算法先随机创建一个初始划分,然后采用一种迭代的重定位技术,通过将对象根据簇类之间的差异从一个划分移到另一个划分来提高簇类内数据之间的相似程度。一种好的划分的一般准则是:在同一个类中的对象尽可能“接近”或相似,而不同类中的对象尽可能“远离”或不同。为了达到全局最优,基于划分的聚类会要求穷举所有可能的划分。典型的划包括:K-means,PAM,EM等。划分法收敛速度快,在对中小规模的数据库中发现球状簇很适用。缺点是它倾向于识别凸形分布大小相近、密度相近的聚类,不能发现分布形状比较复杂的聚类,它要求类别数目k可以合理地估计,且初始中心的选择和噪声会对聚类结果产生很大影响。还要求用户预先指定聚类个数。

3.4 基于网格的聚类算法

首先将数据空间量化为有限个单元的网格结构,然后对量化后的单个的单元为对象进行聚类。典型的算法有STING,CLIQUE等。网格聚类法处理速度快,处理时间与数据对象的数目无关,一般由网格单元的数目决定。缺点是只能发现边界是水平或垂直的聚类,不能检测到斜边界。该类算法也不适用于高维情况,因为网格单元的数目随着维数的增加而呈指数增长。另外还有下列问题:一是如何选择合适的单元大小和数目,二是怎样对每个单元中对象的信息进行汇总,三是存在量化尺度的问题。

3.5 基于模型的聚类算法

基于模型的方法给每一个聚簇假定了一个模型,然后去寻找能够很好满足这个模型的数据集。这个模型可能是数据点在空间中的密度分布函数,它由一系列的概率分布决定,也可能通过基于标准的统计数字自动决定聚类的数目。它的一个潜在假定是:目标数据集是由一系列的概率分布所决定的。一般有2种尝试方向:统计的方案和神经网络的方案。COBWEB是一种流行的简单增量概念聚类算法,以一个分类树的形式来创建层次聚类,它的输入对象用分类属性-值对来描述。COBWEB的优点为:可以自动修正划分中类的数目;不需要用户提供输入参数。缺点为:COBWEB基于这样一个假设:在每个属性上的概率分布是彼此独立的。但这个假设并不总是成立。且对于偏斜的输入数据不是高度平衡的,它可能导致时间和空间复杂性的剧烈变化,不适用于聚类大型数据库的数据。

3.6 模糊聚类算法

现实中很多对象没有严格的属性,其类属和形态存在着中介性,适合软划分。恰好模糊聚类具有描述样本类属中间性的优点,因此成为当今聚类分析研究的主流。常用的模糊聚类有动态直接聚类法、最大树法、FCM等。基本原理为:假设有N个要分析的样本,每个样本有M个可量化的指标,一般步骤为:(1)标准化数据:常用的数据标准化方法有:小数定标规范化,最大最小值规范化,标准差规范化等。(2)建立模糊相似矩阵,标定相似系数。(3)计算多极相似矩阵,计算整体相似关系矩阵,有传递闭包法,动态直接聚类法,最大树法等。(4)给定一个聚类水平,计算绝对相似矩阵。按行列调整绝对相似矩阵,每个分块即为一个分类。

3.6.1 模糊C-均值聚类算法

FCM算法用隶属度确定每个样本属于某个聚类的程度。它与K平均算法和中心点算法等相比,计算量可大大减少,因为它省去了多重迭代的反复计算过程,效率将大大提高。同时,模糊聚类分析可根据数据库中的相关数据计算形成模糊相似矩阵,形成相似矩阵之后,直接对相似矩阵进行处理即可,无须多次反复扫描数据库。根据实验要求动态设定m值,以满足不同类型数据挖掘任务的需要,适于高维度的数据的处理,具有较好的伸缩性,便于找出异常点。但m值根据经验或者实验得来,具有不确定性,可能影响实验结果。并且,由于梯度法的搜索方向总是沿着能量减小的方向,使得算法存在易陷入局部极小值和对初始化敏感的缺点。为克服上述缺点,可在FCM算法中引入全局寻优法来摆脱FCM聚类运算时可能陷入的局部极小点,优化聚类效果。

3.6.2 免疫进化算法

该算法借鉴生命科学中的免疫概念和理论在保留原算法优良特性的前提下,力图有选择、有目的地利用待求问题中的一些特征或知识来抑制其优化过程中出现的退化现象。免疫算法的核心在于免疫算子的构造,通过接种疫苗或免疫选择两个步骤来完成。免疫进化算法能提高个体的适应度和防止群体的退化,从而达到减轻原有进化算法后期的波动现象和提高收敛速度。例如IFCM、IFCL算法。它们既较大地提高了获取全局最优的概率,又减轻了基于遗传聚类算法在遗传后期的波动现象。进一步的工作是参数的适当选取和减小运行时间等。人对于客观事物的识别往往只通过一些模糊信息的综合,便可以获得足够精确的定论。

3.7 其它聚类算法

3.7.1 基于群的聚类方法

该法是进化计算的一个分支,模拟了生物界中蚁群、鱼群等在觅食或避敌时的行为。可分为蚁群算法ACO和PSO。蚁群聚类算法的许多特性,如灵活性、健壮性、分布性和自组织性等,使其非常适合本质上是分布、动态及又要交错的问题求解中,能解决无人监督的聚类问题,具有广阔的前景。PSO模拟了鱼群或鸟群的行为。在优化领域,PSO可以与遗传算法相媲美,并在预测精度和运行速度方面占优势。对ACO或PSO在数据挖掘中应用的研究仍处于早期阶段,要将这些方法用到实际的大规模数据挖掘的聚类分析中还需要做大量的研究工作。

3.7.2 基于粒度的聚类方法

从粒度的角度看,我们会发现聚类和分类有很大的相通之处:聚类操作实际上是在一个统一粒度下进行计算的;分类操作是在不同粒度下进行的。所以说在粒度原理下,聚类和分类是相通的,很多分类的方法也可以用在聚类方法中。作为一个新的研究方向,虽然目前粒度计算还不成熟,尤其是对粒度计算语义的研究还相当少,但相信随着粒度理论的不断发展,今后几年它必将在聚类算法及其相关领域得到广泛的应用。

3.7.3 谱聚法

谱聚类方法建立在谱图理论基础之上,并利用数据的相似矩阵的特征向量进行聚类,是一种基于两点间相似关系的方法,这使得该方法适用于非测度空间。它与数据点的维数无关,而仅与数据点的个数有关,可以避免由特征向量的过高维数所造成的奇异性问题。它又是一个判别式算法,不用对数据的全局结构作假设,而是首先收集局部信息来表示两点属于同一类的可能性;然后根据某一聚类判据作全局决策,将所有数据点划分到不同的数据集合中。通常这样的判据可以在一个嵌入空间中得到解释,该嵌入空间是由数据矩阵的某几个特征向量张成的。谱聚类算法成功原因在于:通过特征分解,可以获得聚类判据在放松了的连续域中的全局最优解。与其他算法相比,它不仅思想简单、易于实现、不易陷入局部最优解,而且具有识别非凸分布的聚类能力,非常适合于许多实际问题。目前,该算法已应用于语音识别、VLSI设计、文本挖掘等领域。

3.7.4 多种聚类方法的融合

实际应用的复杂性和数据的多样性往往使得单一的算法无能为力。因此,很多人对多种算法的融合进行了广泛研究并取得了一些成果。大致可分为以下几类:(1)基于传统聚类方法的融合,如CLIQUE、CUBN等。(2)模糊理论与其他聚类法的融合,如遗传+模糊C2均值混合聚类法等。(3)遗传算法与机器学习的融合。(4)传统聚类法与其他学科理论的融合,如谱算法等。总之,很多新算法是以上几类方法中两种或两种以上方法有机结合而得的,它们取长补短,优势明显,这也是我们数据挖掘研究人员要努力的研究方向之一。

4 结论

综上所述,分层聚类的突出优点是它能够生成比较规整的类集合,聚类结果不依赖元素的初始排列或输入次序,与聚类过程的先后次序无关,聚类结果比较稳定,不易导致类的重构。但计算开销较大,对异常数据比较脆弱。划分聚类的优势是运算量小,能用于处理庞大的样本数据,也为实时处理提供了一定的可能性。但要求用户必须事先给出要生成的簇的数目。网格聚类处理速度快,处理时间与数据对象的数目无关。缺点是只能发现边界是水平或垂直的聚类,而不能检测到斜边界。也不适用于高维情况,并存在量化尺度的问题。密度聚类的优点是一遍扫描,并可以在带有“噪声”的空间数据库中发现形状任意、个数不定的聚类。

通常可参考以下建议:(1)如果希望聚类算法对数据输入的顺序不敏感,可选用基于网格的STING算法。(2)如果目标数据库比较大,建议使用综合性的聚类算法,如CURE等。(3)如果聚类的形状是球形或者凸形,BIRCH和CLARANS比较适合。(4)将不同类型的聚类算法相互结合以满足不同的聚类要求。

5 结束语

各种聚类算法各有优缺点,又由于实际问题的复杂性和数据的多样性,使得无论哪一种方法都只能解决某一类问题。因此,用户应该根据具体问题具体分析,选择恰当的适合自己的聚类算法。近年来,随着数据挖掘、机器学习和人工智能等领域中传统方法的不断发展以及各种新方法和新技术的涌现,聚类算法得到了长足的发展。不难发现其新趋势:(1)传统聚类方法的融合发展。(2)新方法不断涌现。(3)根据实际需要,有针对性地融合众多领域的技术。总之,聚类算法综合了数据挖掘、模式识别、数学等众多领域的研究成果。随着这些领域中相关理论的发展、完善和相互渗透,以及新技术的出现,聚类分析将得到更快的发展。

参考文献

[1]孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):9.

[2]贺玲,吴玲达,蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用研究,2007,(01):16-19.

[3]陆云.聚类分析数据挖掘方法的研究与应用[D].合肥:安徽大学,2007.4.

[4]李东琦.聚类算法的研究[D].成都:西南交通大学,2007.5.

[5]李明华,刘全,刘忠,郗连霞.数据挖掘中聚类算法的新发展[J].计算机应用研究,2008,25(1):60-62.

[6]马帅,王腾蛟,唐世渭,等.一种基于参考点和密度的快速聚类算法[J].软件学报,2003,14(6):61-67.

[7]卜东波,白硕,李国杰.聚类/分类中的粒度原理[J].计算机学报,2002,25(8):810-816.

凝聚聚类算法 篇5

模糊K-Prototypes (FKP) 算法能够对包含数值属性和分类属性相混合的数据集进行有效聚类, 较好地处理大规模混合数据类型, 模糊技术体现聚类的边界特征, 使得更适合于含有噪声和缺失数据的数据库。

然而, FKP算法中仅仅考虑了分类属性对结果的不同影响, 隐含假定待分析样本中数值属性对分类的贡献是均匀的, 而在实际应用中, 由于构成样本特征矢量的各维特征来自不同的传感器, 存在量纲差异和精度的不同, 另外, 所选择的各维特征对分类的贡献程度也是有所不同的。

特征选择在数据挖掘、图象处理、数据压缩、模式识别等诸多方面有广泛的应用, 其基本任务是如何从许多特征中找出那些最有效的特征。ReliefF算法是公认的效果比较好的特征评估方法, 根据特征对近距离样本的区分能力来对特征进行评估, 最后给特征集中每一特征赋予一定的权重, 权重越大, 这个特征区分不同类的样本的重要性越强。

为了考虑特征矢量中各维特征对模式分类的不同贡献, 利用特征选择技术ReliefF对特征进行加权选择, 给予每个特征一个权重。在文章后面的实验部分, 通过实验结果可以看出该方法可以得到较为理想的聚类。

二、模糊K-Prototypes算法

K-Prototypes算法是由Huang提出的可以对分类属性和数值属性相混合的数据进行聚类的一种有效的算法。模糊K-Prototypes算法是对K-Prototypes算法的扩展, 对聚类中的对象分派隶属度, 通过交替更新聚类中心和划分矩阵使得目标函数值达到最小, 使得对于混合数据能够得到较好的聚类结果。

算法简单描述如下:假定数据库表是由m个属性A1, A2, ...Am描述的一组数据对象X={X1, X2, ...XN}, 其中Xi=[xi1, xi2, ..., xim]表示具有m个属性值的数据对象。设K是一个正整数, 对X聚类的目的就是要将N个对象划分到K个不同的类别中。一般使用以下代价函数最小作为聚类的准则:

其中, Z={Z1, Z2, ...ZK}, 元素Zk=[zk1, zk2, ...zkm]是能够代表聚类k的向量或称作聚类中心, ZkjDOM (Aj) , 1≤j≤m;W={wki}是K×N的划分矩阵, 每一个元素wki表示对象Xi划分到聚类k中的隶属度, 且满足

>1是模糊指数, d (Xi, Zk) 是差异测度, 假设数据对象Xi的m个属性中, [xi1, xi2, ..., xip]为数值属性, [xip, xip+1, ..., xim]为分类属性, 那么差异测度定义如下:

在第τ个属性上的取值, γτ是聚类的分类属性的权值。如果对所有聚类, γτ取同一值, 则用γ表示, 当γ=0时, 模糊K-Prototypes算法就是模糊K-means算法, 数据的分类属性不起作用, 聚类过程完全由它的数值属性决定。

划分矩阵的更新方法如下:

聚类中心的更新方法如下:对于数值型属性Aj (1≤j≤p) :

(Aj) , 且γ满足

其中nj表示分类属性Aj取值个数。

综上所述, 模糊K-Prototypes聚类算法步骤描述如下:

初始化聚类数K和聚类中心Z0, 并按公式 (7) 确定W0;

确定Zλ+1, 若│F (Wλ, Zλ+1) -F (Wλ, Zλ) │<ε, 算法停止, 返回Wλ, Zλ+1;

确定Wλ+1, 若│F (Wλ+1, Zλ+1) -F (Wλ, Zλ+1) │<ε, 算法停止, 返回Wλ+1, Zλ+1;

令λ=λ+1, 转至2。

三、Relief F算法

特征选择是从一系列相关或无关的特征中选择出相关性最强的若干特征来表征一个概念或事务的过程。选择不仅能减少特征提取阶段采集、变换等操作的计算压力, 还有利于降低噪声干扰、提高分类的准确性。

基本的Relief算法是由Kira和Rendell在1992年提出, 当时局限于解决两类的分类问题, 是一种权值搜索的特征子集选择方法, 它为每个特征赋予一个权值, 这个权值表征了特征与类别的相关性。其思想为好的特征应该使同类的样本接近, 而使不同类的样本之间远离, 通过不断调整权值逐步凸现特征的相关程度。Kononenko于1994年扩展了Relief算法, 提出了可以解决多类别情况、噪声数据和不完整数据的ReliefF算法。

设X={X1, X2, ..., Xn}是待分析的对象全体, 其中Xi={Xi1, Xi2, ..., Xim}表示第i个样本的m个属性值。ReliefF算法从所有的训练样本中随机选择S个样本, 对于其中任意一个样本Xi, 首先找出β个与Xi同类的最近邻的样本Hj (xi) , 然后在每一个与Xi不同类的子集中找出β个最近邻的样本Mj (C) , 计算样本在各个属性上的间隔, 并累加起来做为属性的权值。样本Xi更新属性p的权值可表示为:

对于离散属性, 函数定义为:

而对于连续属性:

其中, max (p) , min (p) 分别是该属性值的上下届。

当一个属性较容易区分类别时, 意味着同类样本间的距离较近, 而不同类样本间距离较远。因此, 如果属性与分类毫无关系, 那么其权值将趋于零或者很小的数。相反, 如果属性与类别存在很强的相关性, 那么其权值会较高。权值为负数表示同类近邻样本距离比非同类近邻样本距离还大。

函数diff同样用来寻找样本Xi的β个近邻样本。将所有属性的间隔累加起来, 从而得到任意两个样本的距离。

噪声会使特征数据发生微量的偏移, 干扰特征对类别的准确表示。当噪声影响多个属性时, 会严重干扰同类、非同类最近邻样本的判定, 从而对选择产生不利的后果。ReliefF算法中针对此问题, 选择使用β近邻样本而不是最近邻样本进行计算。通过β个样本的平均, 在一定程度上削弱了噪声对数据的影响。

ReliefF算法的步骤描述如下:

·初始化各个属性的权值:λτ0=0;

·随机选取样本Xi;

·找出与Xi最近邻的β个同类别的H (xi) ;

·对每个类c≠class (xi) , 找到与Xi最近邻的β个Mj (C) ;

·按 (6) 式更新每一个属性的权值;

四、改进的模糊K-Prototypes算法 (R-FKP算法)

原始的K-Prototypes算法, 利用权值来控制数值属性和分类型属性的比例, 但在数值属性中, 每一维数值特征对分类的贡献是均匀的。因此, 在K-Prototypes算法的基础上, 对每一维属性都进行加权, 这样, 聚类目标函数修正如下:

ReliefF算法是针对分类技术的, 在分类中, 每一个样本的类别标记是确定的, 而在聚类分析中, 每一个样本的类别标记是未知的, 这时, 我们可以先对待分析的样本集进行一次聚类。

在使用ReliefF算法时, 需要随机抽取一定数量的样本, 而在数据库中, 有时候不同类的样本数量相差悬殊。ReliefF的随机选择样本策略会使得小样本类别选中进行权值计算的概率较小, 甚至可能被忽略, 这样影响了对分离小样本有明显作用的属性。改进的方法是, 在抽取样本时按照第一次聚类得到的各类之间的数量比来从不同类中抽取。

利用ReliefF算法改进FKP算法的流程如下:

·执行FKP算法一次;

·按照各类的数量比, 抽取S个样本Xi (在同一类中选择隶属度较大的) , 分别找出与Xi同类以及不同类的最近邻的β个样本, 再按照前面所述ReliefF算法方法计算各个属性的权值;

·利用得到的权值对各维特征进行加权后, 再执行FKP算法, 就可以得到最后的聚类分析结果。

五、实验结果

本文将FKP算法和ReliefF改进后的算法进行了比较。实验数据Iris和Zoo都来自著名的UCI的机器学习数据库, 有关信息如表1所示。

(一) Iris样本

Iris样本是用来测试聚类或分类算法性能的一个著名基准函数数据集。在数据记录中, 每组数据包含Iris花的四种属性:萼片长度, 萼片宽度、花瓣长度和花瓣宽度。数据集包含三类:Setosa、Versicolor和Virginica, 每类各有50个样本。Hathaway在1995年给出了这组测试数据集的实际类中心位置分别为:Zl= (5.00, 3.42, 1.46, 0.24) , Z2= (5.93, 2.77, 4.

在实验中, FKP算法允许的最小误差为10-6, 模糊指数=1.1, 各算法的聚类中心数为其类别数, 训练样本数S=50, 近邻样本数β=7。将算法分别运行50次, 统计各项指标的平均值, E是分类错误的样本所占的比例, 实验结果如表2所示。

从表中数据可以看到, ReliefF改进的FKP算法, 错误率明显降低, 而且聚类中心更接近实际的类中心位置。其四个属性的平均权值为:[0.030797, 0.022 704, 0.11 518, 0.14981], 可以看出花瓣长度和花瓣宽度这两个属性的贡献比较大, 萼片宽度的贡献最小。

(二) Zoo样本

Zoo样本是动物园的实际数据集, 并且是混合数据集, 包含15个数值属性和1个分类型属性。样本最后被分成7个动物类别, 名称和包含的样本数为:哺乳类 (41) 、鸟类 (20) 、鱼类 (13) 、昆虫类 (8) 、软体类 (10) 、爬行类 (5) 和两栖类 (4) 。

在实验中, FKP算法允许的最小误差为模糊指数, 各算法的聚类中心数为其类别数。训练样本数S=50, 近邻样本数β=3。

表3为R-FKP算法得到的各个属性的权值, 权值越大, 对分类的贡献越大。可以看到, milk这个属性的权值最大, 它描述了动物是否哺乳, 而7个动物类别中哺乳类的数目最多, 正好与之对应。Venomous和domestic这两个属性的权值最小, 接近与0, 它们分别描述了动物是否有毒和是否家禽, 与分类的相关性比较小。predator这个属性的权值也较小, 它描述了是否是食肉动物。同时, 错分率E由原来的14.9%下降到5.94%。

六、结束语

本文在FKP算法的基础上, 将ReliefF算法与其相结合。实验表明, 该算法能够有效地提高聚类性能, 更便于分析各维属性对分类的贡献程度。

参考文献

[1]CHEN N, CHEN A, ZHOU L.Fuzzy K-prototypes algorithm for clustering mixed numeric and categorical valued data (in English) [J].软件学报, 2001.

[2]Kira K, Rendell L A.A practical approach to feature selection[A].In:Sleeman D, Edwards P, eds.Proceedings of the9th International Workshop on Machine Learning[C].San Francisco, CA:Morgan Kaufmann, 1992.

[3]Kononenko I.Estimating attributes:Analysis and extensions of Relief[A].In:De Raedt L, Bergadano F, eds·Proceedings of the7th European Conference on Machine Learning[C].Berlin:Springer, 1994.

谱聚类算法及其应用综述 篇6

聚类就是按照事物的某些特征,把事物分成若干类或簇,使得在同一个类内的对象之间最大程度相似,而不同类之间的对象最大程度不同。聚类分析在数据挖掘、空间数据处理、金融数据分类和入侵检测技术等领域中都得到了广泛应用。传统的聚类算法,如K-means和模糊C均值算法(Fuzzy C-Means,FCM)等大都建立在凸球形样本空间上,如果样本空间不为凸,算法就会陷入局部最优。因此,学者们开始研究一种新的聚类方法———谱聚类(Spectral Clustering,SC)算法。该算法由给定的样本数据集定义一个描述数据点之间相似度的亲和矩阵,并计算矩阵的特征值和特征向量,再选择合适的特征向量聚类不同的数据点[1]。谱聚类算法是一个判别式算法,其思想相对简单易于实现,具有识别非凸分布的聚类能力,适合处理许多实际应用问题。本文着重介绍谱聚类的基本理论、算法描述、当前应用及未来研究方向。

1 谱聚类基本理论与算法描述

1.1 图划分原理

谱聚类是一种基于图论的聚类方法。谱图理论是将数据聚类问题转化成图的多路划分问题,通过分割子图来聚类数据点。谱聚类能对任意形状的样本空间聚类,并能获得全局最优解,其基本思想是通过对样本数据的Laplacian(拉普拉斯)矩阵进行特征分解而得到的特征向量进行聚类。

假定将每个数据样本看作图中的顶点V,且样本中的数据对之间都有一定的相似性,由样本间的相似度,将顶点间的边E赋权重值W,得到一个无向加权图G=(V,E),V={v1,v2,...vn}表示点集。图G中,可将聚类问题转化为在图G上的图划分问题。图论中的划分准则一般有Minimum Cut、Average Cut、Normalized Cut、Min-max Cut、Ratio Cut、MN Cut等,划分准则的好坏对聚类结果的优劣产生很大影响。

1.1.1 最小割集准则(Minimum Cut)

谱图分割过程中,图的边值代表顶点之间的相关性大小,假设G被划分为A、B两个子图,最小割集的代价函数为:

其中,A∩B=φ,A∪B=V,权重Wij表示Vi与Vj之间的关系。属于子图A的顶点和属于子图B的顶点之间的所有边的和最小化,表示两个子图之间的相关性越小。Wu和Leahy[2]提出最小化上述Cut值来划分图G,即最小割集准则,是最常见也是最简单的评价方法。用该准则对一些图像进行分割也能产生不错的效果。该准则的缺点是分割图像时容易出现偏向小区域的情况。

1.1.2 规范割集准则(Normalized Cut)

根据谱图理论,Shi和Malik[3]提出新的目标代价函数NCut为:

规范割集准则即最小化NCut函数。与Minimum Cut相比,该准则能平衡类内样本间的相似度,也能平衡类间样本间的相异度,即可以避免偏向小区域分割。一般的聚类算法中,采用NCut准则的情况比较多。

1.1.3 比例割集准则(Ratio Cut)

为兼顾孤立点和均衡化问题,Hagen和Kahng[4]提出了比例割集准则,其目标代价函数RCut为:

其中,|A|、|B|分别表示子图A、B中顶点的个数,Cut(A,B)是最小割集准则的代价函数。最小化RCut函数引入了一个规模参数作为分母,加大了类间相似性,减低了过分分割的可能性,这是优于最小割集准则的方面,但该准则会使运行速度降低。

1.1.4 平均割集准则(Average Cut)

Sarkar和Soundararajan[5]提出平均割集准则,其目标函数AvCut为:

AvCut同NCut函数一样,最小化目标函数都能产生较准确的划分,两个都考虑了边界损失与分割区域之间的相关性比例。而AvCut准则更容易导致欠分割或易分割出只包含几个少数顶点的极小子图的缺点。

1.1.5 最小最大割集准则(Min-Max Cut)

最大最小割集准则[6]是为了能够使类内顶点的连接度强,类间的连续强度能够最小化,其目标函数MCut为:

可以看出,最小化MCut函数不仅要最小化Cut(A,B),还需要最大化Vol(A,A)和Vol(B,B)。该函数不易出现分割出只包含几个顶点的较小子图,倾向于产生平衡割集,可以有效避免孤立点的出现,但实现速度较慢。

1.1.6 多路规范割集准则(Multiway Normalized Cut)

Meila和Xu[7]在NCut割集函数的基础上,将图G分割成k个子图,将规范割集准则扩展到k类,这就是多路规范割集准则。其目标函数为:

可以看出,当k值为2,即分割成2个子图,聚类成两类时,MNCut函数和NCut函数是相同的。多路规范割集准则在实际应用中更有效、合理,只是优化问题和最小化问题比较难于解决。

1.2 谱聚类算法描述

谱聚类算法大多处理两类问题,多类聚类一般通过两路划分方法来实现。假定k是最终分类个数。谱聚类算法不是直接对数据点集的亲密度矩阵S进行分析而得出分类结果,而是要先计算k个最大的特征值和特征向量,没有充分利用包含有用划分信息的其它特征向量,其计算量较大,计算效率低,并且需要由用户事先给出聚类个数k。然后,用这些特征向量构造一个对称矩阵Q,最后对Q进行亲密度分析才得到数据集的最终聚类。因此,谱聚类算法得到的矩阵Q只是原始亲密度矩阵S的一个近似,近似的程度与k值相关,k越大,Q和S的误差越小。Q对比S的优势主要体现在对Q进行亲密度分析,比对S直接进行分析以实现的分类要容易。

目前,已经出现了许多谱聚类模型和算法,如PF算法、SM算法、SLH算法、KVV算法、MCut算法等几种迭代谱聚类算法;还有多路谱聚类算法,包括MS算法和NJW算法等。

2 当前研究和应用

2.1 图像分割应用

谱聚类算法最初应用在图像分割中。Shi和Malik[3]采用2-way NCut的谱聚类算法对图进行迭代分割,得到满意的聚类效果。但传统谱聚类算法易受到彩色图像大小和相似性测度的影响,会导致计算量大和分割精度低的问题。文献[8]提出了一种谱聚类分割算法,该算法基于超像素集测地线特征。先对彩色图像进行预分割得到超像素集,以超像素集为基础构造加权图,利用测地线距离特征和颜色特征构造权值矩阵,再应用NJW算法得到最终的分割结果,实验表明该算法在分割精度和计算复杂度上都有较大改善。

2.2 半监督学习应用

文献[9]提出了一种有约束的半监督谱聚类特征向量选择算法。该算法通过大量的监督信息寻找能体现数据结构特征的向量组合,来获得优于传统谱聚类算法的聚类性能,采用MNIST手写体数据集和UCI标准数据集进行仿真实验,结果验证了该算法的有效性和鲁棒性。

2.3 大数据分析应用

李斌等[10]提出了一种新的聚类算法NGKCA。首先利用谱聚类NJW算法对大数据集进行列降维和数据归一化处理,其次引入对初始值不敏感的粒子群算法对数据集进行行降维从而选出临时的聚类中心集,接着通过全局k-means算法获取聚类中心点,最后使用粒子群算法调整聚类中心点获取最终的聚类划分。实验结果表明,该算法具有更好的稳定性和更高的检测率、更优的时间复杂度,适用于解决大数据环境下的聚类问题。

2.4 其它应用

朱正伟[11]提出基于谱聚类的入侵检测技术,采用KDD CUP99数据集实验,结果表明谱聚类的检测率和误报率普遍优于K-means和层次聚类算法。周林等[12]提出基于谱聚类的聚类集成算法。先利用谱聚类的内在特性构造多样性的聚类成员,然后用连接三元组算法计算相似度矩阵,再对该矩阵使用谱聚类算法以得到集成结果。最后,用Nystrom采样算法有效降低了算法的计算复杂度,使得算法能扩展到大规模应用。实验结果表明,较之其它常见的聚类集成算法,该算法更优越、更有效,能较好地解决数据聚类、图像分割等问题。

3 研究展望

谱聚类算法是应用矩阵谱分析理论得到聚类数据的新特征,利用新的数据特征对原数据进行聚类。从国内外研究现状来看,谱聚类算法已被广泛运用于各个领域,并取得很好的效果。但是,谱聚类算法仍然存在一些亟待深入研究的问题:

(1)如何智能地确定需要聚类的个数。这不仅仅是谱聚类,也是其它很多聚类算法所面临的困难和挑战。目前已有的谱聚类算法中,如RCut、NLDR(Nonlinear Dimensionality Reduction,非线性降维)算法能够自适应确定聚类个数,但是聚类效果并不是很理想,亟需改进。

(2)如何解决模糊聚类问题。谱聚类算法来源于谱图分割领域,图分割后一般子图与子图之间是不重叠的。谱聚类算法在面对这种情况时往往聚类效果不佳。

(3)如何运用到海量数据中。谱聚类算法涉及到求解大型矩阵的特征值分解问题,其计算复杂度高、计算量和存储量太大,不利于在大规模数据中计算和扩展,这对谱聚类的应用前景非常不利。虽然己经有研究者提出优化这一问题的方法,但仍然是未来研究的方向。

(4)如何与深度学习相融合。近年来深度学习发展迅猛,文献[13]介绍了谱算法中算子谱刻画映射的能力,学者们开始思考将谱聚类算法与深度学习相结合并帮助提高算法效率。

摘要：由于性能优越,谱聚类成为近年来聚类算法研究的热点。谱聚类算法可以在任意形状的样本空间上聚类,并能获得全局最优解。介绍了谱图的基本理论及其划分准则,探讨了谱聚类算法,并针对当前谱聚类应用展望了未来研究方向。

聚类算法的改进的研究 篇7

Web文本挖掘作为Web数据挖掘的一个重要分支,可以对文档集合的内容进行分类、聚类、关联分析等。聚类是知识发现的重要工具,它是一种无指导的学习,能够从海量的数据中分析并挖掘出人们需要的东西,已经被广泛应用到信息管理、搜索引擎、推荐系统等多个领域。

1 类间距离

聚类就是按照对象的类间距离将距离近的放在一类,距离远的放在一类。聚类时常用的类间距离公式如下:

Single linkage(单连通):

Complete linkage(完全连通):

Average group(平均连通):

Centroid distance(质心距离):

2 层次聚类算法

2.1 传统层次凝聚算法

根据结果的生成顺序,层次聚类可以分为两类:分裂的层次聚类、凝聚的层次聚类。大部分层次聚类都属于后者,它先把每个对象看做一个类,然后将距离最近的两个类合并,直到所有对象都在一个类中,或者达到预定的停止条件。

下面举个例子来理解一下层次聚类算法的执行过程。假设有8个对象,每个对象有两个(也可以是多个)属性1x、2x:A(1,1)、B(3,4)、C(1.5,1.5)、D(2,3)、E(4,4)、F(3,3.5)、G(5,5)、H(5,3.5)。我们选用欧几里得距离计算对象之间的初始化距离矩阵,结果如表1所示。

我们选用公式1,找到距离的最小值dB→F=0.50,然后将B、F归为一类(B,F),重新计算距离矩阵。经过一系列地合并、计算距离矩阵,最后我们得到聚类的层次为((((((B,F),E),D),H),G),(A,C)),如图1所示。

分析上面的计算过程,第一次合并的是距离最小的两个类,重新计算该类与其他类之间的距离时我们选择的是公式1,例如:d((B,F),E)→D=min(dBD,dFD,dED),其中dBD、dFD和dED都是从初始距离矩阵中得到的,即新的距离矩阵的值都来源于初始距离矩阵。第二次迭代时是从新的距离矩阵中取的最小值,那么这个最小值应该是初始距离矩阵中的次小值。依此类推,直到所有的对象合并完为止。

2.2 改进后的层次聚类算法

在上面的例子中可以看出,合并过程中每次迭代都要重新计算类间距离,比较浪费时间,我们发现合并是按照初始距离矩阵从小到大的顺序进行的,如果我们把初始距离矩阵中的元素用线性结构存储起来,对其进行从小到大的排序,那么合并类时只要顺序遍历线性结构就行了,这样就提高了层次聚类的速度。具体描述如下:

(1)将给定数据中的每个对象看做一类,计算各个类之间的距离dij,将距离存储在一维数组中。

(2)对一维数组进行升序排列。

(3)对于数组中的当前元素dij(即对象ix与xj之间的距离),可以分为三种情况:(1)如果xi∈Cm,xj∈Cn,则Ck=Cm∪Cn。(2)如果xi∈Cm,xj没有合并到类中,则Cm=Cm∪xj。(3)如果ix、xj都没有合并到类中,则

(4)重复步骤(3),直到数组中所有的元素处理完毕。

文献证明了改进后的层次聚类算法的运行速度提高了近3倍,而聚类的结果不受影响。

3 k-means算法

3.1 传统k-means聚类算法

k-means算法是一种应用最广泛的划分算法,它的聚类结果是平面的,一般用不相交的集合来表示。k-means聚类算法的基本思想:给定n个数据,随机地选择k个对象作为初始聚类中心,计算各个对象到聚类中心的聚类,将剩下的对象分配到聚类最近的类中,然后重新计算聚类中心,不断重复这个过程,直到所有的聚类不再发生变化为止。

下面举个例子来理解一下k-means算法的执行过程。假设有6个对象,每个对象有两个(也可以是多个)属性1x、2x:A(1,1)、B(2,1)、C(3,4)、D(4,3)、E(2,2)、F(5,4),我们的目标是将它们归为两类即K=2。选用A、B作为初始聚类中心,则C1=(1,1),C2=(2,1),选用欧几里得距离计算距离矩阵,如表2所示。

我们根据公式1,将对象划分到距离最近的那个类中,即,然后重新计算聚类中心,采用各个对象的平均值作为新的聚类中心,则再计算各个对象到新的聚类中心的距离。经过一系列地划分、计算聚类中心,最后得到的聚类结果为:C1=(A,B,E),C2=(C,D,F),如图2所示。

在k-means算法执行过程中,每次迭代都把数据分配到距离最近的类中,新的分类产生后,需要计算新的聚类中心,这个过程的时间复杂度为O(nd),则该算法总的时间复杂度为O(nkd),其中d是对象的维数,k是指定的聚类个数,n是数据对象的总个数。当数据量比较大时,算法的时间开销是非常大的。

3.2 改进后的k-means算法

在计算对象到聚类中心的距离时,我们采用的是欧几里得距离,该种计算方法具有4种性质(文档与自身的距离为0、非负性、对称性、三角不等式),其中三角不等式即从对象i到对象j的直接距离小于等于途径其他对象的距离。k-means算法每次迭代都要计算对象到每个聚类中心的距离,通过比较将对象分配到距离最近的聚类中,这些不必要的比较和距离计算比较浪费时间,我们可以利用三角不等式来减少每次迭代的计算次数,这样就可以处理大数据量时的时间开支问题。

具体流程为:

(1)任意选择k个对象作为初始聚类中心。

(2)计算每两个聚类中心的距离d(C i,Cj),其中i,j=1,2,k。

(3)对于每个对象ix,设它当前属于类ξi,ξi类的中心为iC,计算ix与iC的距离d(x i,C i)。如果d(C i,Cj)≥2d(x i,C i),则ix所在的类不变,否则,计算d(x i,Cj);如果d(x i,Cj)

(4)重复(2)、(3)步,直到所有聚类都不变化。

文献证明了该改进算法获得了很好的聚类效果,提高了算法的效率。

4 混合文本聚类算法

凝聚型层次聚类算法能够生成层次化的嵌套簇,准确度较高,但时间复杂性较高,运行速度较慢,在进行合并之后无法回溯。k-means聚类算法的运行速度较快,但是必须事先确定k的取值,对初始聚类中心的依赖性比较强,不适合发现非凸形状的聚类,虽然可以保证局部最小,但不能保证全局最小。

如果将凝聚型层次聚类算法与k-means算法结合起来,利用凝聚型层次聚类算法来产生k-means算法所需要的k值和初始聚类中心,可以有效的克服k-means算法的不足。

为了能更准确的发现用户的兴趣所在,本算法将2.2节改进的凝聚型层次聚类算法和3.2节改进的k-means聚类算法结合起来。

具体流程如下:

(1)计算给定的文档集合D={d 1,di,dn}中各个数据间的距离dij,将距离存放在一维数组中。

(2)对一维数组进行升序排列。

(3)将文档集合D看成是一个聚类C={c 1,ci,cn},其中ci={d i}。

(4)设定一阈值ξm,如果数组中的当前元素dij≤ξm,则分为三种情况:(1)如果di∈cm,dj∈cn,则ck=cm∪cn。(2)如果di∈cm,dj没有合并到类中,则cm=cm∪dj。(3)如果di、dj都没有合并到类中,则ck=di∪dj。重复步骤(4),直到数组中所有元素处理完。否则如果dij>ξm,凝聚算法结束,得到含有k个子类的聚类C={c 1,ci,ck}。

(5)将C={c 1,ci,ck}作为k-means算法的初始聚类中心。

(6)计算每两个聚类中心的距离d(c i,c j)。

(7)对于D中的每个文档di,设它当前属于类ξi,ξi类的中心为ic,计算di与ic的距离d(d i,c i)。如果d(c i,c j)≥2d(d i,c i),则di所在的类不变,否则,计算d(d i,c j);如果d(d i,c j)

(8)重复步骤(6)、(7),直到所有聚类都不再变化。

5 结论

本文提出的混合文本聚类算法的难点就是阈值的确定,要通过相关领域知识来选定阈值,才能得到满意的聚类结果。笔者将该算法用到了一个小型的个性化搜索引擎中,通过试验将阈值定义为5.0,对用户的浏览记录进行聚类,较好的挖掘出了用户感兴趣的内容。

随着Web技术的发展以及用户的需求和行为日益多元化,如何从海量的数据中分析并挖掘出人们需要的内容,个性化的搜索引擎已经成为人们研究的热点,聚类的研究也将成为人们研究的热点。

参考文献

[1]段明秀,杨路明.对层次聚类算法的改进[J].湖南理工学院学报(自然科学版).2008.

[2]王会芬.基于Web的网页聚类系统的研究与实现[D].天津大学硕士学位论文.2005.

[3]严华.一种改进的k-means算法[J].计算机与现代化.2009.

[4]易珺.改进的k-means算法在客户细分中的应用研究[J].微型机与应用.2005.