最近邻查询（精选5篇）
最近邻查询 篇1
反向最近邻(RNN)查询作为空间数据库空间查询的一个最重要技术之一,它是在最近邻查询的基础上提出来的,它最早是由F.Korn和S.Muthukrishnan在2000年提出来的[1]。目前反向最近邻查询的查询粒度大都是基于一维的点,即反向最近邻查询就是在数据集中找到以查询点为最近邻的对象点,这对于能被抽象为点的空间物体,对其进行反向最近邻查询能达到较好的效果,这方面的文献较多,其主要有静态和动态环境下的反向最近邻查询[2,3],低维和高维数据空间中的反向最近邻查询[4,5]。但对于一些不能将其抽象为点的空间物体如航线,按点的反向最近邻查询方法对其进行反向最近邻查询,其准度达不到一定的要求。为此,本文在研究平面线段最近邻查询相关文献[6]和R树[7]索引结构的基础上,提出了一种简单的改进的R树索引结构,并在此基础上给出了平面线段反向最近邻查询的过滤策略,并给出了平面线段反向最近邻的查询算法,该方法能实现平面线段的反向最近邻查询。
1 平面线段反向最近邻的定义
定义1[6]平面线段L到平面线段K的最近距离D(L,K):设l,li,lj∈L,k,ki,kj∈K,dist(l,k)表示点l到点k的距离。则D(L,K)={dis
定义2[6]平面线段最近邻LNN:给定一平面线段集S和查询线段L,平面线段最近邻查询就是要查询满足这样条件的线段:K?S,K为L的最近邻。其形式化定义为:LNN(L)={K∈S|坌M∈S,D(L,K)≤D(L,M)}。
定义3查询线段L与其最近邻LNN(L)的距离(dlnn):dlnn(L)=D(L,LNN(l))。
定义4平面线段反向最近邻(LRNN):给定一平面线段集S和查询线段L,平面线段反向最近邻查询就是要查询满足这样条件的线段:K∈S,L为K的最近邻。其形式化定义为:LRNN(L)={K∈S|坌M∈S,D(L,K)≤D(K,M)}。
定义5查询线段L与其反向最近邻LRNN(L)的距离(dlrnn):dlrnn(L)=D(L,LRNN(L))。
2 Rcd树的定义
2.1 平面线段最小包围圆及线段到最小包围圆的定义
R树[7]的结构可描述为叶子结点:(w,
定义6查询线段L到最小包围圆C的距离D(L,C):D(L,C)=D(L,o)-r。其中D(L,o)是最小包围圆C的圆心o到查询线段L的距离,r是最小包围圆C的半径。
2.2 Rcd树结构
由于R树的叶子结点与中间结点在结构上相同,且叶子结点存储的是空间物体的最小边界矩形,这使得基于它的RNN查询效率不高,下面给出一种改进的R树—Rcd树。
Rcd树是基于R树和平面线段反向最近邻性质提出的。它的特点是在叶子结点中包含线段的最近邻信息,中间结点包含其子结点内的所有线段的最小包围圆的信息。
Rcd树的结构可描述为:
叶子结点:(w,
中间结点:(w,
其中Li为平面线段集中某一线段,dlnn(Li)为线段Li到其最近邻的距离,pti为指向孩子结点的指针,如pti指向的孩子结点是叶子,则Ci是pti指向的叶子结点内所有线段的最小包围圆,如pti指向的孩子结点是中间结点,则Ci是pti指向的中间结点内所有最小包围圆的最小包围圆,M是结点内包含数据项或索引项的最大数目。
2.3 基于Rcd树的平面线段反向最近邻查询定理
定理1若查询线段L到Rcd树的某一分枝的最小包围圆C的距离大于等于此最小包围圆的直径2r,则此分枝中一定没有查询线段的反向最近邻。
证明:根据定义6,D(L,C)为查询线段L到最小包围圆C的距离,由最小包围圆的性质,其内的任意两条线段的最近距离一定小于此最小包围圆的直径,即最小包围圆内的任意线段K到其近邻LNN(K)的距离dlnn(K)<2r,r为最小包围圆的半径,又D(L,C)≥2r,所以D(L,C)>dlnn(K),由定义3即得证。
3基于Rcd树的平面线段反向最近邻查询算法
基于Rcd树的平面线段反向最近邻查询与基于其它树的反向最近邻查询具有以下优点:
1)Rcd树的叶子结点存储的不是空间物体的最小边界区域,而是存储的是它的最近邻信息,这样进行反向最近邻查询时,就不需要计算查询线段与最小边界区域的距离,可以提高查询速度。
2)Rcd树的中间结点存储的是它的孩子结点内所有最小包围圆的最小包围圆,利用最小包围圆的性质,当查询线段到此最小包围圆的距离大于此最小包围圆的直径时,则此最小包围圆内一定没有查询线段的反向最近邻,可以对此分枝进行剪枝处理。
3)从Rcd树的存储结构看,其所占存储空间更少。
下面给出基于Rcd树的平面线段反向最近邻查询的过滤策略。由Rcd树结构的优点与平面线段反向最近邻性质有如下过滤策略:
1)对Rcd树叶子结点中某一线段K,如果查询线段L到此线段K的最近距离小于等于此线段K到其最近邻的距离,即D(L,K≤dlnn(K),则将此线段K加入到查询线段L的反向最近邻中;否则,不予处理。
2)对Rcd树中间结点中某一分枝,如果查询线段L到此分枝的最小包围圆C的距离小于等于此分枝的最小包围圆C的直径,即D(L,C)≤2r,r为C的半径,则要对此分枝作进一步处理;否则,对此分枝作剪枝处理。
3)对要作进一步处理的分枝重复1),2)两步。
由以上过滤策略下面给出基于Rcd树的平面线段反向最近邻查询算法思想:
设当前查询线段为L,在基于Rcd树的索引结构中进行反向最近邻查询时,如果当前结点是叶子结点,由于叶子结点中存储了各条线段到其最近邻的距离信息,则对叶子结点中的每一条线段K,比较查询线段L到线段K的最近距离D(L,K)与线段K到其最近邻的距离dlnn(K),若D(L,K)≤dlnn(K),则说明线段K是查询线段L的一个反向最近邻,将线段K加入LRNN(L),否则不予处理;如果当前结点是中间结点,则对中间结点中的每一分枝,比较查询线段L到此分枝的最小包围圆C的距离D(L,C)与此分枝的最小包围圆C的直径2r,若D(L,C)≤2r,则应对此分枝作进一步处理;否则,根据定理1,对此分枝作剪枝处理。
基于Rcd树的平面线段反向最近邻查询算法描述如下:
算法分析:
Rcd树的叶子结点存储了平面线段集中的所有线段信息,中间结点存储了其孩子结点最小包围圆的信息,查询线段的反向最近邻的过程是遍历Rcd树,采用的是递归地DFS方式,对Rcd树中的每个结点至多调用一次DFS,因此时间复杂度为O(n)。
4 结束语
本文在分析基于平面线段的最近邻查询和R树结构的基础上提出了一种改进的R树—Rcd树,并给出了基于Rcd树的平面线段反向最近邻查询算法,实现了平面线段的反向最近邻查询。下一步的研究可扩展到平面线段的反向k最近邻查询和在动态环境下的线段的反向近邻查询。
参考文献
[1]F.Korn and S.Muthukrishnan.Influence Sets Based on Reverse Nearest Neighbor Queries.In:Proceedings of the ACM International Con-ference on Management of Data(SIGMOD),2000,201-212.
[2]C.Yang and K.I.Lin.An Index Structure for Efficient Reverse Nearest Neighbor Queries.In:Proceedings of the 17th IEEE InternationalConference on Data Engineering(ICDE),2001,485-492.
[3]R.Benetis,C.S.Jensen,G.Karciauskas,and S.Saltenis.Nearest and Reverse Nearest Neighbor Queries for Moving Objects.VLDB Journal,2006,15(3):229-249.
[4]A.Singh,H.Ferhatosmanoglu,and A.Tosun.High Dimensional Reverse Nearest Neighbor Queries.In:Proceedings of the ACM Interna-tional Conference on Information and Knowledge Management(CIKM),2003,91-98.
[5]Y.Tao,D.Papadias,X.Lian,and X.Xiao.Multidimensional Reverse kNN Search.International Journal on Very Large Data Bases(VLD-BJ),2007,16(3):293-316.
[6]郝忠孝,王玉东,何云斌.空间数据库平面线段近邻查询问题研究[J].计算机研究与发展,2008,45(9):1539-1545.
[7]Guttman A.R-trees:A Dynamic index structure for spatial searching[C].ACM.SIGMOD,Boston,USA,1984,13(2):47-57.
最近邻查询 篇2
最近邻(NN,Nearest Neighbor)查询是空间数据库中重要的一类查询,比如,一个正在高速公路上行驶的司机可以找到离当前位置最近的加油站。与其同等重要的查询是连续最近邻(CNN, Continuous Nearest Neighbor)查询,比如还是高速公路上行驶的汽车司机,他可能想知道在一段道路上的最近加油站,这个查询的结果是一个包含道路上有效区间及相应最近邻的集合。
目前为止最有效地解决静态环境数据库中连续最近邻问题的算法是文献[2]中的CNN算法,这个算法的主要思想是寻找分割点si,分割点是最近邻发生变化的点。这个算法的结果是一个列表,包含所有的分割点以及它们相应的最近邻。这个算法的主要缺点是遍历顺序没有优化,磁盘存取数量大。本文的主要目的是改进这个算法,以减少磁盘存取数量,提高I/O效率。
1 CNN算法相关知识
1.1 CNN查询的问题特征
CNN查询的目的是通过分割点列表SL找到线段undefined上最近邻居的集合。s和e是SL中的第一个和最后一个元素。对于si∈SL(0≤i<SL-1)要满足:si∈q并且[si,si+1]上的所有点具有相同的NN。最初,SL={s,e},此时不存在最近邻,在整个查询过程中SL不断被更新,SL中包含着目前为止每一步的处理结果,最后的结果包含每一个分割点si以及它的最近邻si.NN。如果p到一些点u∈[s,e]的距离比当前u.NN到u的距离更近,则要更新SL,这时只需验证p是否覆盖了当前SL中的某些分割点即可。
1.2 基于R树的CNN查询算法
最近邻查询中最普通的类型是点的kNN查询,即从数据集P中找到距离点q最近的k个对象,已有的算法采用分支-限界(BAB)方法来搜索R树。正如点的NN算法,CNN算法也采用BAB方法来修剪搜索空间。这一算法可以避免访问那些不包含有效数据点的结点。下面给出几个删除不必要的中间结点的规则。
规则1:对于一中间结点E和查询线段q,当mindist(E,q)
规则2:对于一中间结点E和查询线段q,当且只当存在一个分割点si∈SL并且dist(si,si.NN)>mindist(si,E),E的子树才被查询。
虽然规则2提出了一个MBR包含有效数据点的更为严密的条件,但它导致了更多的CPU运算。因为它需要计算E到每一个分割点的距离,而且它只适用于那些满足规则1的结点。
规则3:满足规则1和2的结点要根据它们距q的最小距离递增处理。首先访问距离小的结点,再访问距离大的结点。
2 算法优化思想
CNN算法的主要思想就是根据规则1和2来判断哪些结点被删剪,根据规则3决定处理顺序。如图1所示,P={p1,p2,…,p13},移动查询线段undefined以及相应的R树,在遍历根结点之后,计算出所有中间结点距q的距离,首先被访问的中间结点是IN1,在IN1中最先被处理的是较近的LN2中的p3结点,p4和LN1被删剪;下一个被访问的结点是LN3,其中p8被处理,这样IN1就被处理完毕。接着处理IN2中的结点,在IN2中依然是依据三个规则进行访问和删剪,依次处理的结点是p6,p7,p9,p11。
根据图1(a)可知SL={s(.NN=p1),s1(.NN=p9),s2(.NN=p11),e(.NN=p11)},LN1,LN3,LN4三个叶子结点不包含任何一个最近邻,期待的算法是不访问这三个中间结点。但根据文献[2]中算法,LN3,LN4这两个不包含最近邻的结点没有被删剪掉。
根据上面的讨论,可以发现文献[2]中算法没有最大程度地删剪结点,其原因是对R树的遍历顺序不够优化,优化后的规则3应该如下所述:
规则3′:满足规则1和规则2的结点要根据它们距最新分割点的最小距离递增处理。
根据规则3′,在处理p3后,新的分割点为e,首先被处理的结点就变成了p11,如图2所示,得到新的分割点s1,距离s1最近的点是p9,如图3所示,原有的分割点s1被移除,新的分割点s1和s2插入到列表中,这样就完成了整个查询,只访问了p3,p11,p9三个结点,算法得到了优化。
3 算法性能分析
优化后的算法相对于文献[2]中算法而言,其磁盘存取数量是明显减少了,I/O得到了优化,但不能确定CPU的计算量是否减少了,其原因是:
一方面,CPU的计算量增大了,这主要是因为算法需要对中间结点进行规则1和规则2的检测,算法不能在找到一个覆盖此结点的分割点后就退出检测规则2,因为需要找到距这个结点最近的分割点。
另一方面,算法在其它地方明显地减少了CPU的计算量。首先,最明显的是访问了更少的结点,计算了较少的最小距离;其次是优化后的算法在执行过程中尽可能地让SL保持在最小情况下,这就在二分法查找以及计算规则2时减少了计算量,而文献[2]中的算法在中间状态中存在一些分割点,而这些分割点并没有在最后出现,这样在算法执行过程中,就会存在SL要比最终状态时的SL大很多的可能。
在将来的工作中,需要进一步做的是通过实验来评价CPU计算量的变化,以及将这个方法扩展到连续k近邻中。
参考文献
[1]Beckmann N,Kriegel H P,Schneider R,et al.The R*-tree:An effi-cient and robust access method for points and rectangles[C]//Proc.ofthe ACM SIGMOD Intl.Conf.on Management of Data,1990:322-331.
[2]Tao Y,Papadias D,Shen Q.Continuous nearest neighbor search[C]//Proc.of 28th Intl.Conf.on Very Large Data Bases(VLDB),2002:287-298.
[3]Roussopoulos N,Kelley S,Vincent F.Nearest neighbor queries[C]//Proc.of the ACM SIGMOD Intl.Conf.on Management of Data,1995:71-79.
[4]郭景峰,等.连续最近邻查询方法研究[J].现代计算机,2004,7:6-9.
最近邻查询 篇3
作为空间数据库中一种非常重要的查询类型,全局最近邻查询方法在数据分析、数据挖掘和知识发现等众多领域有着广泛的应用。全局最近邻查询的含义是指,对于给定的基础集合P中的所有对象,在参考集合R中查询距离最近的对象。在应用中,基础集合P和参考集合R可以是同一个数据集合。从全局最近邻查询的定义可以发现,该方法是对最近邻查询和空间链接(spatial join)的融合,具有两者的共同特征。可以把全局最近邻查询当成是空间链接的一个变体,该变体的判定条件为最近邻居。不过,因为最近邻判定的复杂程度和计算开销要远远超过相交条件的判断,且最近邻查询具有非对称的特点,所以,在基于索引结构的全局最近邻查询算法中,通常不采用距离空间连接查询中所采用的双向节点展开策略[1],而是采用所谓的单向节点展开的嵌套循环技术[2]。
最简单地解决全局最近邻问题的方法为:依次查找集合P中所有元素在集合R的最近邻[3]。但是,这种方法的缺陷是CPU占用率较高,所以针对不同的应用情况,研究人员纷纷提出新的方法来解决全局最近邻问题。在文献[4]中,提出了一种能够不采用索引结构的全局最近邻查询外存算法,该算法首先把所有的数据划分为不同的数据块,然后再通过扫描线算法来对所有的数据块进行扫描,并计算当前或者相邻数据块中对象的最近邻。在文献[5]中,提出了一计算两个数据集合中距离最近对象的临近对查询算法;该算法可用于对全局最近邻的查询处理,不过,该算法不是专门为全局最近邻查询而设计的,所以容易引起较高的CPU和内存开销。文献[6]中提出一种基于改进的PR四叉书索引结构的全局最近邻查询处理算法,以及一种新型的裁剪规则,但是,这种新型的裁剪规则应用于R树类型的索引结构,其查询效果不太明显。在文献[7]中,则主要对二维平面中的线段对象的最近邻查询处理算法进行探讨分析。当数据集合P和参考集合R为同一集合时,基于索引结构的任意对象的最近邻很可能分布在该对象的同一个或者相邻叶节点中,已有的基于R树的全局最近邻查询算法中,对该情况并没有进行深入考虑,在文献[4]中,也只是给出了不依赖于索引结构的解决方法。所以,根据参考集合和数据集合相同时的这一特点,文中考虑可以不通过批量查询和嵌套循环的索引遍历技术,而是通过其他更合适的方式来得到最近邻处理结果。
所以,研究重点就放在当数据集合和参考集合相同时全局最近邻查询算法的选择上,这种情况下的全局最近邻算法通常是基于通用树形索引结构的。所用算法能够适用于通用的树形索引结构,大量的实验结果表明,该算法能够适用于不同分布特点的数据,且能够处理较大规模的数据,有效提高查询处理的性能,降低CPU的计算复杂度和内存占用率。所以在中低纬度的数据空间中具有较好性能的索引结构中,可以采用该算法来解决全局最近邻查询问题。
2 全局最近邻查询
下面对全局最近邻的相关定义进行简单说明。
对于给定的基础数据集合P,以及参数数据集合R,对P的全局最近邻查询就是要得到任意元素在集合R中的最邻近元素OR。通常最近邻查询以元素的位置临近性为基础。
3 基于索引的查询处理算法
3.1 查询处理的思想
查询元素O及其最近邻元素所在叶节点的最近距离和最近邻的最远距离,就是最近邻搜索的最近和最远距离[8]。并且为了保证最近邻查询结果的正确性,在最不理想的情况下,所有跟元素O的距离不大于最近邻的最远距离的叶节点都需要进行检测,这样就可以确认是否存在比当前最近邻更优的结果。所以最近邻查询的CPU占用率要远远超过相交查询。特别是在数据集合P的规模较大时,对其进行全局最近邻查询所带来的CPU开销更大。在实际使用中,为了能够有效地降低全局最近邻查询的计算量,通常采用批量查询的方式来减少最近邻查询的总次数,相应地,单次最近邻查询中所包含的对象数量就会有所增加。
所以,当基础数据集合跟参考数据集合为同一数据集合是,其中的任何元素O的最近邻最可能位于其相同或者相邻的叶节点,且该距离要远小于最近距离和最近邻的最远距离。在这种情况下,最近距离和最近邻的最远距离的裁剪规则就不能够有效地减少无效的节点访问。有鉴于此,提出了一种新型的过滤无效节点的方法:以叶节点为单位来完成全局最近邻查询计算,对于叶节点中所包含的元素,其最近邻计算包括两个步骤:(1)对叶节点内部元素之间的最近邻计算,此时的计算仅仅局限于叶节点的内部,这样就可以将最近邻计算限制在较小的范围,通过扫描线算法来降低计算开销;(2)采用改进的范围查询算法来获得元素在相邻叶节点中可能存在的最近邻结果。该步骤结束后,就可以获得元素的最后最近邻查询结果。
由于在第一个步骤中可以得到元素在当前叶节点内部的候选最近邻,所以,在第二个步骤中就只需要根据已有的结果,来确认在相邻叶节点中是否包含满足最近邻查询条件的元素就可以。相对于前面的搜索范围,此处的相邻叶节点搜索可以限制在一个相对更小的区域内部。
3.2 索引的遍历方式
最近邻查询的计算过程有可能需要相邻节点来计算完备的最近邻结果,这样,就需将相邻叶节点都读入到内存中;在完成当前叶节点的最近邻查询计算过程后,如果还要对相邻叶节点的最近邻进行计算,就可以利用内存中的现存信息,进而有效地利用内存缓存空间中的已存信息,减少内存空间消耗;但是,这种方法不能够确定下一个计算节点。还有一种方式,就是按照分形曲线的顺序来访问所有节点,这种方式比较简单直观,不需要复杂的判定机制来决定节点的访问序列。
3.3 单节点最近邻计算方法
叶节点的内部元素的最近邻计算也可以分为两个步骤来完成:(1)计算叶节点的内部最近邻及其相邻的矩形;(2)以该相邻矩形为查询窗口,通过范围查询来获得有可能影响最近邻结果的外部元素,并计算该元素的完备最近邻结果。
4 实验结果分析
为了验证文中算法,进行实验如下:采用Visual C++进行代码编写,实验数据采用空间数据集合P和参考数据集合R,且数据集合中的数据元素都经过归一化处理。在实验中,空间数据集合P和参考数据集合R都读入内存,实验结果数据取50次查询的平均值。数据的来源为:(1)Boeing公司737客机0.2马赫风洞实验采集的机翼气流数据,该数据可以从网上直接下载,是当前对该领域方向进行研究所广泛采用的实验数据;(2)人工随机生成的高维数据集合,且这些数据在数据空间内是均匀分布的。
通过验证,结果表明,提出算法的效率要明显优于常用最近邻查询算法,并且对于不同的数据维数和数据元素数量,特别是对于高维的数据空间,该算法具有较高的稳定性。此外,由于需要进行搜索的数据点数量较少,使得该算法的效率要总体上由于常用全局最近邻查询算法。
5 结语
针对基础数据集合和参考数据集合为相同集合的特殊情况,给出了一种新型的全局最近邻查询算法,该算法充分利用数据最近邻结果的自身特点,避免了较大的查询过程中的资源开销,使得计算开销小于常用的最近邻查询算法。实验结果表明,该算法的效率要明显优于常用最近邻查询算法,并且对于不同的数据维数和数据元素数量,特别是对于高维的数据空间,该算法也具有较高的稳定性。
参考文献
[1]Shin H,Moon B,Lee S.Adaptive multirstage distance joinprocessing[J].SIGMOD Record,2000,29(2):343-354.
[2]M amoulis N,Papadias D.Slot index spatial join[J].IEEETrans on Knowledge and Data Engineering,2003,15(1):211-231.
[3]Zhang J,Mamoulis N,Papadias D,et al.All-nearest-neigh-bors queries in spatial databases[C].Proc of the 2004 SS-DBM Int Conf on Scientific and Statistics Data Base.LosAlamitos:IEEE Computer Society,2004:297-306.
[4]Goodrich M T,T say J J,Vengrof f D E,et al.External memo-ry computational geometry[C].Proc of the 1993 FOCS An-nual Foundations of Computer Science.Los Alamitos:IEEEComputer Society,1993:714-723.
[5]Corral A,Manolopoulos Y,Theodoridis Y,et al.Closest pairqueries in spatial databases[J].SIGMOD Record,2000,29(2):189-200.
[6]C hen Y,Patel J M.Efficient evaluation of all-nearest neigh-bor queries[C].Proc of the 2007 Int Conf on Data Engineer-ing.Los Alamitos:IEEE Computer Society,2007:1056-1065.
[7]郝忠孝,王玉东,何云斌.空间数据库平面线段近邻查询问题研究[J].计算机研究与发展,2008,45(9):1539-1545.
最近邻演化网络模型 篇4
在以往的复杂网络模型的研究中很少考虑区域和距离的因素。然而, 很多真实的网络受限于节点的位置和节点间的距离, 例如, 现代物流网络和大型集会中的临时通信网络, 人际关系网络中也有区域的限制。假设存在若干区域, 每块区域中有一个“骨干节点”。每个骨干节点和其邻近的骨干节点相连, 新加入的节点选择其附近的节点进行连接。节点代表了通信节点、物流中心等实际场景, 边代表了节点之间的联系。在这种情况下, 节点和边的连接遵循就近原则, 即节点更倾向于与最近的邻居相连。上述情况在我们的生活中几乎时时刻刻都在发生, 我们该如何构建与之相符的模型来描述这种情况呢?如何得出模型的关键指标?新模型将具有哪些特性?为此, 本文提出了“最近邻演化网络模型”。
1 最近邻演化网络模型的构建
本文在BA无标度网络的构建算法的基础上引入区域和距离的限制, 邻近的节点将会位于同一簇中。最近邻演化网络模型的构建算法如下。
(1) 初始状态:具有m0个节点的最近邻耦合网络。每个节点和邻近的左右两侧各K/2 (K为偶数) 个节点相连, 称这m0个初始节点为“骨干节点”。
(2) 归属节点和节点簇:当一个新节点加入网络后, 距该节点最近 (距离以边数衡量, 最近即最短路径上的边数最少) 的骨干节点称为该节点的“归属节点” (如果几个骨干节点与新节点的距离相同且均是最少, 则从中随机选取一个作为节点i的归属节点) 。具有同一归属节点的节点构成一个“节点簇”。
(3) 增长:每次只允许一个节点加入网络。新节点加入时, 首先选择2个相邻的节点簇, 再从这两个节点簇中选择m (m>=2) 个节点进行连接。 (在初始阶段, 节点簇中的节点数一般会小于m, 所以规定新加入的节点只和其选择的节点簇中2个节点连接)
(4) 优先连接:新节点在选择节点进行连接时, 采用优先连接的机制, 即新节点和节点i相连的概率iΠ与节点i的度ki有关, 度越大, 连接概率越大, 按如下公式计算:
其中, Pclusters表示选择的节点簇中包含节点i的概率,
2 最近邻演化网络模型的基本指标
复杂网络研究中刻画网络特性的三个基本指标为:度分布、聚类系数和平均路径长度。度分布指网络中节点度的分布, 节点的度 (如前述, 即与该节点相连的边的数目) 可以衡量一个节点的重要程度, 充分了解网络的度分布, 可以使我们对网络拓扑有一个直观的把握, 并进一步帮助人们更深入地了解复杂系统。聚类系数是衡量网络中邻近节点联系紧密程度的指标, 网络的聚类特性在某种程度上可以概括为社会关系网络中“物以类聚, 人以群分”的特性。平均路径长度可用来衡量网络中节点间距离的大小, 如果网络的平均路径长度的增加速度至多与网络规模的对数成正比, 就说这个网络具有小世界效应。
度分布
将公式 (2) 带入公式 (1) 得到
长时间后, 每个节点簇中的节点数将远大于m, 所以公式 (3) 中的约等于号成立。
利用主方程法, 得到稳态度分布为:
该公式表明最近邻演化网络模型和BA无标度网络模型具有相同的度分布。实验结果和理论值吻合地较好。双对数坐标系下的斜线表明该网络在具有众多小度数节点的同时, 仍在存在少量的大度节点, 这也是网络增长过程中择优连接的一个必然产物。
聚类系数
聚类系数指节点i的ki个邻居节点之间实际存在的连边数Ei与这ki节点所有可能的连边数目之比, 衡量了网络中邻近节点间的紧密程度, 用Ci表示, 即
这里“i”既是节点的代号, 又是节点加入网络的时间点。利用平均场理论, 得到最近邻演化网络的聚类系数 (随时间变化) 为:
当ti远小于t (即节点i加入网络后又过了较长时间) 时, Ci (t) 可作如下近似,
平均路径长度
网络中两节点i和j之间的距离dij定义为连接这两个节点的最短路径的边数。网络的平均路径长度L定义为任意两个节点之间的距离的平均值, 即
其中N为网络节点个数, 因为每一时刻网络中有且只有一个节点加入, 所以若不考虑网络的初始规模, 该处的N等价于t。
给出了无标度网络平均路径长度的尺度,
如表1所示, 通过仿真, 本文得到了最近邻演化网络的平均路径长度L, L的增长速度介于公式 (9) 和ln N之间。随网络规模的增加, 平均路径长度的增长十分缓慢, 表明该网络具有较明显的“小世界效应”。
3 总结与展望
基于最近邻思想的K-均值算法 篇5
数据聚类是数据挖掘的一个非常活跃的研究方向。聚类在文献[1]中定义为:将数据对象进行分组, 成为多个类或簇。在聚类过程中无须用户提供先验的分类知识, 而是根据数据实际的分布情况得到自然的聚集结果。当前主要的聚类算法可以划分为如下几类:
1) 基于划分的方法, 如k-means (K-均值) 文献[2], k-medoids (K-中心点) 文献[3];
2) 基于层次的方法, 如BIRCH文献[4], C U R E文献[5], R O C K文献[6], Chameleon文献[7];
3) 基于密度的方法, 如D B S C A N文献[8];
4) 基于网格的方法, 如S T I N G;
5) 基于模型的方法。
全文内容安排如下:第二节介绍传统K-均值算法的基本思想, 并进行特性分析;第三节介绍改进的K-均值算法;第四节实验;第五节结束语。
2 传统的K-均值算法
2.1 基本思想
K-均值算法是一种重要的聚类算法, 它是目前应用最广的基于划分的聚类算法, K-均值算法以K为参数, 把N个对象分为K个簇, 使簇内具有较高的相似度, 而簇间的相似度较低。相似度的计算根据一个簇中的对象的平均值来进行。
K-均值算法的处理流程如下:首先从N个数据对象任意选择K个对象作为初始聚类中心, 而对于所剩下的其他对象则根据它们与这些聚类中心的相似度量 (距离) 分别将它们分配给与其最相似的 (聚类中心所代表的) 聚类。然后再计算每个所获新聚类的聚类中心 (该聚类中所有对象的均值) 。不断重复这一过程直到标准函数开始收敛为止。
2.2 K-均值算法的基本过程
输入:聚类个数K, 以及包含N个数据对象的数据库。
输出:K个簇。
处理流程:
(1) 从N个数据对象任意选择K个对象作为初始聚类中心。
(2) 循环下述流程 (3) 到 (4) 直到每聚类不再发生变化。
(3) 根据每个聚类对象的均值 (聚类中心对象) , 计算与这些中心对象的距离, 并根据最小距离重新对相应对象进行划分。
(4) 重新计算每个有变化聚类的均值 (中心对象) 。
2.3 K-均值算法的优缺点
优点:K-均值算法实现起来比较简单其计算复杂度为 (nkt) , 其中, n为对象个数, k为聚类个数, t为循环次数, 它具有可扩展性。
缺点:K-均值算法有以下四个缺点:
(1) K-均值算法只适用于聚类均值有意义的情况。
(2) 用户必须事先指定聚类个数K。
(3) K-均值算法还不适合发现非凸状的聚类。
(4) K-均值算法对噪声和异常数据非常敏感。因为这类数据可能会影响到各聚类的均值。
要想使一种聚类算法能克服以上所有缺点几乎不可能。针对K-均值算法对异常点和噪声敏感的这一缺点, Kaufman和Rousseeuw在文献中提出了一种K-中心点算法, K-中心点算法不采用簇中对象的平均值作为参照点, 而是选用簇中位置最中心的点 (中心点) 作为聚类的中心点。剩余的对象根据其与代表点的距离分配给最近的一个簇。然后反复地用非代表对象代替代表对象, 以改进聚类的质量。
K-中心点聚类算法虽然比K-均值算法更健壮, 但K-中心点聚类算法的执行代价要比K-均值算法要高得多。
3 基于最近邻思想的K-均值算法
3.1 基本思想
在传统K-均值算法中存在的一个主要缺点是对噪声和异常点敏感, 其原因是在K-均值算法的每一次迭代中, 簇中的所有对象都参与计算平均值, 再将新的平均值作为新的聚类中心进行计算, 这样噪声和异常点都会参与平均值的计算。因而对平均值 (聚类中心) 有较大的影响。为了避免该情况发生, 我们可以选择参与平均值 (聚类中心) 计算的对象, 不是全部的对象都参与计算平均值, 而是选择与上次聚类中心最近邻的i (i<n/k) 个数据对象参与计算平均值。如果某个簇中对象个数不足i个则可以将其删除。该簇中的对象在进行下一次迭代时被分配到别的簇。这样就可以有效地去除噪声和异常点对平均值的影响。从而使聚类结果更加合理。
下面分析聚类初始点对该算法的影响。如果所选初始点为正常对象 (不是异常) 点, 则其近邻数一般都会大于i这种情况该中心点形成的簇不会被删除。如果某一初始点选中了异常点, 由于异常点与正常对象之间的距离较远, 则其近邻对象一般都会小于i, 这样就可以将该中心点所形成的簇删除, 从而使聚类结果更加合理。不会受到异常点的影响。
在聚类过程中, 如果某一聚类中心所形成的簇中包含有异常点, 如果该簇中包含的对象个数小于i个, 则该簇被删除;如果该簇中对象的个数大于i个则在计算新的聚类中心时, 异常点必定不会参与计算;如果该簇中对象的个数刚好是i个, 则异常点参与计算。但经过数次迭代之后, 该情况出现的概率很小。
综上所述, 该算法可以有效地去除噪声 (异常点) 对传统K-均值算法中平均值 (聚类中心点) 的影响, 从而使聚类结果更加合理。
3.2 基本过程
输入:簇的数K, 包含n个对象的数据库, i簇中参与计算平均值的对象数目。
输出:K个或小于K个簇。
处理流程:
(1) 任意选择K个对象作为初始的簇中心。
(2) 循环下述流程 (3) (4) 直到每个聚类不再发生变化。
(3) 根据簇中前i个对象的平均值, 将每个对象重新赋给最类似的簇。
(4) 更新簇中聚类中心的值。 (计算每个簇中与前一次聚类中心最邻近的前i个对象平均值。)
3.3 时间复杂度分析
改进后的K-均值算法与传统K-均值算法的最大区别就是取每个簇中与聚类中心最邻近的i个对象作为计算平均值 (下一次聚类中心) 的对象。而不是计算簇中所有对象的平均值作为下一次聚类的中心。这样就需要在计算平均值之前进行一次排序。排序的时间复杂度为k m 2 (其中k为簇的个数, m为最大簇中对象的个数) 。因此改进后的K均值算法的时间复杂度为k (m 2+n) t (其中k为簇的数目, m为最大簇中对象的个数, n为全体数对象个数, t为迭代次数。影响m值的因素很多, 如果则改进后的K均值算法与传统的K_均值算法时间复杂性相同, 但通常m 2>n所以改进后的K平均算法要比传统的K_均值算法时间复杂度要高。
4 实验
我们将本算法应用到学生成绩信息分析中, 学生成绩信息分析的目的是研究学生成绩的分布情况, 找出异常信息, 为教务部门进行教学督查提供决策信息。
1) 实验环境
计算机配置:C P U A t h l o n 6 43 0 0 0+, 1 G H z内存, 1 6 0 G B硬盘
操作系统:Microsoft Windows XP
开发平台:Microsoft Visual Studio2005
开发语言:C#
数据库:Microsoft SQL Server 2005
2) 数据集
近两年来收集的学生公修课学生成绩信息, 数据中含学生学号、姓名、高等数学成绩、大学英语成绩。
实验比较了改进后的K-均值算法与传统K-均值算法。实验前首先将指定数据全部读入内存, 并完成相应的预处理工作。
3) 实验结果分析
通过实验表明改进后的K-均值算法和传统的K-均值算法用时基本相当, 并没有显著增加用时, 但聚类效果却明显改善。
5 结束语
在本文中, 我们提出了一种基于最近邻思想的K-均值算法, 该算法在计算聚类中心点时, 采用了一种最近邻思想有效克服了‘噪声’对平均值的影响, 从而使聚类结果更加合理, 并通过实际数据的实验验证明这种算法是有效的。如何将该算法应用到更多的实际数据的聚类是下一步的研究。
摘要：K-均值聚类算法是一种基于划分方法的聚类算法, 本文通过对传统的K-均值聚类算法的分析, 提出了一种改进的K-均值算法, 并对该算法的时间复杂度和空间复杂度进行了分析。该算法在计算聚类中心点时采用了一种最近邻的思想, 可以有效地去除“噪声”和“孤立点”对簇中平均值 (聚类中心) 的影响, 从而使聚类结果更加合理。最后通过实验表明该算法的有效性和正确性。
关键词：数据挖掘,聚类,K-均值
参考文献
[1]Jiawei Han, Micheline Kamber著;范明, 孟小峰, 等译.数据挖掘概念与技术.机械工业出版社
[2]J.MacQueen.Some methods for classificationand analysis of multivariate observations.Journal of the American Statistical Association, 83:715----728, 1967
[3]L.Kaufman and P.J.Rousseeuw.FindingGroups in Data:An Introduction to ClusterAnalysis.New York:John Wiley&Sons, 1990
[4]T.Zhang, R.Ramakrishnan, and M.Livny.BIRCH:An efficient data clustering method forvery large databases.In Proc.1996 ACM-SIGMOD Int.Conf.Management of data (SIGMOD’96) , oages 103----114, Mibtreak, Cabada, June 1996
[5]S.Guha, R.Rastogi, and K.Shim.Cure:Anefficient clustering algorithm for largedatabases.In Proc.1998 ACM-SIGMOD Int.Conf.Management of Data (SIGMOD’98) , pages73—84, seattle, WA, June 1998
[6]S.Guha, R.Rastogi, and K.Shim.Rock:AnRobust clustering algorithm for categoricalattributes.In Proc.1999 Int.Conf.DataEngineering (ICDE’99) , page512—521, Stdebet, Australia, Mar.1999
[7]G..Karypis, E.-H.Han, and V.Ku-mar.CHANELEON:A hierarchical clustering algorithmusing dynamic modeling.COMPUTER, 32:68—75, 1999
【最近邻查询】推荐阅读：
K-最近邻聚类算法06-07
近邻传播07-23
K近邻算法06-07
K近邻方法06-23
K近邻团11-03
改进K近邻算法06-24
远亲不如近邻六年级作文06-01
潮州市养老保险查询个人账户查询06-12
查询模型10-15