【正文】 不包含在任何簇中的對(duì)象被認(rèn)為是 “ 噪聲 ” 。 ?這種方法可以過濾噪聲孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。 ?聚類過程中， DIANA算法將用到如下兩種測度方法： ? 簇的直徑 ： 一個(gè)簇中的任意兩個(gè)數(shù)據(jù)點(diǎn)的距離中的最大值； ? 平均相異度 （平均距離）： ? ?? ? ?? i jCx Cyjijiav g yxnnCCd1),(DIANA算法 算法 92 DIANA（自頂向下分裂算法） 輸入：包含 n個(gè)對(duì)象的數(shù)據(jù)庫，終止條件簇的數(shù)目 k。 ? 這個(gè)過程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。 37 （ 3）比例數(shù)值變量 比例數(shù)值變量 （比例標(biāo)度型變量）： ?一個(gè)比例數(shù)值變量指在非線性的標(biāo)度上取正的度量值的變量，如指數(shù)比例： 38 （ 3）比例數(shù)值變量 在計(jì)算比例數(shù)值變量所描述對(duì)象間的距離時(shí)，有兩種處理方法： 1）將比例數(shù)值變量看作區(qū)間標(biāo)度變量，采用相同的方法處理，但不佳，因?yàn)楸壤叨仁欠蔷€性的； 2）采用對(duì)數(shù)變換 ，對(duì)比例數(shù)值變量進(jìn)行處理，然后將 yif當(dāng)做區(qū)間標(biāo)度變量來處理。 ?二值變量的總數(shù)為 p，則： p=q+r+s+t。 聚類分析中的數(shù)據(jù)類型 ?基本的數(shù)據(jù)結(jié)構(gòu)； ?區(qū)間標(biāo)度變量； ?二元變量； ?符號(hào)型、順序型和比例數(shù)值型變量； ?混合數(shù)據(jù)類型。 第 9 章 聚類分析 第 9 章 什么是聚類分析？ 聚類分析中的數(shù)據(jù)類型 基于劃分的聚類方法 基于層次的聚類方法 基于密度的聚類方法 3 學(xué)習(xí)目的 ? 理解聚類與分類數(shù)據(jù)挖掘的區(qū)別。 1. 基本的數(shù)據(jù)結(jié)構(gòu)？ 12 基本的數(shù)據(jù)結(jié)構(gòu) 許多基于內(nèi)存的聚類算法選擇如下兩種具有代表性的數(shù)據(jù)結(jié)構(gòu)： （ 1）數(shù)據(jù)矩陣； （ 2）相異度矩陣 。 27 對(duì)稱？不對(duì)稱？ ?如果一個(gè)二值變量取 0或 1所表示的內(nèi)容同等價(jià)值，且有相同的權(quán)重，則該二元變量是對(duì)稱的。 5. 混合數(shù)據(jù)類型？ 40 混合數(shù)據(jù)類型 混合數(shù)據(jù)類型： ?在實(shí)際數(shù)據(jù)庫中，數(shù)據(jù)對(duì)象往往是用復(fù)合數(shù)據(jù)類型來描述的，而且常常包括以上六種數(shù)據(jù)類型：區(qū)間標(biāo)度變量、對(duì)稱二元變量、不對(duì)稱二元變量、符號(hào)類型、順序類型和比例數(shù)值類型。 51 K平均聚類算法 通常選擇均方差作為收斂準(zhǔn)則函數(shù)： 這個(gè)準(zhǔn)則試圖使得生成的結(jié)果盡可能地緊湊和獨(dú)立：當(dāng)結(jié)果簇是密集的，且簇與簇之間區(qū)別明顯時(shí)，算法的效果較好。 輸出： k個(gè)簇，達(dá)到終止條件規(guī)定簇?cái)?shù)目。 ?代表算法有： DBSCAN、 OPTICS、 DENCLUE算法等。 87 DBSCAN算法描述 ? DBSCAN通過檢查數(shù)據(jù)集中每個(gè)對(duì)象的 ε鄰域來尋找聚類。 86 基于密度的方法： DBSCAN 定義 6： 噪聲： 一個(gè)基于密度的簇是基于密度可達(dá)性的最大的密度相連對(duì)象的集合。 ?基于密度的方法 ：只要一個(gè)區(qū)域中點(diǎn)的密度（對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目）超過某個(gè)閾值，就將其加到與之相近的聚類中去。 (1) 將每個(gè)對(duì)象當(dāng)成一個(gè)初始簇； (2) REPEAT (3) 根據(jù)兩個(gè)簇中最近的數(shù)據(jù)點(diǎn)找到最近的兩個(gè)簇； (4) 合并兩個(gè)簇，生成新的簇的集合； (5) UNTIL 達(dá)到定義的簇的數(shù)目； AGNES算法 AGNES算法示意圖 DIANA算法 ?DIANA 算法：與 AGNES算法相反，初始所有節(jié)點(diǎn)都在一個(gè)大簇中，根據(jù)某些準(zhǔn)則被一步步地分解，直到達(dá)到初始設(shè)定的簇?cái)?shù)目。 49 K平均聚類算法 50 K平均聚類算法 算法的基本思想： ? 首先，隨機(jī)的選擇 k個(gè)對(duì)象，每個(gè)對(duì)象初始的代表了一個(gè)簇的平均值； ?對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇； ?然后重新計(jì)算每個(gè)簇的平均值。 36 順序變量的相異度 順序變量的處理與區(qū)間標(biāo)度變量非常類似，假設(shè) f是用于描述 n個(gè)對(duì)象的一組順序變量之一，關(guān)于 f的相異度計(jì)算如下： 接下來就可以用區(qū)間標(biāo)度變量中所描述的任意一組距離度量方法進(jìn)行計(jì)算相異度。 26 二元變量的相異度計(jì)算 其中： ?q表示在對(duì)象 i和對(duì)象 j中均取 1的二值變量個(gè)數(shù)； ?r表示在對(duì)象 i取 1但對(duì)象 j中取 0的二值變量個(gè)數(shù)； ?s表示在對(duì)象 i中取 0而在對(duì)象 j中取 1的二值變量個(gè)數(shù)； ?t則表示在對(duì)象 i和對(duì)象 j中均取 0的二值變量個(gè)數(shù)。 ?聚類方法的質(zhì)量也可以用它發(fā)現(xiàn)一些或所有隱含模式的能力來度量。 ? 掌握聚類的常用方法。 13 （ 1）數(shù)據(jù)矩陣 數(shù)據(jù)矩陣： 是一個(gè)對(duì)象 — 屬性結(jié)構(gòu)，由 n個(gè)對(duì)象組成，如：人；每個(gè)