clustering-資料下載頁
2025-07-15 18:10本頁面
【正文】 n個簇，在結(jié)束的時候有 1個簇，因此在主循環(huán)中有n此迭代，在第 i次迭代中，我們必須在 ni+1個簇中找到最靠近的兩個聚類。另外算法必須計(jì)算所有對象兩兩乊間的距離，因此這個算法的復(fù)雜度為 O(n178。)，該算法對于 n很大的情況是丌適用的。 DIANA算法 ? DIANA（ DIvisive ANAlysis)算法是典型的分裂聚類方法。 ? 在聚類中，用戶能定義希望得到的簇數(shù)目作為一個結(jié)束條件。同時，它使用下面測度方法： 簇的直徑：在一個簇中的任意兩個數(shù)據(jù)點(diǎn)的距離中的最大值。 算法 DIANA（ 自頂向下分裂算法 ） 輸入：包含 n個對象的數(shù)據(jù)庫 ， 終止條件簇的數(shù)目 k。 輸出： k個簇 ， 達(dá)到終止條件規(guī)定簇數(shù)目 。 （ 1） 將所有對象整個當(dāng)成一個初始簇； （ 2） FOR （ i=1。 i≠k。 i++) DO BEGIN （ 3） 在所有簇中挑出具有最大直徑的簇 C； （ 4） 找出 C中與其它點(diǎn)平均相異度最大的一個點(diǎn) p并把 p放入 splinter group， 剩余的放在 old party中； （ 5） . REPEAT （ 6） 在 old party里找出到最近的 splinter group中的點(diǎn)的距離不大于到 old party中最近點(diǎn)的距離的點(diǎn) ， 并將該點(diǎn)加入 splinter group。 （ 7） UNTIL 沒有新的 old party的點(diǎn)被分配給 splinter group； （ 8） splinter group和 old party為被選中的簇分裂成的兩個簇 ， 與其它簇一起組成新的簇集合 。 （ 9） END. 序號 屬性 1 屬性 2 1 1 1 2 1 2 3 2 1 4 2 2 5 3 4 6 3 5 7 4 4 8 4 5 DIANA算法例題 第 1步，找到具有最大直徑的簇，對簇中的每個點(diǎn)計(jì)算平均相異度（假定采用是歐式距離）。 1的平均距離：（ 1+1+++++5） /7= 類似地， 2的平均距離為 ； 3的平均距離為 ； 4的平均距離為 ；5的平均距離為 ； 6的平均距離為 ； 7的平均距離為 ； 8的平均距離為 。 挑出平均相異度最大的點(diǎn) 1放到 splinter group中，剩余點(diǎn)在 old party中。 第 2步，在 old party里找出到最近的 splinter group中的點(diǎn)的距離不大于到 old party中最近的點(diǎn)的距離的點(diǎn)，將該點(diǎn)放入 splinter group中，該點(diǎn)是 2。 第 3步，重復(fù)第 2步的工作， splinter group中放入點(diǎn) 3。 第 4步，重復(fù)第 2步的工作， splinter group中放入點(diǎn) 4。 第 5步，沒有在 old party中的點(diǎn)放入了 splinter group中且達(dá)到終止條件（ k=2），程序終止。如果沒有到終止條件，因該從分裂好的簇中選一個直徑最大的簇繼續(xù)分裂。 步驟 具有最大直徑的簇 splinter group Old party 1 {1， 2， 3， 4， 5， 6， 7， 8} {1} {2， 3， 4， 5， 6， 7， 8} 2 {1， 2， 3， 4， 5， 6， 7， 8} {1， 2} {3， 4， 5， 6， 7， 8} 3 {1， 2， 3， 4， 5， 6， 7， 8} {1， 2， 3} {4， 5， 6， 7， 8} 4 {1， 2， 3， 4， 5， 6， 7， 8} {1， 2， 3， 4} {5， 6， 7， 8} 5 {1， 2， 3， 4， 5， 6， 7， 8} {1， 2， 3， 4} {5， 6， 7， 8} 終止 關(guān)于層次聚類的討論 ?高維災(zāi)難 ?維度非常高時，各個點(diǎn)乊間的距離都近似 ?維度非常高時，各個向量幾乎都正交 ?什么時候會高維？ ? 文本、圖像、基因表達(dá)數(shù)據(jù) 關(guān)于層次聚類的討論 ?停止準(zhǔn)則 ?簇的個數(shù)事先已知 ?自底向上 ? 新合并的簇出現(xiàn)丌合理的情況 – 要求簇內(nèi)所有點(diǎn)到質(zhì)心的距離都大于閾值 ?生成進(jìn)化樹，找出大于閾值的邊 啟發(fā)式課題 ?在本章介紹的聚類算法中，頻繁用到了“質(zhì)心”的概念，對于歐式空間中的向量，我們很容易計(jì)算質(zhì)心。但對于非歐式空間的樣本，比如 string、 text，我們?nèi)绾斡?jì)算一個 cluster的質(zhì)心？ ?Email: 作業(yè) ?請描述 Kmeans算法的原理，并分析其主要缺點(diǎn)。 ?層次聚類的基本策略有哪兩種？分別寫出其算法 ?有監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)的區(qū)別？
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1