基于聚類方法的計算機(jī)網(wǎng)格技術(shù)探析

【摘要】網(wǎng)格技術(shù)和應(yīng)用將成為具有高性能處理、海量數(shù)據(jù)存儲和大量儀器設(shè)備終端等特征的信息處理基礎(chǔ)設(shè)施。通過它可以匯聚Internet中分散異構(gòu)、動態(tài)變化的計算和信息資源，將其中不同組織和機(jī)構(gòu)的資源數(shù)據(jù)空間化。網(wǎng)格技術(shù)的數(shù)據(jù)分析方法將多維空間數(shù)據(jù)劃分為由（超）矩形網(wǎng)格單元組成的網(wǎng)格，然后在網(wǎng)格單元上進(jìn)行聚類，以提取挖掘隱含的、未知但有應(yīng)用價值的信息。本文以聚類算法為代表，對現(xiàn)有基于網(wǎng)格技術(shù)的進(jìn)行了概述探析。

【關(guān)鍵詞】數(shù)據(jù)挖掘；網(wǎng)格；聚類

0.引言

隨著現(xiàn)代商業(yè)計算越來越復(fù)雜，技術(shù)上迫切需要低廉而數(shù)據(jù)處理能力超強(qiáng)的計算模式以進(jìn)行從大型數(shù)據(jù)庫或數(shù)據(jù)倉庫中提取隱含的、未知的有應(yīng)用價值的信息或模式，隨之?dāng)?shù)據(jù)挖掘的概念應(yīng)運(yùn)而生。數(shù)據(jù)挖掘是數(shù)據(jù)庫研究中的一個很有應(yīng)用價值的領(lǐng)域，融合了數(shù)據(jù)庫、機(jī)器學(xué)習(xí)、統(tǒng)計學(xué)等多個領(lǐng)域的理論和技術(shù)。

數(shù)據(jù)挖掘中，聚類分析方法是廣為研究的課題之一，是從數(shù)據(jù)中尋找數(shù)據(jù)間的相似性，并依此對數(shù)據(jù)進(jìn)行分類，從而發(fā)現(xiàn)數(shù)據(jù)中隱含的有用信息或知識。

網(wǎng)格方法是空間數(shù)據(jù)處理中常用的將空間數(shù)據(jù)離散化的方法?；诰W(wǎng)格，聚類算法由于易于增量實現(xiàn)和進(jìn)行高維數(shù)據(jù)處理而被廣泛應(yīng)用于網(wǎng)格技術(shù)中。本文對聚類算法、網(wǎng)格方法進(jìn)行了概述分析。

1.網(wǎng)格的定義與劃分

網(wǎng)格的基本概念，設(shè)N1， N2，…，Nr是數(shù)據(jù)集D={D1，D2，…，Dn}中數(shù)據(jù)對象的r 個屬性的有界定義域，那W=N1×N2×…×Nr 就是一個r 維空間， 將N1，N2，…，Nr看成是W的維（ 屬性、字段），則對于一個包含n 個數(shù)據(jù)點的r 維空間中的數(shù)據(jù)集D={D1，D2，…，Dn}，其中Di={Di1，Di2，…，Dir}（i=1， 2，…，n），Di 的第j 個分量Dij∈Nj。將W的每一維M等分，即把W分割成個網(wǎng)格單元。

聚類算法第一步是劃分網(wǎng)格結(jié)構(gòu)，按搜索子空間的策略不同， 主要有兩種算法，一是由底向上網(wǎng)格劃分方法的算法，另外一個是自頂向下網(wǎng)格劃分方法的算法。

1.1由底向上的劃分方法

由底向上的網(wǎng)格劃分方法按照用戶輸入的劃分參數(shù)（即每維段數(shù)ki，1≤i≤d），將數(shù)據(jù)空間均勻劃分為相等大小的網(wǎng)格單元，假設(shè)落入同一網(wǎng)格單元內(nèi)的所有數(shù)據(jù)點都屬于同一個簇，每個網(wǎng)格單元保存落入其內(nèi)數(shù)據(jù)的統(tǒng)計信息，比如數(shù)據(jù)點個數(shù)，數(shù)據(jù)點之和。包含數(shù)據(jù)點數(shù)據(jù)較多的網(wǎng)格單元被稱為高密度網(wǎng)格單元。

采用由底向上的網(wǎng)格劃分方法的優(yōu)點在于，它能通過對數(shù)據(jù)的一遍掃描，將數(shù)據(jù)壓縮到一個網(wǎng)格數(shù)據(jù)結(jié)構(gòu)內(nèi)，并基于這個網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，發(fā)現(xiàn)任意形狀的簇。其缺點，如果網(wǎng)格單元的粒度較小（即體積較?。敲吹玫降木鄞氐木容^高，但是算法的計算復(fù)雜度較大。此外，由底向上的網(wǎng)格方法存在不適合處理高維數(shù)據(jù)的問題。在高維空間，數(shù)據(jù)的分布是非常稀疏的，網(wǎng)格方法失去其壓縮作用，而且屬于同一個簇的高密度網(wǎng)格單元也可能不相連，這使聚類算法不能發(fā)現(xiàn)合理數(shù)目的簇。

1.2自頂向下的劃分方法

自頂向下的網(wǎng)格劃分方法采取分治的策略，對數(shù)據(jù)空間進(jìn)行遞歸劃分，使問題的規(guī)模不斷減小。首先將原數(shù)據(jù)空間劃分為幾個較大的區(qū)域。對于每個得到的區(qū)域，劃分過程反復(fù)執(zhí)行，直到每個區(qū)域包含屬于同一個簇的數(shù)據(jù)點，那么這些區(qū)域就是最終的網(wǎng)格單元。該算法直接將高密度網(wǎng)格單元識別為一個簇，或是將相連的高密度網(wǎng)格單元識別為簇。

自頂向下劃分方法的主要優(yōu)點在于不需要用戶指定劃分參數(shù)，而是根據(jù)數(shù)據(jù)的分布對空間進(jìn)行劃分，因此這種劃分更為合理。數(shù)據(jù)空間維度對自頂向下網(wǎng)格方法的影響較小，可以快速將大型高維數(shù)據(jù)集中的簇分隔開。這一類方法的計算復(fù)雜度與數(shù)據(jù)集大小和維度都呈線性關(guān)系適合于處理高維數(shù)據(jù)。其缺點，由于劃分是基于數(shù)據(jù)分布的，而通常認(rèn)為噪音是在整個空間均勻分布的，所以自頂向下劃分方法對噪音不敏感。但是，由于這種方法得到的網(wǎng)格單元的體積遠(yuǎn)大于由底向上網(wǎng)格方法中的網(wǎng)格單元體積，因此該方法產(chǎn)生的簇的描述精度比由底向上的網(wǎng)格方法得到的簇的描述精度要低。而且在自頂向下的劃分過程中，同一個簇可能被劃分到不同的區(qū)域中，最終得到的同一區(qū)域也可能包含不同的簇，這樣就進(jìn)一步降低了算法的正確度。這類劃分方法的另一個缺點是它在劃分過程中，需要對數(shù)據(jù)集進(jìn)行多次掃描。

而由底向上劃分方法在于只需對數(shù)據(jù)集進(jìn)行一次線性掃描以及較高的簇的描述精度。因此，兩類方法適用于不同的問題。前者適于處理高維數(shù)據(jù)集，后者能有效處理存取代價較大的超大型數(shù)據(jù)集與動態(tài)數(shù)據(jù)。

2.網(wǎng)格聚類過程

聚類算法的基本過程是，首先將數(shù)據(jù)空間W劃分為網(wǎng)格單元，將對象指派到合適的單元，并計算每個單元的密度。以用戶輸入的密度闕值，刪除低于密度闕值的稀疏網(wǎng)格單元，把鄰近的高于密度闕值的稠密網(wǎng)格單元集中起來形成簇。

相對于稠密網(wǎng)格單元來說，大多數(shù)的網(wǎng)格單元包含非常少甚至空的的數(shù)據(jù)，這一類網(wǎng)格單元被稱為稀疏網(wǎng)格單元。大量的稀疏網(wǎng)格單元的存在會極大的降低聚類的速度，需要在聚類之前對稀疏網(wǎng)格單元進(jìn)行處理。

由稠密網(wǎng)格單元形成簇：

在該聚類算法中，根據(jù)以上分析，由鄰接的稠密單元形成簇是相對直截了當(dāng)?shù)模@也是以網(wǎng)格方法為基礎(chǔ)的優(yōu)點之一。但是需要首先定義鄰接單元的含義。設(shè)n維空問中的存在任意兩個網(wǎng)格單元U1和U2，當(dāng)這兩個網(wǎng)格單元在—個維上有交集或是具有一個公共面時，稱它們?yōu)猷徑泳W(wǎng)格單元。

在二維空間中，比較常使用的是4-connection相鄰定義（如圖1-a）和8-connection相鄰定義（如圖1-b），4-connection更適合在聚類算法中使用。因為當(dāng)尋找某個網(wǎng)格單元的鄰居時，在4-connection定義下，一個網(wǎng)格單元只有2d個鄰居，而在8-connection定義下，有3d-1個鄰居，當(dāng)數(shù)據(jù)維度d較大時，這個數(shù)目非常大。使用4-connection不僅參與計算的單元數(shù)目大為減少，而且單元增加與維數(shù)的關(guān)系由指數(shù)增長變?yōu)榫€性增長，具有較低的計算復(fù)雜度和較高的計算效率。

3.結(jié)論及展望

基于聚類方法的網(wǎng)格技術(shù)優(yōu)點是它的處理速度快，由于該技術(shù)的速度與數(shù)據(jù)對象個數(shù)無直接相關(guān)，而是只依賴于數(shù)據(jù)空間中每個維上單元的個數(shù)，發(fā)現(xiàn)任意形狀、任意大小的簇、計算結(jié)果與數(shù)據(jù)輸入順序無關(guān)、計算時間與數(shù)據(jù)量無關(guān)，同時不要求像k均值一樣預(yù)先指定簇個數(shù)等。，基于聚類算法的網(wǎng)格技術(shù)也有其缺點，其輸入?yún)?shù)對聚類結(jié)果影響比較大，且這些參數(shù)設(shè)置繁瑣困難。當(dāng)數(shù)據(jù)中有噪音時，需要加入特殊的處理，算法，才能保證聚類質(zhì)量，而且，加入的算法對于數(shù)據(jù)維度的可伸縮性有較大影響。

本文對基于聚類方法的網(wǎng)格技術(shù)進(jìn)行了分析和總結(jié)，包括網(wǎng)格的定義與劃分方法、網(wǎng)格單元密度的確定、由鄰接網(wǎng)格單元形成聚簇的聚類過程；最后對網(wǎng)格聚類方法優(yōu)缺點進(jìn)行了總結(jié)。 [科]

【參考文獻(xiàn)】

［１］曹洪其，余嵐，孫志揮.基于網(wǎng)格聚類技術(shù)的離群點挖掘算法[J].計算機(jī)工程，2006（6）.

［２］孫玉芬.基于網(wǎng)格方法的聚類算法研究[J].華中科技大學(xué)，2006.