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