【正文】 性是指算法要能夠處理大數(shù)據(jù)量的數(shù)據(jù)庫對象，比如處理上百萬條記錄的數(shù)據(jù)庫，這就要求算法的時間復(fù)雜度不能太高，最好是多項式時間的算法。 遼寧省物流航運管理系統(tǒng)工程重點實驗室 聚類分析的定義 ?聚類分析方法可以應(yīng)用在數(shù)據(jù)挖掘的各個過程之中，比如在數(shù)據(jù)預(yù)處理操作中，針對數(shù)據(jù)需求，對于數(shù)據(jù)結(jié)構(gòu)簡單或者是與運量分析有單屬性和較少屬性關(guān)聯(lián)的數(shù)據(jù)可以在經(jīng)過數(shù)據(jù)清理等預(yù)處理后直接整合入數(shù)據(jù)倉庫。研究如何在沒有訓(xùn)練的條件下把對象化分為若干類。這時我們就需要對數(shù)據(jù)進行聚類處理。如布爾型、枚舉型、序數(shù)型及混合型等。 ?6. 結(jié)果對輸入記錄順序的無關(guān)性 有些分析算法對記錄的輸入順序是敏感的，即對同一個數(shù)據(jù)集，將它以不同的順序輸入到分析算法，得到的結(jié)果會不同，這是我們不希望的。每一個分組就代表一個聚類， KN。、 ?在時間復(fù)雜度上， kmeans算法的時間復(fù)雜度為 O(nkt)，而 kmedoids算法的時間復(fù)雜度大約為 O(n2)，后者的執(zhí)行代價要高得多。 ?分裂的方法，也稱為自頂向下的方法，它與凝聚層次聚類恰好相反，初始時將所有的對象置于一個簇中，然后逐漸細分為更小的簇，直到最終每個對象都在單獨的一個簇中，或者達到某個終止條件為止。 該算法通過聚類特征可以方便地進行中心 、 半徑 、 直徑及類內(nèi) 、 類間距離的運算 。 在凝聚算法中的每一步 ，距離最近的代表性點所對應(yīng)的簇將被合并 。 這樣通過連接密度較大區(qū)域 ， 就能形成不同形狀的聚類 ， 而且還可以消除孤立點和噪聲對聚類質(zhì)量的影響 ， 發(fā)現(xiàn)任意形狀的簇 。 ?DBSCAN算法不進行任何的預(yù)處理而直接對整個數(shù)據(jù)集進行聚類操作。 遼寧省物流航運管理系統(tǒng)工程重點實驗室 ?常見的基于網(wǎng)格的方法有： STING算法、 CLIQUE算法和 WAVECLUSTER算法。如果數(shù)據(jù)粒度比較細，處理的代價會明顯增加，而且該算法沒有考慮子單元和其他相鄰單元之間的關(guān)系。 遼寧省物流航運管理系統(tǒng)工程重點實驗室 基于模型的聚類方法 ?1. 統(tǒng)計學(xué)方法 ?從統(tǒng)計學(xué)的觀點看，聚類分析是通過數(shù)據(jù)建模簡化數(shù)據(jù)的一種方法。該判定將對象臨時置于每個節(jié)點，并計算劃分結(jié)果的分類效用。 ?在聚類分析中經(jīng)常被用到的神經(jīng)網(wǎng)絡(luò)的方法有： Kohonen自組織神經(jīng)網(wǎng)絡(luò) 競爭神經(jīng)網(wǎng)絡(luò) 自組織共振神經(jīng)網(wǎng)絡(luò) ?這些方法都涉及有競爭的神經(jīng)單元。 ?如果我們將權(quán)重看作定義的一個標本，那么新的對象被分配給具有最近標本的簇。 ?主要分為兩類：一類是蟻群算法或蟻群優(yōu)化（ Ant Colony Optimization, ACO），另一類稱為粒子群算法（ Particle Swarm Optimization, PSO）。 ?kmeans算法的工作過程說明如下： ?首先從 n個數(shù)據(jù)對象任意選擇 k個對象作為初始聚類中心； ?而對于所剩下其它對象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的聚類中心所代表的聚類； 遼寧省物流航運管理系統(tǒng)工程重點實驗室 kmeans聚類方法 ?然后再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）； ?不斷重復(fù)這一過程直到標準測度函數(shù)開始收斂為止。如果 Σ1存在，則馬氏距離為 () ()ij p p? ???11 ( ) ( )1niji j k i k jkx x x xn??? ? ?? ?21( , ) ( ) ( )TM i j i j i jd x x x x x x?? ? ? ?遼寧省物流航運管理系統(tǒng)工程重點實驗室 kmeans聚類方法 ? (Canberra Distance) () ?定義 準則函數(shù) ? () 11( , ) p ik jkL i jk ik jkxxd x x p x x??? ??? ?21,ikii x CE d x z??? ?? ?設(shè)待聚類的數(shù)據(jù)集為 X={x1, x2, ..., xn}， 將其劃分為 k個簇Ci， 均值分別為 zi， 即 zi為簇 Ci的中心 (i=1, 2, … , k)。在一次迭代中產(chǎn)生的最佳對象集合成為下次迭代的中心點。 ?替換的總代價是所有非中心點對象所產(chǎn)生的代價之和。 遼寧省物流航運管理系統(tǒng)工程重點實驗室 AGNES聚類方法 ?AGNES算法是凝聚的層次聚類方法 。 ?在 DIANA方法處理過程中，所有的對象初始都放在一個簇中。 ? Step5 循環(huán) Step2到 Step4直到?jīng)]有新的 old party的點分配給 splinter group； ? Step6 splinter group和 old party為被選中的簇分裂成的兩個簇，與其他簇一起組成新的簇集合。例如，已知半徑 ? ， MitPts， q是一個核心對象， p1是從 q關(guān)于 ? 和 MitPts直接密度可達的，若 p是從 p1關(guān)于 ? 和 MitPts直接密度可達的，則對象 p是從 q關(guān)于 ? 和 MitPts間接密度可達的。 遼寧省物流航運管理系統(tǒng)工程重點實驗室 DBSCAN聚類方法 ?DBSCAN算法描述： ?輸入：包含 n個數(shù)據(jù)對象的數(shù)據(jù)庫，半徑 ?，最少數(shù)目MinPts ?輸出：所有達到密度要求的簇 ?處理流程： ?Step1 從數(shù)據(jù)庫中抽取一個未處理的點； ?Step2 IF抽出的點是核心點 THEN找出所有從該點密度可達的對象，形成一個簇； ?Step3 ELSE抽出的點是邊緣點（非核心對象），跳出本次循環(huán)，尋找下一個點； ?Step4 循環(huán) Step1到 Step3直到所有點都被處理； 遼寧省物流航運管理系統(tǒng)工程重點實驗室 小結(jié) ?聚類分析作為一種非常重要的數(shù)據(jù)挖掘模型，在很多領(lǐng)域都廣泛應(yīng)用，本章對聚類方法的基本理論、常見分類做出詳細說明，主要描述了基于劃分的聚類方法、基于層次的聚類方法、基于密度的聚類方法、基于網(wǎng)格的聚類方法和基于模型的聚類方法。 遼寧省物流航運管理系統(tǒng)工程重點實驗室 DBSCAN聚類方法 ?DBSCAN通過檢查數(shù)據(jù)集中每個對象的 ? 鄰域來尋找聚類。 遼寧省物流航運管理系統(tǒng)工程重點實驗室 DBSCAN聚類方法 ?定義 對象的 ? 鄰域：給定對象在半徑 ? 內(nèi)的區(qū)域。同時，它使用下面兩種測度方法。 ?在聚類中 ， 用戶能定義希望得到的簇數(shù)目作為一個結(jié)束條件 。 nih ji hj= 1=TC C?遼寧省物流航運管理系統(tǒng)工程重點實驗室 kmedoids聚類方法 ?在 PAM算法中 ， 可以把過程分為兩個步驟： ?（ 1） 建立：隨機尋找 k個中心點作為初始的簇中心點 。如果 Oj依然離 Om最近，那對象的隸屬不發(fā)生變化； ?第四種情況： ?假設(shè)