2.3　數(shù)據(jù)聚類性

數(shù)據(jù)聚類是指根據(jù)數(shù)據(jù)的內(nèi)在性質(zhì)將數(shù)據(jù)分成一些聚合類，每一聚合類中的元素盡可能具有相同的特性，不同聚合類之間的特性差別盡可能大。

聚類分析的目的是分析數(shù)據(jù)是否屬于各個(gè)獨(dú)立的分組，使一組中的成員彼此相似，而與其他組中的成員不同。它對(duì)一個(gè)數(shù)據(jù)對(duì)象的集合進(jìn)行分析，但與分類分析不同的是，所劃分的類是未知的，因此聚類分析也稱為無(wú)指導(dǎo)或無(wú)監(jiān)督（Unsupervised）學(xué)習(xí)。聚類分析的一般方法是將數(shù)據(jù)對(duì)象分組為多個(gè)類或簇（Cluster），在同一簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差異較大。由于聚類分析的上述特征，在許多應(yīng)用中，對(duì)數(shù)據(jù)集進(jìn)行了聚類分析后可將一個(gè)簇中的各數(shù)據(jù)對(duì)象作為一個(gè)整體對(duì)待。

數(shù)據(jù)聚類（Cluster Analysis）是對(duì)于靜態(tài)數(shù)據(jù)分析的一門(mén)技術(shù)，在許多領(lǐng)域受到廣泛應(yīng)用，包括機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識(shí)別、圖像分析以及生物信息。

1．聚類應(yīng)用

隨著信息技術(shù)的高速發(fā)展，數(shù)據(jù)庫(kù)應(yīng)用的規(guī)模、范圍和深度不斷擴(kuò)大，積累了大量的數(shù)據(jù)，而這些激增的數(shù)據(jù)后面隱藏著許多重要的信息，因此人們希望能夠?qū)ζ溥M(jìn)行更高層次的分析，以便更好地利用這些數(shù)據(jù)。目前的數(shù)據(jù)庫(kù)系統(tǒng)可以高效、方便地實(shí)現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計(jì)等功能，但是無(wú)法發(fā)現(xiàn)數(shù)據(jù)中存在的各種關(guān)系和規(guī)則，更無(wú)法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測(cè)未來(lái)的發(fā)展趨勢(shì)。數(shù)據(jù)聚類分析正是解決這一問(wèn)題的有效途徑，它是數(shù)據(jù)挖掘的重要組成部分，用于發(fā)現(xiàn)在數(shù)據(jù)庫(kù)中未知的對(duì)象類，為數(shù)據(jù)挖掘提供有力的支持，它是近年來(lái)廣為研究的問(wèn)題之一。聚類分析是一個(gè)極富挑戰(zhàn)性的研究領(lǐng)域，采用基于聚類分析方法的數(shù)據(jù)挖掘在實(shí)踐中取得了較好的效果。聚類分析也可以作為其他一些算法的預(yù)處理步驟，聚類可以作為一個(gè)獨(dú)立的工具來(lái)獲知數(shù)據(jù)的分布情況，使數(shù)據(jù)形成簇，其他算法再針對(duì)生成的簇進(jìn)行處理，聚類算法既可作為特征和分類算法的預(yù)處理步驟，也可將聚類結(jié)果用于進(jìn)一步關(guān)聯(lián)分析。迄今為止，人們提出了許多聚類算法，所有這些算法都試圖解決大規(guī)模數(shù)據(jù)的聚類問(wèn)題。聚類分析還成功地應(yīng)用在了模式識(shí)別、圖像處理、計(jì)算機(jī)視覺(jué)、模糊控制等領(lǐng)域，并在這些領(lǐng)域中取得了長(zhǎng)足的發(fā)展。

2．?dāng)?shù)據(jù)聚類

聚類就是將一個(gè)數(shù)據(jù)單位的集合分割成幾個(gè)稱為簇或類別的子集，每個(gè)類中的數(shù)據(jù)都有相似性，它的劃分依據(jù)就是“物以類聚”。數(shù)據(jù)聚類分析是根據(jù)事物本身的特性，研究對(duì)被聚類的對(duì)象進(jìn)行類別劃分的方法。聚類分析依據(jù)的原則是使同一聚簇中的對(duì)象具有盡可能大的相似性，而不同聚簇中的對(duì)象具有盡可能大的相異性，聚類分析主要解決的問(wèn)題就是如何在沒(méi)有先驗(yàn)知識(shí)的前提下，實(shí)現(xiàn)滿足這種要求的聚簇的聚合。聚類分析稱為無(wú)監(jiān)督學(xué)習(xí)（Unsupervised Study），主要體現(xiàn)是聚類學(xué)習(xí)的數(shù)據(jù)對(duì)象沒(méi)有類別標(biāo)注，需要由聚類學(xué)習(xí)算法自動(dòng)計(jì)算。

3．聚類類型

經(jīng)過(guò)持續(xù)了半個(gè)多世紀(jì)的深入研究聚類算法，聚類技術(shù)已經(jīng)成為最常用的數(shù)據(jù)分析技術(shù)之一。各種算法的提出、發(fā)展、演化使聚類算法家族不斷壯大。下面就針對(duì)目前數(shù)據(jù)分析和數(shù)據(jù)挖掘業(yè)界主流的認(rèn)知對(duì)聚類算法進(jìn)行介紹。

（1）劃分方法

給定具有n個(gè)對(duì)象的數(shù)據(jù)集，采用劃分方法對(duì)數(shù)據(jù)集進(jìn)行k個(gè)劃分，每個(gè)劃分（每個(gè)組）代表一個(gè)簇。其中，k≤n，并且每個(gè)簇至少包含一個(gè)對(duì)象，而且每個(gè)對(duì)象一般只能屬于一個(gè)組。對(duì)于給定的k值，一般要做一個(gè)初始劃分，然后采取迭代重新定位技術(shù)，通過(guò)讓對(duì)象在不同組間移動(dòng)來(lái)改進(jìn)劃分的準(zhǔn)確度和精度。一個(gè)好的劃分原則是：同一個(gè)簇中對(duì)象之間的相似性很高（或距離很近），而不同簇的對(duì)象之間相異度很高（或距離很遠(yuǎn)）。

① K-Means算法：又叫K均值算法，是目前最著名、使用最廣泛的聚類算法。在給定一個(gè)數(shù)據(jù)集和需要?jiǎng)澐值臄?shù)目k后，該算法可以根據(jù)某個(gè)距離函數(shù)反復(fù)把數(shù)據(jù)劃分到k個(gè)簇中，直到收斂為止。K-Means算法用簇中對(duì)象的平均值來(lái)表示劃分的每個(gè)簇，其大致的步驟是：首先將隨機(jī)抽取的k個(gè)數(shù)據(jù)點(diǎn)作為初始的聚類中心（種子中心），然后計(jì)算每個(gè)數(shù)據(jù)點(diǎn)到每個(gè)種子中心的距離，并把每個(gè)數(shù)據(jù)點(diǎn)分配到距離它最近的種子中心；一旦所有的數(shù)據(jù)點(diǎn)都被分配完成，每個(gè)聚類的聚類中心（種子中心）就按照本聚類（本簇）的現(xiàn)有數(shù)據(jù)點(diǎn)重新計(jì)算；這個(gè)過(guò)程不斷重復(fù)，直到收斂，即滿足某個(gè)終止條件為止。最常見(jiàn)的終止條件是誤差平方和SSE（指令集的簡(jiǎn)稱）局部最小。

② K-Medoids算法：又叫K中心點(diǎn)算法，用最接近簇中心的一個(gè)對(duì)象來(lái)表示劃分的每個(gè)簇。K-Medoids算法與K-Means算法的劃分過(guò)程相似，兩者最大的區(qū)別是：K-Medoids算法是用簇中最靠近中心點(diǎn)的一個(gè)真實(shí)的數(shù)據(jù)對(duì)象來(lái)代表該簇，而K-Means算法是用計(jì)算出來(lái)的簇中對(duì)象的平均值（這個(gè)平均值是虛擬的，并沒(méi)有一個(gè)真實(shí)的數(shù)據(jù)對(duì)象具有這個(gè)平均值）來(lái)代表該簇。

（2）層次方法

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

①凝聚層次聚類：又叫自底向上方法，一開(kāi)始將每個(gè)對(duì)象作為單獨(dú)的一類，然后相繼合并與其相近的對(duì)象或類，直到所有小的類別合并成一個(gè)類，即層次的最上面，或者達(dá)到一個(gè)收斂，即終止條件為止。

②分裂層次聚類：又叫自頂向下方法，一開(kāi)始將所有對(duì)象置于一個(gè)簇中，在迭代的每一步中類會(huì)被分裂成更小的類，直到最終每個(gè)對(duì)象在一個(gè)單獨(dú)的類中，或者滿足一個(gè)收斂，即終止條件為止。

（3）基于密度的方法

傳統(tǒng)的聚類算法都是基于對(duì)象之間的距離（距離作為相似性的描述指標(biāo)）進(jìn)行聚類劃分，但是這些基于距離的方法只能發(fā)現(xiàn)球狀類型的數(shù)據(jù)，對(duì)于非球狀類型的數(shù)據(jù)來(lái)說(shuō)只根據(jù)距離來(lái)描述和判斷是不夠的。鑒于此，人們提出了一個(gè)密度的概念——基于密度的方法（Density-Based Methods），其原理是：只要鄰近區(qū)域內(nèi)的密度（對(duì)象的數(shù)量）超過(guò)了某個(gè)閾值，就繼續(xù)聚類。換言之，給定某個(gè)簇中的每個(gè)數(shù)據(jù)點(diǎn)（數(shù)據(jù)對(duì)象），在一定范圍內(nèi)必須包含一定數(shù)量的其他對(duì)象。該算法從數(shù)據(jù)對(duì)象的分布密度出發(fā)，把密度足夠大的區(qū)域連接在一起，因此可以發(fā)現(xiàn)任意形狀的類。該算法還可以過(guò)濾噪聲數(shù)據(jù)（異常值）。基于密度的方法的典型算法包括DBSCAN（Density-Based Spatial Clustering of Application with Noise，具有噪聲的基于密度的空間聚類應(yīng)用算法）以及其擴(kuò)展算法OPTICS（Ordering Points to Identify the Clustering Structure，即通過(guò)點(diǎn)排序識(shí)別聚類結(jié)構(gòu)的密度聚類算法）。其中，DBSCAN算法會(huì)根據(jù)一個(gè)密度閾值來(lái)控制簇的增長(zhǎng)，將具有足夠高密度的區(qū)域劃分為類，并可在帶有噪聲的空間數(shù)據(jù)庫(kù)里發(fā)現(xiàn)任意形狀的聚類。盡管此算法優(yōu)勢(shì)明顯，但是其最大的缺點(diǎn)是需要用戶確定輸入?yún)?shù)，而且對(duì)參數(shù)十分敏感。

（4）基于網(wǎng)格的方法

基于網(wǎng)格的方法（Grid-Based Methods）將把對(duì)象空間量化為有限數(shù)目的單元，這些單元再形成網(wǎng)格結(jié)構(gòu)，讓所有的聚類操作都在這個(gè)網(wǎng)格結(jié)構(gòu)中進(jìn)行。該算法的優(yōu)點(diǎn)是處理速度快，其處理時(shí)間常常獨(dú)立于數(shù)據(jù)對(duì)象的數(shù)目，只跟量化空間中每一維的單元數(shù)目有關(guān)。基于網(wǎng)格方法的典型算法是STING（統(tǒng)計(jì)信息網(wǎng)格方法，Statistical Information Grid）算法。該算法是一種基于網(wǎng)格的多分辨率聚類技術(shù)，將空間區(qū)域劃分為不同分辨率級(jí)別的矩形單元，并形成一個(gè)層次結(jié)構(gòu)，且高層的低分辨率單元會(huì)被劃分為多個(gè)低一層次的較高分辨率單元。這種算法從最底層的網(wǎng)格開(kāi)始逐漸向上計(jì)算網(wǎng)格內(nèi)數(shù)據(jù)的統(tǒng)計(jì)信息并儲(chǔ)存。網(wǎng)格建立完成后，就用類似DBSCAN的方法對(duì)網(wǎng)格進(jìn)行聚類。

4．?dāng)?shù)據(jù)聚類需解決的問(wèn)題

在聚類分析的研究中，有許多急待進(jìn)一步解決的問(wèn)題，比如：處理數(shù)據(jù)為大數(shù)據(jù)量、具有復(fù)雜數(shù)據(jù)類型的數(shù)據(jù)集合時(shí)，聚類分析結(jié)果的精確性問(wèn)題；對(duì)高屬性維數(shù)據(jù)的處理能力；數(shù)據(jù)對(duì)象分布形狀不規(guī)則時(shí)的處理能力；處理噪聲數(shù)據(jù)的能力，能夠處理數(shù)據(jù)中包含的孤立點(diǎn)，未知數(shù)據(jù)、空缺或者錯(cuò)誤的數(shù)據(jù)；對(duì)數(shù)據(jù)輸入順序的獨(dú)立性，也就是對(duì)于任意的數(shù)據(jù)輸入順序產(chǎn)生相同的聚類結(jié)果；減少對(duì)先決知識(shí)或參數(shù)的依賴型……這些問(wèn)題的存在使得我們研究高正確率、低復(fù)雜度、I /O開(kāi)銷小、適合高維數(shù)據(jù)、具有高度可伸縮性的聚類方法迫在眉睫，這也是今后聚類方法研究的方向。

5．?dāng)?shù)據(jù)聚類應(yīng)用

聚類分析可以作為一個(gè)獨(dú)立的工具來(lái)獲得數(shù)據(jù)的分布情況，通過(guò)觀察每個(gè)簇的特點(diǎn)，集中對(duì)特定的某些簇做進(jìn)一步分析，以獲得需要的信息。聚類分析應(yīng)用廣泛，除了在數(shù)據(jù)挖掘、模式識(shí)別、圖像處理、計(jì)算機(jī)視覺(jué)、模糊控制等領(lǐng)域的應(yīng)用，還被應(yīng)用在氣象分析、食品檢驗(yàn)、生物種群劃分、市場(chǎng)細(xì)分、業(yè)績(jī)?cè)u(píng)估等諸多方面。例如，在商務(wù)上，聚類分析可以幫助市場(chǎng)分析人員從客戶基本庫(kù)中發(fā)現(xiàn)不同的客戶群，并且用購(gòu)買(mǎi)模式來(lái)刻畫(huà)不同的客戶群特征。聚類分析還可以應(yīng)用在欺詐探測(cè)中，聚類中的孤立點(diǎn)就可能預(yù)示著欺詐行為的存在。聚類分析的發(fā)展過(guò)程也是聚類分析的應(yīng)用過(guò)程，目前聚類分析在相關(guān)領(lǐng)域已經(jīng)取得豐碩的成果。