论文研究-基于网格密度和引力的不确定数据流聚类算法.pdf

所需积分/C币:5 2019-07-22 19:06:48 643KB .PDF

为改进EMicro算法存在的不足提出了GDF-CUStreams算法。该算法采用网格特征向量存储数据的分布特征,通过更新网格特征向量合并成簇对不确定数据流聚类,对新数据点的到来采用增量聚类。通过网格密度和网格质心之间的距离判定网格是否是零星网格,利用网格引力对簇边界进行优化,检测和删除零星网格,使簇边缘更加平滑,提高聚类精度。其中网格密度和网格质心都采用增量更新。实验结果表明,与EMicro算法相比,GDF-CUStreams效率更高且效果良好。
100 计算机应用研究 第32卷 2.2零星网格的检测与删除 的最大引力低于引力阈值的可能性增大。再次保证了零星网 稀疏网格中由噪声点形成的网格称为零星网格。除了零格的及时删除 星网格,稀疏网格中还有些包含数摒点的网格。随时间的推2.4聚类簇调整算法 移和数据点密度的衰减导致网格内一段时间密度较小,但之后 在 GDF-CUStreams中调用算法 AdjustCluster( GridList)动 还可能进化为过渡网格甚至稠密网格。网格密度阈值函数的态调整所形成的簇。 提出就是为区分零星网格和包含数据点的俙疏网格 算法GDF- CUStreams(哈希表: Gridlist) 定义11密度阈值函数。假设最新的更新时间是!,则 for each(前一次调用 Adjust cluster()格密度变化了的树格G 在当前吋间t树格G密度阈值数 MinPts(!,t)定义为 if(G是稀疏网格) for each(C的相邻密度网格B) C1(1-2-A-+ Min Pis(tn,t)=n∑2 计算F、(G,H,)和所属簇是cn的相邻网格m 2K(1-2-4) if( Fmax(G H, t)< Fmin(i, G, t)) 引理1密度阈值函数的性质 删除网格G; a)t, <t2, MinPts(tu, t,)MinPts(tu, t2) ele将C并入簇cn if(簇c是不连接的) b)MmP(4o,)、CL 将簇c分成两个不同的簇 2K leif(G是密度网格) c)lim MinPts(t. t)2k(1-2)U 挑选与G相邻的且包含数据点最多的簇的网格H(密度网 格G的相邻网格H属于簇Chk) 若t吋刻格密度Den(G,t)< MinPts(tn,1),则G为零星 判定簇c是否包含网格G i(H是密度网格 网格,直接删除。如果Den(G,t)> MinPts(tn,t),则G不应被 if(G不属于任意簇c) 删除。性质a)表明稀疏网格存在时间舨长,其期罩密度舨高 将网格G并入 其密度比 Minpts(t,)小的可能性越大,以便及时删除零星网 e if Ic≥lcr 将ch的所有网格并人 格。性质b)保证了在新到数据点时,网格的密度闵值立刻变 else if Ic<Ic, 得很小,避免一些包含数据点较少稀疏网格被当做零星网格删 将c的所有网格并入Cn 除。性质c)保证了根据该密度阈值函数判定删除的网格必定 else if(H是过渡网格) 是稀疏网格。 if(G不属于簇c且相邻网格H是簇cb的边界网恪 将网格G并入CA 2.3簇边界网格的判别与保留 else if(G属丁簇c且c|≥lck1) 木文提出网格引力就是为避免删除操作造成簇边界精度 将H划分到簇c else if(G是过渡网格) 的丢失。根据算法定义,若裯密网格和稀疏网格不相邻,则将 挑迕与G相邻的包含数据点最多的簇m; 桸疏网格视为孤立点赒除;若有稠密內袼和该稀疏內格相邻, (将G划到簇m后,相邻网格H是簇cn的边界网格) 则计算该稀疏网格的密度阈值;若其密度大于密度阈值,则不 将G并人m 删除;若其密度小于密度阈值,则计算它们之间的网格引力,取 在 AdjustCluster算法中,判别前一次调用它时网格G的级 与该稀疏网格相邻的稠密网格中最大网格引力与该稀疏网格别。若G是稀疏网格且相邻的所有密度网格对它的最大网格 引力國值比较,若大于该阈值则不删除,小于则删除。引力阈引力小于相邻的簇边界N格对它的最小网格引力,则将其删 值函数的提出是为了准确区分簇边界网格与零星网格,用来判 除,否则将其归到该簇中。若此吋簇是不连接的,则将其分成 别某稀疏內格是否是簇边界內格。 两个不同的簇。若G是密度网格且所有相邻网格中网格H所 引理2对网格G与其在第k维上相邻的网格H,若网格属簇c密度最大,若H是密度网格,而G不属于任意簇,则将 的边长为l,假设网格中数据点是等概率分布的,则t时刻的 G归到簇c,否则若G所属簇为c,根据簇c和簇c的数据点 加权质心距 密度决定是簇c归到c还是c归到c若H是过渡网格,G 不属于任意簇而H是簇边界网格,则将G归到ca;反之,若G dist(G, H, t)=lk 所属簇r的密度大于簇c,则将归到簇c。若G是过渡內 定义12引力阈值函数。假设最新的更新时间是,则格,且相邻簇m是数据点密度最大的簇,若将G归到簇m后 在当前时间r,网格G引力阈值函数定义为 网格H是簇c的边界网格,则将G归到簇m k Fmn (i, L,, t)=In k,CCR(1-2-A( (t-ta4+1) 4h2(1-24 3实验结果与分析 如果某稀吮网格和相邻稠密网格的最大引力大于引力阈 值函数,说明此网格为簇边界网格,要保留该网格而不删除。 本文以EMcr算法为基准,使用 MATLABⅤ7R41具实 引力值函数Fmn(,,t)的性质 现算法GDF- CUStreams聚类质量和聚类时间方面的比较。因 k, In L,d 为两者在聚类过程中都关注不确定数据流存在级不确定性,故 )lim Fmi(i, t,, t)=In[ 都可运行在同一个不确定性数据集上。实验平台: Pentium b)若t1<t2,则Fm(i,,,t1)≤Fm(,t,t2) Dual-Core(2.10GHz)处理器,2GB内存, Windows7操作系统。 性质a)定义了相邻网格的最大引力阈值函数,在加权质31实验概述 心趋向网格中心且稠密网格密度接近最小密度Dn时,所删除 测试数据集采用 AMico算法实验的数据集,即模拟数据集 网格的密度一定小于D。性质b)说明若效据点长时间未到和真实数据集,然后再将其转换为相应的不确定数据集。 达,则稀疏网格的引力阈值会逐渐变大,故其和相邻稠密网格 模拟数据集 Sondrio:任意选定一系列簇中心点和簇半径, 第1期 邢长征,等:基于网格密度和引力的不确定数据流聚类算法 ·101 以模拟簇漂移现象。簇内数据点的总体分布服从高斯分布,总和簇数量,将数据集的维度由10增加到50时,与图3显示类 共生成60万个记录 似,木文算法与 EMicro算法相比,斜率较小,显小算法GDF 真实数据集 Corest covertype数据集1:包含581012个记 CUStrealms的执行时间随维度呈线性增长,故认为CDF-CUs 录,48个类,从全部54个属性特征中选取10个数值属性,用 CreaMs相对EⅥ Micro具有更好的维度可扩展性。 做不确定数据集。 1 DF-CUStreams算法的参数设置如下:衰减因子A=3,最小4结束语 密度参数D1=1,最大密度参数Dn=3,引力系数k1=1,k2=1。 本文提出的 GDF-CUSIreams算法,可以发现任意形状的 算法执行五次以提高实验结果的准确性 簇。改进了不确定数据流聚类算法 EMicro算法存在的缺陷。 3.2聚类质量分析 本文算法相对 EMicro的聚类精度更好且执行时间更快,并具 图1分别比较了算法 GDF-CUStreams和算法 EMicro在森较好的伸缔性,更有利于处理高维数据集。 林覆盖类型数据集上的聚类质量,其横轴是不确定数据流量,参考文献 纵轴是簇的平均质量。由图1可知, GDF-CUStreams比 EMicro「11 PENG Yu, SONG Jia, PENG XI-yuan. Survey of fault management 具有较高的聚类纯度。因为 MIcro是基于距离的聚类算法, framework in wireless sensor networks [J. Journal of Electronic 更适合发现球状簇而不是任意形状的簇。全局离群点的删除 Measurement and Instrument, 2009, 23(11): 1-10 大大影响了聚类的质量。而 GDF-CUSUrears利用网格特征冋2 PENG YU, LU Qing-hua, PENG XI-yuan. Analysis of uncertain data 量存储数据概妟信息,通过网格特征向量的实吋维护对灲格信 processing methods in networking test framework [ J]. Chinese Jour- 息动态更新和零星网格的及时删除提高了聚类纯度。 nal of Scientific Instrument, 2010, 31(1): 229-240 3.3聚类效率分析 [3 YE Li, QIN Zhi-guan, YANG Xi-mei, et a/. Uncertain ra ye query and pruning algorithm for bead model [J] Journal of Electronic Mea 图2分别比较了算法GDF- CUStrearms和算法 EMicro在森 surement and Instrument. 2010, 24(8): 722-729 林覆盖类型数据集上的聚类时间。其横轴是不确定数据流量,[4. AGGARWAL CC,YUPS. A framework for clustering uncertain data 纵轴是处理时间。由图2可知,两算法聚类时间都随不确定数 treams [c/Proc of the 24th IEEE International Conference on Da 据沇量呈线性增长,但GDF- CUStreams比 EMicro更快。因为 la Engineering. 2008: 150-159 EMicro算法是基于K- Means算法的聚类。而本算法采用增量5金欲清,钱卫宁,周傲英,流数括分析与管坦综述[J软件学报, 聚类直接将数据点映射到网格,密度和加权质心更新的时间复 004,15(8):1172-1181 杂度为0(1)且哈希表的存储结构时间复杂度接近0(1),提 [6 BABCOCK B, BABU S, DATAR M, el al. Models and issues in data stream syslems [ C]//Proc of the 2l th ACM Symposium on Principle 升了聚类速度。 of Database: Systems. New York: ACM Press, 2002: 1-16 EMicro [7 ZHOU AO-ying, CAO Feng, QIA\ Wei-ming, et al. Tracking clusters aGDF. CUStreams in evolving data streams over sliding windows[J]. Knowledge and >0.5 Information Systems, 2008, 15(2): 1-214 8 CALLAGHAN L, MISHRA N, MEYERSON A, et al. Streaming 0.3 lala algorithm for high-quality cluslering[ C]//Proe of IEEF Interna- tional Conference on Data Engineering. 2002: 685-690 progression of strcam/pointsxIE15 [9 AGGARWAL CC, IIAN Jia-wei, WANG Jian-rong, et al. A framework progression of strcam/pointsxIEt5 图1算法 GDF-CUStreams与 图2算法 GDF- CUStreams与 for clustering evolving data streams C //Proc of the 29th Interna EMico if forest covertype dataset EMico 1 forest covertype dataset tional Conference on Very Large Data Bases.S 1.: VLDB Endow F聚类质量的印车 卜聚类时间的比较 ment.2003:81-92 3.4聚类算法的伸缩性 [10 ZHANG Chen, GAO Ming, ZHOU Ao-ying. Tracking high quality 图3和4显示了基于模拟数据集算法的伸缩性。图3显 clusters over uncertain data streams[ C//Proc of IEEE International 示增加数据量固定维度来测试对数据量的伸缩性。图4固定 erence on Data Engineering.2009: 1641 [11 HUANC Guo-yan, LIANG Da-peng, REN Jia-dong. An algorithm for 数据量增加维度来测试对维度的可扩展性。 liding windows」/ Proc of l80 180 EMirs算法 the 6th International Conference on Digital Content, Multimedia Tech f. CUSteeam l00 GDF. CUSIreanms算法 nology and its Applications. 2010: 173-177 12 DAI Dong-bo, ZHAO Gang, SUN Sheng-li. Effective clustering algo- 100 100 rithm for probabilistic data stream [J] Journal of Software, 2000 60 20(5):1313-1328 13 ZHANG Chen, JIN Chen- qing, ZHOU Ao-ying. Clustering algorithm over uncertain data streams [J. Journal of software, 2010, 21(9) 数据量/1E+5 维度 图3测试对数据量的伸缩性4测试对维度的可扩展性 2173-2182 [14 YANG Yue, LIU Zhou, ZHANG Jian-pei, et al. Dynamic density-based 图3显示了当数据量由100000增至500000时GDF clustering algorithm over uncertain dala st reams[ C//Proc of IEEE CUStreaIms随着聚类时间上升,本文算法与 EMigrE算法相比, International Conference on Data Engineering 2012: 2664-2670 斜率较小,曲线接近直线走势,故认为 GDE-ClStream相对15 NEWMAN D J, HETTICH S, BLAKEC L,ta. uCi repository of m 上 Micro对数据量具有更好的伸缩性。图4固定数据流的长度 chine learning databases Eb/Ol]. htTp: //archive. ies uci. edu/ml/

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐