數據聚類

所謂數據聚類是指根據數據的內在性質將數據分成一些聚合類，每一聚合類中的元素儘可能具有相同的特性，不同聚合類之間的特性差別儘可能大。

聚類分析的目的是分析數據是否屬於各個獨立的分組，使一組中的成員彼此相似，而與其他組中的成員不同。它對一個數據對象的集合進行分析，但與分類分析不同的是，所劃分的類是未知的，因此，聚類分析也稱為無指導或無監督的(Unsupervised)學習。聚類分析的一般方法是將數據對象分組為多個類或簇(Cluster)，在同一簇中的對象之間具有較高的相似度，而不同簇中的對象差異較大。由於聚類分析的上述特徵，在許多套用中，對數據集進行了聚類分析後，可將一個簇中的各數據對象作為一個整體對待。

數據聚類 (Cluster analysis) 是對於靜態數據分析的一門技術，在許多領域受到廣泛套用，包括機器學習，數據挖掘，模式識別，圖像分析以及生物信息。

基本介紹

• 中文名：數據聚類
• 外文名：Cluster analysis
• 作用：靜態數據分析

發展情況

隨著信息技術的高速發展 , 資料庫套用的規模、範圍和深度的不斷擴大, 導致積累了大量的數據, 而這些激增的數據後面隱藏著許多重要的信息 ,因此人們希望能夠對其進行更高層次的分析, 以便更好地利用這些數據 。目前的資料庫系統可以高效 、方便地實現數據的錄入、查詢、統計等功能 ,但是無法發現數據中存在的各種關係和規則, 更無法根據現有的數據預測未來的發展趨勢。而數據聚類分析正是解決這一問題的有效途徑, 它是數據挖掘的重要組成部分, 用於發現在資料庫中未知的對象類 ,為數據挖掘提供有力的支持,它是近年來廣為研究的問題之一。聚類分析是一個極富有挑戰性的研究領域, 採用基於聚類分析方法的數據挖掘在實踐中已取得了較好的效果。聚類分析也可以作為其他一些算法的預處理步驟 ,聚類可以作為一個獨立的工具來獲知數據的分布情況,使數據形成簇, 其他算法再在生成的簇上進行處理,聚類算法既可作為特徵和分類算法的預處理步驟 ,也可將聚類結果用於進一步關聯分析 。迄今為止 ,人們提出了許多聚類算法,所有這些算法都試圖解決大規模數據的聚類問題 。聚類分析還成功地套用在了模式識別 、圖像處理、計算機視覺、模糊控制等領域 ,並在這些領域中取得了長足的發展。

基本原理

所謂聚類, 就是將一個數據單位的集合分割成幾個稱為簇或類別的子集 , 每個類中的數據都有相似性,它的劃分依據就是“物以類聚”。數據聚類分析是根據事物本身的特性, 研究對被聚類的對象進行類別劃分的方法 。聚類分析依據的原則是使同一聚簇中的對象具有儘可能大的相似性, 而不同聚簇中的對象具有儘可能大的相異性, 聚類分析主要解決的問題就是如何在沒有先驗知識的前提下, 實現滿足這種要求的聚簇的聚合。聚類分析稱為無監督學習 (Unsuper-vised Study),主要體現在聚類學習的數據對象沒有類別標記,需要由聚類學習算法自動計算 。

聚類類型

經過持續了半個多世紀的深入研究聚類算法，聚類技術也已經成為最常用的數據分析技術之一。其各種算法的提出、發展、演化，也使得聚類算法家族“家大口闊，人丁興旺”。下面就針對目前數據分析和數據挖掘業界主流的認知對聚類算法進行介紹。

劃分方法

給定具有n個對象的數據集，採用劃分方法對數據集進行k個劃分，每個劃分(每個組)代表一個簇．k≤n，並且每個簇至少包含一個對象，而且每個對象一般來說只能屬於一個組。對於給定的k值，劃分方法一般要做一個初始劃分，然後採取疊代重新定位技術，通過讓對象在不同組間移動來改進劃分的準確度和精度。一個好的劃分原則是：同一個簇中對象之間的相似性很高(或距離很近)，而不同簇的對象之間相異度很高(或距離很遠)。

(1)K-Means算法：又叫K均值算法，這是目前最著名、使用最廣泛的聚類算法。在給定一個數據集和需要劃分的數目k後，該算法可以根據某個距離函式反覆把數據劃分到k個簇中，直到收斂為止。K-Means算法用簇中對象的平均值來表示劃分的每個簇，其大致的步驟是，首先從隨機抽取的k個數據點作為初始的聚類中心(種子中心)，然後計算每個數據點到每個種子中心的距離，並把每個數據點分配到距離它最近的種子中心；一旦所有的數據點都被分配完成，每個聚類的聚類中心(種子中心)按照本聚類(本簇)的現有數據點重新計算；這個過程不斷重複，直到收斂，即滿足某個終止條件為止，最常見的終止條件是誤差平方和SSE(指令集的簡稱)局部最小。

(2)K-Medoids算法：又叫K中心點算法，該算法用最接近簇中心的一個對象來表示劃分的每個簇。K-Medoids算法與K-Means算法的劃分過程相似，兩者最大的區別是K-Medoids算法是用簇中最靠近中心點的一個真實的數據對象來代表該簇的，而K-Medoids算法是用計算出來的簇中對象的平均值來代表該簇的，這個平均值是虛擬的，並沒有一個真實的數據對象具有這些平均值。

層次方法

在給定n個對象的數據集後，可用層次方法(Hierarchical Methods)對數據集進行層次分解，直到滿足某種收斂條件為止。按照層次分解的形式不同，層次方法又可以分為凝聚層次聚類和分裂層次聚類。

(1)凝聚層次聚類：又叫自底向上方法，一開始將每個對象作為單獨的一類，然後相繼合併與其相近的對象或類，直到所有小的類別合併成一個類，即層次的最上面，或者達到一個收斂，即終止條件為止。

(2)分裂層次聚類：又叫自頂向下方法，一開始將所有對象置於一個簇中，在疊代的每一步中，類會被分裂成更小的類，直到最終每個對象在一個單獨的類中，或者滿足一個收斂，即終止條件為止。

層次方法最大的缺陷在於，合併或者分裂點的選擇比較困難，對於局部來說，好的合併或者分裂點的選擇往往並不能保證會得到高質量的全局的聚類結果，而且一旦一個步驟（合併或分裂）完成，它就不能被撤銷了。

基於密度的方法

傳統的聚類算法都是基於對象之間的距離，即距離作為相似性的描述指標進行聚類劃分，但是這些基於距離的方法只能發現球狀類型的數據，而對於非球狀類型的數據來說，只根據距離來描述和判斷是不夠的。鑒於此，人們提出了一個密度的概念——基於密度的方法(Density—Based Methods)，其原理是：只要鄰近區域內的密度(對象的數量)超過了某個閾值，就繼續聚類。換言之，給定某個簇中的每個數據點(數據對象)，在一定範圍內必須包含一定數量的其他對象。該算法從數據對象的分布密度出發，把密度足夠大的區域連線在一起，因此可以發現任意形狀的類。該算法還可以過濾噪聲數據(異常值)。基於密度的方法的典型算法包括DBSCAN(Density—Based Spatial Clustering of Application with Noise)以及其擴展算法OPTICS(Ordering Points to Identify the Clustering Structure)。其中，DBSCAN算法會根據一個密度閾值來控制簇的增長，將具有足夠高密度的區域劃分為類，並可在帶有噪聲的空間資料庫里發現任意形狀的聚類。儘管此算法優勢明顯，但是其最大的缺點就是，該算法需要用戶確定輸入參數，而且對參數十分敏感。

基於格線的方法

基於格線的方法(Grid—Based Methods)將把對象空間量化為有限數目的單元，而這些單元則形成了格線結構，所有的聚類操作都是在這個格線結構中進行的。該算法的優點是處理速度快，其處理時間常常獨立於數據對象的數目，只跟量化空間中每一維的單元數目有關。基於格線的方法的典型算法是STING(統計信息格線方法，Statistical Information Grid)算法。該算法是一種基於格線的多解析度聚類技術，將空間區域劃分為不同解析度級別的矩形單元，並形成一個層次結構，且高層的低解析度單元會被劃分為多個低一層次的較高解析度單元。這種算法從最底層的格線開始逐漸向上計算格線內數據的統計信息並儲存。格線建立完成後，則用類似DBSCAN的方法對格線進行聚類。

需解決的問題

在聚類分析的研究中, 有許多急待進一步解決的問題 ,如 a. 處理數據為大數據量 、具有複雜數據類型的數據集合時 , 聚類分析結果的精確性問題 ;b. 對高屬性維數據的處理能力;c. 數據對象分布形狀不規則時的處理能力;d. 處理噪聲數據的能力 , 能夠處理數據中包含的孤立點, 未知數據 、空缺或者錯誤的數據;e. 對數據輸入順序的獨立性 ,也就是對於任意的數據輸入順序產生相同的聚類結果 ;. f 減少對先決知識或參數的依賴型等問題 。這些問題的存在使得我們研究高正確率 ,低複雜度 , I /O開銷小, 適合高維數據 ,具有高度的可伸縮性的聚類方法迫在眉睫, 這也是今後聚類方法研究的方向 。

套用

聚類分析可以作為一個獨立的工具來獲得數據的分布情況, 通過觀察每個簇的特點, 集中對特定的某些簇再作進一步分析 ,以獲得需要的信息 。聚類分析套用廣泛 , 除了在數據挖掘 、模式識別、圖像處理、計算機視覺、模糊控制等領域的套用, 它還被套用在氣象分析 、食品檢驗、生物種群劃分、市場區隔、業績評估等諸多方面 。如在商務上 ,聚類分析可以幫助市場分析人員從客戶基本庫當中發現不同的客戶群 ,並且用購買模式來刻畫不同的客戶群的特徵 , 聚類分析還可以套用在欺詐探測中, 聚類中的孤立點就可能預示著欺詐行為的存在 。聚類分析的發展過程也是聚類分析的套用過程, 目前聚類分析在相關領域已經取得了豐碩的成果 。

今後發展

聚類分析是數據挖掘中的一種非常有用的技術,用於從大量的數據中尋找隱含的數據分布模式及關聯規則 ,以便於有效地進行數據挖掘。目前 , 聚類已經套用在了各個相關領域, 並取得了豐碩的成果, 但是目前的聚類分析方法仍然有許多缺陷, 在今後, 聚類分析方法將在伸縮性、容錯性 、處理高屬性維數據這些方面加以改進和提高 ,聚類分析將會越來越受到人們的關注 , 它也會被套用在越來越多的相關領域 ,解決許多其他方法不能解決的難題 ,為科學研究做出貢獻 。