导航:首页 > 源码编译 > 聚类算法识别行为

聚类算法识别行为

发布时间:2022-04-14 01:21:32

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

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

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

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

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

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

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

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

(1)聚类算法识别行为扩展阅读:

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

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

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

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

Ⅱ 四种聚类方法之比较

四种聚类方法之比较
介绍了较为常见的k-means、层次聚类、SOM、FCM等四种聚类算法,阐述了各自的原理和使用步骤,利用国际通用测试数据集IRIS对这些算法进行了验证和比较。结果显示对该测试类型数据,FCM和k-means都具有较高的准确度,层次聚类准确度最差,而SOM则耗时最长。
关键词:聚类算法;k-means;层次聚类;SOM;FCM
聚类分析是一种重要的人类行为,早在孩提时代,一个人就通过不断改进下意识中的聚类模式来学会如何区分猫狗、动物植物。目前在许多领域都得到了广泛的研究和成功的应用,如用于模式识别、数据分析、图像处理、市场研究、客户分割、Web文档分类等[1]。
聚类就是按照某个特定标准(如距离准则)把一个数据集分割成不同的类或簇,使得同一个簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起,不同数据尽量分离。
聚类技术[2]正在蓬勃发展,对此有贡献的研究领域包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等。各种聚类方法也被不断提出和改进,而不同的方法适合于不同类型的数据,因此对各种聚类方法、聚类效果的比较成为值得研究的课题。
1 聚类算法的分类
目前,有大量的聚类算法[3]。而对于具体应用,聚类算法的选择取决于数据的类型、聚类的目的。如果聚类分析被用作描述或探查的工具,可以对同样的数据尝试多种算法,以发现数据可能揭示的结果。
主要的聚类算法可以划分为如下几类:划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法[4-6]。
每一类中都存在着得到广泛应用的算法,例如:划分方法中的k-means[7]聚类算法、层次方法中的凝聚型层次聚类算法[8]、基于模型方法中的神经网络[9]聚类算法等。
目前,聚类问题的研究不仅仅局限于上述的硬聚类,即每一个数据只能被归为一类,模糊聚类[10]也是聚类分析中研究较为广泛的一个分支。模糊聚类通过隶属函数来确定每个数据隶属于各个簇的程度,而不是将一个数据对象硬性地归类到某一簇中。目前已有很多关于模糊聚类的算法被提出,如着名的FCM算法等。
本文主要对k-means聚类算法、凝聚型层次聚类算法、神经网络聚类算法之SOM,以及模糊聚类的FCM算法通过通用测试数据集进行聚类效果的比较和分析。
2 四种常用聚类算法研究
2.1 k-means聚类算法
k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高,所以在对大规模数据进行聚类时被广泛应用。目前,许多算法均围绕着该算法进行扩展和改进。
k-means算法以k为参数,把n个对象分成k个簇,使簇内具有较高的相似度,而簇间的相似度较低。k-means算法的处理过程如下:首先,随机地选择k个对象,每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象,根据其与各簇中心的距离,将它赋给最近的簇;然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛。通常,采用平方误差准则,其定义如下:

这里E是数据库中所有对象的平方误差的总和,p是空间中的点,mi是簇Ci的平均值[9]。该目标函数使生成的簇尽可能紧凑独立,使用的距离度量是欧几里得距离,当然也可以用其他距离度量。k-means聚类算法的算法流程如下:
输入:包含n个对象的数据库和簇的数目k;
输出:k个簇,使平方误差准则最小。
步骤:
(1) 任意选择k个对象作为初始的簇中心;
(2) repeat;
(3) 根据簇中对象的平均值,将每个对象(重新)赋予最类似的簇;
(4) 更新簇的平均值,即计算每个簇中对象的平均值;
(5) until不再发生变化。
2.2 层次聚类算法
根据层次分解的顺序是自底向上的还是自上向下的,层次聚类算法分为凝聚的层次聚类算法和分裂的层次聚类算法。
凝聚型层次聚类的策略是先将每个对象作为一个簇,然后合并这些原子簇为越来越大的簇,直到所有对象都在一个簇中,或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类,它们只是在簇间相似度的定义上有所不同。四种广泛采用的簇间距离度量方法如下:

这里给出采用最小距离的凝聚层次聚类算法流程:
(1) 将每个对象看作一类,计算两两之间的最小距离;
(2) 将距离最小的两个类合并成一个新类;
(3) 重新计算新类与所有类之间的距离;
(4) 重复(2)、(3),直到所有类最后合并成一类。
2.3 SOM聚类算法
SOM神经网络[11]是由芬兰神经网络专家Kohonen教授提出的,该算法假设在输入对象中存在一些拓扑结构或顺序,可以实现从输入空间(n维)到输出平面(2维)的降维映射,其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。
SOM网络包含输入层和输出层。输入层对应一个高维的输入向量,输出层由一系列组织在2维网格上的有序节点构成,输入节点与输出节点通过权重向量连接。学习过程中,找到与之距离最短的输出层单元,即获胜单元,对其更新。同时,将邻近区域的权值更新,使输出节点保持输入向量的拓扑特征。
算法流程:
(1) 网络初始化,对输出层每个节点权重赋初值;
(2) 将输入样本中随机选取输入向量,找到与输入向量距离最小的权重向量;
(3) 定义获胜单元,在获胜单元的邻近区域调整权重使其向输入向量靠拢;
(4) 提供新样本、进行训练;
(5) 收缩邻域半径、减小学习率、重复,直到小于允许值,输出聚类结果。
2.4 FCM聚类算法
1965年美国加州大学柏克莱分校的扎德教授第一次提出了‘集合’的概念。经过十多年的发展,模糊集合理论渐渐被应用到各个实际应用方面。为克服非此即彼的分类缺点,出现了以模糊集合论为数学基础的聚类分析。用模糊数学的方法进行聚类分析,就是模糊聚类分析[12]。
FCM算法是一种以隶属度来确定每个数据点属于某个聚类程度的算法。该聚类算法是传统硬聚类算法的一种改进。

算法流程:
(1) 标准化数据矩阵;
(2) 建立模糊相似矩阵,初始化隶属矩阵;
(3) 算法开始迭代,直到目标函数收敛到极小值;
(4) 根据迭代结果,由最后的隶属矩阵确定数据所属的类,显示最后的聚类结果。
3 四种聚类算法试验
3.1 试验数据
实验中,选取专门用于测试分类、聚类算法的国际通用的UCI数据库中的IRIS[13]数据集,IRIS数据集包含150个样本数据,分别取自三种不同的莺尾属植物setosa、versicolor和virginica的花朵样本,每个数据含有4个属性,即萼片长度、萼片宽度、花瓣长度,单位为cm。在数据集上执行不同的聚类算法,可以得到不同精度的聚类结果。
3.2 试验结果说明
文中基于前面所述各算法原理及算法流程,用matlab进行编程运算,得到表1所示聚类结果。

如表1所示,对于四种聚类算法,按三方面进行比较:(1)聚错样本数:总的聚错的样本数,即各类中聚错的样本数的和;(2)运行时间:即聚类整个过程所耗费的时间,单位为s;(3)平均准确度:设原数据集有k个类,用ci表示第i类,ni为ci中样本的个数,mi为聚类正确的个数,则mi/ni为第i类中的精度,则平均精度为:

3.3 试验结果分析
四种聚类算法中,在运行时间及准确度方面综合考虑,k-means和FCM相对优于其他。但是,各个算法还是存在固定缺点:k-means聚类算法的初始点选择不稳定,是随机选取的,这就引起聚类结果的不稳定,本实验中虽是经过多次实验取的平均值,但是具体初始点的选择方法还需进一步研究;层次聚类虽然不需要确定分类数,但是一旦一个分裂或者合并被执行,就不能修正,聚类质量受限制;FCM对初始聚类中心敏感,需要人为确定聚类数,容易陷入局部最优解;SOM与实际大脑处理有很强的理论联系。但是处理时间较长,需要进一步研究使其适应大型数据库。
聚类分析因其在许多领域的成功应用而展现出诱人的应用前景,除经典聚类算法外,各种新的聚类方法正被不断被提出。

Ⅲ 非监督模式识别的经典方法是聚类,聚类的三个要点是什么

第一,聚类分析是一种无监督学习的方法。
第二,聚类的对象是没有分类标记的训练样本。
第三,聚类的目的是将数据集划分为若干个互不相交的子集。

Ⅳ 什么是聚类分析聚类算法有哪几种

聚类分析是分类算法中的一种,是无监督的,不需要训练。
聚类算法分为:硬聚类算法和软聚类算法,硬聚类中最经典的是K均值聚类算法,就是大家所说的K-means算法,软聚类算法中最经典的是模糊C均值聚类算法,就是FCM。后续的一些聚类算法都是在这两种上改进的

Ⅳ 用于数据挖掘的聚类算法有哪些,各有何优势

聚类方法的分类,主要分为层次化聚类算法,划分式聚类算法,基于密度的聚类算法,基于网格的聚类算法,基于模型的聚类算法等。

而衡量聚类算法优劣的标准主要是这几个方面:处理大的数据集的能力;处理任意形状,包括有间隙的嵌套的数据的能力;算法处理的结果与数据输入的顺序是否相关,也就是说算法是否独立于数据输入顺序;处理数据噪声的能力;是否需要预先知道聚类个数,是否需要用户给出领域知识;算法处理有很多属性数据的能力,也就是对数据维数是否敏感。

.聚类算法主要有两种算法,一种是自下而上法(bottom-up),一种是自上而下法(top-down)。这两种路径本质上各有优势,主要看实际应用的时候要根据数据适用于哪一种,Hierarchical methods中比较新的算法有BIRCH主要是在数据体量很大的时候使用;ROCK优势在于异常数据抗干扰性强……

关于数据挖掘的相关学习,推荐CDA数据师的相关课程,课程以项目调动学员数据挖掘实用能力的场景式教学为主,在讲师设计的业务场景下由讲师不断提出业务问题,再由学员循序渐进思考并操作解决问题的过程中,帮助学员掌握真正过硬的解决业务问题的数据挖掘能力。这种教学方式能够引发学员的独立思考及主观能动性,学员掌握的技能知识可以快速转化为自身能够灵活应用的技能,在面对不同场景时能够自由发挥。点击预约免费试听课。

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

一种面向高维数据的集成聚类算法
聚类集成已经成为机器学习的研究热点,它对原始数据集的多个聚类结果进行学习和集成,得到一个能较好地反映数据集内在结构的数据划分。很多学者的研究证明聚类集成能有效地提高聚类结果的准确性、鲁棒性和稳定性。本文提出了一种面向高维数据的聚类集成算法。该方法针对高维数据的特点,先用分层抽样的方法结合信息增益对每个特征簇选择合适数量比较重要的特征的生成新的具代表意义的数据子集,然后用基于链接的方法对数据子集上生成的聚类结果进行集成.最后在文本、图像、基因数据集上进行实验,结果表明,与集成前的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均值算法以及基于链接的聚类集成算法在四个评价标准上的聚类性能,能够看出我们的算法在聚类性能上有一定改善。

Ⅶ 聚类算法有哪些分类

聚类算法的分类有:

1、划分法

划分法(partitioning methods),给定一个有N个元组或者纪录的数据集,分裂法将构造K个分组,每一个分组就代表一个聚类,K小于N。而且这K个分组满足下列条件:

(1) 每一个分组至少包含一个数据纪录;

(2)每一个数据纪录属于且仅属于一个分组(注意:这个要求在某些模糊聚类算法中可以放宽);

2、层次法

层次法(hierarchical methods),这种方法对给定的数据集进行层次似的分解,直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。

例如,在“自底向上”方案中,初始时每一个数据纪录都组成一个单独的组,在接下来的迭代中,它把那些相互邻近的组合并成一个组,直到所有的记录组成一个分组或者某个条件满足为止。

3、密度算法

基于密度的方法(density-based methods),基于密度的方法与其它方法的一个根本区别是:它不是基于各种各样的距离的,而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。

4、图论聚类法

图论聚类方法解决的第一步是建立与问题相适应的图,图的节点对应于被分析数据的最小单元,图的边(或弧)对应于最小处理单元数据之间的相似性度量。因此,每一个最小处理单元数据之间都会有一个度量表达,这就确保了数据的局部特性比较易于处理。图论聚类法是以样本数据的局域连接特征作为聚类的主要信息源,因而其主要优点是易于处理局部数据的特性。

5、网格算法

基于网格的方法(grid-based methods),这种方法首先将数据空间划分成为有限个单元(cell)的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快,通常这是与目标数据库中记录的个数无关的,它只与把数据空间分为多少个单元有关。

代表算法有:STING算法、CLIQUE算法、WAVE-CLUSTER算法;

6、模型算法

基于模型的方法(model-based methods),基于模型的方法给每一个聚类假定一个模型,然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是:目标数据集是由一系列的概率分布所决定的。

通常有两种尝试方向:统计的方案和神经网络的方案。

(7)聚类算法识别行为扩展阅读:

聚类算法的要求:

1、可伸缩性

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

我们需要具有高度可伸缩性的聚类算法。

2、不同属性

许多算法被设计用来聚类数值类型的数据。但是,应用可能要求聚类其他类型的数据,如二元类型(binary),分类/标称类型(categorical/nominal),序数型(ordinal)数据,或者这些数据类型的混合。

3、任意形状

许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是,一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。

4、领域最小化

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

5、处理“噪声”

绝大多数现实中的数据库都包含了孤立点,缺失,或者错误的数据。一些聚类算法对于这样的数据敏感,可能导致低质量的聚类结果。

6、记录顺序

一些聚类算法对于输入数据的顺序是敏感的。例如,同一个数据集合,当以不同的顺序交给同一个算法时,可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。

Ⅷ 聚类算法有什么作用讲的是什么

聚类的用途是很广泛的。
在商业上,聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来,并且概括出每一类消费者的消费模式或者说习惯。它作为数据挖掘中的一个模块,可以作为一个单独的工具以发现数据库中分布的一些深层的信息,并且概括出每一类的特点,或者把注意力放在某一个特定的类上以作进一步的分析;并且,聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。

Ⅸ 如何对用户进行聚类分析

需要搜集用户的哪些特征?

聚类分析变量选择的原则是:在哪些变量组合的前提,使得类别内部的差异尽可能的小,即同质性高,类别间的差异尽可能的大,即同质性低,并且变量之间不能存在高度相关。

常用的用户特征变量有:


人口学变量:如年龄、性别、婚姻、教育程度、职业、收入等。通过人口学变量进行分类,了解每类人口的需求有何差异。


用户目标:如用户为什么使用这个产品?为什么选择线上购买?了解不同使用目的的用户的各自特征,从而查看各类目标用户的需求。


用户使用场景:用户在什么时候,什么情况下使用这个产品?了解用户在各类场景下的偏好/行为差异。


用户行为数据:如使用频率,使用时长,客单价等。划分用户活跃等级,用户价值等级等。


态度倾向量表:如消费偏好,价值观等,看不同价值观、不同生活方式的群体在消费取向或行为上的差异。

需要多少样本量?

没有限制,通常情况下与实际应用有关,如果非要加一个理论的限制,通常认为,样本的个数要大于聚类个数的平方。

①如果需要聚类的数据量较少(<100),那么三种方法(层次聚类法,K-均值聚类法,两步聚类法)都可以考虑使用。优先考虑层次聚类法,因为层次聚类法产生的树状图更加直观形象,易于解释,并且,层次聚类法提供方法、距离计算方式、标准化方式的丰富程度也是其他两种方法所无法比拟的。

②如果需要聚类的数据量较大(>1000),应该考虑选择快速聚类别法或者两步聚类法进行。

③如果数据量在100~1000之间,理论上现在的计算条件是可能满足任何聚类方法的要求的,但是结果的展示会比较困难,例如不可能再去直接观察树状图了。

应用定量方法还是定性方法?

聚类分析是一种定量分析方法,但对聚类分析结果的解释还需要结合定性资料讨论。

1.聚类分析的定义与用途

聚类分析(Cluster Analysis)是一种探索性的数据分析方法,根据指标/变量的数据结构特征,对数据进行分类,使得类别内部的差异尽可能的小,即同质性高,类别间的差异尽可能的大,即同质性低。

2.聚类分析的方法

①层次聚类法(Hierarchical),也叫系统聚类法。既可处理分类变量,也可处理连续变量,但不能同时处理两种变量类型,不需要指定类别数。聚类结果间存在着嵌套,或者说层次的关系。

②K-均值聚类法(K-Means Cluster),也叫快速聚类法。针对连续变量,也可处理有序分类变量,运算很快,但需要指定类别数。K-均值聚类法不会自动对数据进行标准化处理,需要先自己手动进行标准化分析。

③两步聚类法(Two-Step Cluster):可以同时处理分类变量和连续变量,能自动识别最佳的类别数,结果比较稳定。如果只对连续变量进行聚类,描述记录之间的距离性时可以使用欧氏(Euclidean)距离,也可以使用对数似然值(Log-likelihood),如果使用前者,则该方法和传统的聚类方法并无太大区别;但是若进行聚类的还有离散变量,那么就只能使用对数似然值来表述记录间的差异性。当聚类指标为有序类别变量时,Two-Step Cluster出来的分类结果没有K-means cluster的明晰,这是因为K-means算法假定聚类指标变量为连续变量。

3.聚类分析的步骤

①确定研究目的:研究问题关注点有哪些、是否有先验分类数…

②问卷编制:态度语句李克特项目、有序类别…

③确定分析变量:问卷变量的类型,连续or分类,有序类别or无序类别、是否纳入后台数据,变量间相关性低…

④聚类分析:聚类分析方法选择、数据标准化方法、聚类类别数确定…

⑤结果检验:类别间差异分析、是否符合常理…

⑥聚类结果解释:类别的命名、类别间的差异、结合定性资料解释…

Ⅹ 聚类算法有哪几种

聚类分析计算方法主要有: 层次的方法(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. 初始聚类中心的选择对聚类结果有较大的影响。

阅读全文

与聚类算法识别行为相关的资料

热点内容
个人idc销售源码 浏览:70
资治通鉴下载pdf 浏览:456
北京英雄联盟服务器云空间 浏览:781
算法铺砖预留一个空不铺 浏览:933
江苏java程序员接私活项目 浏览:180
wap商城源码下载 浏览:845
天猫精灵接人源码 浏览:293
香港加密货币监管跟踪研究 浏览:543
广州五险一金算法 浏览:449
运用列主元消去法编程 浏览:864
如何在图片中加密 浏览:741
android停止补间动画 浏览:727
空气压缩机图例 浏览:884
怎么让应用加密oppo 浏览:818
甜糖服务器为什么老是网络变化 浏览:123
部队吃的压缩饼干 浏览:88
linux下安装mongodb 浏览:92
phptextarea换行符 浏览:503
做衣服pdf 浏览:801
lcb2服务器怎么用 浏览:216