聚类分析算法（精选12篇）
聚类分析算法 篇1
0 引 言
随着数据挖掘研究领域技术的发展,作为数据挖掘主要方法之一的聚类算法,也越来越受到人们的关注。数据挖掘(Data Mining)又称知识发现(KDD),其实是知识发现过程的一个步骤.它是从数据库、数据仓库或其他信息库中便捷地抽取出以前未知的、隐含的、有用的信息,所挖掘出来的知识可应用于信息管理、决策支持、过程控制和其它许多应用。所谓聚类(Clustering),就是把大量的d维数据样本(n个)聚集成k个类(k,n),使同一类内样本的相似性最大,而不同类中样本的相似性最小。聚类分析作为数据挖掘中的一种分析方法,它可以作为一个单独的工具以发现数据库中数据分布的一些深入的信息。并且概括出每一类的特点,或者把注意力放在某一个特定的类上以作进一步的分析;聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。目前已经提出很多的聚类算法[1]。
1 传统的层次凝聚算法[2]及其局限性
HAC算法在簇对象中是很简单的,它能用类似的方法找出不同形状的簇,但HAC也存在着一些缺点:1)HAC有很高的时空复杂性,例如,对于质心点算法(优先队列法),其时间复杂性为:O(N2logN),虽然可以将HAC应用于大量数据中,一些技术被用到诸如BIRCH[3]和CURE[4],但它们都不能加快传统的HAC算法,在使用最近点且保证正确性前提条件下减少计算量。2)用谱系图获得簇的有效性是有限的。簇的有效性主要用来决定在大型数据量中最优簇的数目。并且,很多有效性方法对谱系图的低层显示出转移模式,这就会导致评估不出不精确的最优簇数。
2 改进算法及其分析过程
经验表明,除了谱系图的一些高层,所有低层聚类的簇既小而且与其他簇也非常接近。我们可称此特性为90-10规则,它难以被很小距离分开的小簇合并。基于90-10规则,我们提出了快速HAC算法,它能有效地减少已存在HAC算法的时空复杂性。在本文中,90-10规则用来改进已存在簇方法的有效性与正确性。90-10规则就是能有效地丢弃不需要的层,聚集潜在的层。所以它能减少计算量,改进被转移模式所避免的正确性。
2.1 算法的基本思想
我们提出基于部分重叠划分POP(Partially Overlapping Partitioning)的改进HAC算法。下面来具体分析一下基于POP的一种新算法——两阶段算法。两阶段算法:在POP基础上对HAC算法提出一个新的两阶段算法。第一个阶段,数据被分配到P个重叠的单元,这个重叠的区域称作δ区域,其中δ是分离的距离。对于质心点算法来讲,每个簇都用单一的代表点表示,如果一个簇的代表点落在δ区域,那么每一个受影响的单元都可捕获它并保存,否则,只有一个单元可以获取到它。基于POP的思想,在每一次迭代过程中,从已发现的全部最近点对中为每个单元找出最接近的点对。如果所有这些最近点对的距离小于δ,那么合并这些点对,并且更新被包含单元中的优先队列。如果最接近点对或合并的簇在δ区内,那么所有受影响的单元都会更新其优先队列。当最远点对距离超出δ时,每一阶段终止。第二个阶段利用传统的聚类算法合并第一阶段余下的簇。这样就以得到一个谱系图。
2.2 改进算法的实现及时空复杂度
这个算法如下所示。通过对距离图中转折点的最近距离对设置δ,可以在第一阶段合并大量的簇,在第二阶段利用传统HAC算法合并剩余的小量的簇。
Input:Data(N,M),p, δ
Output:Dendrogram
/*第一阶段*/
将数据分配到p个重叠单元中,为每个单元创建优先队列P
Do
对每个单元获取它的最近距离对,确定全部的最接近点对(C1,C2)
If dist(C1,C2)< δ
合并C1和C2同时更新相应的P队列;
更新所有受影响单元的P队列
While(dist(C1,C2)> δ)
/* 第二阶段 */
利用传统聚类算法合并第一阶段剩余的簇
Return 谱系图
2.3 改进算法的分析
精确性分析 关于第一阶段使用POP能够确保任意小于δ的距离对都能保留在至少一个单元中,第二阶段使用传统聚类算法,两阶段算法能够保证正确的谱系图。
复杂性分析 为简化这个分析,先假设每个单元有相同的单元大小,相同的δ域大小。|δ|主要是用来表明任意特殊单元δ域中的簇数。最初由Day和Edelshrunner[5]提出的优先队列算法的时间复杂度为:O(n2logN),O(N2),相反,所提出的两阶段算法,它的时间复杂度为O((N-k′)*(β+1)* (n/p+|δ|))。log(n/p+|δ|)要远远大于P,并且β是在每次迭代中受影响单元的平均数。空间复杂度是:O(p*(n/p+|δ|)2)或者O(k′2)或是两者中较大的。如果δ设置为距离图中转折点的最近对距离,那么|δ|和k′都是非常小的,因此,如果没有考虑|δ|与k′,时间复杂度就变为:O(N*(β+1)*(N/p)log(N/p)),即O((β+1)*(N2/p)log(N/p))(获取因子为log(N/p)N*(P/β+1)),空间复杂度为:O(p*(N2*p2)),即O((N2/p))(获取因子为p)。容器中所包含受影响单元的平均数为β+1,这个值主要依赖于数据是如何分配的:在最坏情况下,对于M维数据而言,每次聚类受影响单元的最大可能数为2M,在最好情况下,每次聚类受影响的仅仅是容器本身中的单元,那么这个值仅为1。经验表明β+1对于所有测试数据集而言是小的,它小于2。
原始的质心点算法采用互异矩阵代替了优先队列,并且还没有保留最近邻居。它的时间复杂度为O(N3),空间复杂度为O(N2),如果采用两阶段算法,那么时间复杂度就会变为:O((N-k′)*(β+1)* (n/p+|δ|)2)+ O(k′3),空间复杂度为O(p*(N/p)+|δ|2)或O(k′2)或者两者中较大的。注意,在这个例子中,受影响单元的平均数不是因子,这是因为全部的复杂度是由于需要通过互异矩阵进行搜索需要二次的时间量。经过简化(没有考虑|δ|与k′)时间复杂度为O(N*p*(N2/p2)),即O(N3/p),获取因子为p。空间复杂度为O((N2/p))(获取因子为p)。
按照Anderberg[6]的分类法,上面两种算法都采用矩阵存储的形式,传统的数据存储形式为最近邻居数组,它的时空复杂度分别为:O(a*N2) ,O(N),其中a是每次迭代更新次数。但是,当使用两阶段算法去存储数据时,它的时间复杂度为:O((β+1)*(N-k′)*a*((N/p)+|δ|))+O(a*k′2),简化之后的时间复杂度为O((β+1)*a*(N2/p)),获取因子为:(p/β+1),空间复杂度为 O(p*(N/p)*)|δ|)或O(k′)简化后为 O(N),获取因子为1。如表1所示。
3 结束语
实验表明,利用改进的HAC算法可以有效地减少传统HAC算法的时空复杂度。应用改进的HAC算法可以发现自然的簇,一般的HAC算法通常不能发现自然的簇,这就像文献[7]所指出的那样。Chameleon[7]是基于内部对象间的互连性和近似度一致类似性的算法,它也是一个两阶段的算法,在每阶段,数据被分到很小的簇中,第二阶段利用一致相似性合并这些小簇。一般而言,合并簇所需时间要小于分裂簇所需时间[8],利用改进的HAC算法,我们可以决定在距离图转折点上何时终止合并过程,在那些点上的簇,可以作为Chameleon算法第二阶段的输入,以利于发现更自然的簇。
参考文献
[1]范明,孟小峰,等.数据挖掘概念与技术.机械工业出版社,2001:223-260.
[2]郭崇慧,田凤占,靳晓明,等.数据挖掘教程.清华大学出版社,2005:107-138.
[3]Zhang T,Ramakrishnan R,Livny M.BIRCH:An efficient data cluste-ring method for very large databases.In:Proceedings of ACMSIGMOD Conference on Management of Data,Montreal,Canada,June1996:103-114.
[4]Guha S,Rastogi R,Shim K.CURE:An efficient clustering algorithm for large databases.In:Proceedings of the ACM SIGMOD International Conference on Management of Data,1998:73-84.
[5]Day W HE,Edelsbrunner H.Efficient algorithms for agglomerative hi-erarchical clustering methods.Journal of Classification,1984(1):7-24.
[6]Anderberg M R.Cluster Analysis for Applications.Academic Press,New York,1973.
[7]Karypis G,Han E H,Kumar V.CHAMELEON:a hierarchical clustering algorithm using dynamic modeling.IEEE Computer,1999,32:68-75.
[8]Duda R O,Hart P E.Pattern Classification and Scene Analysis,chap-ter:Unsupervised Learning and Clustering.John Wiley&Sons,1973.
[9]Dash M,Huan L,Scheuermann P,Tan K L.Fast hierarchical clustering and its validation.Data&Knowledge Engineering,2003,44:109-138.
聚类分析算法 篇2
本文是由上传的：基于CRP模型的聚类算法。
【摘要】 关于聚类问题现在已经有很多方法可以实现，但大多数基于有限混合模型的聚类方法需要预先估计聚类的个数，因而聚类的准确性和泛化性会受到一定影响。本文则提出了一种基于无线混合模型――中国餐馆模型(CRP)的聚类方法，CRP模型是Dirichlet过程的一种表示方法，基于Dirichlet无线混合模型找出其后验分布，利用Gibbs采样MCMC方法估计出模型中各个参数以及潜在的聚类个数，并在MATLAB环境下进行一个小实验来验证聚类的效果。
【关键词】 聚类 CRP模型 Dirichlet过程 MCMC采样
一、引言
聚类顾名思义就是把事物按照特定的性质或者相似性进行区分和分类，在这一过程中不指导，属于无监督分类。作为一种重要的数据分析方法，聚类分析问题在很久以前就已经为人们所研究，并且已经取得了一定成果，目前的算法已经能对一般简单的聚类问题做出很好的聚类结果。但随着大数据时代的到来，实际应用中的数据越来月复杂，如基因表达数据，交通流数据，web文档等，有一些数据还存在着极大的不确定性，有的数据可以达到几百维甚至上千维，受“维度效应”的影响，很多在低维空间能得到很好结果的聚类算法在高维空间中并不是十分理想。
关于高维数据的聚类近几年一些基于有限混合模型的方法取得了很有效的成果。但是这些算法需要提前估计聚类个数的前提下，根据样本的属性进行分析分类。本文采用了一种基于Dirichlet无线混合模型的方法，利用CRP模型和Gibbs采样方法，在分析过程中找出潜在的聚类个数，实现对数据的聚类。
二、CRP模型
2.1 关于CRP
CRP模型是Dirichlet过程的一种表示方法，它是关于M个顾客到一家中国餐馆如何就坐问题的一个离散随机过程。具体描述如下：有一家中国餐馆，假设有无限个桌子，并且每张桌子上可以容纳无限个顾客，每一个顾客到来时可以随意选择一个餐桌，也可以自己新开一个餐桌。在CRP过程中，我们把每一位到来的顾客都当作最后一位来看待，有如下分配过程：第一位顾客到来，一定会开一个桌子自己坐下，第二个顾客到来时，以一定概率坐在第一个人开的桌子上，一定概率新开一张桌子，第三个顾客到来时，有一定概率坐在第一、二个人开的桌子上，也可以开第三张桌子……以此类推，具体定义的概率如下：
其中α是狄利克雷的先验参数; c 是第m 个顾客选择的餐桌上已有的顾客人数。顾客选择餐桌时不仅与顾客对餐桌的个人情感有关，还与该桌上在座的顾客关系有关，如果是朋友或是认识的人就算有更好的选择顾客也可能选择与朋友坐一桌。而在CRP模型中并未考虑到顾客的情感色彩因素。
2.2 Gibbs Samping
关于Dirichlet混合模型的Gibbs Sampling实际上就是根据先验求后验的过程，虽然中心思想一样，但具体实现方法有很多种[1]，这里根据CRP的情况，选择其中一种算法，在下一节详细讲解。
2.3 参数估计
假设有一个整体的数据集D={xi}in=1，它的两个参数为z=(z1，…，zn)，zn∈{1，…，K}，φ=(φ1…，φK)
其中Z为隐变量，表示样本聚类的标签，Zi=k代表当前第i个类有k个成员，而φ则是该模型的每一类的成员参数，根据贝叶斯理论，可以得出p(φ，z|D)∝p0(φ)p0(z)p(D|φ，z)，因此，参数φ后验分布可以通过计算其先验分布及似然函数来实现，在此基础上计算出φ的后验分布，并通过Gibbs采样的方法更新参数φ。
其中nk代表当前坐在第k个桌子上的其他人的总数。
2.4 使用Gibbs采样的算法
假设待处理的数据是高斯随机分布的，首先随机初始化参数z，φ。
对于每一个zi才用如下采样方法：
选择已有桌子(第K个)的概率：
新开一个桌子(第K+1)的概率：
而对于参数φ，采用如下方式(每当第k个桌子上加了人，这个类的参数φk就要更新)：
三、实验与结果
本文以matlab为平台，对二维空间上一些随机分布的点进行模拟聚类测试。正如上一节所说，这里对测试数据采用高斯随机来生成，为了简化处理，生成了300个各项同向高斯分布的点，具体代码如下：
这样就默认把这300个点分成了潜在的3个类，我们最后要求出的结果应该就是K=3。实验结果发现，真正的结果与Dirichlet过程CRP模型的集中度参数α有很大关系。α很大的`时候会不准确，我在这里让α随机选取，并重复了100次，最后一次的结果是k=4：
而根据α的不同取值，100次的聚类结果在3-6之间，其中还是以3居多：
由此可知，对于Dirichlet先验参数α的选择会直接影响到最终的聚类效果。而Dirichlet过程作为一个无线混合模型，随着数据的增多，模型的个数是呈现log 增加的，即模型的个数的增长是比数据的增长要缓慢得多的。同时也可以说明Dirichlet过程是有一个马太效应在里面的，即“越富裕的人越来越富裕”，每个桌子已有的人越多，那么下一次被选中的概率越大，因为与在桌子上的个数成正比的，因而这种无线混合模型对于发现潜在的聚类个数会有很好的效果。
四、总结
基于CRP模型的聚类方法不同于先前的有限混合模型，无需预先估计聚类的个数，而是在分析过程中自动确定。聚类的结果与α有关，所以选取合适的集中度参数很重要。关于CRP模型现在的研究还不是很广泛，也有一些在主题模型中的应用，比如基于CRP模型的词汇分类，实现主题模型等。相信在不远的将来，这种利用无线混合模型的聚类方法会有更多的开拓空间。
参 考 文 献
[4] 易莹莹. 基于Dirichlet过程的非参数贝叶斯方法研究综述[J]. 统计与决策. (04)
[5] Pruteanu-Malinici I，Ren L，Paisley J，Wang E，Carin L.Hierarchical Bayesian modeling of topics in time-stamped documents. IEEE Transactions on Pattern Analysis and Ma-chine Intelligence .
[6] H. Ishwaran，M. Zarepour.Markov Chain Monte Carlo in approximate Dirichlet and beta two-parameter process hierarchical models. Biometrika . 2000
聚类分析算法 篇3
关键词：数据挖掘；入侵检测；K-means；初始聚类中心；孤立点
中图分类号：TP301.6 文献标识码：A文章编号：1007-9599 (2011) 03-0000-03
Cluster Analysis and its Application in Intrusion Detection Based on Genetic Algorithm
Shen Lumin, Fan Nianbai
(Hunan University,Changsha410082,China)
Abstract:The data mining technology applied to intrusion detection can enhance inspection accuracy and efficiency.Because K-means algorithm of initial clustering center is very sensitiveit is also depend on the order of data input in the process of clustering,then this paper firstly use the initial center of the genetic algorithm for the improvement of k-means clustering algorithm,and use the fast convergence features of k-means algorithm for obtaining clustering results,and finally test the effectiven -ess of the algorithm in intrusion detection of classical data sets (KDD CUP 1999).Experimental results show that compared with the intrusion detection system,the method and relevant study improve the efficiency and precision.
Keywords:Data mining;Intrusion detection;K—means;Initial clustering center;Isolated point
入侵检测是计算机安全问题中的一个重要研究课题。现在入侵检测系统[1]的设计和实现往往取决于设计人员自身的知识、经验和对已知攻击方法的了解程度，系统的经验化成分较高，自动化程度低。结果系统的可实用性和准确性都受到了不同程度的限制。入侵检测的关键就是从海量的网络活动中要区分什么是正常行为，什么是攻击行为。将数据挖掘应用于入侵检测中的目的就是将入侵检测看作是一个数据分析的过程，通过数据挖掘计算出精确的聚类模型。
在数据挖掘中聚类算法是一种“无指导的学习”，不依靠训练数据，而是以相似性为基础来将记录分组。由于网络对于实效性的要求，现在很多的研究人员将K-means算法应用于入侵检测中，但是由于的属性值是离散的或者属性值之间的差别很大，以及K-means本身的不足，造成误报率提高，检测率降低。聚类算法有很多，比如K-medoids算法[2]对初始的聚类中心不敏感，但是计算量大，一般只适合小数据量，K-means算法具有较小的计算复杂度和良好的扩展性，具有很高的时效性，能够处理大量数据，但是对初始聚类中心很敏感，在聚类过程中对数据输入的顺序也有依赖性[3]。但是对于网络入侵检测实效性的要求选择K-means算法作为进行聚类分析的算法[4]。
本文针对K-means算法的不足提出了一些改进，并将该进的K-means算法应用于入侵检测当中，并通过实验来证明它的可行性。算法设计基于两个假设[5]：（1）正常行为的记录数目远大于入侵行为的数目；（2）入侵行为本质与正常行为不同。
一、原始的K-means算法
K-means算法的思想[6]：首先随机选择k个对象，每个对象代表一个簇的中心，对剩余的每个对象，根据其与各个簇中心的距离，将它指派到最相似（或最近）的簇，然后计算每个簇的新中心；这个过程不断重复，直到每个聚类不再发生变化时算法终止。
二、改进的K-means算法在入侵检测中应用
原始的K-means算法由于初始聚类中心选取的不同会造成聚类结果有很大的不同。本文将采用运用初始化聚类中心的K-means算法，对连接记录进行聚类分析，最后对产生的孤立点进行二次聚类，从而消除K-means算法对聚类中心的敏感和数据输入顺序的依赖性。整个设计过程如图1：
（一）数据预处理
入侵检测的数据源是通过抓包工具来收集的，原始的数据不适合进行分析，所以需要对它进行预处理[7]，消除噪声和不一致数据，多种数据源组合在一起，从数据源中选择和分析任务相关的數据，从这些数据中选择对分析任务很重要的属性，将数据变换或统一成适合挖掘的形式。具体的实现方法如下：属性值之间的差别可能很大，而且它们可以用不同的单位来度量，但使用不同的度量方法，对数据间距离的影响也不同。为了消除由于度量不同对距离产生的影响，通过如下方式进行处理：
首先计算各个属性值的平均值m和 平均绝对偏移S。
mj= （ x1j+ x2j+ x3j+ …+xnj）/n（1）
Sj=（|x1j- mj|+|x2j- mj|+ |x3j- mj|+ …+|xnj- mj|）/n（2）
其中mj和Sj分别是第j个属性的平均值和平均绝对偏移，x1j、x2j、x3j…xnj分别是各个数据第j个属性的取值。
然后对每个数据的每个属性进行如下的处理：Zij=（ xij- mj）/ Sj
其中Zij代表第i个数据的第j个属性。
（二）距离函数
为了使用聚类算法，需要计算数据之间的差异，数据间的差距通常用距离来表示，最常用的是欧氏距离[8]，它的计算方法如下：
d（i，j）= （|xi1-xj1|2+ |xi2-xj2|2+…+ |xip-xjp|2）1/2 （3）
其中i，j 分别代表数据集中的两个数据，它们都有p个属性。
（三）改进的K-means算法
本文将K均值算法与遗传算法[9]相结合，首先随机产生第一代聚类中心，运用K-means算法得到第一代个体；通过遗传算法的进化得到新的聚类中心，再利用K-means算法得到新的个体，比较新的个体与上一代个体的适应度，适应度高的个体作为下一代个体遗传下去；通过若干次遗传算法进化直到适应度函数不在发生变化，从而得到最优的聚类中心和最优的聚类。这种方法通过遗传算法来保证获取全局最优解（即最优的聚类中心），克服了传统K均值算法对初始中心的敏感性。具体过程如下：
1.n个数据对象集{x1，x2，x3，……，xn）中随机选取k个对象{c1，c2，c3，……，ck}为初始聚类中心，将剩余的n-k个对象分配到这k个聚类中心，成为第一代个体并计算适应度：
D（ci，cj）=（ |ci1-cj1|2+ |ci2-cj2|2+…+ |cip-cjp|2）1/2（4）
ci，cj 分别表示聚类中心。
适应度函数为：F（ci，cj）=1/D（ci，cj）（5）
F（ci，cj）越小表示聚类中心的距离越大，聚类的相似性越小，适应度就越高。
2.采用浮点数编码方式[9]对各个聚类中心进行编码。浮点编码方法是指个体的基因值用某一范围内（各个属性值的上限和下限之间）的浮点数来表示，一般是在个体的编码长度等于其决策变量的长度，它能提高算法的精确度，便于多维空间的搜索。
3.任选两个中心作为一组，直到所有的中心都分组完成，对各组中的两个中心部分配对的染色体进行均匀算术交叉操作：
XAi+1 = aXBi+（1-a）XAi
XBi+1 = aXAi+（1-a）XBi
均匀算术交叉的对象一般是浮点数编码所表示的个体，其中a为一个常数，XAi、XBi为父代个体，XAi+1、XBi+1为子代个体。
4.对所有的中心判断其是否符合变异条件，符合变异条件的中心进行均匀变异操作[10]：对于每个变异点，从对应基因位的取值范围内取一随机数代替原有基因值。即
X’=Umin+r（Umin-Umax）（7）
其中，r为（0，1）范围内的随机数；Umin，Umax分别是该基因位的数值上下限。
5.根据产生的新的聚类中心计算适应度并进行比较，适应度较高的成为新的一代遗传下去。
6.计算各对象到聚类中心的距离，并根据最小距离重新划分。
7.更新聚类的平均值，即计算每个聚类中对象的平均值，将此平均值作为新的聚类中心。
8.循环2到7，直到每个聚类不再发生变化时算法终止。
（四）孤立点的处理
原始的K-means算法中由于输入数据的顺序产生的孤立点对算法的性能也会产生很大影响，如何消除这些孤立点[3]也是一件很重要的事情。将每个聚类中每一类记录按所占的比率q（i）按大小排序，q（i）值越小，记录i就越不适合这个聚类，选取q（i）值最小的s个记录作为孤立点，将孤立点从该聚类中剔除，重新计算这个聚类的中心，将孤立点进行二次聚类，直到s个记录全部放到合适的聚类中，最后计算所有聚类的中心。这样能消除对输入数据顺序的依赖性，从而减少噪声对算法的影响。
（五）算法效率分析
对于本问题，变异是能够跳出局部最优的关键，随着的遗传的进化发展适应度趋于最优个体的适应度。同时将孤立点剔除后进行二次聚类，使得本算法对孤立点的敏感性要小于原始的K-means算法。在时间效率方面，改进的K-means算法不如原始的K-means算法收敛速度快，但是它的聚类结果比原始的K-means算法更加合理。
三、实验结果
为了验证本文提出的基于聚类的入侵检测算法，选用KDD Cup1999实验数据。该数据集大约包含近500万个活动事件记录数据对象，每个数据对象均为（模拟）网络连接过程所发生的TCP数据帧，通过对这些TCP数据帧进行预处理从而得到目前描述的记录各种应用层网络连接活动的数据对象。描述这些网络连接事件的特征属性共有43个，其中包括连接时间、协议类型、传输字节数、连接标记或状态，以及文件创建操作、失败登录次数等活动事件属性描述。这些数据所涉及的入侵行为共分为4大类（共22种）：DOS、 R2L、U2R和Probe。
为了方便仿真实验，采用随机抽取的5组 1000个样本数据集，每个数据子集中正常数据记录个数占本子集所有数据记录个数的比例约为99%，同时各种入侵活动数据记录也相应被均匀分配到5个数据子集中。分别计算出两种方法的检测率和误检率，它们分别代表检测为攻击的攻击数据占所有攻击数据的比重，以及檢测为攻击的正常数据占所有正常数据的比重。此实验的硬件环境是：Intel（R），Core™2 Duo， CPU E7200，2.53Hz，2G内存；软件环境是：Windows XP，MyEclipse6。实验结果如表1所示。
通过上面的数据分析可以看到，改进的K-means算法在入侵检测的平均检测率由原来的89.83%提高到92.138%，平均误报率由原来的0.108%降低到0.076%，更加有利于数据挖掘进行入侵检测，可以有效地将正常数据和攻击数据区分开来，有很高的可行性和有效性。
四、结束语
本文分析了数据挖掘在入侵检测中的应用，对现有的K-Means算法进行了改进，把遗传算法引入到K-means中，克服了随机的初始聚类中心产生不稳定的聚类结果这个缺陷，并对孤立点进行了处理，消除了算法对输入数据顺序的敏感性。利用 KDD Cup1999实验数据进行仿真实验，其结果表明该改进的K-means算法能提高入侵检测的效率。
在本文中，数据之间的距离采用的是欧氏距离，但是由于网络数据量的不同，简单的使用欧式距离无法精确地描述数据之间的关系，如果使用网络数据量乘以长度得到的扭矩作为目标函数就可以进一步的改进此算法。
参考文献：
[1]曹元大,薛静锋等.入侵检测技术.北京:人民邮电出版社2007,48-49
[2]Lee W,Stolfo S J.A Framework for constructing features and models for intrution detection systems.ACM Transactions on Information and Systems Security,2000-04
[3]熊家军,李中华.信息熵理论与入侵检测聚类问题研究.小型微型计算机系统,2005,26(7),1163-1166
[4]向继,高能,荆继武.聚类算法在网络入侵检测中的应用.计算机程,2003,29(7)
[5]张克鑫,贺建飙.基于数据挖掘的入侵检测技术.计算机与网络,科学信息,185-186
[6]蒋盛益.基于聚类的入侵检测算法研究.北京:科学出版社,2008,39-41
[7]蒋川,田盛丰.入侵检测中对系统日志审计信息进行数据挖掘的研究.计算机工程,2002,28(1),159-161
[8]李涵,包立辉.基于聚类算法的异常入侵检测模型的研究与实现.计算机应用与软件,2006,23(10)
[9]赖玉霞,刘建平,杨国兴.基于遗传算法的K均值聚类分析.计算机工程,2008,34(20),163-164
[10]周明,孙树栋.遗传算法原理及应用,北京:国防工业出版社,1996,32-41
高维数据对象聚类算法效果分析 篇4
聚类分析是数据挖掘领域中的一项重要的研究课题, 高维数据对象的聚类又是聚类分析的重要研究课题, 也是涉及到聚类算法是否能够有效地应用于各个领域, 例如多属性 (高维) 流数据的聚类分析。高维数据的特点表现为: (1) 高维数据集中存在大量无关的属性使得在所有维中存在簇的可能性几乎为零; (2) 高维空间中数据比低维空间中数据分布稀疏, 其中数据间距离几乎相等是普遍现象。目前, 对高维数据的聚类主要有3种方法:属性转换、子空间聚类、协同聚类、属性转换是通过创建新属性, 将一些旧属性合并在一起来降低数据集的维度的方法。目前, 主成分分析方法 (PCA) 、自组织特征映射 (SOM) 、多维缩放 (MDS) 、小波分析等是普遍应用的降维方法。虽然采用降维技术使得数据的维度大大降低, 但数据的可理解性和可解释性变得较差, 一些对聚类有用的信息也可能会随之丢失, 很难准确地表达和理解结果。在处理高维数据时, 采用属性转换的方法得到的聚类效果并不是很理想, 有一定的局限性, 不能满足当前高维聚类算法发展的需要。
子空间聚类算法对特征选择的任务进行了拓展, 它是在同一个数据集的不同子空间上进行聚类。子空间聚类和特征选择一样使用搜索策略和评测标准来筛选出需要聚类的簇, 因为不同的子空间上存在不同的簇, 因此我们要对评测标准设置一些条件。
协同聚类在数据点聚类和属性聚类之间达到了一种平衡。因为它从对象—属性两个角度同时进行聚类操作。假设X是由数据对象和数据属性构成的矩阵, 一般被叫做关系矩阵、可能性矩阵、影响矩阵、频率矩阵等。一般被应用于反映基因响应的强度、一个Web页面的点击率, 或一个仓库里各项商品的销售数量等。Govaert于1995提出了可能性矩阵表中行列块的同时聚类算法。Dhillon于2001年提出了一种协同代数聚类算法, 它与文本挖掘相关, 是基于二部图和它们的最小切割的。Oyanagi等人于2001年提出了一种简单的Ping-Pong算法, 它能在稀疏二元矩阵中发现相应区域, 该算法能建立矩阵元素的横向联系, 并用此来重新分布列对行的影响, 并反过来进行。
本文在对数据对象间的最大距离和平均距离随维数增加的变化趋势实验基础上, 通过实验研究了聚类算法的聚类精度随数据对象维度的变化特征。同时, 提出了利用复相关系数倒数阈值实现降维的方法。
2 数据对象离散度与维度的关系
2.1 实验数据
实验中所用的数据集均来自UCI数据库, 数据集包括Iris, Wine, Wisconsin Diagnostic Breast Cancer, SPECT Heart和Libras Movement。数据集的详细描述见表1。
2.2 相关定义
为了确定数据对象随维度变化规律, 我们定义了数据对象间的最大距离和平均距离来定量确定数据对象间的离散度。
最大距离:假设数据集D有n个数据对象, 每个数据对象有d个属性 (维) , 即Xi={xk, k=1, …, d}, i=1, …, n。数据对象间的最大距离被定义为:
平均距离:数据对象间的平均距离被定义为:
2.3 实验结果
为了研究维数对聚类精度的影响, 有必要研究对象间的距离随维数增高的变化趋势。根据上面定义的公式 (1) 和公式 (2) , 数据对象间的最大距离和平均距离随维数的增加而增大。我们使用UCI数据库中的Libras Movement数据集, 先对数据集进行最小—最大标准化处理, 然后计算此数据集中数据对象间随维数增高的最大距离和平均距离。实验结果分别显示在图1和图2中。
如图1和图2所示, 随着维数的增加, 数据对象间的最大距离和平均距离逐渐增大。表明数据对象在高维数据空间变得比较稀疏, 很可能导致数据空间中客观簇的消失, 使得基于距离的聚类算法往往不能够取得良好的聚类效果。因此, 为了获得有效的聚类结果, 基于距离、密度和密度可达的聚类算法有必要进行改进或降维。
3 维数对算法聚类精度的影响
3.1 直接聚类
我们给出了确定聚类效果的准确度公式。假设数据集D中有k个类, 即Ci (i=1, …, k) , Oip (p=1, …, mp) 是类Ci中的数据对象。数据集D经过聚类后, 出现了k个类Ci′ (i=1, …, k) , O′ip (p=1, …, mp′) 是Ci′类中的数据对象, 准确度被定义为:
|Ck∩Ci′|是同时属于类Ci和Ci′的数据对象Oip (p=1, …, mp) 和Oip′ (p=1, …, mp′) 的个数;|D|是数据集D中的数据对象的个数。
为了研究维数对算法聚类精度的影响, 我们分别用K-means和层次聚类算法对以上5个不同维数的数据集进行聚类分析, 聚类结果如图3所示。当数据集的维数小于30的时候, 两种聚类算法的性能较好, 当数据集的维数大于30的时候, 聚类算法的精度随维数的增高而降低。实验结果在一定程度上表明, 当数据集的维数小于30的时候, 传统的聚类算法, 如K-means和层次聚类算法, 这种基于距离的聚类算法是有效的, 但是当维数大于30的时候它们的聚类结果很不理想。
3.2 PCA降维聚类
Wine数据集有13维, 经过主成分分析 (PCA) 降维后, 原有的13维变成了3维, 为了比较PCA降维前和降维后的效果, 我们用K-means和层次聚类算法对原有的数据集和经过降维后的数据集进行聚类, 结果如图4所示。
对数据集降维后, K-means和层次聚类算法的聚类精度有所提高, 但是效果不是很明显。此结果也说明了K-means和层次聚类对30维以内的数据集的聚类精度比较高。
Libras Movement数据集有90维, 经过PCA降维后变成了10维, 降维前和降维后的聚类结果如图5所示。
降维前和降维后K-means和层次聚类算法的聚类精度都很低, 结果表明: (1) 以上两种聚类算法不能有效地处理高维数据; (2) PCA降维对聚类算法不总是有效的; (3) 此数据集包含15个类, 对于高维、多类的数据集, 聚类算法不能很好地辨别存在的类 (簇) 。
4 基于复相关系数倒数降维
4.1 复相关系数倒数加权
复相关系数的倒数赋权法是在方差倒数赋权法的基础上提出来的。假设数据对象的某一属性为Xk, 则它的复相关系数记为ρk。ρk越大, 表明Xk与其余的属性越相关, 越能被非Xk代替, 也就是说Xk属性对聚类的作用越小;反之, ρk越小, Xk与其余的属性越不相关, Xk属性对聚类的作用越大。所以可以用|ρi|-1计算数据对象属性权重系数wk。
因此, 数据点密度计算公式中的加权欧式距离公式为:
4.2 降维实验
我们也可以采用复相关系数的倒数赋权法作为一种特征选择方法, 对数据集中数据对象的每个属性加权后, 得到了每个属性的权值, 然后根据权值的大小, 我们设定一个阈值参数σ, 选择权值大于σ的属性, 从而实现了对数据集的降维, 然后对降维后数据集进行聚类。为了说明此方法的有效性, 采用k-means算法、层次聚类算法、CADD (基于密度和密度可达聚类算法) 算法对WDBC数据集和SPECT Heart数据集进行聚类, 来对比降维前和降维后的结果。
WDBC数据集有30个属性, 取权值σ≥0.036时, 该数据集降为3维;取权值大于0.034时, 该数据集降为6维;取权值大于0.033时, 该数据集降为15维。降为3维、6维、15维的数据集和原数据集的聚类精度如图6所示, 实验结果表明该数据集降为6维时聚类效果最好。
SPECT Heart数据集有44个属性, 取权值大于0.024时, 该数据集降为5维;取权值大于0.023时, 该数据集降为18维;取权值大于0.022时, 该数据集降为28维。降为5维、18维、28维的数据集和原数据集的聚类精度如图7所示, 实验结果表明该数据集降为18维时聚类效果最好。
Libras Movement数据集有90个属性, 取权值大于0.0111113时, 该数据集降为10维;取权值大于0.0111111时, 该数据集降为34维;取权值大于0.0111110时, 该数据集降为47维。降为10维、34维、47维的数据集和原数据集的聚类精度如图8所示。实验结果表明聚类算法对该数据集的聚类效果较差, 原因是此数据集包含15个类, 类比较多, 聚类算法不能很好地识别, 但是该数据集降为47维时聚类效果有所提高, 仍能体现出本文降维方法的有效性, CADD算法的聚类效果相对好一些, 从而体现了CADD算法的优越性。
由以上实验结果表明: (1) 采用复相关系数的倒数赋权法作为一种属性选择方法是有效的, 并且计算量较小, 适合处理高维数据; (2) 降维要降到合适的维度, 如果维数太少, 则会丢失对聚类重要的属性信息, 如果维数太多, 则会产生“噪声”, 影响聚类结果; (3) 一般的聚类算法不能很好地处理高维且类比较多的数据集, 因此有待于进一步研究能处理高维且类比较多的数据集的聚类算法。
5 结论
对于传统的基于距离的聚类算法, 当数据对象的维数小于或等于30时, 聚类分析往往能够取得良好的聚类效果;维数高于30时, 聚类效果不佳。甚至使用PCA降维后, 聚类算法对高维数据的聚类效果的改进也不是很明显。用复相关系数的倒数赋权法为差异度加权, 并且把复相关系数的倒数赋权法用作一种属性选择方法, 通过设定属性加权系数的阈值参数对数据对象进行降维也能取得较好的聚类结果。
摘要：虽然经典聚类算法能够有效地处理维度较低的数据对象, 但随着维度的增加, 算法的性能和效率就会明显下降。本文在对数据对象间的最大距离和平均距离随维数增加的变化趋势实验基础上, 对聚类算法的聚类精度随数据对象维度增加的变化特征进行了实验研究。同时, 利用复相关系数的倒数对属性进行加权, 提出了利用复相关系数倒数阈值实现降维的方法, 并取得了良好的实验结果。
关键词：高维数据,聚类效果,复相关系数,降维
参考文献
[1]冯永, 吴开贵, 熊忠阳, 等.一种有效的并行高维聚类算法[J].计算机科学, 2005, 32 (3) :216-218.
[2]王永卿.高维海量数据聚类算法研究[D].南宁:广西大学, 2007.
[3][加]Jiawei Han, [加]Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社, 2001.
[4]G Govaert.Simultaneous Clustering of Rows and Columns[J].Control and Cyberyretics, 1995, 24 (4) :437-458.
[5]Inderjit S Dhillon.Co-clustering Documents and Words Using Bipartite Spectral Graph Partitioning[C]//Proceedings and the7th ACM SIGKDD, New York, NY, 2001.
[6]Shigeru Oyanagi, Kazuto Kubota, Ahihiko Nakase.Application of Matrix Clustering to Web Log Analysis an d Access Prediction[C]//7th ACM SIGKDD, San Francisco, CA, 2001.
[7]宋宇辰, 张玉英, 孟海东.一种基于加权欧氏距离聚类方法的研究[J].计算机工程与应用, 2007, 43 (4) :179-180.
聚类分析算法 篇5
基于K均值聚类和遗传算法的多航迹规划方法
提出了一种在未知动态环境中利用K均值聚类和遗传算法的.飞行器多航迹规划方法.针对飞行器在动态环境下需要调整飞行航迹的问题,该方法可以规划出多条可供选择的航迹,使飞行器能在障碍和威胁等环境发生变化时选择可行的飞行线路.实验结果表明,该方法能有效地完成多条航迹的规划,获得满足要求的多条飞行航迹.
作 者：严江江 丁明跃 周成平YAN Jiang-jiang DING Ming-yue ZHOU Cheng-ping 作者单位：华中科技大学图像识别与人工智能研究所,武汉,430074 刊 名：火力与指挥控制 ISTIC PKU英文刊名：FIRE CONTROL & COMMAND CONTROL 年，卷(期)： 35(3) 分类号：V279 关键词：无人飞行器 聚类 遗传算法 多航迹规划
聚类分析算法 篇6
关键词：Hadoop；MapReduce；聚类；Canopy-Kmeans算法
中图分类号：TP391.1
Hadoop[1]是一种开源式的分布式平台，由它的分布式文件系统（HDFS）和MapReduce编程模型组成，这是Hadoop的核心。Kmeans算法[2]是被广泛使用的经典的聚类算法之一，思想简单，收敛速度快，而且易于实现，但是要先确立初始聚类中心，容易受主观因素的影响而造成聚类结果的局部最优。为解决该问题，本文引入Canopy对算法初始中心点的选取进行优化处理。
1 MapReduce并行编程模型
MapReduce是现在各种云计算平台的基础模型。此模型的核心是Map和Reduce函数，他们都可以高度并行运行。Map函数可以处理多组数据，把一对Key＼Value对映射成新的Key＼Value对，Reduce的输入数据为Map函数的输出数据。由并发Reduce函数来确保所有映射Key＼Value对中的每组都有相等的Key键值[3]。MapReduce的运行机制是将大数据集分解成为许多小数据集splits，每个数据集分别由集群中的一个节点执行Map过程并生成中间结果。接着这些中间结果被大批的并行执行的 Reduce过程做相应的处理，从而产生最终结果，输出给用户[4]。
2 Canopy-Kmeans算法
2.1 算法的思想
Canopy-Kmeans算法采用Canopy进行初始聚类中心点的优化。数据子集分别分布在集群中的各个不同的站点。在Map阶段引用Canopy算法迅速地产生多个局部Canopy中心，各站点传来的局部Canopy中心在Reduce阶段被再次利用 Canopy算法得到全局的canopy中心集合。与Map阶段不同的是可對阈值t1、t2（t1>t2）进行重置。意思是Reduce阶段的阈值可与Map阶段的不同，以便能得到下步Kmeans所需的k个初始聚类中心。
2.2 基于MapReduce的Canopy-Kmeans算法
在基于Hadoop的并行Kmeans算法的基础上，本文使用Canopy算法对Kmeans 算法进行优化。Canopy-Kmeans算法包括两部分：Canopy生成中心点算法和Kmeans算法。Canopy中心点的生成过程包括Map和Reduce函数。算法实现需四个阶段，分别用四个Job实现。如图1所示。Job1生成k个canopy中心。Job2借助Job1阶段的k个canopy中心点来生成k个相互重叠的canopy。Job3对处于同一canopy内的数据集进行K-means聚类。通过多次的迭代，生成稳定的Kmeans聚类中心。最后，Job4使用稳定的Kmeans聚类中心点开始聚类。直到输出最终结果。
图1 Canopy-Kmeans 实现流程
3 算法时间复杂度分析
传统的Kmeans算法的时间复杂度为O（nck）。其中n为数据对象数量，c为迭代次数，k为类数量。该文引入Canopy聚类，产生k个canopy，每一个数据对象有可能同时属于q（q≤k）个canopy。当集群数量为p时，可知算法的时间复杂度为O（ncq2k/p）。可以看出该算法的时间复杂度与传统的Kmeans时间复杂度相比明显降低了。
4 实验与结果分析
4.1 数据集和实验环境
实验数据是从UCI机器学习库中选取的部分数据集，如表1所示。这些标准数据集用以准确度量本文算法的聚类效果。
表1 实验数据集
数据集样本数属性数类别数
Synthetic_Control600606
Segmentation2310187
Waveform-405000403
Hadoop为开发平台，运用MapReduce编程框架完成实验。本实验是在5台VMWare平台下的虚拟机搭建成的Hadoop集群环境中完成，实验由5台PC机构成，其中一台作为主节点，剩余四台作为从节点。
4.2 实验结果及分析
将本文算法与MapReduce框架下的Kmeans聚类（算法a）、Weka环境下的串行Kmeans聚类（算法b）做比较。实验结果如表2所示。实验结果表明，算法a、b的正确率和误差平方和相对接近，可以看出该算法的聚类效果明显更好。
表2 实验结果
数据集算法a算法b本文算法
正确率/（%）误差平方和迭代时间/ms正确率/（%）误差平方和迭代时间/ms正确率/（%）误差平方和Canopy聚类时间/ms迭代时间/ms
Synthetic_Control66.9600.0719154364.8604.651094871.35533.5418945173475
Segmentation56.70606.0720376254.9607.201169365.21390.6519715145665
Waveform-4061.83530.3299855759.1540.741094669.36490.9794810564431
从算法的迭代时间来看，算法a的迭代时间比本文算法的迭代时间要长。这说明本文在引进Canopy聚类后。大大减少了每次迭代中的计算量，降低了运行时间。
5 结束语
针对大规模数据聚类的问题。本文提出了基于Map Reduce的并行化Canopy-Kmeans算法。对Kmeans聚类算法的优化确实避免了传统Kmeans算法的缺陷，明显降低时间复杂度，减少了计算量，提高聚类效率。MapReduce是目前主流的并行编程模型，但该模型本身存在一些局限性。最新的并行计算框架Prlter，Spark等对MapReduce进行了改进，怎么在最新的并行计算框架上对算法进行并行化设计和实现需要做进一步的实践。
参考文献：
[1]陆嘉恒.Hadoop实战[M].北京：机械工业出版社，2012.
[2]李应安.基于MapReduce聚类算法的并行化研究[D].中山大学，2010.
[3]张石磊，武装.一种基于Hadoop云计算平台的聚类算法优化的研究[J].计算机科学，2012（10）：114-118.
[4]赖玉霞，刘建平.K-means算法的初始聚类中心的优化[J].计算机工程应用，2008（10）：147-149.
作者简介：崔莉霞（1989-），女，甘肃会宁人，硕士研究生，主要研究方向：数据挖掘、并行分布式计算。
聚类分析算法 篇7
随着科技的发展,网络中出现了一种新的表现形式Blog。本文主要是基于链接聚类算法来分析Blog网页,Blog页面具有不稳定性、即时更新性,以常用图聚类算法为基础,根据GMC算法来进行聚类,在此基础上提Blog聚类的图聚类算法。本文还对GMC算法制定相应的数学解决方案,以得到较高的算法运行效率。
1 对链接的分析
进行聚类是要在页面上寻找Blog相似内容讨论的社区,这些社区具有一定的谈论话题,有很多成员参与。本文进行链接聚类算法分析,就需要对Blog内链接的类型进行详细的分析,去掉对聚类结果分析没有意义的、会造成干扰的链接。
对于典型的Blog,对于一些链接,首先要剔除。一般Blog,除了日志内容外,还会有很多的链接,主要是为了进行用户本身的Blog内、日志作者所在的Blog站内、站外还有广告的跳转,这样的链接对于聚类分析是没有任何意义的。
对于正文内的Blog链接,则要分成两部分来考虑,一是和正文内容确实有关联的,二是一些Blog作者想扩大自己网页的影响面,会在文章的结尾用广告的方式插进去,这种链接,我们需要筛选出来剔除,但是这种链接比较难以识别,为保证聚类主题的核心,只好采用所有和Blog用户同一主域名的链接,全部忽略这在一定程度上会对合格的日志作者造成影响。
2 对聚类算法的分析
从广义上讲,Blog可以看作是一种类型的Web页面,但从现行的Blog页面形式来看,Blog网页中已经不存在传统意义上的中枢页面概念,作为Blog用户可以根据自己的需要随时增删自己的日志。而且,Blog也很少能成为比较权威的页面,主要是因为Blog日志更多记录的是个人生活化的随笔,因此,限制了Blog日志向权威方面的发展。我们用到的数据都是源自于网上的Blog的实时的收集。我们要建立一种比较适用于我们应用的图形聚类算法。现在对于邻接关系的图形聚类算法有好多种形式,一般在聚类算法中都是针对的无向图,在处理的过程中,一些有向图也被当作无向图了,文献[2]中对此作了比较详细的介绍。在这里介绍几种比较重要的常用的算法。
2.1 MCL(Markov Cluster)
这种聚类算法是以随机游走为基础的[3]。它的基本思想是,对于和每个节点相连的边,根据权重比较赋予游走的概率。比如节点有权重为0.51.5 3 4 5的四条边,则从该节点沿着这几条边走出去的概率分别为1/28,3/28,3/14,2/7,5/14,假如我们记k步以前从节点i走到节点j的概率聚阵为N(k),那么让k趋向于无穷大,我们就可以得到从一个节点走到另一个节点的概率矩阵N。取定适当的阈值,剔除N中的小概率元素,然后确定连通分支,得出最后的聚类结果。
MCL算法的实验结果,是比较理想的,但是它的致命缺点在于,对于规模比较大的图,中间求幂循环复杂度较高,尤其对于大规模的稀疏矩阵,计算出的中间结果N将很快变得稠密,导致无法充分利用图的边稀疏性这一特点。
2.2 ICC(Iterative Conductance Cutting)
这种聚类算法的基本思想和二分法比较相似,就是要对图不断地使用最小割算法进行二分,直至得到满意的结果。计算最小割NP-hard的,通常采用的是一种近似的poly-logarithmic的算法:
ICC算法的计算结果缺陷,就是它的聚类最重类的大小需要人工操作进行控制,这与我们Blog聚类开始的目标有一定的差距,我们的目的是紧密联系在一起的Blog页面,都可以作为一类,不用管这个类的规模大小。由于Blog的社会性或者说不确定性,我们面对如此庞杂的数据无法得出最终聚类的规模,而且也不适宜一刀切的模式来规划所有类,所以ICC并不适用于我们的应用。
2.3 GMC(Geometric MST Cluster)
GMC算法与前两个算法相比并不是那么直观和容易理解。它是从一类称作谱方法(Spectral Method)的算法中推演而来的。这类方法的一般过程可以总结如下:
1)对于给定的加权图G,计算它的邻接矩阵M;
2)计算M的特征向量x1,x2,…,xk;
3)利用x1,x2,…,xk生成聚类(该步通称为Interpretation)。
这类算法,第1)步基本上都是一样的。对于GMC,第2)3)步中的k通常设为2或者3。第3)步interpretation是最重要的,它决定着整个聚类的质量。GMC的第3)步可具体描述如下:(1)计算特征向量x1,x2,…,xk的一个加权和v;(2)利用v重新定义图中所有边的权重wi,j=|vivj|;(3)对新的权重计算该图的一个最小生成树(Minimum Spanning Tree,MST);(4)给定一个阈值,将(3)中得到的MST中所有权重小于该阈值的边砍掉;(5)计算各连通分支,即是最后的聚类结果。
综合起来,GMC算法可以描述如下:
1)计算邻接矩阵M并规一化为矩阵N(所谓规一化,即将每行的元素除以该行元素的和以使得每行元素和均为1);2)计算N的除1之外的最大的k个正特征值对应的特征向量(通常k取2,3);3)根据特征向量计算边的新权值;4)根据新权值生成MST;5)分别计算原图以及MST的平均权重和最大权重;6)根据平均权重和最大权重确定阈值;7)根据阈值删除MST中的相应边;8)求MST的连通分支,即是聚类结果。
GMC相对前两个算法来说,相对简单,且可充分地利用生成的邻接矩阵的稀疏性,最终聚类的效果也很不错[2]。
3 详细算法实现
我们的算法可以综述如下:
1)处理过滤Blog数据的链接,生成以页面(URL)为顶点,链接为边的图;2)处理图的邻接关系,产生邻接矩阵;3)使用GMC算法聚类。
其中第一步由于把图看作无向的来处理,因此对于两个页面相互链接的情况,可认为它们之间的边的权重为2,因此生成的是一个边权重可取1,2的无向图。
算法的第三步GMC算法的具体实现可参考3.3节中GMC算法的步骤,可以看到,GMC算法中除了第二步之外,其余的七步都很容易实现。对于第二步计算特征向量,注意到我们只需要求两到三个极端的特征对,因此我们采用了幂迭代的方法。但是通常来说,幂迭代只能求一个极端特征对,而我们要求的是多个。对于对称矩阵,有比较简单的方法:
对于n阶对称矩阵A,假设c1,c2,…,cn是它的特征值,v1,v2,…,vn是对应的正交单位特征向量,那么就有:
即对于对称阵,可采用从原矩阵中减掉极端特征对的方法来求第二极端的特征对。
但是,注意到要求特征对的矩阵N是规一化之后的,尽管规一化之前的邻接矩阵M是对称阵,但是不能保证N也是对称的。所以,还需要一点小技巧来求N的特征对。假设A是对称阵,D是以A的每行元素之和为对角元素的对角阵,N是A的规一化之后的矩阵,那么:
假设c,v是N的一个特征对,则:
这里D-1/2AD-1/2是对称矩阵,并且它的特征对可以很容易地转换成N的特征对,问题得以解决。
由于建立的图是一个规模较大的边稀疏的图,对应到邻接矩阵就是一个大规模的稀疏对称矩阵,需要充分地利用而不要破坏这一特性。GMC算法中,对称性虽然被破坏,但通过一个简单的变换来加以恢复,且这种变换后的矩阵稀疏性和原矩阵相同,从而稀疏性得以保留。幂迭代算法同样不会改变原矩阵的稀疏性,这样就可充分地利用稀疏矩阵的数值算法。
4 对实验作出分析
我们的实验数据是大约3千万个从网上随机抓取的Blog,运行平台是志强双核CPU(1.8GHz)+UNIX,每运行一次聚类算法,大约需要十五分钟,该时间说明程序的运行效率还是比较高的。
程序运行的结果大约产生了一百多万个聚类,其中绝大部分都是单个的页面作为一类,有大概一千个聚类是规模比较大的,这是有意义的结果,通过对其中网页内容的分析,基本上都是内容相关的,与我们目标相一致。至于单个页面作为一类的情况,是因为页面正文中没有有意义的链接,因此成为单独的一类。
5 结束语
综上所述,在Blog的特性基础上,提出了Blog聚类的图聚类算法,聚类的结果体现出了内容的相关性,也取得了不错的效果。但从实验结果中也可以看出,由于链接的稀疏性,在Blog上产生了大量的孤立节点,这些节点对于聚类来说是毫无意义的。单纯地采用链接分析的方法还是存在很大的缺陷,可以综合其他的算法来加强聚类分析,在一些文献中已经有了这方面的描述。
参考文献
[1]K.Bhatart,M.Henzinger.Improved Algorithms for Topic Distillation in Hyperlink Environments.The 21st ACM SIGIR Conf.on Research and Development in Information Retrieval,Melbourne,Australia,1998.
[2]U.Brandes,M.Gaertler,and D.Wagner."Experiments on graph clustering algorithms.",Proceedings of the ESA 2003 Eleventh European Symposium on Algorithms,pp.568-579,LNCS 2832,Berlin:Springer-Verlag,2003.
基于向量空间的文档聚类算法分析 篇8
1 文档聚类
通俗的讲, 文档聚类就是将内容相似的文档聚集为一个类中。这样, 可以将一个文档集分组为几个聚类簇, 使得同类文档的相似度尽可能大, 而不同类的文档间相似度尽可能小, 以达到文档分类的目的。文档聚类是一种无监督的机器学习方法, 不需要训练过程, 没有任何关于划分的先验知识和指导, 仅仅依靠文档间的相似度作为文档集合划分的准则, 因此具有一定的灵活性和自动化处理能力, 成为文本挖掘领域越来越多的人研究的热点。
目前, 聚类的方法主要有以下几种:划分法 (partitioning methods) , 层次法 (hierarchical methods) , 基于密度的方法 (density-based methods) , 基于网格的方法 (grid-based methods) , 基于模型的方法 (model-based methods) 。其中最常用的文档聚类算法是基于划分的k-means算法。
2 向量空间模型
向量空间模型是一种用来表示文档的方法, 它的思想是将文档分解为由词条特征构成的向量。具体做法是将文档进行分词, 然后计算文档中每个词条的权重, 权重计算可以利用TF-IDF算法, 由计算得到的权重构成一个矢量空间, 即形成这个文档的向量空间。例如, 文档Dj可以表示成如下的向量空间:
其中, m表示文档D中分词的特征词条数;Wij为词条ti在文档Dj中的权重。
3 k-means算法
3.1 文档相似度
k-means算法是利用多个文档形成的对应的向量空间来计算各个文档的相似性, 从而对多个文档进行聚类。K-means算法计算文档向量的相似度是采用基于距离的方法, 即文档之间的相似性是通过计算文档向量之间的距离来表示的, 空间向量的距离用如下公式表示:
距离越小, 则两个文档间的相似度就越大。当然, 也可以用余弦值来表示相似度。
3.2 k-means算法具体分析
k-means算法进行文档聚类的基本思想是:
1) 首先确定聚类的个数k, 即簇的数目k;
2) 随机选取k个文档对象, 作为初始聚类质心;
3) 计算剩余的文档向量到每个聚类质心的距离, 将剩余文档分配到距离它最近的一个聚类质心的划分;
4) 计算每个簇的文档对象的均值向量, 作为新的聚类质心;
5) 重复3) 、4) , 直到k个聚类不再发生变化, 即k个簇的聚类质心不再发生变化, 或者准则函数收敛为止。
通常采用的准则函数是平方误差准则, 其公式如下:
其中, X∈Ci, 表示X是簇Ci里对象, mi是簇Ci的质心。
下面, 通过具体的例子来进一步了解k-means算法。
假设有六个文档, 空间向量分别为X1= (1, 0) , X2= (2, 4) , X3= (1, 1) , X4= (3, 3) , X5= (2, 1) , X6= (4, 3) , 为计算简单起见, 假定为二维的。聚类个数k为2。
首先, 随机选取k=2个向量作为初始的聚类质心, 为m1=X3, m2=X5。
然后将剩余向量分配到距离最近的聚类质心所形成的划分中:
因此, X1属于m1对应的簇中。
同理可得, X2属于m2, X4属于m2, X6属于m2。
则第一次划分后得到的两个聚簇分别为C1= (X1, X3) , C2= (X2, X4, X5, X6) 。
再分别计算两个簇的质心:m1= (1, 0.5) ;m2= (2.75, 2.75)
计算平方误差
计算各个点到新的聚类质心的距离, 将它们分配到距离最近的质心所形成的划分中:
因此, X1属于m1对应的簇中。
同理可得, X2属于m2, X3属于m1, X4属于m2, X5属于m1, X6属于m2。
则第二次划分后得到的两个聚簇分别为C1= (X1, X3, X5) , C2= (X2, X4, X6) 。
再分别计算两个簇的质心:m1= (1.33, 0.67) m2= (3, 3.33)
相应的平方误差为:E12=1.3334, E22=2.6667, E2=1.3334+2.6667=4.0001
可以看出, 第一次迭代后, 平方误差显著减小, 从8降低到4.0001。
再次计算各个点到聚类质心的距离, 将他们分配到距离最近的质心所形成的划分中, 结果和上次的相同, 即为C1= (X1, X3, X5) , C2= (X2, X4, X6) 。可见, 第一次迭代也是最后一次迭代, 算法停止。
上述计算如图1所示。
3.3 k-means算法优缺点
k-means算法主要有如下优点:
1) k-means算法简单, 快速, 是解决聚类问题的一种经典算法。
2) k-means算法的复杂度是O (nkt) , 其中, n是所有聚类文档的数目, k是簇的数目, t是迭代的次数, 因此, 该算法具有较好的可伸缩性和很高的效率, 适合于处理大文档集。特别是当各簇之间的区别明显并且结果簇密集时采用该算法效果比较好。
但k-means算法也存在一些问题, 主要表现在如下两点:
1) 在k-means算法中需要事先确定聚类数目k的值, 但这个k值的选定通常是难以估计的, 因为多数时候我们并不知道给定的文档集应该分为多少个类别才合适。
2) k-means算法对于文档集中的噪声和孤立点非常敏感, 少量的这类文档对聚类结果将会产生较大影响。
4 k-中心点算法
由于k-means算法对噪声和孤立点非常敏感, 在这种情况下会影响到聚类的结果, 而k-中心点算法正好能解决k-means算法中的“噪声”敏感这个问题。
k-中心点算法 (k-mediods) 的基本策略是不采用簇中文档样本的平均值作为参照点 (质心) , 而是选取簇中的样本点作为参照点 (质心) , 而这个样本点在簇中的位置是最中心的。它的算法如下:
1) 随机选择k个文档对象作为初始的聚类质心。
2) 将剩余文档对象分配给离它最近的质心代表的簇中。
3) 随机选择一个非质心的文档对象, 计算用该文档对象替代质心的效果。
4) 若效果是使类簇更紧凑, 则可用该文档对象替代质心, 形成新的质心。
5) 重复2) 3) 4) , 直到k个质心不再发生变化。
但是, 如何评价上述所说的类簇紧凑程度呢?该算法使用绝对误差标准来定义一个类簇的紧凑程度。其公式如下:
其中, X∈Ci, 表示X是簇Ci里对象, mi是簇Ci的质心。
如果某样本点成为质点后, 其绝对误差小于原来质点所造成的绝对误差, 那么我们认为该样本点使得类簇更紧凑, 该样本点可以取代原质点。在一次迭代重新计算类簇质点的时候, 选择绝对误差最小的那个样本点成为新的质点。
那么, k-中心点算法如何能解决k-means算法中“噪声”敏感这个问题?首先让我们来分析一下为什么k-means算法会对“噪声”敏感。
k-means算法确定质点是通过对某类簇中所有的样本点的向量求平均值得到的, 而如果聚类的样本点中有异常点, 即“噪声”, 那么在计算类簇的质点位置的过程中会受到异常点的干扰, 导致得到的质点的位置与实际值有较大的偏差, 从而影响聚类结果。可大致通过一些数据举例说明。例如, 某类簇C1中已经包括了点X1= (1, 0) , X2= (2, 4) , X3= (1, 1) , X4= (3, 3) , 点A (100, 150) 为异常点, 当点A被纳入了类簇C1中, 此时计算C1的质心为 ( (1+2+1+3+100) /5, (0+4+1+3+150) /5) = (21.4, 31.6) , 可见导致了类簇C1质心的偏离, 那么在下一次迭代重新划分样本点的过程中, 可能会将不属于类簇C1的样本点也归入了类簇C1, 从而影响聚类结果。
而k-中心点算法则采用了新的方法选取质心, 每次迭代后质心的选取都是从聚类的样本点中得到, 从而可以解决k-means算法对异常点敏感的问题。
5 结束语
本文较为详细地叙述了基于向量空间的文档聚类算法中的k-means算法的基本算法过程以及优缺点, 并在此基础上又简要介绍了k-中心点算法, 主要针对k-中心点算法解决k-means算法对异常点敏感的问题。
摘要：随着科技的发展, 网络信息迅速增加, 而文本聚类技术则成为web文本挖掘中的研究热点。该文详细介绍了文档聚类算法中的基于划分的k-means算法, 对于k-means算法的缺陷, 又介绍了对k-means算法有所改善的k中心点算法, 并比较二者的优缺点。
关键词：文档聚类,向量空间模型,k-means算法,k中心点算法
参考文献
[1]万小军, 杨建武, 陈晓鸥.文档聚类中k-means算法的一种改进算法[J].计算机工程, 2003, 29 (2) :102-103.
[2]许伟佳.基于向量空间模型的文档聚类研究[J].电脑知识与技术, 2009, 5 (25) :7281-7283.
[3]何飞, 蒋冬初.基于向量空间模型的文档聚类算法研究[J].湖南城市学院学报:自然科学版, 2003, 24 (3) :114-116.
[4]杨建武.文本挖掘技术[Z].北京大学计算机科学技术研究所, 2010.
[5]新浪博客.聚类分析 (二) K-MEANS.[EB/OL].http://blog.sina.com.cn/s/blog_4882f26d0100pd21.html.
基于改进蚁群算法的聚类分析 篇9
数据聚类是数据挖掘中的一个重要课题,在很多领域有着广泛的应用,如模式识别、图像处理和数据压缩,破产预测、交通管理、塞车状况预测等方面都有过成功的应用等。聚类分析是按照不同对象之间的差异,通过无监督学习将样本按类似性分类,把相似性大的样本归为一类,每个聚类中心起着相应类型代表的作用。聚类分析是一种典型的组合优化问题[1]。
蚁群算法是一种新型仿生类进化算法,是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能优化算法,具有很强的通用性和鲁棒性。意大利学者Dorigo M等于1991年在法国巴黎召开的第一届欧洲人工生命会议上最早提出了蚁群算法的基本模型,1992年,Dorigo M又在其博士论文中进一步阐述蚁群算法的核心思想[2]。蚁群算法成功地应用于求解TSP、二次分配、 着色、车辆调度、集成电路设计及通信网络负载等问题。蚁群算法从提出到现在,以其在组合优化中的突出表现,吸引了人们的极大关注。
本文介绍一种蚁群聚类算法,并进行了改进,提出了改进的蚁群聚类算法。它改进蚂蚁形成解的方法,引入动态参数,采用最近原则和轮盘赌两种方式确定模式样本所属的类。改进的蚁群聚类算法将遗传算法中均匀交叉算子引入蚁群聚类算法,将遗传算法和蚁群算法融合,改善蚁群算法的搜索时间较长,容易出现停滞,过早地收敛于非最优解的现象。算法利用UCI机器学习数据库中的三个经典数据集iris、wine、glass进行实验,均取得较好的效果。
1 聚类分析
聚类是数据挖掘领域最为常见的技术之一,用于发现在数据库中未知的对象类。这种对象类划分的依据是“物以类聚”,即考察个体或数据对象间的相似件,将满足相似件条件的个体或数据对象划分在一组内,不满足相似性条件的个体或数据对象划分在不同的组。通过聚类过程形成的每一个组称为一个类[3]。
聚类分析就是从数据中寻找数据间的相似性,并依此对数据进行分类,把数据划分到不同的类中,使各类之间的离散度尽可能大,类内的离散度尽可能小。其一般数学描述为:
设模式样本集X={ Xi,| Xi=(xi1,xi2, …,xid), i=1,2, …,n }有n个样本,其中样本Xi=(xi1,xi2, …,xid)为d维向量,样本集有k个模式分类。
聚类问题就是要找一个划分C={C1,C2, …,Ck},满足:
其中d(Xi,mj) 表示第Cj类中模式样本Xi到该类中心mj的欧氏距离。
2 蚁群聚类算法
蚂蚁在寻找食物源时,能在其走过的路上释放一种特殊的分泌物—信息素,随着时间的推移该物质会逐渐挥发,蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越多时,其留下的信息素也越来越多,后来蚂蚁选择该路径的概率也越高,从而更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁,从而形成一种正反馈机制。通过这种正反馈机制,蚂蚁最终可以发现最短路径[4]。
基于上述蚂蚁觅食原理和求解TSP问题的基本蚁群算法[5],介绍一种蚁群聚类算法,用于解决聚类问题,其分述如下。
2.1 蚁群聚类算法中各元素的定义
在蚁群聚类算法中ACCA(Ant Colony Clustering Algorithm),模式样本Xi到聚类中心mj的欧氏距离为d(i,j)(i=1,2, …,n;j=1,2,…,k),启发函数定义为:η(i,j)= 1/ d(i,j)。样本Xi到聚类中心mj之间的信息素为τ(i,j) (i=1,2, …,n;j=1,2,…,k),信息素τ(i,j)积累在模式样本和聚类中心之间。目标函数为求式(1)中F的最小值。蚂蚁搜索模式样本所归属的聚类中心的概率计算公式如式(2),其中:α、β为参数。初始聚类中心为随机选取的k个模式样本点。蚂蚁搜索整个模式样本空间,形成一个聚类结果后,聚类中心mj各分量的值为该类Cj中模式样本各属性的均值,计算公式如式(3)。
2.2 解的形成及信息素的更新
蚂蚁a随机选择一个模式样本Xi作为起点,按式(2)计算该样本选择各个聚类中心的概率pij(j=1,2,…,k),根据概率pij确定所属的聚类r,1<r<k,模式样本Xi归并到类Cr中,蚂蚁再选择另一个模式样本,重复上述过程,再把它归属到相应的类中,如此循环,直到蚂蚁a搜索完所有的样本空间,形成一个解。
信息素的更新方式采用最大最小蚁群算法(MMAS)[2]中信息素的更新方式,即全局信息素更新方式。在本代进化过程中,仅对m只蚂蚁找到的最优值,所形成的聚类结果,进行信息素增加,其余衰减。信息素的更新方程如式(4),其中,△τ(i,j)为信息素的增量,lmb为最优聚类结果中各模式样本到其聚类中心的距离之和,Q、ρ(0<ρ<1)为参数,1-ρ(0<ρ<1)表示信息素挥发程度。
τ(i,j)= ρτ(i,j)+△τ(i,j) (4)
其中
2.3 蚁群聚类算法描述
蚁群聚类算法(ACCA)描述如下:
① 初始化。设定各参数α、β、ρ、Q的值,蚂蚁个数m,最大进化代数Nc,初始信息素τ(i,j)=1(i=1,2, …,n;j=1,2,…,k)。
② 初始化k个聚类中心。随机选取k个模式样本点作为初始聚类中心。
③ 计算模式样本到各聚类中心的距离d(i,j)及启发函数η(i,j)。
④ 每只蚂蚁按2.2节中解的形成方式独立地构造一个解。
⑤ 根据新构造的解和公式(3)计算新的k个聚类中心,计算目标函数F的值,即按公式(1)计算各模式样本到其聚类中心的距离之和。
⑥ 若m只蚂蚁都构造完成各自的解,则转⑦,否则转④。
⑦ 比较m只蚂蚁求的目标函数值,保存其最优值和最优解。
⑧ 按2.2节中信息素的处理方式进行全局信息素更新。
⑨ 若满足结束条件,则输出最优解,否则进化代数GEN=GEN+1,转③。结束条件为GEN>Nc或当前解已稳定。
3 改进的蚁群聚类算法
3.1 改进解的搜索方法
在2.2节解的形成过程中,蚂蚁按概率式(2)计算模式样本分配到各类的概率,依据概率确定所属的类。虽然这样可以聚类到最临近的聚类中心,但在进化初期,聚类中心很大程度上不是最优聚类中心,不利于发现更好的解,因此容易出现停滞现象,过早地收敛于非最优解。为了增加搜索的随机性,兼顾解空间的各种情况,搜索到最优解,向最优解进化,对蚂蚁确定模式样本所属类的方法进行改进。蚂蚁确定模式样本所属类采用两种方法:给定参数q0(0≤q0<1),生成随机数q(0≤q<1)。
(1) 当q≤q0时,蚂蚁按最近的原则将模式样本分配给一个类,即按式(5)计算,蚂蚁将模式样本分配给[τ(i,j)]α×[η(i,j)]β达到最大的类。
max([τ(i,j)]α×[η(i,j)]β) (5)
(2)当q>q0时,按概率公式(2)计算模式样本分配到各聚类中心的概率,然后采用轮盘赌的方法确定模式样本所属的类,这样既兼顾了概率大小,又增加了搜索的随机性。
轮盘赌(roulette-wheel)实现的伪代码如下:
① 生成一随机数r,0≤r<1 , i=0, s= pij;
② 如果s≥r,则转④;
③ i=i+1, s=s + pij,转②;
④ 被选中的聚类为i,输出i, 结束。
对上述给定的参数q0采用动态改变的方式。在进化的前期,由于初始信息素匮乏,信息素还不能很好地起到引导作用,q0取较大的值,这样蚂蚁较多地按最近的原则将模式样本分配给一个类,蚂蚁容易找到较好的解,减少蚂蚁的盲目搜索,缩短搜索时间,加快收敛速度。在进化的后期,q0取较小的值,蚂蚁较多地依据概率按轮盘赌方法确定模式样本所属类,在信息素的引导下,增加搜索的随机性,能有效地突破局部最优解,改善停滞现象,向最优解转化。
3.2 引入均匀交叉算子进一步改进解的质量
遗传算法中的均匀交叉过程是[7]:先随机地产生一个与父辈个体基因串具有同样长度的二进制串,该串中0表示不交换,1表示交换。该二进制串称为交叉模板,然后根据该模板对两个父辈基因串进行交叉,得到两个新基因串,即为后代新个体。例如
父辈个体A:10110111001 父辈个体B:00101100100
交叉模板:10011011100
→新个体A’: 00101100101 新个体B’: 10110111000
对蚁群聚类算法ACCA的改进体现在,保存进化以来得到的最好解best-solutions和每代m只蚂蚁搜索到的较好解local-solutions。把best-solutions和local-solutions作为两个父辈基因串,进行均匀交叉,得到两个新基因串个体,即两个新的聚类结果,计算这两个新个体的目标函数值,即式(1)F的值,若优于两个父辈个体,则作为best-solutions保留。均匀交叉算子能容易地产生很多随机的解,且对原有的解有很大的突破,兼顾解空间的多种情况,有效地改善了蚁群算法的早熟现象。
例如:假如有10个模式样本,需要聚成3类,聚类结果best-solutions的存储形式如:1123222333,其中1,2,3表示样本所属的类,位置表示第几个样本,即样本1聚在第1类,样本2聚在第1类,样本3聚在第2类,样本4聚在第3类等等。均匀交叉过程如下:
best-solutions:1123222333 local-solutions:2131222333
交叉模板:1001101110
→新个体A’: 2121222333 新个体B’: 1133222333
3.3 改进的蚁群聚类算法描述
通过对蚁群聚类算法(ACCA)的上述改进,本文提出改进的蚁群聚类算法IACCA(Improved Ant Colony Clustering Algorithm),其算法描述如下:
① 初始化。设定各参数α、β、ρ、Q的值,蚂蚁个数m,最大进化代数,初始信息素τ(i,j)=1(i=1,2,…,n;j=1,2,…,k)。
② 初始化k个聚类中心。随机选取k个模式样本点作为初始聚类中心。
③ 计算各模式样本到各聚类中心的距离d(i,j)及启发函数η(i,j)。
④ 每只蚂蚁按3.1节的方式确定模式样本所属的类,独立地构造一个解,且q0进化初期取值较大,后期取值较小,动态变化。
⑤ 根据新构造的解和公式(3)计算新的k个聚类中心,计算目标函数F的值,即按公式(1)计算各模式样本到其聚类中心的距离之和。
⑥ 若m只蚂蚁都构造完成各自的解,则转⑦,否则转④。
⑦ 比较m只蚂蚁求的目标函数值,保存其最好值和最好解。
⑧ 按3.2节方式,将求得的全局最好解和⑦步得到的本代最好解进行均匀交叉。如新解优于其父辈,则保存。重复执行此步若干次。
⑨ 按2.2节中信息素的处理方式进行全局信息素更新。
⑩ 若满足结束条件,则输出最优解,否则进化代数GEN=GEN+1,转③。结束条件为GEN>Nc或当前解已稳定。
4 仿真实验
实验数据来源于UCI机器学习数据库中的三个经典数据集:iris, wine, glass数据集。实验运行环境为:Pentium 4, 2.26G CPU, 512内存,Eclipse-SDK-3.4.1,Java编程。
实验参数:α=1,β=1, ρ=0.9,初始τ(i,j)=1,最大进化代数为Nc=200。进化初期q0=0.9,中期q0=0.8,后期q0=0.7。在iris、glass实验中Q=0.001,在wine中 Q=100。
实验采用k均值算法(k-means),蚁群聚类算法(ACCA),改进的蚁群聚类算法(IACCA)对上述三个数据集进行聚类分析,实验结果如表1、表2、表3所示。
表1为连续10次算法ACCA和IACCA运算结果,表2为连续100次算法ACCA和IACCA运算结果的统计。表2中IACCA求解的最优值、平均值、最差值等各指标均优于k-均值和ACCA,优于原数据集提供的分类结果求得的目标函数值。可以看出IACCA能容易收敛到最优解,求解结果稳定,通用性较强。
表2中,最优解次数为连续100次求解中各算法收敛到最优解的次数,对iris、wine数据集,IACCA收敛到最优解的次数达到84、82次,而k—均值和ACCA仅达到几次,差别明显,说明IACCA对初始数据不敏感,能突破局部最优,达到全局最优,稳定求解。对glass数据集,IACCA能求其最优解,而k-均值和ACCA求解其最优解困难。
表3反映了均匀交叉算子对解的改进情况,体现了均匀交叉的有效性。且均匀交叉计算简单,运算时间增加不多。
图1-图3分别为iris、wine、glass数据集用IACCA求解,收敛到最优解时,解的进化情况。横坐标为进化代数,纵坐标为目标函数值F。进化初期收敛较快,中后期变化充分,最后收敛到最优解。反映出参数q0在初期较大,蚂蚁较多按最近方法求解,快速找到较好解,积累信息素,收敛速度加速;在中后期,q0较小,蚂蚁较多依据概率按轮盘赌方式求解,在较好解附近搜索充分,找到更优解,影响信息素,最后收敛到最优解。
5 结 论
本文研究在分类数目已知,利用目标函数方法的聚类分析。在聚类算法上,根据蚁群觅食原理,利用蚁群算法模型解决聚类问题。通过元素的定义、解的形成、信息素的更新及算法描述介绍蚁群聚类算法,并对蚁群聚类算法进行改进,提出改进的蚁群聚类算法。算法的改进体现在:第一,蚂蚁确定模式样本所属的聚类中心采用两种方式:最近原则或轮盘赌,并依据动态参数随机选择这两种方式;第二,将遗传算法和蚁群算法融合,引入均匀交叉算子,来进一步改进解的质量。算法的改进加快了初期向较好解进化速度,信息素积累在较好解上,减少蚂蚁的盲目搜索,缩短搜索时间。中后期,算法增强搜索的随机性,在较好解附近充分搜索,兼顾解空间的各种情况,影响信息素,能有效地突破局部最优解,改善停滞,过早地收敛于非最优解的现象。实验选用UCI机器学习数据库中的iris、wine、glass经典数据集,对k均值算法(k-means),蚁群聚类算法(ACCA),改进的蚁群聚类算法(IACCA)进行测试。实验表明IACCA产生了上述作用,求解结果稳定,通用性较强,取得较好的效果。进一步需要解决的问题是:研究蚁群算法中各参数对算法的影响,使算法更稳定,更通用。
参考文献
[1]高坚.基于并行多种群自适应蚁群算法的聚类分析[J].计算机工程与应用,2003,25:78-79.
[2]Dorigo M.Optimization learning and nature algorithms[D].PhD.The-sis,Department of Electronics,Politecnico diMilano,Italy,1992.
[3]谢维信.工程模糊数学方法[M].西安电子科技大学出版社,1991:136-165.
[4]丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法的融合[J].计算机研究与发展,2003,40(9):1351-1356.
[5]王会颖,贾瑞玉,刘慧婷,等.一种求解TSP问题的分段交换蚁群算法[J].计算机工程与应用,2006,35:30-32.
[6]Stutzle T,Hoos H H.MAX-MIN ant system[J].Future Generation Computer Systems,2000,16(8):889-914.
聚类分析算法 篇10
当今时代的一个重要特点是信息爆炸、信息超载、信息过量, 这几乎成为每个人都需要认真面对的问题。如何不被海量信息而淹没?如何更深入的分析这些庞大的信息数据?如何发现信息数据背后隐藏的关系和规则?如何更好的利用这些数据信息, 从而获取有用的数据, 将他们加以加工利用。在“数据丰富而知识匮乏”的现象下, 数据挖掘和知识发现技术应运而生, 并得以在社会生活的各个领域蓬勃发展, 展现出其澎湃而强悍的生命力, 另一方面有用信息却很缺乏这种不正常现象。
本文就是利用当今最受关注且最具广泛应用前景的数据挖掘技术来对高校图书馆这一行业进行理论分析和应用研究。文中重点介绍了聚类分析的理论基础、算法设计和分析对比。其目的就是运用数据挖掘技术对图书管理系统数据库进行数据发掘, 通过对数据进行抽取、转换、分析和其他模型化处理, 得到大量数据中隐藏的有用知识, 为图书馆的决策与发展提供依据, 使有限的资源发挥更大的效率。
K-均值聚类算法步骤
聚类分析技术[3]是数据挖掘中进行数据处理的重要分析工具和方法。K-均值聚类算法 (K-means算法) 首次由Mac Queen于1967年首次提出。迄今为止, 很多聚类任务都选择这一经典算法。K-means算法是一种硬聚类算法, 利用函数求极值的方法得到迭代运算的调整规则, 它是数据点到原型的某种距离作为优化的目标函数, 算法采用误差平方和准则函数作为聚类准则函数, 是典型的局域原型的目标函数聚类方法的代表。K-均值算法的聚类准则是使每一聚类中, 多模式点到该类别的中心的距离的平方和最小。K-均值算法的主要思想是计算三个聚类中心的距离, 初始聚类中心在需要分类的数据中寻找K组数据, 将数据归入与其距离最近的聚类中心, 之后再对这K个聚类的数据计算均值, 作为新的聚类中心, 继续以上步骤, 直到新的聚类中心与上一次的聚类中心值相等时结束算法。具体算法步骤如下:
(1) 根据问题性质和经验确定K个初始聚类中心, Z11, Z21, ∧Zk1, 其中上标的序号为寻找聚类中心的迭代运算的次序号。聚类中心的向量值可选择初始K个模式样本的向量值作为初始聚类中心, 或者将数据随机分为K个类, 计算每个类的重心作为初始聚类中心。
(2) 对任一模式样本{x}逐个按距离平方和最小准则分配给K个聚类中心中的某一个Zj () 1。对所有的i≠j, j=1, 2, …, K, 如果Z11, Z21, ∧Zk1则, X∈Sjk其中k为迭代运算的次序号, 第一次迭代k=1, Sj表示第j个聚类, 其聚类中心为Z j (k+) 1。
(3) 通过上一步的迭代过程, 计算各个聚类中心的新的聚类中心Zj (k+1) , j=1, 2, …, K, 求各聚类域中所包含样本的均值向量:
其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心, 可使如下聚类准则函数J最小:
在这一步中要分别计算K个聚类中的样本均值向量, 所以称之为K-均值算法。
(4) 若Zj (k+) 1≠Zj (k+) 1, j=1, 2, …, K, 则返回第二步, 将模式样本逐个重新分类, 重复迭代运算;若Zj (k+) 1=Zj (k+) 1, j=1, 2, …, K, 则算法收敛, 计算结束。
实例分析
1.数据准备与预处理
在数字图书馆数据分析应用中, 用到的原始数据主要包括图书馆自动化系统数据库里的采访、编目、典藏、流通等的业务数据。数据挖掘分析主要用到数据集有三个, 即读者信息表、借阅信息表和馆藏图书信息表。
数据获取后, 还要对数据进行预处理, 预处理是清除数据源中不正确, 不完整的数据, 具体应用到图书馆数据库中, 主要是检查数据完整性和一致性、去除噪声、删除无效数据、填补丢失的域、去除空白数据域、考虑时间顺序和数据变化。通过一系列的数据预处理工作, 可以为下一步的数据挖掘过程提供良好的数据基础, 做好前期准备。
2.挖掘实验及分析
本文从图书馆提取2011年10月1日至31日的图书借阅记录, 并对数据进行预处理和字段合并, 最后生成一张聚类分析表, 共1450条记录, 包括8个字段, 即图书编号、图书名称、分类、存放区域、库存数量、价格、页数、借出次数, 通过K-均值聚类算法进行聚类分析, 假设初始值K=3, 经过4次迭代, 具体聚类结果如下表1所示。
图形化显示结果如下图1所示。
上图中列表示类别, 行表示聚类变量, 各个单元格以柱形高矮表示某类中某聚类变量均值的大小, 最后一列表示各个聚类变量的均值是否存在显著差异, 即变量的重要性区分。通过图表可以得出如下分析结论。
(1) 饼图显示了各类所包含的样本比例, 从图中可以看出第二类包含的样本个数最多, 但是其重要属性借出次数却比较少, 存放区域集中在CDE三个区域。而C区距离图书馆的入口较远, 说明该类图书的利用率不高, 主要集中于军事、哲学、宗教以及政治法律方面的书籍。第一类和第三类样本个数比较少, 但是第一类书籍借出次数明显高于其他两类, 存放区域都在A区, 而A区距离图书馆的入口较近。上述结果可以用来指导图书订阅与采购, 使图书资源的层次与结构更加科学化、合理化, 同时也有利于进行图书馆的馆藏布局调整提供依据。
(2) 上图最后一列显示出各个聚类变量的对聚类的重要程度, 从图中可以看出图书价格、库存数量以及图书页数对聚类影响不大, 而借出次数、图书分类、存放区域的均值显著影响着聚类结果。因此我们在进行图书馆资源进行数据挖掘时, 应该重点考虑。借出次数反映了该类图书的受欢迎程度, 图书分类反映了图书馆信息资源体系的科学性和合理性, 而存放区域即图书馆的馆藏布局也很大程度上影响着书籍的利用率。
小结
在基于图书馆流通日志信息的维度数据模型中, 聚类能够帮助分析人员从借阅事实中发现不同时期不同职称读者对书的偏爱状况根据数据模型的特点, 聚类操作可以得出在不同时期流通较活跃的图书分类在基于网站点击流维度数据模型中, 聚类能够帮助分析人员了解读者对不同类型新书的喜爱程度和检索图书的类型, 从而得出使用频率较高的图书分类。
聚类分析算法 篇11
关键词：学生成绩评价；教学管理；聚类算法；k-means
中图分类号：G434 文献标志码：A 文章编号：1673-8454（2014）13-0075-04
一、引言
在学校教育中，考试与教学不可分割，考试成绩扮演着检验学生学习情况和状态的重要角色。因此，成绩评价对于检测和监控教育质量、引导教师的教学行为，督促学生积极努力地学习是非常有必要的。现在，学校里拥有各种系统和各类数据库，积累了大量的学生成绩数据，但是由于工作人员缺乏相关挖掘知识和技术，只能通过Excel工具的简单统计获得少量信息，隐藏在这些大量数据中的信息不能得到应用。因此，如何利用学生前期的考试成绩数据进行统计分析对提高学生的知识水平有着至关重要的意义。面对这一挑战，数据挖掘技术应运而生，并逐渐显示出了强大的生命力，[1]作为数据挖掘的重要算法，k-means算法是一种硬聚类方法，即在n维的欧几里得空间把n个样本数据分成k类。[2]由于k-means聚类算法对噪声和孤立点敏感以及对处理大数据集非常有效的特点，[3]本文将k-means算法应用于成绩分析，从而全面地分析学生考试结果。
本文所引用的文献一阐述了成绩管理的作用、现状以及现有成绩管理的不足，并说明了决策树算法及粗糙集理论在成绩管理中的作用；文献二介绍了k-means聚类算法，并在此基础上提出了一种改进的遗传k-means聚类算法；文献三在分析k-means聚类算法优缺点的基础上进行改进，并通过实验比较了改进算法与原算法的优劣；文献四介绍了典型的数据预处理技术，实现了一种基于日志请求的参考文件的启发式会话识别算法。
论文利用k-means聚类算法对学生的成绩进行评价、统计和分析，从而确定学生的学业成绩在一个群体中所处的相对位置，为提高学生的成绩做准备，为教学工作提供反馈信息，并采取针对性的补救措施，从而进一步提高学校的教学质量。
二、基于聚类算法的成绩评价方案
1.总体设计方案
本论文将按图1所示，设计总体方案。同时论文将选用所在学院的成绩数据库，成绩数据库中包括了学生所有课程的考试成绩。
第一步，数据采集，为了保证数据的完整性和准确性，首先必须做好原始数据的选择和整理工作，本文选取学院某个年级的学生在某一学期的课程成绩。
第二步，数据预处理，数据预处理是一个逐步深入、由表及里的过程，经过数据审查、数据清理、数据转换和数据验证四大步骤对数据进行预处理，解决数据冲突和数据不一致等问题，最终形成一份学生成绩表。[4]
第三步，执行聚类算法在确定挖掘任务后，通过编写k-means聚类算法在matlab程序代码，实现k-means在学生成绩分析上的处理。
第四步，聚类结果评价，对聚类结果所发现的信息进行解释和评价。采用k-means聚类算法后，在学生成绩评价中，每一个类就是一个成绩群，不同的类相应地对各个成绩群进行了划分，也相应地给出了不同成绩群的中心成绩，这些中心成绩就是学生成绩划分参考标准之一。
第五步，提出针对策略，将挖掘出来的信息提供给教学决策者，调整教学策略，进一步指导教学工作，提高学生成绩。
2.基于k-means的算法设计原理
图2给出了K-means算法研究学生成绩的流程，在整个设计流程中，存在两个关键问题，分别是成绩的表示和成绩的距离计算，对于第一个问题，论文将每个学生各科目的考试成绩看做q维向量，记作xi=（x1i，x2i，…，xqi），（i=1，2，…，n），其中xki表示学生编号为i的第k门科目的成绩，成绩采用百分制，并根据不同的科目赋予不同的权重。对于第二个问题，论文采用欧式加权距离来定义学生成绩之间的距离，将聚类组数设为P，cj（j=1，2，…，p）为聚类中心，则成绩到聚类中心的距离可以用公式表示为：
xi-cj=■，（1≤j≤p）（1）
其中，q为粒子的属性组成的维数，？諼k为各属性的权值；
对所有学生的各科成绩进行分组聚类的K-means聚类算法的具体步骤如下：
Step1：设学生成绩集为Q=（x1，x2，…xn-1，xn），其中xi=（x1i，x2i，…，xqi）；
Step2：随机选取每个类里的一个粒子作为初始聚类中心c1，c2，…，cP；
Step3：根据公式（2）将学生成绩集Q中的对象xi（i=1，2，…，n）依次按欧式平均距离分配给距离最近的中心cj（j=1，2，…，p）。
xi-cj=min（■），（1≤j≤p）（2）
其中，q为粒子的属性组成的维数，？諼k为各属性的权值；
Step4：按公式（3）计算P个聚类新的中心cj（j=1，2，…，P）。
cj=■■xi，j=1，2，…，P（3）
其中，Nj为第j个聚类Sj中所包含的粒子个数；
Step5：如果各个聚类中心cj（j=1，2，…，p）不再变化，否则结束，否则返回Step3。
3.基于成绩评价的学生管理策略
在论文设计方案中，将学生（其中不包含不及格需要补考的学生）分为四类，分别是优秀、良好、中等、偏差，并从自我发展和教学管理两方面向不同类别的学生提出了建议性策略。（见表1）endprint
三、实证分析
1.实例描述与成绩评价过程
第一步：数据采集
通过学院提供的数据库，选取某个年级的学生在某一学期的课程成绩。学生该学期均有8门功课，分别是信息资源管理、概率论、会计学、口语、工程力学、毛概、体育、数学实验，依次对应的加权是0.2、0.2、0.2、0.1、0.1、0.1、0.05、0.05，学生成绩均为百分制，随机选择200名学生的成绩形成一张原始成绩单。
第二步：数据预处理
论文将200名学生原始成绩单集成为一张成绩单。通过数据处理，使表中的每一个数据都是唯一和没有疑义的，同时对空白数据进行填补或者删除。首先考虑到数据库中存在“0分”异常数据会对k-means算法造成很大的影响，因此本论文不将其考虑在研究范围内。同时，通过Excel工具将成绩小于60分的选出，所对应的该学生成绩也不采取k-means算法进行处理，因为成绩一旦低于60分，该学生要进行补考，相应分数也会做更改处理。本论文数据采集的200名学生中一共有10人出现挂科情况，接下来会对剩下的190名学生的考试成绩做k-means算法处理。
第三步：k-means算法对学生成绩进行分析处理
确定聚类个数k值，聚类个数要接近于所用的聚类变量的个数，本次实验选取k=4。通过数据初始中心分析，随机选择几个学生的学习成绩作为初始聚类中心，通过matlab算法实现。
实验结果可视化：（见图3-图7）
2.实证结果分析
（1）由图3可知，第二类学生成绩为优秀，第一类学生成绩为良好，第三类学生成绩为中等，第四类学生成绩为偏差。通过计算，优秀和良好的人数占总人数的47%，中等和偏差的人数占总人数的48%，其余为存在挂科学生的比例，说明本文随机选取的这个专业整体的学习状态有待进步，相关教职人员和教师应该采取必要的措施提高学生学习的积极性。同时，通过分析研究还可以发现，每一科学生成绩随中心的变化都会影响整体成绩的分布情况，特别是像会计学、概率论、信息资源管理等加权比较重的科目。
（2）如图4、5、6、7所示，距离第二个聚类中心更近的21名学生聚成一类；距离第三个聚类中心更近的52名学生聚成一类；距离第四个聚类中心更近的44名学生聚成一类；距离第一个聚类中心更近的73名学生聚成一类。从中可以看出相近的成绩都被划分到了同一类，从而弥补了传统划分方法“在学生成绩差别不大的情况下，经过划分后结果可能相差很大”的缺陷。
（3）聚类分析技术的应用不仅可以使190名学生清楚自己相对于整体成绩的位置，还可以体现某类学生某些学科的不足，从而提醒教学人员针对性地采取相应的措施，实验结果可以为教学人员制定出有针对性的解决办法提供依据，从而提高学生后期的学习成绩。
四、结论
本文研究k-means聚类算法在学生成绩评价分析中的应用。通过对数据的预处理，采用k-means算法，利用matlab工具对数据进行处理分析，弥补了传统统计方法的缺陷。并针对不同类型的学生，给出了学生自我发展策略和教学管理策略，从而为后期提高学生成绩和教学质量做准备。
参考文献：
[1]谭庆.基于k-means聚类算法的试卷成绩分析研究[J].河南大学学报（自然科学版），2009，39（4）： 412-415.
[2]刘婷，郭海湘，诸克军，高思维.一种改进的遗传k-means聚类算法[J].数学的实践与认识，2007，37（8）：104-111.
[3]周爱武，于亚飞. k-means聚类算法的研究[J].计算机技术与发展，2011，21（2）：61-65.
[4]张丽伟，李礼.Web 挖掘中数据预处理技术研究[J].电脑知识与技术，2010，6（15）： 4324-4325.
（编辑：王天鹏）endprint
三、实证分析
1.实例描述与成绩评价过程
第一步：数据采集
通过学院提供的数据库，选取某个年级的学生在某一学期的课程成绩。学生该学期均有8门功课，分别是信息资源管理、概率论、会计学、口语、工程力学、毛概、体育、数学实验，依次对应的加权是0.2、0.2、0.2、0.1、0.1、0.1、0.05、0.05，学生成绩均为百分制，随机选择200名学生的成绩形成一张原始成绩单。
第二步：数据预处理
论文将200名学生原始成绩单集成为一张成绩单。通过数据处理，使表中的每一个数据都是唯一和没有疑义的，同时对空白数据进行填补或者删除。首先考虑到数据库中存在“0分”异常数据会对k-means算法造成很大的影响，因此本论文不将其考虑在研究范围内。同时，通过Excel工具将成绩小于60分的选出，所对应的该学生成绩也不采取k-means算法进行处理，因为成绩一旦低于60分，该学生要进行补考，相应分数也会做更改处理。本论文数据采集的200名学生中一共有10人出现挂科情况，接下来会对剩下的190名学生的考试成绩做k-means算法处理。
第三步：k-means算法对学生成绩进行分析处理
确定聚类个数k值，聚类个数要接近于所用的聚类变量的个数，本次实验选取k=4。通过数据初始中心分析，随机选择几个学生的学习成绩作为初始聚类中心，通过matlab算法实现。
实验结果可视化：（见图3-图7）
2.实证结果分析
（1）由图3可知，第二类学生成绩为优秀，第一类学生成绩为良好，第三类学生成绩为中等，第四类学生成绩为偏差。通过计算，优秀和良好的人数占总人数的47%，中等和偏差的人数占总人数的48%，其余为存在挂科学生的比例，说明本文随机选取的这个专业整体的学习状态有待进步，相关教职人员和教师应该采取必要的措施提高学生学习的积极性。同时，通过分析研究还可以发现，每一科学生成绩随中心的变化都会影响整体成绩的分布情况，特别是像会计学、概率论、信息资源管理等加权比较重的科目。
（2）如图4、5、6、7所示，距离第二个聚类中心更近的21名学生聚成一类；距离第三个聚类中心更近的52名学生聚成一类；距离第四个聚类中心更近的44名学生聚成一类；距离第一个聚类中心更近的73名学生聚成一类。从中可以看出相近的成绩都被划分到了同一类，从而弥补了传统划分方法“在学生成绩差别不大的情况下，经过划分后结果可能相差很大”的缺陷。
（3）聚类分析技术的应用不仅可以使190名学生清楚自己相对于整体成绩的位置，还可以体现某类学生某些学科的不足，从而提醒教学人员针对性地采取相应的措施，实验结果可以为教学人员制定出有针对性的解决办法提供依据，从而提高学生后期的学习成绩。
四、结论
本文研究k-means聚类算法在学生成绩评价分析中的应用。通过对数据的预处理，采用k-means算法，利用matlab工具对数据进行处理分析，弥补了传统统计方法的缺陷。并针对不同类型的学生，给出了学生自我发展策略和教学管理策略，从而为后期提高学生成绩和教学质量做准备。
参考文献：
[1]谭庆.基于k-means聚类算法的试卷成绩分析研究[J].河南大学学报（自然科学版），2009，39（4）： 412-415.
[2]刘婷，郭海湘，诸克军，高思维.一种改进的遗传k-means聚类算法[J].数学的实践与认识，2007，37（8）：104-111.
[3]周爱武，于亚飞. k-means聚类算法的研究[J].计算机技术与发展，2011，21（2）：61-65.
[4]张丽伟，李礼.Web 挖掘中数据预处理技术研究[J].电脑知识与技术，2010，6（15）： 4324-4325.
（编辑：王天鹏）endprint
三、实证分析
1.实例描述与成绩评价过程
第一步：数据采集
通过学院提供的数据库，选取某个年级的学生在某一学期的课程成绩。学生该学期均有8门功课，分别是信息资源管理、概率论、会计学、口语、工程力学、毛概、体育、数学实验，依次对应的加权是0.2、0.2、0.2、0.1、0.1、0.1、0.05、0.05，学生成绩均为百分制，随机选择200名学生的成绩形成一张原始成绩单。
第二步：数据预处理
论文将200名学生原始成绩单集成为一张成绩单。通过数据处理，使表中的每一个数据都是唯一和没有疑义的，同时对空白数据进行填补或者删除。首先考虑到数据库中存在“0分”异常数据会对k-means算法造成很大的影响，因此本论文不将其考虑在研究范围内。同时，通过Excel工具将成绩小于60分的选出，所对应的该学生成绩也不采取k-means算法进行处理，因为成绩一旦低于60分，该学生要进行补考，相应分数也会做更改处理。本论文数据采集的200名学生中一共有10人出现挂科情况，接下来会对剩下的190名学生的考试成绩做k-means算法处理。
第三步：k-means算法对学生成绩进行分析处理
确定聚类个数k值，聚类个数要接近于所用的聚类变量的个数，本次实验选取k=4。通过数据初始中心分析，随机选择几个学生的学习成绩作为初始聚类中心，通过matlab算法实现。
实验结果可视化：（见图3-图7）
2.实证结果分析
（1）由图3可知，第二类学生成绩为优秀，第一类学生成绩为良好，第三类学生成绩为中等，第四类学生成绩为偏差。通过计算，优秀和良好的人数占总人数的47%，中等和偏差的人数占总人数的48%，其余为存在挂科学生的比例，说明本文随机选取的这个专业整体的学习状态有待进步，相关教职人员和教师应该采取必要的措施提高学生学习的积极性。同时，通过分析研究还可以发现，每一科学生成绩随中心的变化都会影响整体成绩的分布情况，特别是像会计学、概率论、信息资源管理等加权比较重的科目。
（2）如图4、5、6、7所示，距离第二个聚类中心更近的21名学生聚成一类；距离第三个聚类中心更近的52名学生聚成一类；距离第四个聚类中心更近的44名学生聚成一类；距离第一个聚类中心更近的73名学生聚成一类。从中可以看出相近的成绩都被划分到了同一类，从而弥补了传统划分方法“在学生成绩差别不大的情况下，经过划分后结果可能相差很大”的缺陷。
（3）聚类分析技术的应用不仅可以使190名学生清楚自己相对于整体成绩的位置，还可以体现某类学生某些学科的不足，从而提醒教学人员针对性地采取相应的措施，实验结果可以为教学人员制定出有针对性的解决办法提供依据，从而提高学生后期的学习成绩。
四、结论
本文研究k-means聚类算法在学生成绩评价分析中的应用。通过对数据的预处理，采用k-means算法，利用matlab工具对数据进行处理分析，弥补了传统统计方法的缺陷。并针对不同类型的学生，给出了学生自我发展策略和教学管理策略，从而为后期提高学生成绩和教学质量做准备。
参考文献：
[1]谭庆.基于k-means聚类算法的试卷成绩分析研究[J].河南大学学报（自然科学版），2009，39（4）： 412-415.
[2]刘婷，郭海湘，诸克军，高思维.一种改进的遗传k-means聚类算法[J].数学的实践与认识，2007，37（8）：104-111.
[3]周爱武，于亚飞. k-means聚类算法的研究[J].计算机技术与发展，2011，21（2）：61-65.
[4]张丽伟，李礼.Web 挖掘中数据预处理技术研究[J].电脑知识与技术，2010，6（15）： 4324-4325.
聚类分析算法 篇12
目前,各层次图书馆的藏书数量也有了很大的提高。但与文化氛围明显提升相对的是,随着图书数量的不断增加,图书管理的难度也逐渐增大。以前老套的图书管理系统越来越不能满足图书馆管理需要。
二、聚类分析算法
1.聚类分析法的概念简介
聚类分析法是指通过对物体(数据)的特性进行分类,从而挖掘出想要的数据,是数据挖掘中一种最常见的技术。通过对物体个体的特性进行充分研究、观察个体间的相似性与差异性,将相似的数据或物体归入一个类别内,不同的放入另一个类别,然在再通过分析重新整理的数据系统,分析或查找想要的数据,从而得出想要的结论。
2.聚类划分及其算法简介
聚类分析法根据不同数据类型、分类目的有着不同的划分方法和计算方法。要运用聚类分析法对事物进行有效的分析,就必须根据实际情况对不同的数据选择不同的分类方法。同时如果聚类分析法被用来进行描述性和探索性的分析工具,就可以选择多个分析法对同一数据进行分析研究,从而获得具体、准确的描述。
(1)聚类划分方法
聚类划分方法根据划分对象的不同分为四种方法,即层次分析法,划分方法、基于密度的方法以及基于网格的方法。这四种分析方法根据使用对象的不同而有不同的作用,只有根据具体的对象实施具体的方法才能真正发挥聚类分析法的作用。
(2)典型的聚类算法
聚类分析方法根据不同的对象有不同的划分方法,同样根据不同的划分方法有着不同的聚类算法。典型的聚类算法主要有以下四类,即CLARANS算法、 DBSCAN算法、BIRCH算法以及CURE算法,其中CURE算法则属于层次划分方法,应用也最为广泛。这四种聚类算法解决了医学、工程等不同行业中的归类问题。
3.各种聚类方法计算性能的比较
通过以上我们对聚类分析法的各种划分方法以及计算方法的简单介绍,我们可以知道聚类分析法没有绝对的好与坏,各种方法都有自己独特的优缺点,在不同的方面,不同的领域有着不同的应用。
4.聚类分析方法在图书管理系统中应用的可行性分析
(1)技术的可行性
聚类分析法能不能在图书管理系统中进行充分的应用,节省人力、物力,提高图书管理工作的工作效率,主要看是否达到了以下要求:第一,各种聚类分析法的硬件设备、软件设备是否齐全。第二,各种技术人员的技术水平是否支持;第三,能不能将这种技术与图书管理系统结合起来。目前,随着计算机技术的不断发展,各种计算机专业人才辈出,在技术上计算机能够快速精准地处理并传递信息,就为聚类算法在图书管理系统中的应用提供了充分的技术条件。
(2)经济上的可行性
聚类方法的使用却大大地节省了人力、节省了很多资源、并从很大程度上提高了图书管理的工作效率, 其潜在的价值十分巨大。其潜在价值比所付出的成本有过之而无不及,同时,图书馆费用支出主要用于图书的购买与维修上,因此,聚类分析法在图书管理上具有可行的经济性。
三、聚类分析法在图书管理系统中的应用
1.读者的年级聚类
为了进一步提高图书管理的效率,可以将读者及其年龄与性别、行业进行分类,从而提供专门适合其阅读、借阅量大的图书,这时只要读者进入系统中进行查询,就能够快速找到自己需要的书籍。
2.对图书的特性与使用效率进行聚类
对读者借阅图书的次数与借阅书籍类别进行分析研究可以发现,不同的行业、不同的年龄对于不同的图书有着不同的需求,因此,就可以通过层次分析法对其进行具体分类,方法为:输入读者行业、性别或年龄以后就会出现相应图书借阅的种类、借阅次数、以及不同读者对图书的需求种类。
随着聚类分析法的发展和广泛传播,图书管理系统也有了较大的改进,通过对聚类分析法原理的吸收、 借鉴,图书管理系统在分类收藏,扫描借出入上取得了巨大的成就。聚类分析法的引入,极大地提高了图书管理系统的工作效率,为读者进行阅读提供了一个良好的平台。
摘要：随着国家对图书馆建设的重视,相应的书籍迅速充实,图书管理的难度逐渐增大。随着高新技术的不断引入,聚类分析法也被作为一种高新技术设计进入了图书管理系统,聚类分析法的介入,极大地提高了图书管理效率,促进了图书馆管理水平的提高。而本文正是在介绍聚类分析法的概念、聚类方法的基础上,重点研究了如何将聚类分析法融入到图书管理中,从而为图书管理系统的改进提出意见,为图书馆管理者的决策提供必要的决策依据。