基于几何光滑度的案例聚类方法

来源:用户上传      作者: 刘 强

　　摘要:聚类分析技术是近年迅速发展的一种数据处理技术,它在诸如经济学、生物学、统计学、机器学习、数据挖掘等许多领域具有广泛的应用。首先阐述聚类分析的基本概念,接下来介绍了当前典型的几种聚类方法,然后提出了基于几何光滑度的光滑拼接聚类算法,最后提及了聚类算法的未来发展。
　　关键词:聚类分析;相似度;共享最近邻;k-平均算法;数据挖掘
　　中图分类号:F224.0 文献标志码:A 文章编号:1673-291X(2010)05-0238-03
　　
　　引言
　　随着信息技术的不断发展,数据库应用的范围、规模和深度也在不断的扩大,这样就导致积累了大量的数据,而人们所关心的往往是这些数据背后所隐藏的信息。目前,商业界普遍使用的条形码和科学研究领域利用先进的数据测量仪器所测出的数据,这些数据都是海量的。面对这样庞大的数据库,人们迫切的需要一种有效的技术从这些庞大的数据中智能、自动地提取出来有价值的知识或是信息,这就是所谓的数据挖掘技术。而聚类分析正是数据挖掘所采用的关键技术之一,它被用于发现隐藏在大量数据中的分组和令人感兴趣的数据模式。迄今为止,人们提出了许多聚类算法,所有这些算法都试图解决大规模数据的聚类问题。
　　一、聚类的基本概念
　　1.聚类的定义
　　所谓聚类[1],就是将一个数据集合分成若干个称为簇或是类别的子集,每个簇中的数据都是具有很高的相似度,而簇之间具有较低的相似度。
　　簇的定义[2]:由于不同的应用所分析的具体数据具有不同的特征,因此聚类的目标簇具有不同的的形式和定义。简单的来讲,簇就是聚类分析结果中由相似的数据对象所组成的一个个的分组就成为簇,同一簇中的点具有很高的相似性,不同簇中的点具有很高的相异性。
　　2.聚类的一般步骤
　　聚类分析一般的主要步骤如下:
　　(1)特征选择。首先必须适当的选择特征,尽可能多的包含任务所关心的信息。在选择特征中,信息的多余减少和最小化是主要的目的。
　　(2)相似性度量。用于定量度量两个特征向量之间的相似度。一个简单的度量如欧氏距离经常被用来反应两个特征向量之间的非相似度。
　　(3)聚类算法。已经选择了合适的相似性度量,这步涉及到选择特定的聚类算法,用于揭示数据集中隐藏的数据结构。
　　(4)结果验证。一旦用聚类算法得到了结果,就需要验证其正确性。
　　(5)结果的判定。在许多情况下,应用领域的专家必须用其他实验数据和分析判定聚类结果,最后得出可被人理解的正确的结论。
　　3.聚类的典型要求
　　一种好的健壮的聚类方法应当具有可伸缩性、具有处理不同类型属性的能力、能够发现任意形状的簇、先验知识最小化、具有处理噪声数据的能力、对输入数据的顺序不敏感、具有处理高维数据的能力、基于约束的聚类、具有可解释性和可用性。
　　二、典型的聚类方法
　　1.基于划分的方法
　　给定一个包含n个数据对象的数据库,以及要生成簇的数目k,一个基于划分的聚类算法将数据对象组织为k个划分(k

　　1.SNN相似度
　　数据对象之间相似的程度取决于它们共享最近邻的数量。任一数据对象的k个最近邻组成 一个最近邻列表,两个对象之间的共享最近邻为它们最近邻列表的交集。特殊地,当两个对象的k最近邻列表完全一致时,它们的相似程度最大。SNN相似度就是它们共享的近邻个数。计算SNN相似度可利用下述算法。
　　2.相关定义
　　如前所述,SNN相似度就是它们共享的最近邻个数。通过算法1我们能够计算出所有样本间的SNN相似度并组成相似度图。随后我们可以应用到基于SNN的聚类算法中,但是一般的基于SNN的聚类算法如JP聚类[7]和基于SNN密度聚类[8]都存在一个共同的缺点:一个样本集是分裂成两个类还是保持不变,可能依赖于一条链,这使它们显得有些脆弱。例如,如果有3个样本x1,x2,x3,x1和x2有一个很高的SNN相似度,x2和x3也有一个很高的SNN相似度,但x1和x3的SNN相似度却为0,这时应用JP聚类算法或基于SNN密度聚类算法,x1,x2,x3一般会归到一类中去。这显然不是很好的聚类。因为直观上看,如果这3个样本是一类,那么x1和x3也应该有一个较高的SNN相似度,而不至于很快降为0。这类似于几何中计算参数曲线拼接问题,如果两条参数曲线在拼接点满足越高阶的导数连续性,拼接后的曲线就被认为越光滑,在直观上也觉得它更象一条曲线了。因此,我们根据几何中的这种现象提出基于SNN相似度的n阶光滑度的定义。在此基础上再提出光滑拼接聚类算法。
　　定义1:如果有一条长链,由2n+1个样本点x-n,…,x-1,x0,x1,…,xn组成。假设链可表示为:x-n?圮x-n+1?圮…?圮x-1?圮x0?圮x1?圮…?圮xn-1?圮xn,其中,每个样本点和其后的样本点之间的SNN相似度是这两个样本点组成的单链强度(大于0)。我们把这个长链看作是一个短链x-n?圮x-n+1?圮…?圮x-1?圮x0与另一个短链x0?圮x1?圮…?圮xn-1?圮xn在x0处的拼接。如果x-1与x1的SNN相似度不为0,则称原长链在x0处是1阶光滑的;否则称为0阶光滑的;如果x-2,x-1,x1,x2的两两SNN相似度都不为0,则称原长链在x0处是2阶光滑的;一直下去,如果有x-n,…,x-1,x1,…,xn两两之间SNN相似度都不为0,则称原长链在x0处是n阶光滑的。
　　定义2:如果有一条长链,由n+1个样本点x0,x1,…,xn组成。假设链可表示为:x0?圮x1?圮…?圮xn-1?圮xn,其中,每个样本点和其后的样本点之间的SNN相似度是这两个样本点组成的单链强度(大于0)。我们把这个长链看作是一个单链x0?圮x1与另一个短链x1?圮…?圮xn-1?圮xn在x1处的拼接。如果x0与x2的SNN相似度不为0,则称原长链在x1处是1阶单侧光滑的;否则称为0阶单侧光滑的;如果x0,x2的SNN相似度也不为0,则称原长链在x1处是2阶单侧光滑的;一直下去,如果有x0 , x1,…,xn两两之间SNN相似度都不为0,则称原长链在x1处是n阶单侧光滑的。
　　3.算法设计
　　通过算法1我们可以从数据集{xi1≤i≤m}中计算出任意两个样本间的SNN相似度,并组成一个m×m阶的SNN相似度矩阵。从此矩阵中可以找出Cm2个单链,其中,每个单链的强度为两个样本点的SNN相似度。如果两个短链中含有相同的样本点,我们可以考虑把它们合并成一条链,并检查这种拼接在拼接点是否满足s阶光滑(如果两条都是单链,则s只能取1),如果满足,就合并;否则,它们就不拼接而维持原状。由于拼接需要考虑光滑度,因此这种拼接聚类不仅仅依赖于单链的强度,s值如果过大,会导致一些单链无法拼接。这将会导致类别数目过多。假设已有一个连通图,而一条单链要在连通图的一个节点处拼接,从这个节点出发在连通图中可以找到若干条短链,这个单链要与这些短链在拼接点满足一个指定的光滑度。因为拼接要有确定的先后顺序,以保持实验结果的稳定,所以我们预先将单链集中的单链按强度(即SNN值)由大到小排序。这样先拼接的单链的强度大,但光滑度要求低;后参加拼接的单链的强度(同一类内而言)越来越小,但光滑度要求越来越高。由此可知,这种拼接是强度和光滑度之间互补的。这显然是合理的,因为如果一个样本点要加入一个类中,如果和类中的某个样本没有很大的SNN相似度,那么它至少应该和这个类中的很多样本有一个共享最近邻(SNN值为1)。由于算法内含强度和光滑度互补的运行机制,因而算法本身不需要设置参数。在拼接过程中,满足条件就进行拼接,但在第k层节点拼接之间,我们可以删除之前的第k-1层节点的单链,因为这些节点已经属于一类,无需参加拼接,这样单链集容量就能迅速降低,加快算法。
　　具体的基于SNN相似度的光滑拼接聚类算法可以描述如下:
　　四、实验与分析
　　本次试验我们采用数值型数据进行试验,这样可以简化操作,便于进行数据进行处理,突出我们所采用的聚类算法的有效性。
　　1.数据集
　　实验所采用的数据集来源于国家从2004―2007年全国总共发生的洪涝灾害,总共由100条数据点组成。在这个数据集中,我们可以将取值密集但相同的变量去掉,并将一些非数值文字型的不影响实验结果的变量去掉,最终每个数据点都是一个24维的向量。
　　2.实验结果分析
　　对于算法1中我们将最近邻参数k取值为常数6,算法2中光滑度参数s取定值为1。我们采用算法2进行聚类分析,在结果中我们发现类别编号1、3、5、7四个类是算法所发现的类,这些类中数据点相对集中,其他还有少量数据点的类别均看作是噪声。并且发现四级响应级别数据点相对比较集中。并发现那些被看做是噪声的数据点一般都是属于个别年份离类别较远的数据点。
　　聚类分析是数据挖掘中的一种非常实用的技术,它能够发现大量数据背后所隐藏的数据分布模式与关联规则,以便提供给我们有价值的信息。目前聚类算法已经应用到许多领域,但是仍然存在诸多缺陷。今后,聚类算法将在可伸缩性、容错性、易用性、处理高维数据等方面加以提高和改进,以便能够更好地应用于更多的领域,解决其他方法不能够解决的问题。
　　
　　参考文献:
　　[1] Han JiaWei.Kamber数据挖掘概念与技术[M].北京: 机械工业出版社, 2001.
　　[2] 邵峰晶,于忠清. 数据挖掘――原理与算法[M].北京: 中国水利水电出版社, 2003.
　　[3] 王实,高文. 数据挖掘中的聚类算法[J].计算机科学,2007, (4): 42-45.
　　[4] 武森,高学东. 高维稀疏聚类知识发现[M]. 北京: 冶金工业出版社, 2003.
　　[5] 周水庚,周傲英,曹晶. 基于数据分区的DBSCAN算法[J]. 计算机研究与发展, 2000,(10): 1153-1159.
　　[6] Guha, S, R. Rastogi, and K Shim, Rock. A robust clustering algorithm for categorical attributes. Information Systems, 2000,25(5): 345-366.
　　[7] Abascal E, Garcia Lautre I, Mallor F. Data Mining in a Bicriteria Clustering Problem, 2006:705-716.
　　[8] MacQueen, J., Some methods for classification and analysis of multivariate observations. Proc. Fifth Berkeley Symp. on Math. Statist. and Prob., 1967,(1):281-297.

转载注明来源:https://www.xzbu.com/2/view-399420.htm