【正文】 所有的中心點(diǎn)都被選擇過(guò)； ? Step8 IF在 S中的所有非中心點(diǎn)代替所有中心點(diǎn)后計(jì)算出的總代價(jià)有小于 0的存在， THEN找出 S的中心點(diǎn)，形成一個(gè)新的 k個(gè)中心點(diǎn)的集合。 ? Step9 循環(huán) Step3到 Step8直到?jīng)]有再發(fā)生簇的重新分配，即 S中所有的元素都大于 0。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 AGNES聚類方法 ?AGNES算法是凝聚的層次聚類方法 。 AGNES算法最初將每個(gè)對(duì)象作為一個(gè)簇 ， 然后這些簇根據(jù)某些準(zhǔn)則被一步步地合并 。 ?這是一種單鏈接方法 ， 其每個(gè)簇可以被簇中所有對(duì)象代表 ， 兩個(gè)簇間的相似度由這兩個(gè)不同簇中距離最近的數(shù)據(jù)點(diǎn)對(duì)的相似度來(lái)確定 。 ?聚類的合并過(guò)程反復(fù)進(jìn)行直到所有的對(duì)象最終合并形成一個(gè)簇 。 ?在聚類中 ， 用戶能定義希望得到的簇?cái)?shù)目作為一個(gè)結(jié)束條件 。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 AGNES聚類方法 ?AGNES算法描述： ?輸入：包含 n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)，終止條件簇的數(shù)目 k ?輸出：達(dá)到終止條件規(guī)定的 k個(gè)簇 ?處理流程： ?Step1 將每個(gè)對(duì)象當(dāng)成一個(gè)初始簇； ?Step2 根據(jù)兩個(gè)簇中最近的數(shù)據(jù)點(diǎn)找到最近的兩個(gè)簇； ?Step3 合并兩個(gè)簇，生成新的簇的集合； ?Step4 循環(huán) Step3到 Step4直到達(dá)到定義的簇的數(shù)目。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 DIANA聚類方法 ?DIANA算法屬于分裂的層次聚類。與凝聚的層次聚類相反，它采用一種自頂向下的策略，它首先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來(lái)越小的簇，直到每個(gè)對(duì)象自成一簇，或者達(dá)到了某個(gè)終結(jié)條件，例如達(dá)到了某個(gè)希望的簇?cái)?shù)目，或者兩個(gè)最近簇之間的距離超過(guò)了某個(gè)閾值。 ?在 DIANA方法處理過(guò)程中，所有的對(duì)象初始都放在一個(gè)簇中。根據(jù)一些原則（如簇中最臨近對(duì)象的最大歐式距離），將該簇分裂。簇的分裂過(guò)程反復(fù)進(jìn)行，直到最終每個(gè)新的簇只包含一個(gè)對(duì)象。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 DIANA聚類方法 ?在聚類中，用戶能定義希望得到的簇?cái)?shù)目作為一個(gè)結(jié)束條件。同時(shí)，它使用下面兩種測(cè)度方法。 ?1. 簇的直徑：在一個(gè)簇中的任意兩個(gè)數(shù)據(jù)點(diǎn)都有一個(gè)距離（如歐氏距離），這些距離中的最大值是簇的直徑。 ?2. 平均相異度（平均距離）： ? () ?其中： davg(x,C)表示點(diǎn) x在簇 C中的平均相異度， n為簇 C中點(diǎn)的個(gè)數(shù)， d(x, y)為點(diǎn) x與點(diǎn) y之間的距離（如歐式距離）。 ? ? ? ?,1,1a v g y C y xd x C d x yn ??? ? ?遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 DIANA聚類方法 ? DIANA算法描述： ? 輸入：包含 n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)，終止條件簇的數(shù)目 k輸出：達(dá)到終止條件規(guī)定的 k個(gè)簇 ? 處理流程： ? Step1 將所有對(duì)象整個(gè)當(dāng)成一個(gè)初始簇； ? Step2 在所有簇中挑出具有最大直徑的簇； ? Step3 找出所挑簇里與其他點(diǎn)平均相異度最大的一個(gè)點(diǎn)放入 splinter group，剩余的放入 old party中； ? Step4 在 old party里找出到 splinter group中點(diǎn)的最近距離不大于到 old party中點(diǎn)的最近距離的點(diǎn)，并將該點(diǎn)加入 splinter group。 ? Step5 循環(huán) Step2到 Step4直到?jīng)]有新的 old party的點(diǎn)分配給 splinter group； ? Step6 splinter group和 old party為被選中的簇分裂成的兩個(gè)簇，與其他簇一起組成新的簇集合。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 DBSCAN聚類方法 ?DBSCAN是一個(gè)比較有代表性的基于密度的聚類算法。與劃分和層次聚類方法不同，它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類。 ?下面首先介紹關(guān)于密度聚類涉及的一些定義。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 DBSCAN聚類方法 ?定義 對(duì)象的 ? 鄰域：給定對(duì)象在半徑 ? 內(nèi)的區(qū)域。 ?定義 核心對(duì)象：如果一個(gè)對(duì)象的 ? 鄰域至少包含最小數(shù)目 MinPts個(gè)對(duì)象，則稱該對(duì)象為核心對(duì)象。 ?定義 直接密度可達(dá)：給定一個(gè)對(duì)象集合 D，如果 p是在q的 ? 鄰域內(nèi)，而 q是一個(gè)核心對(duì)象，我們說(shuō)對(duì)象 p從對(duì)象 q出發(fā)是直接密度可達(dá)的。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 DBSCAN聚類方法 ?定義 間接密度可達(dá)的：如果存在一個(gè)對(duì)象鏈 p1, p2, …, pn, p1=q， pn=p，對(duì) pi∈ D， 1≤i≤n， pi+1是從 pi關(guān)于 ? 和 MitPts直接密度可達(dá)的，則對(duì)象 p是從對(duì)象 q關(guān)于 ? 和MinPts密度可達(dá)的。例如，已知半徑 ? ， MitPts， q是一個(gè)核心對(duì)象， p1是從 q關(guān)于 ? 和 MitPts直接密度可達(dá)的，若 p是從 p1關(guān)于 ? 和 MitPts直接密度可達(dá)的，則對(duì)象 p是從 q關(guān)于 ? 和 MitPts間接密度可達(dá)的。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 DBSCAN聚類方法 ?定義 密度相連的：如果對(duì)象集合 D中存在一個(gè)對(duì)象 o，使得對(duì)象 p和 q是從 o關(guān)于 ?和 MitPts密度可達(dá)的，那么對(duì)象 p和 q是關(guān)于 ? 和 MinPts密度相連的。 ?定義 噪聲：一個(gè)基于密度的簇是基于密度可達(dá)性的最大的密度相連對(duì)象的集合。不包含在任何簇中的對(duì)象被認(rèn)為是“噪聲”。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 DBSCAN聚類方法 ?DBSCAN通過(guò)檢查數(shù)據(jù)集中每個(gè)對(duì)象的 ? 鄰域來(lái)尋找聚類。如果一個(gè)點(diǎn) p的 ? 鄰域包含多余 MinPts個(gè)對(duì)象，則創(chuàng)建一個(gè) p作為核心對(duì)象的新簇。然后， DBSCAN反復(fù)地尋找從這些核心對(duì)象直接密度可達(dá)的對(duì)象，這個(gè)過(guò)程可能涉及一些密度可達(dá)簇的合并。當(dāng)沒(méi)有新的點(diǎn)可以被添加到任何簇時(shí)，該過(guò)程結(jié)束。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 DBSCAN聚類方法 ?DBSCAN算法描述： ?輸入：包含 n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)，半徑 ?，最少數(shù)目MinPts ?輸出：所有達(dá)到密度要求的簇 ?處理流程： ?Step1 從數(shù)據(jù)庫(kù)中抽取一個(gè)未處理的點(diǎn)； ?Step2 IF抽出的點(diǎn)是核心點(diǎn) THEN找出所有從該點(diǎn)密度可達(dá)的對(duì)象，形成一個(gè)簇； ?Step3 ELSE抽出的點(diǎn)是邊緣點(diǎn)（非核心對(duì)象），跳出本次循環(huán)，尋找下一個(gè)點(diǎn)； ?Step4 循環(huán) Step1到 Step3直到所有點(diǎn)都被處理； 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 小結(jié) ?聚類分析作為一種非常重要的數(shù)據(jù)挖掘模型，在很多領(lǐng)域都廣泛應(yīng)用，本章對(duì)聚類方法的基本理論、常見(jiàn)分類做出詳細(xì)說(shuō)明，主要描述了基于劃分的聚類方法、基于層次的聚類方法、基于密度的聚類方法、基于網(wǎng)格的聚類方法和基于模型的聚類方法。同時(shí)詳細(xì)介紹了五種聚類方法（包括 kmeans、 kmediods、 AGNES、 DIANA以及 DBSCAN算法）的算法模型及實(shí)例應(yīng)用。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 本章內(nèi)容結(jié)束！