1）

10.聚類分析：基本概念和方法

聚類是一個把數(shù)據(jù)對象集劃分成多個組或簇的過程，使得簇內(nèi)的對象具有很高的相似性，但與其他簇中的對象很不相似。相異性和相似性根據(jù)描述對象的屬性值評估，涉及到距離度量。

10.1?聚類分析

聚類分析把一個數(shù)據(jù)對象（或觀測）劃分子集的過程。由聚類分析產(chǎn)生的簇的集合稱做一個聚類。聚類分析用來洞察數(shù)據(jù)的分析，觀察每個簇的特征，將進(jìn)一步分析集中在特定的簇集合上。聚類分析也可作為其他算法如特征化、屬性子集選擇和分類的預(yù)處理步驟。聚類也看用于離群點檢測。聚類是無監(jiān)督學(xué)習(xí)。

數(shù)據(jù)挖掘?qū)垲惖囊?#xff1a;可伸縮性、處理不同屬性類型的能力、發(fā)現(xiàn)任意形狀的簇、對于確定輸入?yún)?shù)的領(lǐng)域知識的要求、處理噪聲數(shù)據(jù)的能力、增量聚類和對輸入次序不敏感、聚類高維數(shù)據(jù)的能力、基于約束的聚類、可解釋性和可用性。比較聚類方法的有劃分準(zhǔn)則、簇的分離性、相似性度量、聚類空間。

聚類方法的特點：

1）劃分方法（原型方法）：發(fā)現(xiàn)球形互斥的簇、基于距離、可以用均值或中心點等代表簇中心、對中小規(guī)模數(shù)據(jù)集有效；

2）層次方法：聚類是一個層次分解（多層）、不能糾正錯誤的合并或劃分、可以集成其他技術(shù)如微聚類或考慮對象連接；

3）密度方法：可以發(fā)現(xiàn)任意形狀的簇、簇是對象空間中被低密度區(qū)域分隔的稠密區(qū)域、簇密度每個點的鄰域內(nèi)必須具有最少個數(shù)的點、可能過濾離群點；

4）網(wǎng)格方法：使用一種多分辨率網(wǎng)格數(shù)據(jù)結(jié)構(gòu)、快速處理（典型地，獨(dú)立于數(shù)據(jù)對象數(shù)，但依賴于網(wǎng)格大小）。

10.2?劃分方法

劃分方法把數(shù)據(jù)對象組織成k個分區(qū)，每個分區(qū)代表一個簇。同一簇中的對象是相似的，而不同簇中的對象是相異的。

K-均值一種基于形心的技術(shù)，對離群點敏感。k-中心點一種基于代表對象的技術(shù)，在存在噪聲和離群點下更魯棒性。

10.3?層次方法

層次聚類方法將數(shù)據(jù)對象組成層次結(jié)構(gòu)或簇的樹。層次聚類方法分類為凝聚的和分裂的，取決于層次分解是自底向上合并的還是自頂向下的分裂方式形成。

凝聚層次聚類使用自底向上策略。令每個對象形成自己的簇開始，并且迭代地把簇合并成越來越大的簇，直到所有的對象都在一個簇中，或者滿足某個終止的條件。該單個簇成為層次結(jié)構(gòu)的根。在合并步驟中，它找出兩個最接近的簇（根據(jù)某種相似性度量），并且合并它們，形成一個簇。因為每次迭代合并兩個簇，其中每個簇至少包含一個對象，因此凝聚方法最多需要n次迭代。

分類層次聚類使用自頂向下策略。從把所有對象置于一個簇中，該簇是層次結(jié)構(gòu)的根。然后，把根上的簇劃分成多個較小的子簇，并且遞歸地把這些簇劃分成更小的簇。劃分過程繼續(xù)，直到最底層的簇都足夠凝聚-或者僅包含一個對象，或者簇內(nèi)的對象彼此都充分相似。

凝聚方法和分裂方法的核心問題都是度量兩個簇之間的距離。

采用最小距離的稱為最近鄰聚類算法。當(dāng)最近的兩個簇之間的距離超過用戶給定的閾值時聚類過程就終止，稱為單連接算法。使用最小距離度量的凝聚層次聚類也稱為最小生成樹算法。

使用最大距離的稱為最遠(yuǎn)鄰聚類算法。如果當(dāng)最近的兩個簇之間的最大距離超過用戶給定的閾值時聚類過程終止，稱為全連接算法。

最小和最大距離代表了簇間距離度量的兩個極端，趨向?qū)﹄x群點或噪聲數(shù)據(jù)過分敏感。使用均值距離或平均距離是對最小和最大距離之間的一種折中方法，并且可以克服離群點敏感性問題。

利用層次結(jié)構(gòu)的平衡迭代歸約和聚類是為大量數(shù)值數(shù)據(jù)聚類設(shè)計的，將層次聚類和其他聚類方法集成一起，克服了凝聚聚類所面臨的可伸縮性和不可撤銷先前步驟工作的困難。BIRCH（使用聚類特征樹的多階段聚類）使用聚類特征來概括一個簇，使用聚類特征樹（CF-樹）來表示聚類的層次結(jié)構(gòu)。簇的聚類特征CF是一個3維向量，匯總了對象簇的信息，是給定簇的統(tǒng)計匯總。使用聚類特征可以避免存儲個體對象或點的詳細(xì)信息。CF樹是一顆高度平衡的樹，存儲了層次聚類的聚類特征。支持增量聚類。

Chameleon（變色龍）使用動態(tài)建模的多階段層次聚類，采用動態(tài)建模來確定一對簇之間的相似度。簇的相似度依據(jù)兩點評估：簇中對象的連接情況、簇的鄰近性。如果兩個簇的互連性很高并且它們之間靠得很近則將其合并，不用依賴于靜態(tài)的、用戶提供的模型，能夠自動適應(yīng)被合并簇的內(nèi)部特征。這一合并過程有利于發(fā)現(xiàn)自然、同構(gòu)的簇，并且只要定義了相似度函數(shù)就可應(yīng)用于所有類型的數(shù)據(jù)。過程是先依據(jù)k近鄰構(gòu)建稀疏圖，在分割邊割最小的子簇，最后用層次聚類的凝聚子簇。

層次聚類存在三個缺點：1）距離度量選擇是困難的；2）不能很好解決有缺失的屬性值；3）層次聚類方法是啟發(fā)式的，在每一步中局部地搜索好的合并或劃分。概率層次聚類通過使用概率模型度量簇之間的距離，克服這些缺點。概率層次聚類把待聚類的數(shù)據(jù)對象看做要分析的基礎(chǔ)數(shù)據(jù)生成機(jī)制的一個樣本，或生成模型，這樣聚類的任務(wù)是使用待聚類的觀測數(shù)據(jù)，盡可能準(zhǔn)確地估計生成模型。可以假定數(shù)據(jù)的生成模型采用常見的分布函數(shù)，如高斯分布或伯努利分布，由參數(shù)確定，學(xué)習(xí)生成模型的任務(wù)歸結(jié)為找出使得模型最佳擬合觀測數(shù)據(jù)集的參數(shù)值。概率層次聚類只輸出一個關(guān)于選取的概率模型的層次結(jié)構(gòu)，不能處理聚類層次結(jié)構(gòu)的不確定性，但給定一個數(shù)據(jù)集，可能存在多個擬合觀測數(shù)據(jù)的層次結(jié)構(gòu)。

10.4?基于密度的方法

劃分方法和層次方法都是發(fā)現(xiàn)球形簇，不能發(fā)現(xiàn)其他形狀的簇。要能發(fā)現(xiàn)任意形狀的簇，可以把簇看做數(shù)據(jù)空間中被稀疏區(qū)域分開的稠密區(qū)域，這就是基于密度的聚類方法的主要策略，可以發(fā)現(xiàn)非球狀的簇。

DBSCAN，具有噪聲應(yīng)用的基于密度的空間聚類，找出核心對象，即其鄰域稠密的對象，連接核心對象及其鄰域，形成稠密區(qū)域作為簇。構(gòu)建過程有鄰域半徑參數(shù)和核心對象鄰域內(nèi)要求的最少點數(shù)兩個參數(shù)控制。這兩個參數(shù)設(shè)置靠經(jīng)驗。

OPTICS，通過點排序識別聚類結(jié)構(gòu)，不顯式地產(chǎn)生數(shù)據(jù)集聚類，而是輸出簇排序，排序是所有分析對象的線性表，并且代表了數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)。較稠密簇中的對象在簇排序中相互靠近，排序等價于從廣泛的參數(shù)設(shè)置中得到的基于密度的聚類。需要兩個重要信息，核心距離和可達(dá)距離。

DENCLUE，一種基于一組密度分布函數(shù)的聚類算法。密度估計是根據(jù)一系列觀測數(shù)據(jù)集來估計不可觀測的概率密度函數(shù)。在基于密度聚類的背景下，不可觀測的概率密度函數(shù)是待分析的所有可能的對象的總體的真實分布。觀測數(shù)據(jù)集被看做取自該總體的一個隨機(jī)樣本。核密度估計，非參數(shù)密度估計方法，把每個觀測對象都看做是周圍區(qū)域中高概率密度的一個指示器，一個點上的概率密度依賴于從該點到觀測對象的距離。一個簇是一個密度吸引點的集合X和一個輸入對象的集合C，使得C中的每個對象都被分配到X中的一個密度吸引點，并且每對密度吸引點之間都存在一條其密度大于閾值的路徑。

10.5?基于網(wǎng)格的方法

基于網(wǎng)格的聚類，是空間驅(qū)動的方法，把嵌入空間劃分成獨(dú)立于輸入對象分布的單元。基于網(wǎng)格的聚類方法使用一種多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，將對象空間量化成有限數(shù)目的單元，形成網(wǎng)格結(jié)構(gòu)，所有的聚類操作在該結(jié)構(gòu)上進(jìn)行。這種方法處理速度快，處理時間獨(dú)立于數(shù)據(jù)對象數(shù)，而僅依賴于量化空間中每一維上的單元數(shù)。

STING，統(tǒng)計信息網(wǎng)格，基于網(wǎng)格的多分辨率的聚類技術(shù)，將輸入對象的空間區(qū)域劃分成矩形單元。空間可以用分層和遞歸方法進(jìn)行劃分。這種多層矩形單元對應(yīng)不同級別的分辨率，并且形成一個層次結(jié)構(gòu)：每個高層單元被劃分為多個第一層單元。關(guān)于每個網(wǎng)格單元的屬性的統(tǒng)計信息，如均值、最大值、最小值，被作為統(tǒng)計參數(shù)預(yù)先計算和存儲。

CLIQUE，一種類似于Apriori的子空間聚類方法，用于發(fā)現(xiàn)子空間中基于密度的簇。CLIQUE把每個維劃分成不重疊的區(qū)間，從而把數(shù)據(jù)對象的整個嵌入空間劃分成單元，使用一個密度閾值識別稠密單元和稀疏單元，一個單元是稠密的，如果映射到它的對象數(shù)超過該密度閾值。CLIQUE識別候選搜索空間的主要策略是使用稠密單元關(guān)于維度的單調(diào)性，這基于頻繁模式和關(guān)聯(lián)規(guī)則挖掘使用的先驗性質(zhì)。

10.6?聚類評估

聚類評估的主要任務(wù)包括估計聚類趨勢、確定數(shù)據(jù)集中的簇數(shù)、測定聚類質(zhì)量。

聚類趨勢評估確定給定的數(shù)據(jù)集是否具有可以導(dǎo)致有意義的聚類的非隨機(jī)結(jié)構(gòu)。霍普金斯統(tǒng)計量是一種空間統(tǒng)計量，檢驗空間分布的變量的空間的隨機(jī)性。該評估通過霍普金斯統(tǒng)計量來檢驗數(shù)據(jù)分布是否均勻。

合適的簇數(shù)可以控制適當(dāng)?shù)木垲惙治隽６?#xff0c;也是在聚類分析的可壓縮性和準(zhǔn)確性之間尋找好的平衡點。確定合適的簇數(shù)依賴于數(shù)據(jù)集分布的形狀和尺度，也依賴于用戶要求的聚類分辨率。估計簇的方法有肘方法，增加簇數(shù)有助于降低每個簇的簇內(nèi)方差之和，因為更多的簇可以捕獲更細(xì)的數(shù)據(jù)對象簇，簇中對象之間更為相似。不過，如果形成太多的簇，則降低簇內(nèi)的方差和的邊緣效應(yīng)可能下降，把一個凝聚的簇分裂成兩個只引起簇內(nèi)方差和的稍微降低，因此選擇正確的簇數(shù)的啟發(fā)式方法是使用簇內(nèi)方差和關(guān)于簇數(shù)的曲線的拐點。

測定聚類質(zhì)量有外在方法（監(jiān)督方法）和內(nèi)在方法（無監(jiān)督方法）。

1）外在方法：有簇的同質(zhì)性、簇的完全性、碎布袋、小簇保持性四項標(biāo)準(zhǔn)來評估聚類質(zhì)量度量Q是有效的。BCubed精度和召回率滿足滿足這四個標(biāo)準(zhǔn)，根據(jù)基準(zhǔn)，對給定數(shù)據(jù)集上聚類中的每個對象估計精度和召回率。一個對象的精度指示同一簇中有多少個其他對象與該對象同屬一個類別。一個對象的召回率反映有多少同一類別的對象別分配在相同的簇中。

2）內(nèi)在方法：在沒有數(shù)據(jù)集的基準(zhǔn)可用時，使用內(nèi)在方法評估聚類的質(zhì)量，通過考察簇的分離情況和簇的緊湊情況來評估聚類。利用數(shù)據(jù)集對象之間的相似性度量。輪廓系數(shù)就是這種度量。

?

10.7?小結(jié)

1）簇是數(shù)據(jù)對象的集合，同一個簇中的對象彼此相似，而不同簇中的對象彼此相異。將物理或抽象對象的集合劃分為相似對象的類的過程是聚類。

2）聚類分析具有廣泛的應(yīng)用，包括商務(wù)智能、圖像模式識別、Web搜索、生物學(xué)和安全。聚類分析可以作為獨(dú)立的數(shù)據(jù)挖掘工具來獲得對數(shù)據(jù)分布的了解，也可以作為在檢測的簇上運(yùn)行的其他數(shù)據(jù)挖掘算法的預(yù)處理步驟。

3）聚類是數(shù)據(jù)挖掘研究一個富有活力的領(lǐng)域，與機(jī)器學(xué)習(xí)的無監(jiān)督學(xué)習(xí)有關(guān)。

4）聚類的要求包括可伸縮性、處理不同類型的數(shù)據(jù)和屬性的能力、發(fā)現(xiàn)任意形狀的簇、確定輸入?yún)?shù)的最小領(lǐng)域知識需求、處理噪聲數(shù)據(jù)的能力、增量聚類和對輸入次序的不敏感性、聚類高維數(shù)據(jù)的能力、基于約束的聚類，以及聚類的可解釋性和可用性。

5）聚類方法根據(jù)劃分標(biāo)準(zhǔn)、簇的分離性、所所用的相似性度量和聚類空間有：劃分方法、層次方法、基于密度的方法和基于網(wǎng)格的方法。

6）劃分方法首先創(chuàng)建k個分區(qū)的初始集合，其中參數(shù)k是要構(gòu)建的分區(qū)數(shù)。然后，采用迭代重定位技術(shù)，試圖通過把對象從一個簇移到另一個簇來改進(jìn)劃分的質(zhì)量。典型的劃分方法包括k-均值、k-中心點、CLARANS。

7）層次方法創(chuàng)建給定數(shù)據(jù)對象集的層次分解。根據(jù)層次分解的形成方式，層次方法可以分為凝聚的（自底向上）和分裂的（自頂向下）。為彌補(bǔ)合并或分裂的僵硬性，凝聚的層次方法的聚類質(zhì)量可通過以下方法改進(jìn)：分析每個層次劃分中的對象連接（如Chameleon），或者首先執(zhí)行微聚類（把數(shù)據(jù)劃分為微簇），然后使用其他的聚類技術(shù)，迭代重定位，在微簇上聚類（如BIRCH）。

8）基于密度的方法基于密度的概念來聚類對象。它或者根據(jù)鄰域中對象的密度（如DBSCAN），或者根據(jù)某種密度函數(shù)(如DENCLUE)來生成簇。OPTICS是一個基于密度的方法，它生成數(shù)據(jù)聚類結(jié)構(gòu)的一個增廣序。

9）基于網(wǎng)格的方法首先將對象空間量化為有限數(shù)目的單元，形成網(wǎng)格結(jié)構(gòu)，然后在網(wǎng)格結(jié)構(gòu)上進(jìn)行聚類。STING是基于網(wǎng)格方法的一個例子，基于存儲在網(wǎng)格單元中的統(tǒng)計信息聚類。CLIQUE是基于網(wǎng)格的子空間聚類算法。

10）聚類評估估計在數(shù)據(jù)集上進(jìn)行聚類分析的可行性和由聚類方法產(chǎn)生的結(jié)果的質(zhì)量。任務(wù)包括評估聚類趨勢、確定簇數(shù)和測定聚類的質(zhì)量。

?

總結(jié)

以上是生活随笔為你收集整理的【数据挖掘笔记十】聚类分析：基本概念和方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。