基于层次距离计算的聚类算法

基于层次距离计算的聚类算法

1冲突处理的聚类算法数据收集是捕获数据的重要分支。在收集过程中，用户提供初始分类知识是没有必要的，但根据数据的实际分布情况获得自然收集结果。目前的主要分组算法是：（1）基于k平均算法和k中心点算法的划分方法；（2）基于层的方法，如cu和birch；（3）基于密度的方法，如dapan和opts；（4）基于网格的方法，如sted、close和worm扩展；（5）基于模型方法的方法，如cobweb。关于数据收集。现有的聚类算法处理的主要变量数据类型包括区间标度变量、二元变量、标称型、序数型和比例标度型变量等等.针对其它数据类型,聚类算法或者要求将其数值化转换为区间标度变量;或者采用标称型的处理方法,即通过判断数据是否相等,来获得数据点的距离,如相等则距离为0,不相等则为1.在实际数据库应用中大量存在一种采用层次编码方式来表示特定信息的数据类型.如行政区划、域名等等.这类变量有下列特点:(1)变量可划分为多个部分,这些部分之间具有层次的关系;(2)相同前缀越多的变量之间彼此相似程度越高,反之变量之间相似程度越低.如果简单将其按照区间标度变量处理,难以表示数据之间的相近程度,在行政区划中,同一地区内所属县之间,并不会因为行政区划编码相邻距离就更近.采用区间标度变量,在聚类中也会导致无意义的结果,例如,通过行政区划聚类得到的聚类中心点有可能为一个不存在的行政区划,即使得到聚类结果,也难以解释,对用户也没有意义.如果采用标称型变量的处理方法,又丢失了大量有用信息,例如,会导出“在行政区划中不同省之间的县和同一地区县之间的距离均是相同”的不合理信息.针对以上问题,本文提出了一种新的数据聚类算法HDCA(HierarchyDistanceComputingbasedclusteringAlgorithm).本文主要工作如下:(1)提出了一种新的针对层次编码变量的距离处理方法.(2)对k中心点聚类算法作了修改,提出针对层次编码变量求取聚类中心点的快速算法.(3)从理论上和实验上分别证明了HDCA算法的有效性和高效性.(4)成功将HDCA算法应用到警用流动人口的聚类分析中.本文第2节描述层次编码变量的定义和距离公式;第3节介绍数据聚类算法HDCA;第4节是对算法的分析;第5节是本文的实验部分;第6节对全文作了总结并提出下一步的工作.2层次编码变量的距离定义和反证法在现实生活中,邮政编码、行政区划、车辆类型、域名等等都是层次编码变量,其特点是可以分为n个互不相交的部分,记为P=(V1,V2,…,Vn),其中每个Vi(i=1,2,…,n)是一个标称型变量,同时任意Vi(i=2,3,…,n)都有一个直接的祖先节点Vi-1,Vi的值域由Vi-1决定.因此我们可以将层次编码转换为1棵平衡树T,而任意层次编码变量P,可以看作是从树T的根到叶子的路径上经过的节点集合,由于树T的每个叶子与路径具有一一对应关系,因此可以用叶子来代表任意层次编码变量P,记为T(P).平衡树T上每层节点之间的路径权重,记为W1,W2,…,Wn-1(Wi>0,i=1,2,…,n-1),其中Wi表示从第i层到第i+1层节点间的路径权重,权重代表节点之间的相异程度,越小表示越相似.在实际计算中通常使用加权和W′i=n∑k=i∑k=inWk(i=1,2,…,n).以行政区划编码为例,成都市青羊区(510104)的行政区划可以用图1中的粗线路径表示.把上述直观事实形式化,定义层次编码变量的距离如下.定义1(编码距离).设P1,P2为两个相同值域条件下的层次编码变量,则称从T(P1)到T(P2)经过的最短路径的加权和为编码距离,并记为d(P1,P2).相同值域条件是指P1,P2包含的标称型变量数量相同,且相对应的标称型变量具有相同的取值范围.如图2所示,P1,P2的距离d(P1,P2)=2×W2+2×W3=2×W′2.定理1.编码距离满足欧式空间距离函数条件,即满足(1)d(i,j)≥0:距离是一个非负的数值.(2)d(i,i)=0:一个对象与自身的距离是0.(3)d(i,j)=d(j,i):距离函数具有对称性.(4)d(i,j)≤d(i,h)+d(h,j):从对象I到对象j的直接距离不会大于途经任何其它对象的距离.证明.(1)因为Wi>0,所以有任意d(i,j)≥0成立;(2)根据定义1,知道有d(i,i)=0;(3)同理由层次编码变量定义知道有d(i,j)=d(j,i);(4)现证明第4部分,即d(i,j)≤d(i,h)+d(h,j).其中i,j,h为相同值域条件下的层次编码变量.使用反证法,设存在一组层次编码变量i,j,h,满足d(i,j)≥d(i,h)+d(h,j),则存在一条从i到h,再从h到j的路径距离,真小于i到j的距离,这与层次编码变量的距离定义矛盾,故假设不成立.命题第4部分得证.综(1)(2)(3)(4)所述,定理得证.证毕.定理2.设Q为树T上P1,P2的最近的共同祖先,则有d(P1,P2)等于从P1到Q的路径距离加上从P2到Q的路径距离之和.证明思路:要点在于“最近的共同祖先”的表述,严格的叙述比较冗长,但很直观,故略去证明.从层次编码变量的特点上看,它具有树的特点,如果用区间标度来表示变量的距离,则需将树转换为一维来处理,是不合理的处理方式;如采用标称型方式,则完全忽略了层次编码变量间客观存在的不同相近关系,从而丢失了主要的信息.本文的主要思想是利用层次编码变量树型结构的特点,采用叶子间通过树的最短路径值来表示层次编码变量间的距离,显然比前述两个方法合理.3相异的.算法HDCA算法是基于划分的聚类方法,目标是:给定一个包含n个数据元组的数据库以及要生成的簇的数目k,算法完成将数据元组组织为k个划分(k≤n),其中每个划分代表一个簇,同一个簇中的元组是相似的,而不同簇中的元组是相异的.算法的基本策略是:首先为每个簇随意选择一个代表元组;剩余的元组根据其与代表元组的距离分配给最近的一个簇.然后反复地用非代表元组来替代代表元组,以改进聚类的质量,直到每个元组对应的簇不再改变或超过最大迭代次数为止.聚类结果的质量用公式(1)来估算,该函数评估了元组与其参照元组之间的平均相异度.E=k∑i=1∑p∈Ci∑i=1k∑p∈Cid(p-mi)2(1)其中E表示数据库所有元组的平方误差的总和,p代表任意元组,mi表示簇Ci的中心点.HDCA算法的主要工作包括以下部分:(1)针对层次编码变量提出相应的距离计算方法.(2)提出了计算同一聚类下的层次编码变量的中心点算法.(3)对k中心算法作了修改,减少了迭代次数.3.1模型层次编码算法在求取数据元组距离时,首先在元组的每个维度上根据数据类型计算距离,然后采用加权欧几里得距离或加权曼哈顿距离计算元组之间总的距离.加权欧几里得距离和加权曼哈顿距离的定义分别如式(2),(3)所示.d0(i,j)=2√(wd1⋅d(xi1,xj1))2+(wd2⋅d(xi2,xj2))2+⋯+(wdn⋅d(xin,xjn))2(2)dm(i,j)=|wd1⋅d(xi1,xj1)|+|wd2⋅d(xi2,xj2)|+⋯+|wdn⋅d(xin,xjn)|(3)d0(i,j)=(wd1⋅d(xi1,xj1))2+(wd2⋅d(xi2,xj2))2+⋯+(wdn⋅d(xin,xjn))2−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√2(2)dm(i,j)=|wd1⋅d(xi1,xj1)|+|wd2⋅d(xi2,xj2)|+⋯+|wdn⋅d(xin,xjn)|(3)其中wd1,wd2,…,wdn表示元组在每个维度上的权重,如wd1=wd2=…wdn=1,则公式(2),(3)退化为传统的欧几里得距离和曼哈顿距离.对于维度数据类型为层次编码变量的,则根据定理2,采用如下算法.算法1.层次编码距离计算(hd-Distance)输入:层次编码变量Pi,Pj输出:d(Pi,Pj)Begin1.k←1;2.While(k<=n)and(Pik=Pjk)3.k←k+1;4.rc←0;5.ForEachm∈[k,n]Do6.rc←rc+2×wm7.ReturnrcEnd.hd_Distance中n表示层次编码变量具有n个不相交的部分.Wm(m=1,2,…,n-1)表示从第m层到第m+1层节点间的路径权重.3.2团队编码算法描述绝大多数的聚类方法均需要求取聚类的中心点或代表点,在求取这样的点时,对于区间标度型变量可以直接采用求平均值的方法,但对于层次编码变量是不可行的,因为层次编码变量无法简单映射到一个单维空间.因此首先必须对层次编码变量的中值作一个定义.定义2(层次编码变量集合的中值点).设层次编码变量p,满足p=argmin{Ei|Ei=∑pj∈C|d(pi,pj)|},其中C表示层次编码变量的集合,则称p为集合C的中值点,记为CCentre.定义2实际上就是取到其它所有变量距离和最短的变量作为集合的中值点.依据定义2,本文提出了一种在聚类中快速求取层次编码数据中心点的算法.算法的总体思路是:(1)建立平衡树结构存储不同的编码,用树代表编码的层次.(2)依次遍历每个层次编码变量,将其分配给不同的树节点并计算.(3)最后根据平衡树上各参数的统计结果得出中心点编码.算法中涉及平衡树中每个节点的数据结构如下:TCodingNodeStructure=RECORDParent:POINTER;//父亲指针FirstChild:POINTER;//第1个孩子指针MinWeightChild:POINTER;//最小权重子节点指针Value:DATA;//本级代码值Count:INTEGER;//表示叶子节点的总数Weight:FLOAT;//权重NextSilbing:POINTER;//下1个兄弟指针END.示意图如图3所示.结构中最小权重子节点,表示在该节点的所有子节点中具有最小权重的点.权重字段表示该节点的权重值,具体定义及计算方法稍后描述.其中对层次编码变量处理算法的形式化描述如下.算法2.HDCA_CountTree.输入:T(当前聚类树),P(层次编码变量)输出:T(当前聚类树)Begin1.Root←GetRootNode(T)2.CurrentNode←SearchTree(Root)3.RegressTree(CurrentNode)4.ReturnTEnd.FunctionSearchTree(NodeParent)1.ForEachkIn[1..n]Do2.CurrentNode←NodeParent.FirstChild;3.IfCurrentNode=NULLThen4.CurrentNode=NewNode(NodeParent,NULL,Pk)5.ElseBegin6.Found←False;7.WhileDo8.IfCurrentNode.Value=PkThenFound←True;break;9.IfCurrentNode.NextSilbing=NULLThenbreak;10.CurrentNode←CurrentNode.NextSilbing11.EndWhile12.IfFoundThenCurrentNode.Count←CurrentNode.Count+113.ElseCurrentNode←NewNode(NodeParent,CurrentNode,Pk)14.End15.NodeParent←CurrentNode16.EndforFunctionRegressTree(CurrentNode)1.Fork=nDownto1Do2.NodeParent←CurrentNode.Parent3.tWeight←CurrentNode.Weight+(NodeParent.Count-CurrentNode.Count)×2×W′k-14.NodeParent.Weight←NodeParent.Weight+2×W′k-15.IftWeight<NodeParent.WeightThen6.NodeParent.Weight←tWeight7.NodeParent.MinWeightChild←CurrentNode8.EndIf9.CurrentNode←NodeParent10.EndFor算法计算的过程是,(1)首先从顶到下寻找该层次编码变量合适的位置,如找到则相应统计数加1,找不到就创建新的节点.(2)自底向上,依次判断权重值,如发生改变就修改相应的MinWeightChild属性.其中Pk表示层次编码变量P的第k部分的值,W′k代表从第k层到第n层节点间的路径权重和.为方便理解,举例如下:设当前树结构如图3所示,现考察处理P=(“51”,“01”,“05”)的过程:(1)首先判断P在树的每层是否有对应点,并作相应处理.结果如图4所示.(2)从叶节点开始,逐步回溯到根节点,每步判断相应权重值,并调整权重和MinWeightChild指针,最后如图5所示.HDCA_CountTree算法实际上是完成了一个层次编码变量的处理,在主算法中的过程是依次遍历所有的元组,对其中的层次编码变量,分别调用HDCA_CountTree算法进行处理.在所有数据处理完成后,通过对平衡树的一次查找,就可获得中值点的编码.获得层次编码变量中值点的形式化描述如下.算法3.hd_Final.输入:T聚类簇的层次编码树输出:P聚类簇的中值编码Begin1.CurrentNode←GetRootNode()2.ForEachkIn[1..n]Do3.CurrentNode.Node←CurrentNode.MinWeightChild4.Pk←CurrentNode.Value5.Endfor6.ReturnPEnd.其中Pk表示层次编码变量P的第k部分的值.3.3身份编码变量的计算HDCA_MAIN算法实际上是聚类的主调用过程,它完成整个聚类的过程并返回.其间根据处理的数据类型调用前述的中值处理和距离算法.算法的形式化描述如下.算法4.HDCA_MAIN算法.输入:DataSet数据集k聚类个数输出:ClusterInfos聚类结果Begin1.ClusterInfos←Initialize(DataSet,k)2.IterativeNum←03.WhileIterativeNum<MaxValueDo4.ClusterInfos.Initialize5.ForEachTupleinDataSet6.i←AssignToMinDistance(ClusterInfos,Tuple)7.CountEveryDimension(ClusterInfos[i])8.EndFor9.ForEachiIn[1..k]Do10.ComputeCentrePoint(ClusterInfos[i].CentreValue)11.ForEachTupleInDataSet12.tempDistance←Distance(ClusterInfos[Tuple.ClusterID].CentreValue,Tuple)13.IftempDistance<ClusterInfos[i].CentrePointThen14.ClusterInfos[i].CentrePoint←Tuple15.EndFor16.IterativeNum←IterativeNum+117.IfNotChangedThenReturn18.EndWhileEnd.其中Initialize完成每个聚类的初始化工作,AssignToMinDistance完成计算当前元组与所有聚类中心点的聚类计算,将当前元组分配给最近的聚类,最后返回聚类的编号;在计算距离时采用了3.1节的算法,层次编码变量计算采用算法1.CountEveryDimension函数完成对当前聚类在加入1个元组后在每个维度上的汇总计算,如果是普通区间标度型变量就直接累加变量值;对层次编码变量则采用了算法2.ComputeCentrePoint函数是在完成对每个维度上的汇总计算基础上,求取每个聚类的中值点(CentreValue),对于普通区间标度型变量采用中值计算方法,而层次编码变量的中值计算采用了算法3.Distance完成两个元组的距离计算,根据维度类型的不同分别采用不同的算法,具体细节请参见3.1节.算法中聚类的CentreValue与CentrePoint属性具有不同的含义,CentreValue表示聚类的中值点(元组),这样的点(元组)在数据集中有可能不存在;而CentrePoint表示在实际数据集中存在并且靠中值点最近的点(元组).由HDCA_MAIN可以看到聚类算法的总体过程为:首先完成聚类初始工作,如初始化每个聚类等,然后通过一个迭代过程每次重新求取每个聚类的中心点,判断是否有错误划分的元组,迭代过程直到达到没有错误划分的元组或最大迭代次数为止.其中,对元组中的层次编码变量的处理采用本文前述的方法.在实际应用过程中,聚类算法可以应用到任意包含层次编码变量的数据表中,但首先应该通过配置确定需要参与聚类计算的维度和聚类的数据条件等初始信息.由以上形式化描述可知,与传统k中心点算法不同,HDCA算法每次迭代均计算每个聚类最靠近中心的点(元组);而传统k中心点算法是从聚类中随机抽取这样的点,与上一个代表点比较,如果更好则替换.因此从方法上看传统k中心点算法每次迭代耗费时间略少,但迭代次数会远多于HDCA算法.通过第5节实际数据的对比实验可以看到,本文的方法在总耗费时间上远小于k中心点算法.4twiiitch大小的大小定理3.HDCA算法得到层次编码变量集合的中值点符合定义2关于层次编码中值点的标准.证明.HDCA算法中的层次编码变量中值点是根据算法2和算法3得到的.算法3中值点的求取是从该聚类树的根开始,依次搜索每个节点的MinWeightChild,即最小权重子节点,从而得到的.因此证明算法的结果是否符合定义2的要求,只需证明任意节点的MinWeightChild指向子树的中值点即可.根据算法2对每个层次编码变量的插入过程,当前节点的父节点的MinWeightChild是否修改指向,根据的是父节点的权重和当前节点的权重比较.比较的是NodeParent.Weight+2×W′k-1和tWeight的大小(tWeight=CurrentNode.Weight+(NodeParent.Count-CurrentNode.Count)×2×W′k-1)的大小,如果后者较大,则将父节点的MinWeightChild指向当前节点.如果当前节点为叶子节点,则后面的公式代表的是以父节点为根,根据当前节点计算出的与其它节点的距离差的和;因此父节点的MinWeightChild指向的必然是中值点对应的子节点,同时父节点的权重就是子树中值点与其它节点的距离差的和;以此类推,根据算法2处理的每个节点的Weight均代表了以该节点为根的中值点与其它节点的距离差的和.算法中之所以采用NodeParent.Weight+2×W′k-1与tWeight比较是因为在新插入一个节点后,父节点包含的叶子节点的总数(Count)增加了1个,因此Weight(中值点的与其它节点的距离差的和)也相应增加2×W′k-1(在父节点原来的MinWeightChild与当前节点不同的条件下).根据以上讨论,任意插入一个层次编码变量,依次处理的各层节点的MinWeightChild必定指向以该节点为根的节点集合的中值节点(虽然算法不保证树中任意节点的Weight均是正确的,但MinWeightChild的指向却可以保证无误);因此根据算法3,最后返回的结果必然是层次编码变量集合的中值点.证毕.定理4.HDCA算法的时间复杂度为O(n×k),其中n是元组的个数,k为迭代的次数.证明.根据HDCA算法主调用过程(算法4),算法最大需循环k次(k为迭代的次数),在每次循环中需遍历1次数据.对每个元组的任意区间标度类型维度的处理均可理解为常数时间.对层次编码型变量的处理(算法2),主要工作分为从聚类的根查找并统计,然后从叶子节点回溯到聚类根,这个过程一共访问了2×m次树节点,其中m为聚类树的高度.因为树的高度独立于元组数量,因此在算法2的处理时间可以认为是一个常数.综上所述,HDCA算法的时间复杂度为O(n×k),其中n是元组的个数,k为迭代的次数.证毕.5不同层次编码变量中聚类算法的能耗比较我们已经成功地将HDCA算法应用到了警用流动人口信息分析中.警用流动人口信息分析的目的是通过研究发现各类人员的流动模式以及流动人口的趋势性问题,找出异常的流动信息和模式,为公安机关打击、防范犯罪提供决策支持,为案件侦破提供线索.利用HDCA算法本文成功实现了各类流动人口信息的自动聚类及相关的分析工作,通过对远离聚类中心点元组的分析,获取了数据的离群点,这样就可为案件侦破和治安防范工作提供有用的情报信息.实验的硬件环境为Athlon643000+,1GHz内存,160GB硬盘,开发工具为DELPHI7.0,数据库使用的是Oracle9i.实验的样本数据为近两年来收集的流动人口的旅店住宿登记信息,总数据量为3700000条.数据中含人员姓名、身份证号、来源地行政区划、旅店行政区划、旅店编号、入住时间、离开时间等信息.实验前首先将指定数据全部读入内存,并完成相应的预处理工作,后面实验部分得到的时间均不包括数据加载和预处理的时间.实验1.HDCA算法求取中值点与朴素算法性能比较.为证明算法在求取中值点上的性能,根据定义2,本文另实现了计算层次编码变量中值点的朴素算法,算法思路为依次计算每个点到其它点的距离并求和,然后取出距离和最小的点作为集合的中值点.很明显朴素算法的时间复杂度为O(n2),如层次编码变量中值点计算采用朴素算法,则聚类算法的总时间复杂度将增大为O(n2k).实验中,本文分别抽取500～5000数据,选取其中的来源地行政区划字段,分别采用HDCA算法中的中值点计算方法(算法2,3)和朴素算法对所耗费的时间进行比较,实验结果如图6(a)所示.其中横坐标为数据集大小,纵坐标为耗费时间,单位为ms.由实验结果可以看到,在5000以下的数据规模,HDCA算法耗费的时间可以忽略不计,而朴素算法的增长就非常快,由此可见HDCA算法性能远远高于朴素算法.为测试算法性能,将数据规模提高到从50000到500000条,HDCA算法耗费时间结果如图6(b)所示,图6(b)的横坐标为数据集大小/50000,纵坐标为耗费时间,单位为ms.可以看到,算法耗费时间随数据规模基本呈线性增长;即使数据规模在500000条,算法耗费的时间仍然控制在1.2s以内.实验2.HDCA算法性能与数据量的关系.实验主要测试在实际数据条件下,HDCA算法耗费时间与数据量的关系.聚类中使用了流动人口的4个关键属性:来源地行政区划、旅店行政区划、旅店编号、入住时间(其中前3个维度为层次编码类型),k值设为8.结果如图7所示.图7中横坐标为数据集大小/50000,纵坐标为耗费时间,单位为s.Total_Time表示实际耗费时间,Average_Time表示在当前数据规模下,每次迭代耗费的时间.由实验结果可以看到,在4个维度进行聚类操作时,HDCA算法平均每次迭代耗费时间与数据规模呈线性增长.实验3.算法与标准k中心点算