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

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

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

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

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

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

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

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