模式識別_第二章_聚類分析PPT課件

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