基于空間劃分的優(yōu)化聚類算法及相關(guān)技術(shù)研究.pdf

1、數(shù)據(jù)挖掘是在海量的數(shù)據(jù)中提取隱含的、未知的、潛在有用的知識(shí)或信息模式的決策支持方法，是20世紀(jì)90年代初針對(duì)“數(shù)據(jù)豐富、知識(shí)貧乏”問題應(yīng)運(yùn)而生的一種新技術(shù)。為了有效地從海量數(shù)據(jù)中提取信息，數(shù)據(jù)挖掘算法必須具有良好的可伸縮性，也就是說，數(shù)據(jù)挖掘算法的運(yùn)行時(shí)間必須是可預(yù)計(jì)的、可接受的。 在眾多方法中，基于空間劃分的方法是一種有效處理海量數(shù)據(jù)的數(shù)據(jù)挖掘方法，其主要應(yīng)用于聚類分析算法與孤立點(diǎn)檢測(cè)算法。然而，現(xiàn)有的基于空間劃分的方法卻存在

2、如下問題：第一，由于空間劃分時(shí)產(chǎn)生的單元數(shù)與維數(shù)呈指數(shù)增長，該方法多適用于維數(shù)相對(duì)較低的數(shù)據(jù)。第二，在一些基于空間劃分的數(shù)據(jù)挖掘方法中，如基于單元的聚類算法，如果劃分粒度越細(xì)，則聚類精度越高，但同時(shí)粒度越細(xì)生成的單元數(shù)也越多，造成算法效率下降。如果劃分的粒度變粗，則算法精度難以保證。 針對(duì)目前基于空間劃分的方法存在的問題，本文提出了一種新的基于空間劃分的索引結(jié)構(gòu)CD-Tree。為了降低空間復(fù)雜度，在保持單元間關(guān)系的條件下，CD-

3、Tree只保存了非空單元，使得聚類與孤立點(diǎn)檢測(cè)過程易于實(shí)現(xiàn)。文中給出了CD-Tree詳細(xì)定義，設(shè)計(jì)了CD-Tree的構(gòu)建、節(jié)點(diǎn)刪除、樹合并等相關(guān)算法，分析了CD-Tree相關(guān)算法的時(shí)間復(fù)雜度，并與其它存儲(chǔ)結(jié)構(gòu)的時(shí)間復(fù)雜度進(jìn)行了對(duì)比。通過理論分析，對(duì)于空間劃分問題，CD-Tree結(jié)構(gòu)要優(yōu)于其它可用于存儲(chǔ)劃分后單元的結(jié)構(gòu)。 CD-Tree適用于當(dāng)空間劃分產(chǎn)生較多的空單元情況，而空單元的數(shù)量與數(shù)據(jù)的偏斜程度有關(guān)，數(shù)據(jù)偏斜程度越高，則生

4、成的空單元數(shù)越多。為了確定CD-Tree的適用條件，需要一個(gè)度量來衡量空間劃分下的數(shù)據(jù)偏斜程度。現(xiàn)有的衡量數(shù)據(jù)偏斜的度量不能用于衡量空間劃分下的數(shù)據(jù)偏斜程度，本文提出了一種新的偏斜度的度量DSF(DataSkewFactor)。DSF相當(dāng)于劃分后空單元所占的比例，可用來估計(jì)生成非空單元數(shù)目。另外，DSF還可用于優(yōu)化CD-Tree結(jié)構(gòu)及在數(shù)據(jù)流聚類中動(dòng)態(tài)調(diào)整劃分的粒度。 在CD-Tree及DSF基礎(chǔ)上，本文研究了基于空間劃分的優(yōu)化

5、聚類算法及相關(guān)技術(shù)，具體包括：基于空間劃分的聚類算法；基于空間劃分的數(shù)據(jù)流聚類算法；基于空間劃分的孤立點(diǎn)檢測(cè)算法。 在基于空間劃分的聚類算法方面，分析現(xiàn)有的基于空間劃分的聚類方法的特點(diǎn)及適用范圍，提出了基于CD-Tree的聚類分析算法CDT，設(shè)計(jì)了兩種剪枝優(yōu)化策略以提高CDT算法的效率：基于分支結(jié)點(diǎn)數(shù)據(jù)點(diǎn)總數(shù)的剪枝策略和基于分支結(jié)點(diǎn)數(shù)據(jù)對(duì)象個(gè)數(shù)最大值剪枝策略。通過分析這兩種優(yōu)化方法的適用條件，本文認(rèn)為當(dāng)數(shù)據(jù)維數(shù)相對(duì)較高時(shí)，這兩種

6、優(yōu)化算法有優(yōu)勢(shì)。通過在真實(shí)與人工數(shù)據(jù)集上的測(cè)試，也驗(yàn)證了CDT算法優(yōu)于其它同類方法。 在基于空間劃分的數(shù)據(jù)流聚類算法方面，本文著重研究了流挖掘中的流聚類方法和類演化問題。目前數(shù)據(jù)流聚類方法多著重于在傳統(tǒng)聚類算法基礎(chǔ)上，解決在流數(shù)據(jù)上算法的效率問題，而本文進(jìn)一步研究了如何挖掘任意形狀簇，設(shè)計(jì)了一種基于空間劃分的數(shù)據(jù)流聚類算法。算法擴(kuò)展CD-Tree索引為CDS-Tree，為每個(gè)單元維護(hù)了一個(gè)鏈表，以實(shí)現(xiàn)數(shù)據(jù)流滑動(dòng)窗口的維護(hù)，并采用

7、了一種基于“跳”滑動(dòng)窗口的更新方法。同時(shí)，為了能夠適應(yīng)流數(shù)據(jù)分布的變化，算法采用一種動(dòng)態(tài)調(diào)整劃分粒度策略，從而在固定的內(nèi)存使用下，以獲得盡可能高的聚類精度。該策略是基于本文提出的數(shù)據(jù)偏斜度DSF概念來實(shí)現(xiàn)的。對(duì)于數(shù)據(jù)流上的類演化分析，本文提出采用傾斜的時(shí)間窗來記錄歷史統(tǒng)計(jì)信息，利用單元間的集合運(yùn)算來實(shí)現(xiàn)演化分析。 針對(duì)數(shù)據(jù)流的特點(diǎn)及數(shù)據(jù)流分析的要求，本文對(duì)所提出的算法進(jìn)行了大量測(cè)試，測(cè)試內(nèi)容包括算法的可伸縮性、聚類精度、算法的內(nèi)

8、存使用情況以及粒度調(diào)整和演化分析的情況。實(shí)驗(yàn)結(jié)果表明，基于CDS-Tree的數(shù)據(jù)流聚類算法對(duì)數(shù)據(jù)窗口的大小及數(shù)據(jù)維數(shù)有較好的可伸縮性，優(yōu)于其它基于空間劃分的方法，同時(shí)，在一定的內(nèi)存限制下，可以實(shí)現(xiàn)聚類精度的最大化。 孤立點(diǎn)檢測(cè)是數(shù)據(jù)挖掘的一個(gè)重要方面，用于發(fā)現(xiàn)與大多數(shù)對(duì)象不同的對(duì)象。孤立點(diǎn)檢測(cè)廣泛用于電信和信用卡詐騙檢測(cè)、網(wǎng)絡(luò)入侵檢測(cè)等方面。在基于空間劃分的孤立點(diǎn)檢測(cè)算法方面，本文分析了基于空間劃分的孤立點(diǎn)檢測(cè)算法存在的問題，設(shè)

9、計(jì)了基于CD-Tree的孤立點(diǎn)檢測(cè)算法。對(duì)基于CD-Tree的孤立點(diǎn)檢測(cè)算法利用真實(shí)數(shù)據(jù)集與人工數(shù)據(jù)集進(jìn)行了測(cè)試。實(shí)驗(yàn)表明，基于CD-Tree的孤立點(diǎn)檢測(cè)算法較基于單元的算法在效率及有效處理的維數(shù)方面均有顯著提高。 總之，基于空間劃分的聚類算法是一類重要的數(shù)據(jù)挖掘方法，本文基于CD-Tree結(jié)構(gòu)及數(shù)據(jù)偏斜度DSF較大程度地提高了傳統(tǒng)的基于空間劃分的聚類與孤立點(diǎn)檢測(cè)算法的效率，這些新算法將有效應(yīng)用到聚類分析與孤立點(diǎn)檢測(cè)的應(yīng)用中。