基于網(wǎng)格和密度的優(yōu)化聚類(lèi)算法研究及其在電信數(shù)據(jù)分析中的應(yīng)用.pdf

1、數(shù)據(jù)挖掘是指從海量數(shù)據(jù)中提取有效的、新穎的、潛在有用的和最終可被理解的知識(shí)或信息模式的非平凡過(guò)程，是20世紀(jì)90年代初針對(duì)“數(shù)據(jù)豐富、知識(shí)貧乏”問(wèn)題應(yīng)運(yùn)而生的一種新技術(shù)。為了有效地從海量數(shù)據(jù)中提取信息，數(shù)據(jù)挖掘算法必須具有良好的可伸縮性，也就是說(shuō)，數(shù)據(jù)挖掘算法的運(yùn)行時(shí)間必須是可預(yù)計(jì)的、可接受的。 聚類(lèi)分析是數(shù)據(jù)挖掘的最主要功能之一，現(xiàn)有的典型聚類(lèi)算法大致可以分為以下幾種：劃分的聚類(lèi)方法、層次的聚類(lèi)方法、基于模型的聚類(lèi)方法、基于網(wǎng)

2、格的聚類(lèi)方法和基于密度的聚類(lèi)方法等。在眾多方法中，基于網(wǎng)格和密度的方法因聚類(lèi)速度快，能處理噪聲及發(fā)現(xiàn)任意形狀的空間聚簇而受到了比較廣泛的關(guān)注。然而，這些方法仍然存在著某些不足，對(duì)基于網(wǎng)格的方法而言：第一，由于空間劃分時(shí)產(chǎn)生的單元數(shù)與維數(shù)呈指數(shù)增長(zhǎng)，該方法多適用于維數(shù)相對(duì)較低的數(shù)據(jù)。第二，在一些基于空間劃分的數(shù)據(jù)挖掘方法中，如基于單元的聚類(lèi)算法，如果劃分粒度越細(xì)，則聚類(lèi)精度越高，但同時(shí)粒度越細(xì)生成的單元數(shù)也越多，造成算法效率下降。如果劃分

3、的粒度變粗，則算法精度難以保證；對(duì)基于密度的方法而言：第一，密度閾值τ的選擇對(duì)聚類(lèi)結(jié)果的影響非常大。如果τ值太高，則簇可能丟失。如果τ值太低，則本應(yīng)分開(kāi)的兩個(gè)簇可能被合并。第二，如果存在不同密度的簇，那么很難找到一個(gè)適用于數(shù)據(jù)空間所有部分的單個(gè)τ值。 針對(duì)目前基于網(wǎng)格和密度聚類(lèi)方法存在的問(wèn)題，本文先后提出了三種新的改進(jìn)算法，并通過(guò)廣泛的實(shí)驗(yàn)，驗(yàn)證了提出的聚類(lèi)算法的高效性，證實(shí)它們對(duì)具有不同分布特性的數(shù)據(jù)集都有非常好的適應(yīng)性，能夠

4、輸出理想的聚類(lèi)結(jié)果。本文的主要工作和貢獻(xiàn)點(diǎn)總結(jié)如下： (1)提出了空間密度單元的概念，并在此基礎(chǔ)上提出了SUDBC算法。首先將被聚類(lèi)的數(shù)據(jù)劃分成若干個(gè)空間單元，然后基于空間單元密度將密度超過(guò)給定閾值的鄰居單元合并為一個(gè)類(lèi)。在存儲(chǔ)空間單元時(shí)，通過(guò)建立哈希表提高查找速度。算法具有如下優(yōu)點(diǎn)：不用計(jì)算兩點(diǎn)間的距離；只需對(duì)數(shù)據(jù)進(jìn)行一遍掃描，具有近似線(xiàn)性的時(shí)間復(fù)雜性；主要基于空間單元密度信息進(jìn)行聚類(lèi)，而空間單元密度信息比實(shí)際數(shù)據(jù)小得多，可以

5、直接存儲(chǔ)在內(nèi)存中，因此適合聚類(lèi)大規(guī)模數(shù)據(jù)集。 (2)提出了基于引力概念的聚類(lèi)結(jié)果評(píng)估方法，并在此基礎(chǔ)上提出了SECDU算法。通過(guò)遍歷兩個(gè)取值范圍有限的整形參數(shù)，對(duì)數(shù)據(jù)集進(jìn)行多遍聚類(lèi)，然后利用提出的基于引力概念的評(píng)估函數(shù)對(duì)全部聚類(lèi)結(jié)果進(jìn)行評(píng)估，找到聚類(lèi)質(zhì)量最高的一個(gè)作為聚類(lèi)算法的最終輸出。這種利用引力概念對(duì)聚類(lèi)結(jié)果進(jìn)行質(zhì)量評(píng)估的方法在國(guó)內(nèi)外尚屬首創(chuàng)。它將數(shù)據(jù)點(diǎn)看作具有單位質(zhì)量的質(zhì)點(diǎn)，將聚類(lèi)結(jié)果看作質(zhì)點(diǎn)分布的一種格局，認(rèn)為一個(gè)高質(zhì)量

6、的聚類(lèi)結(jié)果，其各個(gè)有效聚類(lèi)內(nèi)部的“凝聚力”應(yīng)該盡可能的大，而噪音點(diǎn)受到的“吸引力”應(yīng)該盡可能的小。 (3)提出了SECDU算法的改進(jìn)算法SECDUF。通過(guò)爬山算法對(duì)SECDU進(jìn)行優(yōu)化，在保持聚類(lèi)結(jié)果具有較高質(zhì)量的同時(shí)，大大地加快了聚類(lèi)速度。與SECDU相比，SECDUF的另一個(gè)優(yōu)點(diǎn)是可以產(chǎn)生多個(gè)高質(zhì)量聚類(lèi)結(jié)果，這是因?yàn)榕郎剿惴梢哉业蕉鄠€(gè)局部最優(yōu)值。這個(gè)特點(diǎn)在聚類(lèi)具有層次分布特性的數(shù)據(jù)集(如DS2)時(shí)，表現(xiàn)為能夠找出不同密度的多

7、個(gè)聚類(lèi)結(jié)果。另外，SECDUF算法還具有聚類(lèi)參數(shù)自行調(diào)整，無(wú)需人工干預(yù)等優(yōu)點(diǎn)。 (4)最后，本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)中國(guó)電信數(shù)據(jù)分析系統(tǒng)，主要包括聚類(lèi)分析和OLAP兩大部分。聚類(lèi)分析部分將之前提出的幾種聚類(lèi)算法用于真實(shí)的電信數(shù)據(jù)分析，并針對(duì)存在的某些不足，進(jìn)一步提出了一種改進(jìn)的基于特征點(diǎn)分布的聚類(lèi)算法CFPD，以使聚類(lèi)分析模塊達(dá)到識(shí)別具有相似特征的客戶(hù)群，成為分析客戶(hù)和形成市場(chǎng)策略基礎(chǔ)的目的，真正做到了在恰當(dāng)?shù)臅r(shí)間，通過(guò)恰當(dāng)?shù)那溃?/p>