數(shù)據(jù)挖掘?qū)д損pt課件.ppt

《數(shù)據(jù)挖掘?qū)д損pt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、聚類分析：附加的問題與算法第9章聚類分析：附加的問題與算法在各種領(lǐng)域，針對(duì)不同的應(yīng)用類型，已經(jīng)開發(fā)了大量聚類算法。在這些算法中沒有一種算法能夠適應(yīng)所有的數(shù)據(jù)類型、簇和應(yīng)用。事實(shí)上，對(duì)于更加有效或者更適合特定數(shù)據(jù)類型、簇和應(yīng)用的新的聚類算法，看來總是有進(jìn)一步的開發(fā)空間。我們只能說我們已經(jīng)有了一些技術(shù)，對(duì)于某些情況運(yùn)行良好。其原因是，在許多情況下，對(duì)于什么是一個(gè)好的簇集，仍然憑主觀解釋。此外，當(dāng)使用客觀度量精確地定義簇時(shí)，發(fā)現(xiàn)最優(yōu)聚類問題常常是計(jì)算不可行的。比較k均值和DBSCANDBSCAN和k均值都是將每個(gè)對(duì)象指派到單個(gè)簇的劃分聚類算法，但是K均

2、值一般聚類所有對(duì)象，而DBSCAN丟棄被它識(shí)別為噪聲的對(duì)象。K均值使用簇的基于原形的概念，而DBSCAN使用基于密度的概念。DBSCAN可以處理不同大小和不同形狀的簇，并且不太受噪聲和離群點(diǎn)的影響。K均值很難處理非球狀的簇和不同大小的簇。當(dāng)簇具有很不同的密度時(shí)，兩種算法的性能都很差。K均值只能用于具有明確定義的質(zhì)心（如均值或中位數(shù)）的數(shù)據(jù)。DBSCAN要求密度定義（基于傳統(tǒng)的歐幾里得密度概念）對(duì)于數(shù)據(jù)是有意義的。K均值可以用于稀疏的高維數(shù)據(jù)，如文檔數(shù)據(jù)，DBSCAN通常在這類數(shù)據(jù)上性能很差，因?yàn)閷?duì)于高維數(shù)據(jù)，傳統(tǒng)的歐幾里得密度定義不能很好處理。K

3、均值和DBSCAN的最初版本都是針對(duì)歐幾里得數(shù)據(jù)設(shè)計(jì)的，但是它們都被擴(kuò)展，以便處理其他類型的數(shù)據(jù)。DBSCAN不對(duì)數(shù)據(jù)的分布做任何假定?；緆均值算法等價(jià)于一種統(tǒng)計(jì)聚類方法（混合模型），假定所有的簇都來自球形高斯分布，具有不同的均值，但具有相同的斜方差矩陣。DBSCAN和k均值都尋找使用所有屬性的簇，即它們都不尋找可能只涉及某個(gè)屬性子集的簇。K均值可以發(fā)現(xiàn)不是明顯分離的簇，即便簇有重疊也可以發(fā)現(xiàn)，但是DBSCAN會(huì)合并有重疊的簇。K均值算法的時(shí)間復(fù)雜度是O（m），而DBSCAN的時(shí)間復(fù)雜度是O（m2）.DBSCAN多次運(yùn)行產(chǎn)生相同的結(jié)果，而k均值

4、通常使用隨機(jī)初始化質(zhì)心，不會(huì)產(chǎn)生相同的結(jié)果。DBSCAN自動(dòng)地確定簇個(gè)數(shù)；對(duì)于k均值，簇個(gè)數(shù)需要作為參數(shù)指定。然而，DBSCAN必須指定另外兩個(gè)參數(shù)：Eps和MinptsK均值聚類可以看作優(yōu)化問題，即最小化每個(gè)點(diǎn)到最近的質(zhì)心的誤差的平方和，并且可以看作一種統(tǒng)計(jì)聚類的特例。DBSCAN不基于任何形式化模型。數(shù)據(jù)特性高維性隨著維度的增加，體積迅速增加，除非點(diǎn)的個(gè)數(shù)也隨著維度指數(shù)增加，否則密度將趨向于0.處理該問題的方法是使用維歸約技術(shù)規(guī)模許多聚類算法對(duì)于小規(guī)模和中等規(guī)模的數(shù)據(jù)集運(yùn)行良好，但是不能處理大型數(shù)據(jù)集稀疏性稀疏數(shù)據(jù)通常由非對(duì)稱的屬性組成，其中

5、零值沒有非零值重要。.噪聲和離群點(diǎn)非常見點(diǎn)可能嚴(yán)重地降低聚類算法的性能，特別是k均值這樣的基于原型的算法另一方面，噪聲也可能導(dǎo)致單鏈等技術(shù)合并兩個(gè)不應(yīng)當(dāng)合并的簇。屬性和數(shù)據(jù)集類型屬性可能是分類的（標(biāo)稱的或序數(shù)的）或定量的（區(qū)間的或比率的），二元的、離散的或連續(xù)的。不同的近鄰性和密度度量適合于不同類型的數(shù)據(jù)。尺度不同的屬性，如高度和重量，可能用不同的尺度度量。這些差別可能嚴(yán)重影響兩個(gè)對(duì)象之間的距離或相似性，從而影響聚類分析的結(jié)果。簇特性數(shù)據(jù)分布某些聚類技術(shù)假定數(shù)據(jù)具有特定的分布。更具體的說，它們常常假定可以用混合分布對(duì)數(shù)據(jù)建模，其中每個(gè)簇對(duì)應(yīng)于一個(gè)

6、分布。形狀有些簇具有規(guī)則的形狀，如矩形和球形。但是，更一般地，簇可以具有任意形狀。如DBSCAN和單鏈等技術(shù)可以處理任意形狀?；谠偷姆椒ê鸵恍哟尉垲惣夹g(shù)不能進(jìn)行這樣的處理。Chameleon和cure是專門用來處理這一問題的技術(shù)不同大小許多聚類算法，如k均值，當(dāng)簇具有不同的大小時(shí)不能很好的處理不同密度具有很不相同的密度的簇可能對(duì)諸如DBSCAN和k均值等算法造成影響基于SNN密度的聚類技術(shù)可以處理這個(gè)問題無明顯分離的簇當(dāng)簇接觸或重疊時(shí)，有些聚類技術(shù)將應(yīng)當(dāng)分開的簇合并。甚至有些發(fā)現(xiàn)不同簇的技術(shù)隨意地將點(diǎn)指派到一個(gè)或另一個(gè)簇。模糊聚類可以處理這

7、一問題簇之間的聯(lián)系在大部分聚類技術(shù)中，都不考慮簇之間的聯(lián)系，如簇的相對(duì)位置自組織映射（SOM）是一種在聚類期間直接考慮簇之間聯(lián)系的聚類技術(shù)。子空間簇簇可能只在維（屬性）的一個(gè)子集中存在，并且使用一個(gè)維集合確定的簇可能也使用另一個(gè)維確定的簇很不相同。聚類算法的一般特征次序依賴性對(duì)于某些算法，所產(chǎn)生的簇的質(zhì)量和個(gè)數(shù)可能因數(shù)據(jù)處理的次序不同而顯著地變化。如SOM非確定性有些算法不是次序依賴的，但是它們每次運(yùn)行都產(chǎn)生不同的結(jié)果，因?yàn)樗鼈円蕾囉谛枰S機(jī)選擇的初始化步驟。變換聚類問題到其他領(lǐng)域?qū)⒕垲悊栴}映射到一個(gè)不同的領(lǐng)域。如，基于圖的聚類可伸縮性包含數(shù)以百

8、萬計(jì)對(duì)象的數(shù)據(jù)集并不罕見，而用于這種數(shù)據(jù)集的聚類算法應(yīng)當(dāng)具有線性或接近線性的時(shí)間或空間復(fù)雜度。對(duì)于大型數(shù)據(jù)集，即使具有O(m2)復(fù)雜度也