《模式識(shí)別_第二章_聚類分析PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《模式識(shí)別_第二章_聚類分析PPT課件（77頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第二章聚類分析 第二章聚類分析 2 1距離聚類的相關(guān)概念2 2模式相似性的測(cè)度和聚類準(zhǔn)則2 3基于距離閾值的聚類算法2 4層次聚類法2 5動(dòng)態(tài)聚類法2 6聚類結(jié)果的評(píng)價(jià) 2 1距離聚類的相關(guān)概念 定義對(duì)一批沒有標(biāo)出類別的模式樣本集 按照樣本之間的相似程度分類 相似的歸為一類 不相似的歸為另一類 這種分類稱為聚類分析 也稱為無監(jiān)督分類 2 1距離聚類的相關(guān)概念 模式相似 分類的依據(jù) 相似性的含義 把整個(gè)模式樣本集的特征向量看成是分布在特征空間中的一些點(diǎn) 點(diǎn)與點(diǎn)之間的距離即可作為模式相似性的測(cè)量依據(jù) 聚類分析是按不同對(duì)象之間的差異 根據(jù)距離函數(shù)的規(guī)律 大小 進(jìn)行模式分類的 2 1距離聚類的相關(guān)概念 聚類分析的有效性聚類分析方法是否有效 與模式特征向量的分布形式有很大關(guān)系 若向量點(diǎn)的分布是一群一群的 同一群樣本密集 距離很近 不同群樣本距離很遠(yuǎn) 則很容易聚類 若樣本集的向量分布聚成一團(tuán) 不同群的樣本混在一起 則很難分類 對(duì)具體對(duì)象做聚類分析的關(guān)鍵是選取合適的特征 特征選取得好 向量分布容易區(qū)分 選取得不好 向量分布很難分開 2 1距離聚類的相關(guān)概念 兩類模式分類的實(shí)例 一攤黑白圍棋子選顏色作為特征進(jìn)行分類 用 1 代表白 0 代表黑 則很容易分類 選大小作為特征進(jìn)行分類 則白子和黑子的特征相同 不能分類 把白子和黑子分開 2 1距離聚類的相關(guān)概念 特征選擇的維數(shù)在特征選擇中往往會(huì)選擇一些多余的特征 它增加了維數(shù) 從而增加了聚類分析的復(fù)雜度 但對(duì)模式分類卻沒有提供多少有用的信息 在這種情況下 需要去掉相關(guān)程度過高的特征 進(jìn)行降維處理 降維方法如果第i維特征與第j維特征所反映的特征規(guī)律接近 因此可以略去其中的一個(gè)特征 或?qū)⑺鼈兒喜橐粋€(gè)特征 從而使維數(shù)降低一維 2 1距離聚類的相關(guān)概念 模式對(duì)象特征測(cè)量的數(shù)字化計(jì)算機(jī)只能處理離散的數(shù)值 因此根據(jù)識(shí)別對(duì)象的不同 要進(jìn)行不同的數(shù)據(jù)化處理 連續(xù)量的量化 用連續(xù)量來度量的特性 如長(zhǎng)度 重量 面積等等 僅需取其量化值 量級(jí)的數(shù)量化 度量時(shí)不需要詳盡的數(shù)值 而是相應(yīng)地劃分成一些有次序的量化等級(jí)的值 名義尺度 指定性的指標(biāo) 即特征度量時(shí)沒有數(shù)量關(guān)系 也沒有明顯的次序關(guān)系 如黑色和白色的關(guān)系 男性和女性的關(guān)系等 都可將它們分別用 0 和 1 來表示 超過2個(gè)狀態(tài)時(shí) 可用多個(gè)數(shù)值表示 2 2模式相似性的測(cè)度和聚類準(zhǔn)則 2 2 1相似性測(cè)度目的 為了能將模式集劃分成不同的類別 必須定義一種相似性的測(cè)度 來度量同一類樣本間的類似性和不屬于同一類樣本間的差異性 復(fù)習(xí) 已知向量 則 2 2模式相似性的測(cè)度和聚類準(zhǔn)則 2 2 1相似性測(cè)度歐氏距離量綱對(duì)分類的影響 下頁圖例 馬氏距離特點(diǎn) 排除了模式樣本之間的相關(guān)性問題 協(xié)方差矩陣在實(shí)際應(yīng)用中難以計(jì)算明氏距離漢明距離角度相似性函數(shù)Tanimoto測(cè)度 當(dāng)特征的取值僅為0 1兩個(gè)值的特例 特點(diǎn) 反映了幾何上相似形的特征 對(duì)于坐標(biāo)系的旋轉(zhuǎn) 放大和縮小等變化是不變的 1 歐氏距離 Euclid 歐幾里德 簡(jiǎn)稱距離設(shè)X1 X2為兩個(gè)n維模式樣本 注意 1 各特征向量對(duì)應(yīng)的維上應(yīng)當(dāng)是相同的物理量 注意物理量的單位 D Distance 距離越小 越相似 歐氏距離定義為 某些維上物理量采用的單位發(fā)生變化 會(huì)導(dǎo)致對(duì)同樣的點(diǎn)集出現(xiàn)不同聚類結(jié)果的現(xiàn)象 量綱對(duì)分類的影響 圖例 2 解決方法 使特征數(shù)據(jù)標(biāo)準(zhǔn)化 使其與變量的單位無關(guān) 對(duì)n維向量 2 馬氏距離 Maharanobis 平方表達(dá)式 式中 X 模式向量 M 均值向量 C 該類模式總體的協(xié)方差矩陣 M Mean C covariance 表示的概念是各分量上模式樣本到均值的距離 也就是在各維上模式的分散情況 越大 離均值越遠(yuǎn) 優(yōu)點(diǎn) 排除了模式樣本之間的相關(guān)影響 當(dāng)C I時(shí) 馬氏距離為歐氏距離 當(dāng)m 2時(shí) 明氏距離為歐氏距離 n維模式樣本向量Xi Xj間的明氏距離表示為 式中 xik xjk分別表示Xi和Xj的第k個(gè)分量 歐氏 3 明氏距離 Minkowaki 當(dāng)k 2時(shí) 圖示 4 漢明 Hamming 距離 設(shè)Xi Xj為n維二值 1或 1 模式樣本向量 則 兩個(gè)模式向量的各分量取值均不同 Dh Xi Xj n 全相同 Dh Xi Xj 0 式中 xik xjk分別表示Xi和Xj的第k個(gè)分量 漢明距離 5 角度相似性函數(shù) 是模式向量Xi Xj之間夾角的余弦 6 Tanimoto測(cè)度 用于0 1二值特征的情況 相似性測(cè)度函數(shù)的共同點(diǎn)都涉及到把兩個(gè)相比較的向量Xi Xj的分量值組合起來 但怎樣組合并無普遍有效的方法 對(duì)具體的模式分類 需視情況作適當(dāng)選擇 2 2模式相似性的測(cè)度和聚類準(zhǔn)則 2 2 2聚類準(zhǔn)則有了模式的相似性測(cè)度 還需要一種基于數(shù)值的聚類準(zhǔn)則 能將相似的模式樣本分在同一類 相異的模式樣本分在不同的類 試探方法 閾值準(zhǔn)則 聚類準(zhǔn)則函數(shù)法 2 2模式相似性的測(cè)度和聚類準(zhǔn)則 2 2 2聚類準(zhǔn)則試探方法 閾值準(zhǔn)則 憑直觀感覺或經(jīng)驗(yàn) 針對(duì)實(shí)際問題定義一種相似性測(cè)度的閾值 然后按最近鄰規(guī)則指定某些模式樣本屬于某一個(gè)聚類類別 例如對(duì)歐氏距離 它反映了樣本間的近鄰性 但將一個(gè)樣本分到不同類別中的哪一個(gè)時(shí) 還必須規(guī)定一個(gè)距離測(cè)度的閾值作為聚類的判別準(zhǔn)則 2 2模式相似性的測(cè)度和聚類準(zhǔn)則 2 2 2聚類準(zhǔn)則聚類準(zhǔn)則函數(shù)法依據(jù) 由于聚類是將樣本進(jìn)行分類以使類別間可分離性為最大 因此聚類準(zhǔn)則應(yīng)是反映類別間相似性或分離性的函數(shù) 由于類別是由一個(gè)個(gè)樣本組成的 因此一般來說類別的可分離性和樣本的可分離性是直接相關(guān)的 可以定義聚類準(zhǔn)則函數(shù)為模式樣本集 x 和模式類別 Sj j 1 2 c 的函數(shù) 從而使聚類分析轉(zhuǎn)化為尋找準(zhǔn)則函數(shù)極值的最優(yōu)化問題 2 2模式相似性的測(cè)度和聚類準(zhǔn)則 2 2 2聚類準(zhǔn)則聚類準(zhǔn)則函數(shù)法一種聚類準(zhǔn)則函數(shù)J的定義J代表了屬于c個(gè)聚類類別的全部模式樣本與其相應(yīng)類別模式均值之間的誤差平方和 對(duì)于不同的聚類形式 J值是不同的 目的 求取使J值達(dá)到最小的聚類形式 適用范圍 適用于各類樣本密集且數(shù)目相差不多 而不同類間的樣本又明顯分開的情況 聚類準(zhǔn)則函數(shù) 式中 c為聚類類別的數(shù)目 為中樣本數(shù)目 J代表了分屬于c個(gè)聚類類別的全部模式樣本與其相應(yīng)類別模式均值之間的誤差平方和 例1 類內(nèi)誤差平方和很小 類間距離很遠(yuǎn) 可得到最好的結(jié)果 類長(zhǎng)軸兩端距離中心很遠(yuǎn) J值較大 結(jié)果不易令人滿意 錯(cuò)誤分類 例2 另一種情況 有時(shí)可能把樣本數(shù)目多的一類分拆為二 造成錯(cuò)誤聚類 原因 這樣分開 J值會(huì)更小 正確分類 2 3基于距離閾值的聚類算法 2 3 1近鄰聚類法 按最近鄰規(guī)則的簡(jiǎn)單試探法算法討論這種方法的優(yōu)點(diǎn) 計(jì)算簡(jiǎn)單 若模式樣本的集合分布的先驗(yàn)知識(shí)已知 則可通過選取正確的閾值和起始點(diǎn) 以及確定樣本的選取次序等獲得較好的聚類結(jié)果 1 問題 有N個(gè)待分類的模式 要求按距離閾值T分類到以為聚類中心的模式類中 2 算法描述 任取樣本Xi作為第一個(gè)聚類中心的初始值 如令Z1 X1 計(jì)算樣本X2到Z1的歐氏距離 若 定義一新的聚類中心Z2 X2 否則X2 以Z1為中心的聚類 T threshold 2 3 1近鄰聚類法 3 算法特點(diǎn) 2 優(yōu)點(diǎn) 計(jì)算簡(jiǎn)單 一種雖粗糙但快速的方法 1 局限性 很大程度上依賴于第一個(gè)聚類中心的位置選擇 待分類模式樣本的排列次序 距離閾值T的大小以及樣本分布的幾何性質(zhì)等 2 3基于距離閾值的聚類算法 2 3 1按最近鄰規(guī)則的簡(jiǎn)單試探法 近鄰聚類法討論 續(xù) 在實(shí)際中 對(duì)于高維模式樣本很難獲得準(zhǔn)確的先驗(yàn)知識(shí) 因此只能選用不同的閾值和起始點(diǎn)來試探 所以這種方法在很大程度上依賴于以下因素 第一個(gè)聚類中心的位置待分類模式樣本的排列次序距離閾值T的大小樣本分布的幾何性質(zhì) 2 3基于距離閾值的聚類算法 2 3 1按最近鄰規(guī)則的簡(jiǎn)單試探法 近鄰聚類法討論 續(xù) 距離閾值T對(duì)聚類結(jié)果的影響 2 3基于距離閾值的聚類算法 2 3 2最大最小距離算法基本思想 以試探類間歐氏距離為最大作為預(yù)選出聚類中心的條件 2 3基于距離閾值的聚類算法 2 3 2最大最小距離算法 小中取大距離算法 1 問題 已知N個(gè)待分類的模式 分類到聚類中心對(duì)應(yīng)的類別中 2 算法描述 選任意一模式樣本做為第一聚類中心Z1 選擇離Z1距離最遠(yuǎn)的樣本作為第二聚類中心Z2 逐個(gè)計(jì)算各模式樣本與已確定的所有聚類中心之間的距離 并選出其中的最小距離 例當(dāng)聚類中心數(shù)k 2時(shí) 計(jì)算 將樣本按最近距離劃分到相應(yīng)聚類中心對(duì)應(yīng)的類別中 重復(fù)步驟 直到?jīng)]有新的聚類中心出現(xiàn)為止 在所有最小距離中選出最大距離 如該最大值達(dá)到的一定分?jǐn)?shù)比值 閾值T 以上 則相應(yīng)的樣本點(diǎn)取為新的聚類中心 返回 否則 尋找聚類中心的工作結(jié)束 為使聚類中心更有代表性 可取各類的樣本均值作為聚類中心 例k 2時(shí) 思路總結(jié) 先找中心后分類 關(guān)鍵 怎樣開新類 聚類中心如何定 例2 1對(duì)圖示模式樣本用最大最小距離算法進(jìn)行聚類分析 選Z1 X1 距Z1最遠(yuǎn) 選為Z2 計(jì)算T 對(duì)應(yīng)最小距離中的最大值 且 T 選作Z3 結(jié)果 Z1 X1 Z2 X6 Z3 X7 用全體模式對(duì)三個(gè)聚類中心計(jì)算最小距離中的最大值 無 T情況 停止尋找中心 聚類 2 4層次聚類法 HierarchicalClusteringMethod 系統(tǒng)聚類法 分級(jí)聚類法 基本思想每個(gè)樣本先自成一類 將模式樣本按距離準(zhǔn)則逐步分類 類別由多到少 直到獲得合適的分類要求為止 算法 2 4層次聚類法 HierarchicalClusteringMethod 系統(tǒng)聚類法 分級(jí)聚類法 1 算法描述 1 N個(gè)初始模式樣本自成一類 即建立N類 計(jì)算各類之間 即各樣本間 的距離 得一N N維距離矩陣D 0 0 表示初始狀態(tài) G Group 2 假設(shè)已求得距離矩陣D n n為逐次聚類合并的次數(shù) 找出D n 中的最小元素 將其對(duì)應(yīng)的兩類合并為一類 由此建立新的分類 3 計(jì)算合并后新類別之間的距離 得D n 1 4 跳至第2步 重復(fù)計(jì)算及合并 結(jié)束條件 1 取距離閾值T 當(dāng)D n 的最小分量超過給定值T時(shí) 算法停止 所得即為聚類結(jié)果 2 或不設(shè)閾值T 一直將全部樣本聚成一類為止 輸出聚類的分級(jí)樹 2 4層次聚類法 類間距離計(jì)算準(zhǔn)則 距離準(zhǔn)則函數(shù)進(jìn)行聚類合并的一個(gè)關(guān)鍵就是每次迭代中形成的聚類之間以及它們和樣本之間距離的計(jì)算 采用不同的距離函數(shù)會(huì)得到不同的計(jì)算結(jié)果 主要的距離計(jì)算準(zhǔn)則 最短距離法最長(zhǎng)距離法中間距離法重心法類平均距離法 2 問題討論 類間距離計(jì)算準(zhǔn)則 1 最短距離法如H K是兩個(gè)聚類 則兩類間的最短距離定義為 H類中的某個(gè)樣本XH和K類中的某個(gè)樣本XK之間的歐氏距離 DHK H類中所有樣本與K類中所有樣本之間的最小距離 如果K類由I和J兩類合并而成 則 得到遞推公式 2 最長(zhǎng)距離法 若K類由I J兩類合并而成 則 有 3 中間距離法介于最長(zhǎng)與最短的距離之間 如果K類由I類和J類合并而成 則H和K類之間的距離為 4 重心法將每類中包含的樣本數(shù)考慮進(jìn)去 若I類中有nI個(gè)樣本 J類中有nJ個(gè)樣本 則類與類之間的距離遞推式為 定義類間距離的方法不同 分類結(jié)果會(huì)不太一致 實(shí)際問題中常用幾種不同的方法 比較分類結(jié)果 從而選擇一個(gè)比較切合實(shí)際的分類 5 類平均距離法 H類任一樣本Xi和K類任一樣本Xj之間的歐氏距離平方 若K類由I類和J類合并產(chǎn)生 則遞推式為 2 4層次聚類法 舉例 設(shè)有6個(gè)五維模式樣本如下 按最小距離準(zhǔn)則進(jìn)行聚類分析 x1 0 3 1 2 0 x2 1 3 0 1 0 x3 3 3 0 0 1x4 1 1 0 2 0 x5 3 2 1 2 1x6 4 1 1 1 0 計(jì)算各類間歐氏距離 解 1 將每一樣本看作單獨(dú)一類 得 2 將最小距離對(duì)應(yīng)的類和合并為1類 得新的分類 計(jì)算聚類后的距離矩陣D 1 由D 0 遞推出D 1 得距離矩陣D 0 3 將D 1 中最小值對(duì)應(yīng)的類合為一類 得D 2 4 將D 2 中最小值對(duì)應(yīng)的類合為一類 得D 3 若給定的閾值為 D 3 中的最小元素 聚類結(jié)束 若無閾值 繼續(xù)分下去 最終全部樣本歸為一類 可給出聚類過程的樹狀表示圖 層次聚類法的樹狀表示 類間距離閾值增大 分類變粗 2 5動(dòng)態(tài)聚類法 基本思想首先選擇若干個(gè)樣本點(diǎn)作為聚類中心 再按某種聚類準(zhǔn)則 通常采用最小距離準(zhǔn)則 使樣本點(diǎn)向各中心聚集 從而得到初始聚類 然后判斷初始分類是否合理 若不合理 則修改分類 如此反復(fù)進(jìn)行修改聚類的迭代算法 直至合理為止 K 均值算法 或C 均值算法 ISODATA算法 迭代自組織數(shù)據(jù)分析算法 2 5 1K 均值算法 思想 基于使聚類準(zhǔn)則函數(shù)最小化 聚類準(zhǔn)則函數(shù) 聚類集中每一個(gè)樣本點(diǎn)到該類中心的距離平方之和 算法 K 均值算法的聚類準(zhǔn)則 聚類中心的選擇應(yīng)使準(zhǔn)則函數(shù)J極小 即使Jj的值極小 2 5 1K 均值算法 對(duì)于第j個(gè)聚類集 準(zhǔn)則函數(shù)定義為 Sj 第j個(gè)聚類集 域 聚類中心為Zj Nj 第j個(gè)聚類集Sj中所包含的樣本個(gè)數(shù) 對(duì)所有K個(gè)模式類有 應(yīng)有 即 可解得 上式表明 Sj類的聚類中心應(yīng)選為該類樣本的均值 1 算法描述 括號(hào)內(nèi)序號(hào) 迭代運(yùn)算的次序號(hào) 1 任選K個(gè)初始聚類中心 Z1 1 Z2 1 ZK 1 2 按最小距離原則將其余樣品分配到K個(gè)聚類中心中的某一個(gè) 即 注意 k 迭代運(yùn)算次序號(hào) K 聚類中心的個(gè)數(shù) Nj 第j類的樣本數(shù) 3 計(jì)算各個(gè)聚類中心的新向量值 4 如果 則回到 2 將模式樣本逐個(gè)重新分類 重復(fù)迭代計(jì)算 這里 分別計(jì)算K個(gè)聚類中的樣本均值向量 故稱K 均值算法 算法收斂 計(jì)算完畢 如果 聚類過程中 聚類中心位置或個(gè)數(shù)發(fā)生變化 2 算法討論結(jié)果受到所選聚類中心的個(gè)數(shù)和其初始位置 以及模式樣本的幾何性質(zhì)及讀入次序等的影響 實(shí)際應(yīng)用中需要試探不同的K值和選擇不同的聚類中心起始值 例2 3 已知20個(gè)模式樣本如下 試用K 均值算法分類 解 取K 2 并選 計(jì)算距離 聚類 可得到 計(jì)算新的聚類中 從新的聚類中心得 有 計(jì)算聚類中心 返回第 步 以Z1 3 Z2 3 為中心進(jìn)行聚類 以新的聚類中心分類 求得的分類結(jié)果與前一次迭代結(jié)果相同 計(jì)算新聚類中心向量值 聚類中心與前一次結(jié)果相同 即 故算法收斂 得聚類中心為 結(jié)果圖示 圖2 10K 均值算法聚類結(jié)果 2 5 1K 均值算法 2 算法討論K 均值算法的結(jié)果受如下選擇的影響 所選聚類的數(shù)目聚類中心的初始分布模式樣本的幾何性質(zhì)讀入次序在實(shí)際應(yīng)用中 需要試探不同的K值和選擇不同的聚類中心的起始值 如果模式樣本可以形成若干個(gè)相距較遠(yuǎn)的孤立的區(qū)域分布 一般都能得到較好的收斂效果 K 均值算法比較適合于分類數(shù)目已知的情況 上述K 均值算法 其類型數(shù)目假定已知為K個(gè) 當(dāng)K未知時(shí) 可以令K逐漸增加 此時(shí)Jj會(huì)單調(diào)減少 最初減小速度快 但當(dāng)K增加到一定數(shù)值時(shí) 減小速度會(huì)減慢 直到K 總樣本數(shù)N時(shí) Jj 0 Jj K關(guān)系曲線如下圖 3 聚類準(zhǔn)則函數(shù)Jj與K的關(guān)系曲線 曲線的拐點(diǎn)A對(duì)應(yīng)著接近最優(yōu)的K值 J值減小量 計(jì)算量以及分類效果的權(quán)衡 并非所有的情況都容易找到關(guān)系曲線的拐點(diǎn) 迭代自組織的數(shù)據(jù)分析算法可以確定模式類的個(gè)數(shù)K 2 5 2ISODATA算法 與K 均值算法的比較K 均值算法通常適合于分類數(shù)目已知的聚類 而ISODATA算法則更加靈活 從算法角度看 ISODATA算法與K 均值算法相似 聚類中心都是通過樣本均值的迭代運(yùn)算來決定的 ISODATA算法加入了一些試探步驟 并且可以結(jié)合成人機(jī)交互的結(jié)構(gòu) 使其能利用中間結(jié)果所取得的經(jīng)驗(yàn)更好地進(jìn)行分類 2 5 2ISODATA算法 基本思路 1 選擇某些初始值 可選不同的參數(shù)指標(biāo) 也可在迭代過程中人為修改 以將N個(gè)模式樣本按指標(biāo)分配到各個(gè)聚類中心中去 2 計(jì)算各類中諸樣本的距離指標(biāo)函數(shù) 按最近鄰規(guī)則進(jìn)行分類 3 5 按給定的要求 將前一次獲得的聚類集進(jìn)行分裂和合并處理 4 為分裂處理 5 為合并處理 從而獲得新的聚類中心 6 重新進(jìn)行迭代運(yùn)算 計(jì)算各項(xiàng)指標(biāo) 判斷聚類結(jié)果是否符合要求 經(jīng)過多次迭代后 若結(jié)果收斂 則運(yùn)算結(jié)束 算法特點(diǎn)加入了試探性步驟 組成人機(jī)交互的結(jié)構(gòu) 可以通過類的自動(dòng)合并與分裂得到較合理的類別數(shù) 算法共分十四步 第一 六步 預(yù)選參數(shù) 進(jìn)行初始分類 為合并和分裂準(zhǔn)備必要的數(shù)據(jù) 第七步 決定下一步是進(jìn)行合并還是進(jìn)行分裂 第八 十步 分裂算法 第十一 十三步 合并算法 第十四步 決定算法是否結(jié)束 算法描述 設(shè)有N個(gè)模式樣本X1 X2 XN 預(yù)選參數(shù) 進(jìn)行初始分類 第一步 預(yù)選NC個(gè)聚類中心 NC也是聚類過程中實(shí)際的聚類中心個(gè)數(shù) 預(yù)選指標(biāo) K 希望的聚類中心的數(shù)目 N 每個(gè)聚類中應(yīng)具有的最少樣本數(shù) 若樣本少于 N 則該類不能作為一個(gè)獨(dú)立的聚類 應(yīng)刪去 S 一個(gè)聚類域中樣本距離分布的標(biāo)準(zhǔn)差閾值 標(biāo)準(zhǔn)差向量的每一分量反映樣本在特征空間的相應(yīng)維上 與聚類中心的位置偏差 分散程度 要求每一聚類內(nèi) 其所有分量中的最大分量應(yīng)小于 S 否則該類將被分裂為兩類 C 兩聚類中心之間的最小距離 若兩類中心之間距離小于 C 則合并為一類 L 在一次迭代中允許合并的聚類中心的最大對(duì)數(shù) I 允許迭代的次數(shù) 第二步 把N個(gè)樣本按最近鄰規(guī)則分配到NC個(gè)聚類中 若 則 第三步 若Sj中的樣本數(shù)Nj N 則取消該類 并且NC減去1 第四步 修正各聚類中心值 第五步 計(jì)算Sj類的類內(nèi)平均距離 第六步 計(jì)算總體平均距離 即全部樣本到各自聚類中心距離的平均距離 3 如果迭代的次數(shù)是偶數(shù) 或NC 2K 即聚類中心數(shù)目大于或等于希望數(shù)的兩倍 則跳到第十一步 合并 否則進(jìn)入第八步 分裂 第七步 判決是進(jìn)行分裂還是進(jìn)行合并 決定迭代步驟等 判斷分裂還是合并 1 如迭代已達(dá)I次 最后一次 置 C 0 跳到第十一步 合并 2 若NC K 2 即聚類中心小于或等于希望數(shù)的一半 進(jìn)入第八步 分裂 C 兩聚類中心之間的最小距離 NC 預(yù)選的聚類中心數(shù) I 允許迭代的次數(shù) K 希望的聚類中心的數(shù)目 分裂處理 第八步 計(jì)算每個(gè)聚類中樣本距離的標(biāo)準(zhǔn)差向量 對(duì)第Sj類有 分量 是聚類數(shù) 是維數(shù) 特征個(gè)數(shù) 第九步 求每個(gè)標(biāo)準(zhǔn)差向量的最大分量 j的最大分量記為 jmax j 1 2 NC 第十步 在最大分量集中 如有 1 和 即類內(nèi)平均距離大于總體平均距離 并且Sj類中樣本數(shù)很大 說明Sj類樣本在對(duì)應(yīng)方向上的標(biāo)準(zhǔn)差大于允許的值 此時(shí) 又滿足以下兩個(gè)條件之一 2 即聚類數(shù)小于或等于希望數(shù)目的一半 則將Zj分裂成兩個(gè)新的聚類中心和 并且NC加1 其中 N 每個(gè)聚類中應(yīng)具有的最少樣本數(shù) S 聚類域中樣本距離分布的標(biāo)準(zhǔn)差閾值 分裂系數(shù) 若完成了分裂運(yùn)算 迭代次數(shù)加1 跳回第二步 否則 繼續(xù) 按鄰近規(guī)則聚類 合并處理 第十一步 計(jì)算所有聚類中心之間的距離 Si類和Sj類中心間的距離為 第十二步 比較所有Dij與 C的值 將小于 C的Dij按升序排列 第十三步 如果將距離為的兩類合并 得到新的聚類中心為 C 兩聚類中心之間的最小距離 每合并一對(duì) NC減1 判斷結(jié)束 第十四步 若是最后一次運(yùn)算 迭代次數(shù)為I 算法結(jié)束 否則 有兩種情況 1 需要由操作者修改輸入?yún)?shù)時(shí) 試探性步驟 跳到第一步 2 輸入?yún)?shù)不需改變時(shí) 跳到第二步 按鄰近規(guī)則聚類 此時(shí) 選擇兩者之一 迭代次數(shù)加1 然后繼續(xù)進(jìn)行運(yùn)算 2 5 2ISODATA算法 例2 4 舉例 對(duì)如圖模式樣本用ISODATA算法進(jìn)行分類 1 評(píng)價(jià)的重要性 1 對(duì)高維特征向量樣本 不能直觀看清聚類效果時(shí) 2 人機(jī)交互系統(tǒng)中 需要迅速地判斷中間結(jié)果 及時(shí)指導(dǎo)輸入?yún)?shù)的改變 較快地獲得較好的聚類結(jié)果 2 6聚類結(jié)果的評(píng)價(jià) 2 6聚類結(jié)果的評(píng)價(jià) 2 迅速評(píng)價(jià)聚類結(jié)果 在上述迭代運(yùn)算中是很重要的 特別是具有高維特征向量的模式 不能直接看清聚類效果 因此 可考慮用以下幾個(gè)指標(biāo)來評(píng)價(jià)聚類效果 聚類中心之間的距離距離值大 通?？煽紤]分為不同類聚類域中的樣本數(shù)目樣本數(shù)目少且聚類中心距離遠(yuǎn) 可考慮是否為噪聲聚類域內(nèi)樣本的距離方差方差過大的樣本可考慮是否屬于這一類討論 模式聚類目前還沒有一種通用的放之四海而皆準(zhǔn)的準(zhǔn)則 往往需要根據(jù)實(shí)際應(yīng)用來選擇合適的方法 結(jié)束 同學(xué)們 來學(xué)校和回家的路上要注意安全 同學(xué)們 來學(xué)校和回家的路上要注意安全