計算機(jī)工程與設(shè)計Computer Engineering and Design2009,30 (16)3801●軟件與算法●改進(jìn)的CLIQUE優(yōu)化算法高亞魯，宋余慶，朱玉全(江蘇大學(xué)計算機(jī)科學(xué)與通信工程學(xué)院，江蘇鎮(zhèn)江212013)摘要: 為了解決子空間聚類算法時間復(fù)雜度偏高和網(wǎng)格劃分不太合理的問題，通過對數(shù)據(jù)空間進(jìn)行網(wǎng)格劃分并尋找稀疏區(qū)域來發(fā)現(xiàn)簇的邊界,對算法的時間復(fù)雜度進(jìn)行優(yōu)化，達(dá)到對子空間聚類算法CLIQUE進(jìn)行了優(yōu)化和改進(jìn)目的。優(yōu)化算法采用了自適應(yīng)的網(wǎng)格劃分方法，提高了發(fā)現(xiàn)高維子空間的可能性。優(yōu)化算法通過對剪枝方式的優(yōu)化，有效地控制了算法的復(fù).雜度。實(shí)驗(yàn)結(jié)果表明，該算法在精度、時間復(fù)雜性等方面的性能良好。關(guān)鍵詞:數(shù)據(jù)挖掘;子空間聚類;網(wǎng)格劃分;密度聚類; CLIQUE中圖法分類號: TP312文獻(xiàn)標(biāo)識碼: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導(dǎo)致某- -聚類被人為的分為多個區(qū)域。.?引言(2)CLIQUE算法所花的時間與數(shù)據(jù)集中的數(shù)據(jù)維數(shù)和實(shí)聚類分析是數(shù)據(jù)挖掘領(lǐng)城重要研究課題，聚類分析就是例數(shù)呈線性關(guān)系,一股產(chǎn)生簇的維數(shù)不高。將數(shù)據(jù)劃分為有意義或者有用的組(簇)"。數(shù)據(jù)挖掘?qū)τ诰?3)密度閾值和網(wǎng)格尺寸兩個參數(shù)的確定比較困難。類的要求有:可伸縮性,處理不同類型屬性的能力，發(fā)現(xiàn)任意本文主要是對CLIQUE算法的缺點(diǎn)(1)和(2)進(jìn)行了改進(jìn)。形狀聚類的能力，對于輸入?yún)?shù)需求量少,處理帶噪聲數(shù)據(jù)的本文采用了自適應(yīng)網(wǎng)格技術(shù)對稀疏單元進(jìn)行再次分析，來確能力,對輸入次序不敏感性,高維性，基于約束的聚類,可解釋定劃分的邊界,這樣能夠盡可能的使劃分更加合理,增加了發(fā)性和可用性"。迄今為止,已經(jīng)提出了許多聚類算法,主要有現(xiàn)高維 族的可能性，大大降低了某個簇被分為多個區(qū)域的可劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法和基能性。本文采用了剪枝優(yōu)化處理，有效的控制了算法的復(fù)雜于模型的方法。大部分算法都是為低維數(shù)據(jù)設(shè)計的，當(dāng)數(shù)據(jù)度，提高了算法的運(yùn)行效率。我們對算法在數(shù)據(jù)機(jī)上進(jìn)行實(shí)實(shí)際的維數(shù)很高時，這些聚類算法就面臨挑戰(zhàn)。目前對于高驗(yàn)分析,試驗(yàn)結(jié)果證明了算法的效率和有效性。維數(shù)據(jù)的處理方法不外乎以下兩類:特征(或者屬性)轉(zhuǎn)換方1 NEW-CLIQUE子空間聚類算法法,例如主成分分析和奇異值分解:特征(或者屬性)選擇技術(shù)。子空間聚類是- -種屬性子集選擇的擴(kuò)展，它在高維數(shù)據(jù)聚類NEW-CLIQUE算法是對CLIQUE算法的改進(jìn)和優(yōu)化。主方面有著明顯的優(yōu)勢網(wǎng)。它能夠發(fā)現(xiàn)不同的子空間可能包含要從以下兩個方面對原有的算法進(jìn)行了改進(jìn):不同的，有意義的簇。并且大部分的子空間聚類算法都是基(1)通過對網(wǎng)格劃分后產(chǎn)生的稀疏網(wǎng)格的研究,來確定劃于CLIQUE算法。分的邊界,這樣使劃分更合理。.CLIUQE算法是綜合運(yùn)用基于密度和網(wǎng)格方法優(yōu)點(diǎn)所構(gòu)(2)本文使用了更為高效的剪枝優(yōu)化算法，有效的控制了造的聚類方法，但是CLIQUE算法有不少的缺點(diǎn),主要有以下算法的復(fù)雜度。幾點(diǎn): .改進(jìn)后的算法運(yùn)行效率根高了.發(fā)現(xiàn)簇的維數(shù)增高了,運(yùn)(1)用戶根據(jù)輸入的參數(shù)進(jìn)行等寬分割每一維,這樣可能行所中國煤化工收稿日期: 2008-08-16; 修訂日期: 2009-03-02.TYHCNMHG基金項(xiàng)目:國家自然科學(xué)基金項(xiàng)目(60572112. 60841003).作者簡介:高亞魯(1981-), 男，山東滕州人,碩士研究生,研究方向?yàn)閿?shù)據(jù)挖掘及數(shù)據(jù)庫:宋余慶 (1959-),男，教授，博士生導(dǎo)師，研究方向?yàn)閿?shù)據(jù)挖掘;朱玉全 (1966-), 男，副教授，研究方向?yàn)閿?shù)據(jù)挖掘及數(shù)據(jù)庫。E-mail: gy)59689@126.com38022009,30 (16)計算機(jī)工程與設(shè)計Computer Enineering and Design1.1 概念定義1空間S;A= {A,A, "..A)是d個城的集合,那么A= (AxXx-.xAu}就是一個d維的空間,.,A.則是S的維(屬性)。{定義2點(diǎn)集V:V=vVv..,.VJ, 其中V,= {v,v,.,GV小. V.的第j個分量V,∈4(1≤j≤d.定義3標(biāo)準(zhǔn)的網(wǎng)格單元 G,通過輸入?yún)?shù)，引知.，,將空間S中的任意一個類矩形子空間S&(.CS定義-一個標(biāo)準(zhǔn)的單元G。G= :.*.",n,其中的Bi = [4,4號)是一個前閉圖1網(wǎng)格的劃分后開的區(qū)間[1≤j≤d].定義4密度單元D(U): D(U)落入一個單元U的總點(diǎn)數(shù)。密單元，如果是稠密單元，則稠密單元的區(qū)間的區(qū)城擴(kuò)展為一個點(diǎn) V.落入了一個單元U。中,即w∈U,當(dāng)且盡當(dāng)對于每-[intd,Min+號)。如果是稀疏單元，則不作任何處理。綜合個U。都有l(wèi)≤V≤h,成立,[1≤= k++)/的項(xiàng)目數(shù)大于(k-1)項(xiàng)最小值為Min,最大值為Max,那么區(qū)域?qū)挾葹閐=Max-Min,然forechtED/對于屬于數(shù)據(jù)庫D的每一條記錄進(jìn)行掃描1f(記錄t的數(shù)據(jù)項(xiàng)數(shù)$) dleletfrom D} /對事務(wù)數(shù)據(jù)進(jìn)后考察區(qū)間[Mor+號Min+d)是不是稠密單元,如果是稠密單元, .行壓中國煤化工則將稠密單元的區(qū)域擴(kuò)展為[Min+號Mint+o.如果是稀疏單元,據(jù)庫YHCNMHGop column A} /壓縮數(shù)則不作任何處理。同理,考察區(qū)間([Mr+2d,MGn+號是不是稠Prod. Cand(,/i生的L候選集,并進(jìn)行計數(shù)高亞魯，宋余慶，朱五全:改進(jìn)的CLIQUE優(yōu)化算法2009,30 (16) 3803Foreacb候選項(xiàng)c∈候選項(xiàng)目集C.圖2(a)(c)分別是算法性能測試的結(jié)果。圖例中的NCLI{If(候選項(xiàng)c的個數(shù)>閾值){向表3中插入L}代表算法NEW-CLIQUE, CLI代表算法CLIQUE。圖2(a)表明, .}}}隨著實(shí)例數(shù)的增加，兩種算法的時間開銷都呈線性的增加。由示例數(shù)據(jù)庫如表1所示,為了簡化表,將由數(shù)據(jù)設(shè)置為了于改進(jìn)的算法中使用了效率更高的發(fā)現(xiàn)頻繁集合Apriori-id算1,將無數(shù)據(jù)設(shè)置為了0,閩值為2.使用Apriori算法,生成L=法, 所以消耗的時間更少一- 些。圖2(b)表明,在隨著維數(shù)的增{{a}, , {c}, osqwwom0, {e}};Ln= {{ac}, {bc}, {be}, {ce}, {ef}. L和加，改進(jìn)后的算法的運(yùn)行所消耗的時間略有減少。由于在算法L.的頻繁項(xiàng)目集，如表2所示，把L和La如表3所示存儲。對中Aprior-tid處理過程對事務(wù)數(shù)據(jù)庫的壓縮，剔出一些屬性,所于L及其以上的頻繁集都使用Aprioni-Otid算法進(jìn)行處理。以消耗的時間略有減少。圖2(c)由于對網(wǎng)格單元的劃分進(jìn)行了優(yōu)化,可以使算法在更少的時間內(nèi)發(fā)現(xiàn)更多的高維子空間。表1事務(wù)數(shù)據(jù)庫IDad201o200 400 600 800 1000表2 L和L.頻繁集實(shí)例數(shù)/條LID10+NCL;凸CLI頻繁(a)實(shí)例數(shù)xe|be|ce|cf項(xiàng)目集表3挖掘過程中的事務(wù)數(shù)據(jù)庫TL6(a}{e}{舊{ac}{en晏4{b){e}{e}{bc){ce{bce}{a}{e}{e) (ac} {be) bel{le)){bee)2.004408發(fā)事_{e}{n(bel204060 80 100維敷母NCLI;公CLI1.4 New-CLIQUE算法的步驟(b)維數(shù)(1)首先對數(shù)據(jù)進(jìn)行自適應(yīng)劃分，得到每一維的稠密網(wǎng)格單元分別記作Al,A, .. ,B, B), .. ,C,C.-",等。(2)分別以A,A, .. B, .. ,C,C, ..等作為屬性，10-對數(shù)據(jù)庫進(jìn)行稍描然后得到事務(wù)數(shù)據(jù)庫D.(3)對事務(wù)數(shù)據(jù)庫采用優(yōu)化的Apriori-tid算法，來發(fā)現(xiàn)頻繁項(xiàng)集合。(4)將發(fā)現(xiàn)的頻繁集描述出來。o3在發(fā)現(xiàn)頻繁集的過程中,先使用Apriori算法去發(fā)現(xiàn)頻繁子空間最大維數(shù)集L,和L(表2),然后將頻繁集L和L,重新存儲(表3),并且使NCLI; A CLI用Apror-Otid算法去發(fā)現(xiàn)L,及其以上的頻繁集。Insert into(6)子空間最大維數(shù)Table(L,L)將生成的L和L,用表3的方式重新進(jìn)行存儲。Apriori-Otid(L)(k>2)對于K大于2的情況使用這個算法圖2隨著實(shí)例數(shù)，維數(shù)、子空間最大維數(shù)變化時間的消耗來發(fā)現(xiàn)頻繁項(xiàng)目集. .3結(jié)束語2實(shí)驗(yàn)分析本文結(jié)合自適應(yīng)的網(wǎng)格劃分和Apriori-tid算法的優(yōu)化對實(shí)驗(yàn)表明，采用自適應(yīng)的網(wǎng)格單元劃分,可以使得到的網(wǎng)于CLI中國煤化工w.CLIQUE算法。使格邊界更加準(zhǔn)確，劃分更加合理。在發(fā)現(xiàn)頻繁項(xiàng)目集的時候用自適子單元劃分的精度,使采用的是優(yōu)化的Apriori-tid算法，有助于控制算法的時間復(fù)雜算法得CNMH C中對于發(fā)現(xiàn)子空間族度，提高算法的運(yùn)算效率。以下從3個方面對算法New-CL-的迭代過程進(jìn)行了優(yōu)化,使算法的運(yùn)行效率提高了不少。QUE和CLIQUE進(jìn)行比較。New-CLIQUE算法的不足之處在于聚類的結(jié)果還依賴于3804 2009,30 (16)計算機(jī)工程與設(shè)計Computer Engineering and Design密度閾值,從輸入的參數(shù)上看沒有什么改進(jìn)"。對于閾值的依賴4] Rakesh Agrawal. IBM almaden research center [C]. Automatic性是基于密度聚類算法的。對于網(wǎng)格邊界的處理改進(jìn)還不夠。Subspace Clustering ofHigh Dimensional Data for Data Mining雖然算法對于網(wǎng)格劃分進(jìn)行了優(yōu)化,但是優(yōu)化后的算法也可能Applcations,1998.丟棄一些科密區(qū)域,希望下一步進(jìn)-步提高網(wǎng)格劃分的精度。[5] HSU C2M,CHEN M2S.Subspace clustering ofhigh dimensionalspatial data with noises[C].PAKDD 2004(Lecture Notes in Com-參考文獻(xiàn):puter Science),2004:31-40.[1] Tan Pang-Ning, Michael Steinbach,Vipin Kumar數(shù)據(jù)挖掘?qū)д揫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.數(shù)據(jù)挖掘概念與技術(shù)[M].范明,ledge and Data Eninering.2006(18)-289-303.孟小峰譯.北京:機(jī)械工業(yè)出版社2007:252.285.[7] 陳慧萍,王煜,王建東子空間聚類算法的研究新進(jìn)展[).計算機(jī)[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] 彭儀普,熊擁軍.關(guān)聯(lián)規(guī)則挖拋Apriori Tid算法優(yōu)化研究[J].ledge Discovy20011):5-33.計算機(jī)工程206325)55-57.(上接第3736頁)8x8色度塊l DCT_NT-_ QDCT - +HDCT. JNT- tQHDCT圖2整數(shù)變換與量化設(shè)計在HDCT INT模塊中，計算a"、b".c".d"時要涉及到如何使16個數(shù)據(jù)能夠在較短時間內(nèi)相加的問題，只有解決這個問題，我們的算法優(yōu)化才算真正成功。由于在第2節(jié)中我們已圍3頂層模塊仿真經(jīng)提到一個時鐘內(nèi)可以完成4個數(shù)的加減和移位運(yùn)算，因此行運(yùn)行,縮短了哈達(dá)瑪變換所需要的時間，并成功設(shè)計實(shí)現(xiàn)了在設(shè)計的時候，我們把16個數(shù)據(jù)平均分成4組,在一個時鐘周基于FPGA的整數(shù)變化及量化模塊，達(dá)到了在少量增加硬件期內(nèi)計算出4個組中每組所有元素的和，即得到4個中間結(jié)資源耗費(fèi)的基礎(chǔ)上大大減少時間消耗的設(shè)計效果。本文的設(shè)果，然后再用一個時鐘時間計算出a",b"、c"、d"的計算方法相計經(jīng)過仿真驗(yàn)證,具有一定的應(yīng)用價值和現(xiàn)實(shí)意義。同。這樣總共耗時3個時鐘即完成哈達(dá)瑪變換。由于在算法優(yōu)化的時候，我們只是把中間結(jié)果變量進(jìn)行代入，因此實(shí)際設(shè)計時候?qū)嶋H使用的加法器只增加了少許，也就是說我們的設(shè)計是在少量增加硬件資源消耗的基礎(chǔ)上大大減少了時間消耗，1] 畢厚杰新一代視頻壓縮編碼標(biāo)準(zhǔn)- -H.264/AVC[M].北京人民具體的資源消耗我們將在下一節(jié)仿真驗(yàn)證中進(jìn)行詳細(xì)說明。2] 余兆明圖像編碼標(biāo)準(zhǔn)H.264技術(shù)[M].北京:人民郵電出版社,郵電出版社.2005.4仿真驗(yàn)證2006.在qurusH中，采用Alern公司的Stratix I1系列的[3] Joimt Video Team of ISOTEC MPEG and mu.T VCEG,DratEP3SL340F1760C4L FPGA芯片對頂層模塊DCT_ Q TOP進(jìn)行ITU-T recommendation and final draft intermational standard of仿真，時鐘頻率為50MHZ.仿真結(jié)果表明，優(yōu)化后整個整數(shù)joint video secificationo ITU-T Rec.H.264ISO/TEC 14496-10DCT變換及量化算法消耗了6122個LE,而在同樣的PFGA平AVC[S]JVT-G050,2003.臺和時鐘頻率下，優(yōu)化前整個算法消耗了5820個LE,所消耗4] 周斌,嚴(yán)德聰.H.64AVC先進(jìn)視頻編碼研究[J計算機(jī)工程與的硬件資源只上升了5%。優(yōu)化后算法的仿真結(jié)果如圖3所設(shè)計2004,25(9):1523-1525.示，其中ou00.-out07是DCT變換的量化結(jié)果，out00 _quv、[5] 何云壯.H.264輅數(shù)DCT變換的FPGA實(shí)現(xiàn)[].微計算機(jī)信息,out01_ quv 是哈達(dá)瑪變換的量化結(jié)果。從圖3中也可以看出,2007,23(6-2):205-206.除去量化模塊消耗的2個時鐘，哈達(dá)瑪變換只消耗了3個時倪偉.H.264變換編碼和量化算法的研究[D].計算機(jī)工程與應(yīng)鐘,驗(yàn)證了我們在文中作出的結(jié)論。用2004,40(3):33-36.7]:11. Low complexity trans-5結(jié)束語中國煤化工IEEE Trans CrutSys本文充分利用了H.264運(yùn)算的整潔性和FPGA的強(qiáng)大并YHCNMHG行處理能力，并對輅數(shù)變換部分進(jìn)行了優(yōu)化,采用消除中間變[8]王一皓,陳磊. H.264中的DCTHadamard變換多時鐘方式的量的方法把原來串行運(yùn)行的DCT變換和哈達(dá)瑪變換變成了井FPGA實(shí)現(xiàn)[)]中國有線電視2007(8):754-757.