改進(jìn)的CLIQUE優(yōu)化算法

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