第9章聚類分析本章將介紹聚類分析的基礎(chǔ)知識和常用方法。首先探討聚類分析的概念，它是一種無監(jiān)督學(xué)習(xí)方法，通過計(jì)算數(shù)據(jù)點(diǎn)之間的相似性度量將相似的數(shù)據(jù)點(diǎn)聚集在一起。然后研究了相似性度量的概念，選擇合適的相似性度量對聚類結(jié)果至關(guān)重要。接著，討論聚類的評價(jià)指標(biāo)，這些指標(biāo)能夠幫助估聚類算法的性能和效果。然后，詳細(xì)介紹基于劃分、層次和密度的聚類分析方法，包括K-Means聚類、K-Means++聚類、自底向上聚類算法、自頂向下聚類算法、DBSCAN算法和OPTICS算法。通過本章的學(xué)習(xí)，將對聚類分析有更深入的理解，能夠選擇合適的聚類算法并解釋聚類結(jié)果。第9章聚類分析9.1聚類分析基礎(chǔ)9.2基于劃分的聚類分析9.3基于層次的聚類分析9.4基于密度的聚類分析9.5實(shí)踐--聚類分析9.6本章小結(jié)9.1聚類分析基礎(chǔ)聚類分析是一種無監(jiān)督學(xué)習(xí)方法，通過計(jì)算數(shù)據(jù)點(diǎn)之間的相似性度量，將相似的數(shù)據(jù)點(diǎn)歸為一類，形成不同的簇。9.1聚類分析基礎(chǔ)9.1.1聚類分析的概念9.1.2相似性度量9.1.3聚類的評價(jià)指標(biāo)9.1.1聚類分析的概念1.聚類分析的目標(biāo)2.相似性度量的作用3.簇的定義和特征4.聚類的應(yīng)用5.聚類與分類的區(qū)別9.1聚類分析基礎(chǔ)1.聚類分析的目標(biāo)聚類分析的目標(biāo)是將相似的數(shù)據(jù)點(diǎn)聚集在一起，使得同一簇內(nèi)的數(shù)據(jù)點(diǎn)相似度較高，而不同簇之間的數(shù)據(jù)點(diǎn)相似度較低。9.1聚類分析基礎(chǔ)2.相似性度量的作用相似性度量是聚類分析的核心概念，用于衡量兩個(gè)數(shù)據(jù)點(diǎn)之間的相似程度。它可以基于不同的特征和距離度量方法進(jìn)行計(jì)算，如歐氏距離、曼哈頓距離、余弦相似度等。選擇合適的相似性度量對聚類分析的結(jié)果具有重要影響。9.1聚類分析基礎(chǔ)3.簇的定義和特征簇是聚類分析中的基本單位，代表了一組相似的數(shù)據(jù)點(diǎn)。每個(gè)簇具有一些共同的特征，可以通過簇內(nèi)數(shù)據(jù)點(diǎn)的統(tǒng)計(jì)特性或質(zhì)心來表示。簇的個(gè)數(shù)可以預(yù)先設(shè)定，也可以通過算法自動(dòng)確定。9.1聚類分析基礎(chǔ)4.聚類的應(yīng)用聚類分析可以發(fā)現(xiàn)數(shù)據(jù)中的內(nèi)在結(jié)構(gòu)和模式，幫助理解數(shù)據(jù)并做出有效的決策。聚類分析可以用于數(shù)據(jù)挖掘、模式識別、市場分析等領(lǐng)域，如用戶分群、推薦系統(tǒng)、異常檢測等。9.1聚類分析基礎(chǔ)5.聚類與分類的區(qū)別聚類分析與分類分析不同。聚類分析是一種無監(jiān)督學(xué)習(xí)方法，不需要事先標(biāo)記的訓(xùn)練數(shù)據(jù)，它將數(shù)據(jù)點(diǎn)自動(dòng)組織成簇。而分類分析是一種有監(jiān)督學(xué)習(xí)方法，需要有標(biāo)記的訓(xùn)練數(shù)據(jù)進(jìn)行模型的訓(xùn)練和預(yù)測，它將數(shù)據(jù)分為預(yù)定義的類別。9.1聚類分析基礎(chǔ)9.1.2相似性度量常用的數(shù)據(jù)相似性度量包括以下幾種9.1聚類分析基礎(chǔ)9.1.2相似性度量1.歐幾里得距離2.曼哈頓距離3.余弦相似度9.1聚類分析基礎(chǔ)1.歐幾里得距離歐幾里得距離（Euclideandistance）是一種常用的相似性度量方法，用于衡量兩個(gè)數(shù)據(jù)點(diǎn)之間的距離或相似度。它基于歐幾里得幾何中的距離定義，計(jì)算兩個(gè)數(shù)據(jù)點(diǎn)在特征空間中的直線距離。9.1聚類分析基礎(chǔ)2.曼哈頓距離曼哈頓距離（Manhattandistance），也稱為城市街區(qū)距離或L1距離，是一種常用的相似性度量方法，用于衡量兩個(gè)數(shù)據(jù)點(diǎn)之間的距離或相似度。它以城市中相鄰街區(qū)之間的距離為模型，計(jì)算兩個(gè)數(shù)據(jù)點(diǎn)在特征空間中的距離。9.1聚類分析基礎(chǔ)3.余弦相似度余弦相似度（Cosinesimilarity）是一種常用的相似性度量方法，用于衡量兩個(gè)向量之間的相似度。它基于向量的夾角余弦值來度量向量之間的方向一致性和相似性。在n維空間中，兩個(gè)點(diǎn)x(x1,x2,…,xn)和y(y1,y2,…,yn)之間的余弦相似度如式子9-3所示。9.1聚類分析基礎(chǔ)9.1.3聚類的評價(jià)指標(biāo)聚類的評價(jià)指標(biāo)用于評估聚類算法的性能和效果。以下是一些常見的聚類評價(jià)指標(biāo)：9.1聚類分析基礎(chǔ)9.1.3聚類的評價(jià)指標(biāo)1.輪廓系數(shù)（SilhouetteCoefficient）2.Davies-Bouldin指數(shù)（Davies-BouldinIndex，記作DBI）3.Calinski-Harabasz指數(shù)(Calinski-HarabaszIndex，記作CHI)4.Dunn指數(shù)（DunnIndex，記作DI）5.聚類純度（ClusterPurity，記作CP）6.蘭德系數(shù)（RandIndex，記作RI）9.1聚類分析基礎(chǔ)1.輪廓系數(shù)（SilhouetteCoefficient）輪廓系數(shù)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的輪廓系數(shù)，然后取所有數(shù)據(jù)點(diǎn)的平均值作為聚類結(jié)果的輪廓系數(shù)。輪廓系數(shù)的公式為式子（9-4）。9.1聚類分析基礎(chǔ)2.Davies-Bouldin指數(shù)（Davies-BouldinIndex，記作DBI）DBI基于聚類結(jié)果中各簇之間的平均距離和簇內(nèi)數(shù)據(jù)點(diǎn)的離散程度來度量聚類的緊密性和分離度。DBI的公式為式子（9-5）。9.1聚類分析基礎(chǔ)3.Calinski-Harabasz指數(shù)（Calinski-HarabaszIndex，記作CHI）CHI基于簇內(nèi)的離散程度和簇間的分離程度來度量聚類結(jié)果的質(zhì)量。CHI的公式為式子（9-6）。9.1聚類分析基礎(chǔ)4.Dunn指數(shù)（DunnIndex，記作DI）Dunn指數(shù)基于簇內(nèi)最近鄰距離和簇間最遠(yuǎn)鄰距離的比值來度量聚類結(jié)果的緊密性和分離度。Dunn指數(shù)的公式為式子（9-7）。9.1聚類分析基礎(chǔ)5.聚類純度（ClusterPurity，記作CP）聚類純度用于評估聚類結(jié)果中簇內(nèi)數(shù)據(jù)點(diǎn)的類別一致性。聚類純度的公式為式子（9-8）所示。9.1聚類分析基礎(chǔ)6.蘭德系數(shù)（RandIndex，記作RI）蘭德系數(shù)用于度量聚類結(jié)果與真實(shí)類別標(biāo)簽之間的一致性。蘭德系數(shù)的公式為式子（9-9）所示。9.1聚類分析基礎(chǔ)9.2基于劃分的聚類分析9.2基于劃分的聚類分析9.2.1K-Means聚類9.2.2K-Means++聚類9.2.1K-Means聚類K-Means算法是一種常用的基于劃分的聚類算法，用于將數(shù)據(jù)點(diǎn)劃分為K個(gè)簇，使得每個(gè)數(shù)據(jù)點(diǎn)與所屬簇的質(zhì)心之間的距離最小化。9.2基于劃分的聚類分析9.2.1K-Means聚類K-Means算法的基本步驟K-Means算法的優(yōu)缺點(diǎn)9.2基于劃分的聚類分析K-Means算法的基本步驟初始化：隨機(jī)選擇K個(gè)數(shù)據(jù)點(diǎn)作為初始的質(zhì)心。分配數(shù)據(jù)點(diǎn)到最近的質(zhì)心：對于每個(gè)數(shù)據(jù)點(diǎn)，計(jì)算其與每個(gè)質(zhì)心之間的距離，將數(shù)據(jù)點(diǎn)分配給與其距離最近的質(zhì)心所屬的簇。更新質(zhì)心：對于每個(gè)簇，計(jì)算該簇內(nèi)所有數(shù)據(jù)點(diǎn)的平均值，將該平均值作為新的質(zhì)心。重復(fù)步驟2和步驟3，直到質(zhì)心的位置不再發(fā)生變化或達(dá)到預(yù)定的迭代次數(shù)。在K-Means算法中，通過迭代的方式不斷更新質(zhì)心和重新分配數(shù)據(jù)點(diǎn)，直到達(dá)到穩(wěn)定狀態(tài)。算法的收斂性與初始質(zhì)心的選擇有關(guān)，因此可以嘗試多次運(yùn)行K-Means算法并選擇最好的結(jié)果。9.2基于劃分的聚類分析K-Means算法的優(yōu)缺點(diǎn)K-Means算法的優(yōu)點(diǎn)包括簡單、易于理解和實(shí)現(xiàn)，計(jì)算效率較高。然而，K-Means算法對初始質(zhì)心的選擇較為敏感，可能會收斂到局部最優(yōu)解。此外，K-Means算法對異常值和噪聲較為敏感，可能導(dǎo)致不準(zhǔn)確的聚類結(jié)果。為了改進(jìn)K-Means算法的性能，可以使用K-Means++算法進(jìn)行初始質(zhì)心的選擇，或者使用其他改進(jìn)的聚類算法，如譜聚類（SpectralClustering）和層次聚類（HierarchicalClustering）等。9.2基于劃分的聚類分析9.2.2K-Means++聚類K-Means++是對K-Means聚類算法的改進(jìn)，通過改變初始質(zhì)心的選擇方式，提高了算法的收斂速度和結(jié)果的穩(wěn)定性。9.2基于劃分的聚類分析K-Means++聚類算法的基本步驟初始化第一個(gè)質(zhì)心：從數(shù)據(jù)集中隨機(jī)選擇一個(gè)數(shù)據(jù)點(diǎn)作為第一個(gè)質(zhì)心。計(jì)算距離權(quán)重：對于每個(gè)數(shù)據(jù)點(diǎn)，計(jì)算它與已選擇的質(zhì)心之間的距離，將距離的平方作為權(quán)重。選擇下一個(gè)質(zhì)心：根據(jù)距離權(quán)重的分布，以較大概率選擇離已選擇質(zhì)心較遠(yuǎn)的數(shù)據(jù)點(diǎn)作為下一個(gè)質(zhì)心。具體選擇方法是根據(jù)距離權(quán)重進(jìn)行加權(quán)采樣。重復(fù)步驟2和步驟3，直到選擇了K個(gè)質(zhì)心。運(yùn)行K-Means算法：使用選擇的初始質(zhì)心運(yùn)行K-Means算法的剩余步驟，包括分配數(shù)據(jù)點(diǎn)到最近的質(zhì)心和更新質(zhì)心的過程。K-Means++算法通過改變初始質(zhì)心的選擇方式，使得初始質(zhì)心更好地分布在數(shù)據(jù)空間中，避免了隨機(jī)選擇可能導(dǎo)致的不穩(wěn)定性和低效性。這種改進(jìn)能夠提高算法的收斂速度和聚類結(jié)果的質(zhì)量。9.2基于劃分的聚類分析9.3基于層次的聚類分析基于層次的聚類分析（HierarchicalClustering）是一種將數(shù)據(jù)點(diǎn)逐步劃分或合并的聚類方法。它不需要預(yù)先設(shè)定聚類的數(shù)量，而是基于數(shù)據(jù)點(diǎn)之間的相似性度量，構(gòu)建一個(gè)層次結(jié)構(gòu)的聚類樹?；趯哟蔚木垲惙治隹梢苑譃閮煞N主要方法：自底向上（凝聚型）和自頂向下（分裂型）。9.3基于層次的聚類分析9.3.1自底向上聚類算法9.3.2自頂向下聚類算法9.3.1自底向上聚類算法自底向上聚類算法（AgglomerativeClustering）是一種基于層次的聚類方法，從每個(gè)數(shù)據(jù)點(diǎn)作為一個(gè)簇開始，逐步合并相似的簇，直到達(dá)到預(yù)設(shè)的聚類數(shù)目。9.3基于層次的聚類分析自底向上聚類算法的基本步驟初始化：將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)初始的簇。計(jì)算相似性度量：計(jì)算任意兩個(gè)簇之間的相似性度量，如距離或相似度。常用的相似性度量包括歐氏距離、曼哈頓距離、余弦相似度等。合并最相似的簇：選擇相似性度量最高的兩個(gè)簇進(jìn)行合并，形成一個(gè)新的簇。合并的方式可以是簡單平均、加權(quán)平均或其他方式。更新相似性度量：更新簇之間的相似性度量，以反映新形成的簇與其他簇之間的相似程度。常見的更新方法包括單鏈接、完全鏈接和平均鏈接等。重復(fù)合并步驟：重復(fù)步驟2和步驟3，直到達(dá)到預(yù)設(shè)的聚類數(shù)目或只剩下一個(gè)簇。9.3基于層次的聚類分析9.3.2自頂向下聚類算法自頂向下聚類算法（DivisiveClustering）是一種基于層次的聚類方法，從所有數(shù)據(jù)點(diǎn)作為一個(gè)簇開始，逐步將簇分裂為更小的子簇，直到達(dá)到預(yù)設(shè)的聚類數(shù)目。9.3基于層次的聚類分析自頂向下聚類算法的基本步驟初始化：將所有數(shù)據(jù)點(diǎn)視為一個(gè)初始的簇。計(jì)算相似性度量：計(jì)算當(dāng)前簇中任意兩個(gè)數(shù)據(jù)點(diǎn)之間的相似性度量，如距離或相似度。常用的相似性度量包括歐氏距離、曼哈頓距離、余弦相似度等。選擇分裂簇：選擇需要分裂的簇，通常是具有較高方差或離散度的簇?？梢允褂媚承?biāo)準(zhǔn)或閾值來選擇分裂簇。分裂簇：將選擇的簇分裂為兩個(gè)或多個(gè)子簇，使用相似性度量來決定數(shù)據(jù)點(diǎn)的歸屬。常見的分裂方法包括K-Means算法、K-Medoids算法等。重復(fù)分裂步驟：重復(fù)步驟2和步驟3，直到達(dá)到預(yù)設(shè)的聚類數(shù)目或達(dá)到停止條件。9.3基于層次的聚類分析9.4基于密度的聚類分析9.4基于密度的聚類分析9.4.1DBSCAN算法9.4.2OPTICS算法9.4.1DBSCAN算法DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）的核心思想是通過定義數(shù)據(jù)點(diǎn)的密度來劃分簇。根據(jù)給定的半徑（ε）和最小密度（MinPts），DBSCAN定義了以下概念9.4基于密度的聚類分析9.4.1DBSCAN算法基本概念算法步驟算法的優(yōu)缺點(diǎn)9.4基于密度的聚類分析基本概念核心點(diǎn)（CorePoint）：在給定半徑內(nèi)至少包含最小密度數(shù)量的數(shù)據(jù)點(diǎn)。邊界點(diǎn)（BorderPoint）：在給定半徑內(nèi)不滿足最小密度數(shù)量要求的數(shù)據(jù)點(diǎn)，但位于核心點(diǎn)的鄰域內(nèi)。噪聲點(diǎn)（NoisePoint）：既不是核心點(diǎn)也不是邊界點(diǎn)的數(shù)據(jù)點(diǎn)。9.4基于密度的聚類分析算法步驟選擇一個(gè)未被訪問的數(shù)據(jù)點(diǎn)作為當(dāng)前點(diǎn)，如果當(dāng)前點(diǎn)的鄰域內(nèi)包含至少最小密度數(shù)量的數(shù)據(jù)點(diǎn)，則將其標(biāo)記為核心點(diǎn)，并將其鄰域內(nèi)的數(shù)據(jù)點(diǎn)添加到同一個(gè)簇中。對于核心點(diǎn)的鄰域內(nèi)的每個(gè)數(shù)據(jù)點(diǎn)，如果其也是核心點(diǎn)，則將其鄰域內(nèi)的數(shù)據(jù)點(diǎn)添加到同一個(gè)簇中。重復(fù)步驟1和步驟2，直到所有數(shù)據(jù)點(diǎn)都被訪問。標(biāo)記剩余的未分配數(shù)據(jù)點(diǎn)為噪聲點(diǎn)。9.4基于密度的聚類分析算法的優(yōu)缺點(diǎn)DBSCAN算法的優(yōu)點(diǎn)包括能夠發(fā)現(xiàn)具有不同密度和不規(guī)則形狀的簇，對噪聲和離群點(diǎn)有較強(qiáng)的魯棒性，并且不需要預(yù)先指定簇的數(shù)量。然而，DBSCAN的計(jì)算復(fù)雜度較高，特別是在處理大規(guī)模數(shù)據(jù)集時(shí)。此外，DBSCAN對于參數(shù)的選擇（如半徑ε和最小密度MinPts）比較敏感，需要進(jìn)行參數(shù)調(diào)優(yōu)和結(jié)果評估。9.4基于密度的聚類分析9.4.2OPTICS算法OPTICS（OrderingPointsToIdentifytheClusteringStructure）算法是一種基于密度的聚類算法，用于發(fā)現(xiàn)密度可達(dá)的樣本集合。與DBSCAN相似，OPTICS也能夠自動(dòng)識別聚類的數(shù)量，并能夠處理具有不同密度的簇。9.4基于密度的聚類分析核心概念OPTICS算法基于兩個(gè)核心概念，即可達(dá)距離（reachabilitydistance）和核心距離（coredistance）。1.可達(dá)距離：對于兩個(gè)數(shù)據(jù)點(diǎn)p和q，p到q的可達(dá)距離表示p通過一系列距離不超過給定半徑（ε）的數(shù)據(jù)點(diǎn)，能夠到達(dá)q的最小距離。2.核心距離：對于一個(gè)數(shù)據(jù)點(diǎn)p，核心距離表示p到其ε-鄰域內(nèi)的最小距離。9.4基于密度的聚類分析OPTICS主要步驟初始化：為每個(gè)數(shù)據(jù)點(diǎn)設(shè)置初始的可達(dá)距離為無窮大。鄰域查詢：對每個(gè)數(shù)據(jù)點(diǎn)，計(jì)算其ε-鄰域內(nèi)的數(shù)據(jù)點(diǎn)，并計(jì)算其核心距離。擴(kuò)展種子：從未處理的數(shù)據(jù)點(diǎn)中選擇一個(gè)作為種子點(diǎn)，將其標(biāo)記為已處理，并根據(jù)其核心距離擴(kuò)展可達(dá)距離。擴(kuò)展可達(dá)距離：對于每個(gè)已處理的數(shù)據(jù)點(diǎn)，計(jì)算其ε-鄰域內(nèi)的數(shù)據(jù)點(diǎn)的可達(dá)距離，并將其加入到有序的優(yōu)先隊(duì)列中。提取聚類結(jié)構(gòu)：根據(jù)可達(dá)距離從優(yōu)先隊(duì)列中提取數(shù)據(jù)點(diǎn)，并形成聚類結(jié)構(gòu)。9.4基于密度的聚類分析9.5實(shí)踐--聚類分析9.5實(shí)踐--聚類分析9.5.1基于劃分聚類實(shí)現(xiàn)能源效率信息聚類9.5.2利用HierarchicalK-Means算法完成用戶行為數(shù)據(jù)聚類9.5.3利用DBSCAN進(jìn)行城市人口信息聚類9.5.1基于劃分聚類實(shí)現(xiàn)能源效率信息聚類本節(jié)使用的是能源效率信息的數(shù)據(jù)集，此數(shù)據(jù)集來源于數(shù)據(jù)科學(xué)競賽平臺kaggle：/datasets/elikplim/eergy-efficiency-dataset，共有768條數(shù)據(jù)，共有10個(gè)屬性9.5實(shí)踐--聚類分析圖9-1K-Means的不同K值對應(yīng)的輪廓系數(shù)由運(yùn)行結(jié)果可知，當(dāng)聚類個(gè)數(shù)達(dá)到10時(shí)，輪廓系數(shù)最高且為0.81。9.5實(shí)踐--聚類分析9.5.2利用HierarchicalK-Means算法完成用戶行為數(shù)據(jù)聚類本節(jié)使用的是用戶行為信息的數(shù)據(jù)集，此數(shù)據(jù)集來源于數(shù)據(jù)科學(xué)競賽平臺kaggle：/datasets/bhanupratapbiswas/app-users-segmentation-case-study，共有9