基于聚類方法的計算機網格技術探析

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

【關鍵詞】數據挖掘；網格；聚類

0.引言

隨著現代商業計算越來越復雜，技術上迫切需要低廉而數據處理能力超強的計算模式以進行從大型數據庫或數據倉庫中提取隱含的、未知的有應用價值的信息或模式，隨之數據挖掘的概念應運而生。數據挖掘是數據庫研究中的一個很有應用價值的領域，融合了數據庫、機器學習、統計學等多個領域的理論和技術。

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

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

1.網格的定義與劃分

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

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

1.1由底向上的劃分方法

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

采用由底向上的網格劃分方法的優點在于，它能通過對數據的一遍掃描，將數據壓縮到一個網格數據結構內，并基于這個網格數據結構，發現任意形狀的簇。其缺點，如果網格單元的粒度較小（即體積較小），那么得到的聚簇的精度較高，但是算法的計算復雜度較大。此外，由底向上的網格方法存在不適合處理高維數據的問題。在高維空間，數據的分布是非常稀疏的，網格方法失去其壓縮作用，而且屬于同一個簇的高密度網格單元也可能不相連，這使聚類算法不能發現合理數目的簇。

1.2自頂向下的劃分方法

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

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

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

2.網格聚類過程

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

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

由稠密網格單元形成簇：

在該聚類算法中，根據以上分析，由鄰接的稠密單元形成簇是相對直截了當的，這也是以網格方法為基礎的優點之一。但是需要首先定義鄰接單元的含義。設n維空問中的存在任意兩個網格單元U1和U2，當這兩個網格單元在—個維上有交集或是具有一個公共面時，稱它們為鄰接網格單元。

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

3.結論及展望

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

本文對基于聚類方法的網格技術進行了分析和總結，包括網格的定義與劃分方法、網格單元密度的確定、由鄰接網格單元形成聚簇的聚類過程；最后對網格聚類方法優缺點進行了總結。 [科]

【參考文獻】

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

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