【正文】 然后， DBSCAN反復(fù)地尋找從這些核心對(duì)象直接密度可達(dá)的對(duì)象，這個(gè)過程可能涉及一些密度可達(dá)簇的合并。 ?定義 直接密度可達(dá)：給定一個(gè)對(duì)象集合 D，如果 p是在q的 ? 鄰域內(nèi)，而 q是一個(gè)核心對(duì)象，我們說對(duì)象 p從對(duì)象 q出發(fā)是直接密度可達(dá)的。 ?2. 平均相異度（平均距離）： ? () ?其中： davg(x,C)表示點(diǎn) x在簇 C中的平均相異度， n為簇 C中點(diǎn)的個(gè)數(shù)， d(x, y)為點(diǎn) x與點(diǎn) y之間的距離（如歐式距離）。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 DIANA聚類方法 ?DIANA算法屬于分裂的層次聚類。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 kmedoids聚類方法 ? kmedoids算法描述： ? 輸入：聚類個(gè)數(shù) k，以及包含 n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù) ? 輸出：滿足方差最小標(biāo)準(zhǔn)的 k個(gè)聚類 ? 處理流程： ? Step1 從 n個(gè)數(shù)據(jù)對(duì)象任意選擇 k個(gè)對(duì)象作為初始簇中心點(diǎn)； ? Step2 指派每個(gè)剩余的對(duì)象給離它最近的中心點(diǎn)所代表的簇； ? Step3 選擇一個(gè)未被選擇的中心點(diǎn)對(duì)象 Oi； ? Step4 選擇一個(gè)未被選擇過的非中心點(diǎn)對(duì)象 Oh； ? Step5 計(jì)算用 Oh替代 Oi的總代價(jià)并記錄在集合 S中； ? Step6 循環(huán) Step4到 Step5直到所有的非中心點(diǎn)都被選擇過； ? Step7 循環(huán) Step3到 Step6直到所有的中心點(diǎn)都被選擇過； ? Step8 IF在 S中的所有非中心點(diǎn)代替所有中心點(diǎn)后計(jì)算出的總代價(jià)有小于 0的存在， THEN找出 S的中心點(diǎn)，形成一個(gè)新的 k個(gè)中心點(diǎn)的集合。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 kmedoids聚類方法 ?每當(dāng)重新分配發(fā)生時(shí)， E所產(chǎn)生的差別對(duì)代價(jià)函數(shù)會(huì)有影響。對(duì)可能的各種組合，估算聚類結(jié)果的質(zhì)量。 1/1( , ) ( | | )pqqi j ik jkkd x x x x????遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 kmeans聚類方法 ?（ Euclidean Distance） ?當(dāng)明氏距離中 q=2時(shí)，公式 。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 ? kmeans聚類方法 ? kmedoids聚類方法 ? AGNES聚類方法 ? DIANA聚類方法 ? DBSCAN聚類方法 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 kmeans聚類方法 ?kmeans算法接受輸入量 k，然后將 n個(gè)數(shù)據(jù)對(duì)象劃分為 k個(gè)聚類以便使得所獲得的聚類滿足：同一聚類中的對(duì)象相似度較高，而不同聚類中的對(duì)象相似度較小。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 基于模型的聚類方法 ?3. 基于群的聚類方法 ?基于群的聚類方法是進(jìn)化計(jì)算的一個(gè)分支。 ?一個(gè)層次內(nèi)的聯(lián)系是抑制式的，以便在任何簇中只有一個(gè)單元是活躍的。 ?COBWEB不適用于聚類大型數(shù)據(jù)庫(kù)的數(shù)據(jù)。它的輸入對(duì)象用“分類屬性 — 值”對(duì)來描述。 ?在這類算法中 ， 聚類的數(shù)目也根據(jù)統(tǒng)計(jì)數(shù)字自動(dòng)決定 ，噪聲和孤立點(diǎn)也是通過統(tǒng)計(jì)數(shù)字來分析 。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 ?STING算法效率高，是獨(dú)立于查詢的，且利于并行處理和增量更新。 ?缺點(diǎn)是只能發(fā)現(xiàn)邊界是水平或垂直的簇，而不能檢測(cè)到斜邊界。 ?然后反復(fù)地尋找從這些核心對(duì)象直接密度可達(dá)的對(duì)象，當(dāng)沒有新的點(diǎn)可以被添加到任何簇時(shí)，該過程結(jié)束。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 ?基于密度的方法與其它方法的一個(gè)根本區(qū)別是：它不是基于各種各樣的距離的 ， 而是基于密度的 ， 這樣就能克服基于距離的算法只能發(fā)現(xiàn)球狀聚類 ， 對(duì)發(fā)現(xiàn)任意形狀的聚類則顯得不足的缺點(diǎn) 。 通過多個(gè)有代表性的點(diǎn) ， 簇的形狀可以更好地被表示出來 。 ?其核心是用一個(gè)聚類特征三元組表示一個(gè)簇的有關(guān)信息 ，從而使簇中的點(diǎn)可用對(duì)應(yīng)的聚類特征表示 。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 ?凝聚的方法，也稱為自底向上的方法，初始時(shí)每個(gè)對(duì)象都被看成是單獨(dú)的一個(gè)簇，然后通過逐步的合并相近的對(duì)象或簇形成越來越大的簇，直到所有的對(duì)象都在一個(gè)簇中，或者達(dá)到某個(gè)終止條件為止。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 基于劃分的聚類方法 ?kmeans算法只有在平均值被定義的情況下才能使用，因此該算法容易受到孤立點(diǎn)的影響， kmedoids算法采用簇中最中心的位置作為代表點(diǎn)而不是采用對(duì)象的平均值。領(lǐng)域知識(shí)如何影響聚類分析算法的設(shè)計(jì)是很重要的一個(gè)研究方面。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 對(duì)聚類算法性能的要求 ?5. 能夠處理異常數(shù)據(jù) 現(xiàn)實(shí)數(shù)據(jù)庫(kù)中常常包含有異常數(shù)據(jù)，例如數(shù)據(jù)不完整、缺乏某些字段的值，甚至是包含錯(cuò)誤數(shù)據(jù)現(xiàn)象。值得注意的是，當(dāng)算法不能處理大數(shù)據(jù)量時(shí)，用抽樣的方法來彌補(bǔ)也不是一個(gè)好主意，因?yàn)樗ǔ?huì)導(dǎo)致歪曲的結(jié)果。 ?對(duì)于復(fù)雜結(jié)構(gòu)的多維數(shù)據(jù)可以通過聚類的方法將數(shù)據(jù)聚集后構(gòu)造出邏輯庫(kù)，使復(fù)雜結(jié)構(gòu)數(shù)據(jù)標(biāo)準(zhǔn)化，為某些數(shù)據(jù)挖掘方法（如關(guān)聯(lián)規(guī)則、粗糙集方法）提供預(yù)處理。數(shù)據(jù)挖掘技術(shù)與應(yīng)用 陳燕教授 第 6章 聚類分析方法與應(yīng)用 大連海事大學(xué) 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 本章提綱 聚類分析的基礎(chǔ)理論 聚類分析的方法 應(yīng)用聚類分析方法 小結(jié) 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 ? 聚類分析的定義 ? 對(duì)聚類算法性能的要求 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 聚類分析的定義 ?聚類（ Clustering）是將數(shù)據(jù)劃分成群組的過程。 ?為了滿足某些數(shù)據(jù)挖掘算法的需要，我們需要對(duì)連續(xù)的數(shù)據(jù)進(jìn)行離散化處理，使條件屬性和決策屬性值簡(jiǎn)約化、規(guī)范化。 ?2. 處理不同字段類型的能力 算法不僅要能處理數(shù)值型的字段，還要有處理其他類型字段的能力。有一些數(shù)據(jù)算法可能會(huì)對(duì)這些數(shù)據(jù)很敏感，從而導(dǎo)致錯(cuò)誤的分析結(jié)果。 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 ? 基于劃分的聚類方法 ? 基于層次的聚類方法 ? 基于密度的聚類方法 ? 基于網(wǎng)格的聚類方法 ? 基于模型的聚類方法 遼寧省物流航運(yùn)管理系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室 基于劃分的聚類方法 ?給定一個(gè)含有 N個(gè)對(duì)象的數(shù)據(jù)集，以及要生成的簇的數(shù)目 K。 ?因此，與 kmeans算法相比，當(dāng)存在噪聲和孤立點(diǎn)數(shù)據(jù)時(shí)， kmedoids算法要較 kmeans算法健壯，而且沒有kmeans算法那樣容易受到極端數(shù)據(jù)的影響。層次凝聚的代表是AGNES（ AGglomerative NESting）算法。 它通過構(gòu)造滿足分支因子和簇直徑限制的聚類特征樹來求聚類 。 ?再使用層次聚類算法中的凝聚算法 。 ?基于密度的聚類方法從對(duì)象分布區(qū)域的密度著手 ， 對(duì)于給定類中的數(shù)據(jù)點(diǎn) ， 如果在給定范圍的區(qū)域中 ， 對(duì)象或數(shù)據(jù)點(diǎn)的密度超過某一閾值就繼續(xù)聚類 。不被包含在任何簇中的對(duì)象被認(rèn)為是“噪聲”。此外，在處理高維數(shù)據(jù)時(shí)，網(wǎng)格單元的數(shù)目會(huì)隨著屬性維數(shù)的增長(zhǎng)而成指數(shù)增長(zhǎng)。 ?但由于 STING采用