改进的CLIQUE优化算法

计算机工程与设计Computer Engineering and Design2009,30 (16)3801●软件与算法●改进的CLIQUE优化算法高亚鲁，宋余庆，朱玉全(江苏大学计算机科学与通信工程学院，江苏镇江212013)摘要: 为了解决子空间聚类算法时间复杂度偏高和网格划分不太合理的问题，通过对数据空间进行网格划分并寻找稀疏区域来发现簇的边界,对算法的时间复杂度进行优化，达到对子空间聚类算法CLIQUE进行了优化和改进目的。优化算法采用了自适应的网格划分方法，提高了发现高维子空间的可能性。优化算法通过对剪枝方式的优化，有效地控制了算法的复.杂度。实验结果表明，该算法在精度、时间复杂性等方面的性能良好。关键词:数据挖掘;子空间聚类;网格划分;密度聚类; CLIQUE中图法分类号: TP312文献标识码:A文章编号: 100-704 (2009) 16-3801-04Improved CLIQUE algorithmGAO Ya-lu，SONG Yu-qing，ZHU Yu-quan(School of Computer Science and Telecommunications Engineering, Jiangsu University, Zhenjiang 212013, China)Abstract: Subspace clustering algorithm CLIQUE is improved. Boundaries between clusters are located by partitioning grids in thedata space and finding sparse regions. The improved algorithm uses self-adaptive grid generation method, which improves the possibilityof finding high-dimensional subspace cluster. The improved algorthm optimized pruning procedure, which reduces the computationalcomplexity. The experimental resuts show that the improved algorithm performed very well in accuracy and computational complexity.Key words: data mining; subspace clustering; gid generation; density clustring; CLIQUE导致某- -聚类被人为的分为多个区域。.➊引言(2)CLIQUE算法所花的时间与数据集中的数据维数和实聚类分析是数据挖掘领城重要研究课题，聚类分析就是例数呈线性关系,一股产生簇的维数不高。将数据划分为有意义或者有用的组(簇)"。数据挖掘对于聚(3)密度阈值和网格尺寸两个参数的确定比较困难。类的要求有:可伸缩性,处理不同类型属性的能力，发现任意本文主要是对CLIQUE算法的缺点(1)和(2)进行了改进。形状聚类的能力，对于输入参数需求量少,处理带噪声数据的本文采用了自适应网格技术对稀疏单元进行再次分析，来确能力,对输入次序不敏感性,高维性，基于约束的聚类,可解释定划分的边界,这样能够尽可能的使划分更加合理,增加了发性和可用性"。迄今为止,已经提出了许多聚类算法,主要有现高维 族的可能性，大大降低了某个簇被分为多个区域的可划分方法、层次方法、基于密度的方法、基于网格的方法和基能性。本文采用了剪枝优化处理，有效的控制了算法的复杂于模型的方法。大部分算法都是为低维数据设计的，当数据度，提高了算法的运行效率。我们对算法在数据机上进行实实际的维数很高时，这些聚类算法就面临挑战。目前对于高验分析,试验结果证明了算法的效率和有效性。维数据的处理方法不外乎以下两类:特征(或者属性)转换方1 NEW-CLIQUE子空间聚类算法法,例如主成分分析和奇异值分解:特征(或者属性)选择技术。子空间聚类是- -种属性子集选择的扩展，它在高维数据聚类NEW-CLIQUE算法是对CLIQUE算法的改进和优化。主方面有着明显的优势网。它能够发现不同的子空间可能包含要从以下两个方面对原有的算法进行了改进:不同的，有意义的簇。并且大部分的子空间聚类算法都是基(1)通过对网格划分后产生的稀疏网格的研究,来确定划于CLIQUE算法。分的边界,这样使划分更合理。.CLIUQE算法是综合运用基于密度和网格方法优点所构(2)本文使用了更为高效的剪枝优化算法，有效的控制了造的聚类方法，但是CLIQUE算法有不少的缺点,主要有以下算法的复杂度。几点: .改进后的算法运行效率根高了.发现簇的维数增高了,运(1)用户根据输入的参数进行等宽分割每一维,这样可能行所中国煤化工收稿日期: 2008-08-16; 修订日期: 2009-03-02.TYHCNMHG基金项目:国家自然科学基金项目(60572112. 60841003).作者简介:高亚鲁(1981-), 男，山东滕州人,硕士研究生,研究方向为数据挖掘及数据库:宋余庆 (1959-),男，教授，博士生导师，研究方向为数据挖掘;朱玉全 (1966-), 男，副教授，研究方向为数据挖掘及数据库。E-mail: gy)59689@126.com38022009,30 (16)计算机工程与设计Computer Enineering and Design1.1 概念定义1空间S;A= {A,A, "..A)是d个城的集合,那么A= (AxXx-.xAu}就是一个d维的空间,.,A.则是S的维(属性)。{定义2点集V:V=vVv..,.VJ, 其中V,= {v,v,.,GV小. V.的第j个分量V,∈4(1≤j≤d.定义3标准的网格单元 G,通过输入参数，引知.，,将空间S中的任意一个类矩形子空间S&(.CS定义-一个标准的单元G。G= :.*.",n,其中的Bi = [4,4号)是一个前闭图1网格的划分后开的区间[1≤j≤d].定义4密度单元D(U): D(U)落入一个单元U的总点数。密单元，如果是稠密单元，则稠密单元的区间的区城扩展为一个点 V.落入了一个单元U。中,即w∈U,当且尽当对于每-[intd,Min+号)。如果是稀疏单元，则不作任何处理。综合个U。都有l≤V≤h,成立,[1≤= k++)/的项目数大于(k-1)项最小值为Min,最大值为Max,那么区域宽度为d=Max-Min,然forechtED/对于属于数据库D的每一条记录进行扫描1f(记录t的数据项数$) dleletfrom D} /对事务数据进后考察区间[Mor+号Min+d)是不是稠密单元,如果是稠密单元, .行压中国煤化工则将稠密单元的区域扩展为[Min+号Mint+o.如果是稀疏单元,据库YHCNMHGop column A} /压缩数则不作任何处理。同理,考察区间([Mr+2d,MGn+号是不是稠Prod. Cand(,/i生的L候选集,并进行计数高亚鲁，宋余庆，朱五全:改进的CLIQUE优化算法2009,30 (16) 3803Foreacb候选项c∈候选项目集C.图2(a)(c)分别是算法性能测试的结果。图例中的NCLI{If(候选项c的个数>阈值){向表3中插入L}代表算法NEW-CLIQUE, CLI代表算法CLIQUE。图2(a)表明, .}}}随着实例数的增加，两种算法的时间开销都呈线性的增加。由示例数据库如表1所示,为了简化表,将由数据设置为了于改进的算法中使用了效率更高的发现频繁集合Apriori-id算1,将无数据设置为了0,闽值为2.使用Apriori算法,生成L=法, 所以消耗的时间更少一- 些。图2(b)表明,在随着维数的增{{a}, {b}, {c}, {d}, {e}};Ln= {{ac}, {bc}, {be}, {ce}, {ef}. L和加，改进后的算法的运行所消耗的时间略有减少。由于在算法L.的频繁项目集，如表2所示，把L和La如表3所示存储。对中Aprior-tid处理过程对事务数据库的压缩，剔出一些属性,所于L及其以上的频繁集都使用Aprioni-Otid算法进行处理。以消耗的时间略有减少。图2(c)由于对网格单元的划分进行了优化,可以使算法在更少的时间内发现更多的高维子空间。表1事务数据库IDad201o200 400 600 800 1000表2 L和L.频繁集实例数/条LID10+NCL;凸CLI频繁(a)实例数xe|be|ce|cf项目集表3挖掘过程中的事务数据库TL6(a}{e}{旧{ac}{en晏4{b){e}{e}{bc){ce{bce}{a}{b}{e}{e) (ac} {be) bel{le)){bee)2.004408发事_{b}{e}{n(bel204060 80 100维敷母NCLI;公CLI1.4 New-CLIQUE算法的步骤(b)维数(1)首先对数据进行自适应划分，得到每一维的稠密网格单元分别记作Al,A, .. ,B, B), .. ,C,C.-",等。(2)分别以A,A, .. B, .. ,C,C, ..等作为属性，10-对数据库进行稍描然后得到事务数据库D.(3)对事务数据库采用优化的Apriori-tid算法，来发现频繁项集合。(4)将发现的频繁集描述出来。o3在发现频繁集的过程中,先使用Apriori算法去发现频繁子空间最大维数集L,和L(表2),然后将频繁集L和L,重新存储(表3),并且使NCLI; A CLI用Apror-Otid算法去发现L,及其以上的频繁集。Insert into(6)子空间最大维数Table(L,L)将生成的L和L,用表3的方式重新进行存储。Apriori-Otid(L)(k>2)对于K大于2的情况使用这个算法图2随着实例数，维数、子空间最大维数变化时间的消耗来发现频繁项目集. .3结束语2实验分析本文结合自适应的网格划分和Apriori-tid算法的优化对实验表明，采用自适应的网格单元划分,可以使得到的网于CLI中国煤化工w.CLIQUE算法。使格边界更加准确，划分更加合理。在发现频繁项目集的时候用自适子单元划分的精度,使采用的是优化的Apriori-tid算法，有助于控制算法的时间复杂算法得CNMH C中对于发现子空间族度，提高算法的运算效率。以下从3个方面对算法New-CL-的迭代过程进行了优化,使算法的运行效率提高了不少。QUE和CLIQUE进行比较。New-CLIQUE算法的不足之处在于聚类的结果还依赖于3804 2009,30 (16)计算机工程与设计Computer Engineering and Design密度阈值,从输入的参数上看没有什么改进"。对于阈值的依赖4] Rakesh Agrawal. IBM almaden research center [C]. Automatic性是基于密度聚类算法的。对于网格边界的处理改进还不够。Subspace Clustering ofHigh Dimensional Data for Data Mining虽然算法对于网格划分进行了优化,但是优化后的算法也可能Applcations,1998.丢弃一些科密区域,希望下一步进-步提高网格划分的精度。[5] HSU C2M,CHEN M2S.Subspace clustering ofhigh dimensionalspatial data with noises[C].PAKDD 2004(Lecture Notes in Com-参考文献:puter Science),2004:31-40.[1] Tan Pang-Ning, Michael Steinbach,Vipin Kumar数据挖掘导论[6] Chen Xia, Wyune Hsu,Mong Li Lee,et al. BORDER eficient[M.范明,范建宏,译北京:人民邮电出版社, 2006:205-305.computation of boundary points[J].IEEE transaction on Know-2] Han Jiawei,Micheline Kamber.数据挖掘概念与技术[M].范明,ledge and Data Eninering.2006(18)-289-303.孟小峰译.北京:机械工业出版社2007:252.285.[7] 陈慧萍,王煜,王建东子空间聚类算法的研究新进展[).计算机[3] Agrawal R, Gehrke J, Gunopulos D, et al. Automatic subspace仿真,2007.3:6-8.clustering of high dimensional datJ].Data Mining and Know-[8] 彭仪普,熊拥军.关联规则挖抛Apriori Tid算法优化研究[J].ledge Discovy20011):5-33.计算机工程206325)55-57.(上接第3736页)8x8色度块l DCT_NT-_ QDCT - +HDCT. JNT- tQHDCT图2整数变换与量化设计在HDCT INT模块中，计算a"、b".c".d"时要涉及到如何使16个数据能够在较短时间内相加的问题，只有解决这个问题，我们的算法优化才算真正成功。由于在第2节中我们已围3顶层模块仿真经提到一个时钟内可以完成4个数的加减和移位运算，因此行运行,缩短了哈达玛变换所需要的时间，并成功设计实现了在设计的时候，我们把16个数据平均分成4组,在一个时钟周基于FPGA的整数变化及量化模块，达到了在少量增加硬件期内计算出4个组中每组所有元素的和，即得到4个中间结资源耗费的基础上大大减少时间消耗的设计效果。本文的设果，然后再用一个时钟时间计算出a",b"、c"、d"的计算方法相计经过仿真验证,具有一定的应用价值和现实意义。同。这样总共耗时3个时钟即完成哈达玛变换。由于在算法优化的时候，我们只是把中间结果变量进行代入，因此实际设计时候实际使用的加法器只增加了少许，也就是说我们的设计是在少量增加硬件资源消耗的基础上大大减少了时间消耗，1] 毕厚杰新一代视频压缩编码标准- -H.264/AVC[M].北京人民具体的资源消耗我们将在下一节仿真验证中进行详细说明。2] 余兆明图像编码标准H.264技术[M].北京:人民邮电出版社,邮电出版社.2005.4仿真验证2006.在qurusH中，采用Alern公司的Stratix I1系列的[3] Joimt Video Team of ISOTEC MPEG and mu.T VCEG,DratEP3SL340F1760C4L FPGA芯片对顶层模块DCT_ Q TOP进行ITU-T recommendation and final draft intermational standard of仿真，时钟频率为50MHZ.仿真结果表明，优化后整个整数joint video secificationo ITU-T Rec.H.264ISO/TEC 14496-10DCT变换及量化算法消耗了6122个LE,而在同样的PFGA平AVC[S]JVT-G050,2003.台和时钟频率下，优化前整个算法消耗了5820个LE,所消耗4] 周斌,严德聪.H.64AVC先进视频编码研究[J计算机工程与的硬件资源只上升了5%。优化后算法的仿真结果如图3所设计2004,25(9):1523-1525.示，其中ou00.-out07是DCT变换的量化结果，out00 _quv、[5] 何云壮.H.264輅数DCT变换的FPGA实现[].微计算机信息,out01_ quv 是哈达玛变换的量化结果。从图3中也可以看出,2007,23(6-2):205-206.除去量化模块消耗的2个时钟，哈达玛变换只消耗了3个时倪伟.H.264变换编码和量化算法的研究[D].计算机工程与应钟,验证了我们在文中作出的结论。用2004,40(3):33-36.7]:11. Low complexity trans-5结束语中国煤化工IEEE Trans CrutSys本文充分利用了H.264运算的整洁性和FPGA的强大并YHCNMHG行处理能力，并对輅数变换部分进行了优化,采用消除中间变[8]王一皓,陈磊. H.264中的DCTHadamard变换多时钟方式的量的方法把原来串行运行的DCT变换和哈达玛变换变成了井FPGA实现[)]中国有线电视2007(8):754-757.