模式識(shí)別第2章課件聚類分析v.ppt

第二章聚類分析 分類與聚類的區(qū)別 分類 用已知類別的樣本訓(xùn)練集來設(shè)計(jì)分類器 監(jiān)督學(xué)習(xí) 聚類 集群 用事先不知類別的樣本 而利用樣本的先驗(yàn)知識(shí)來構(gòu)造分類器 無(wú)監(jiān)督學(xué)習(xí) 2 1聚類分析的概念 基本思想 對(duì)一批沒有標(biāo)明類別及類數(shù)的模式樣本集 根據(jù)模式間的相似程度 按照物以類聚 人以群分的思想 將相似的模式分為一類 不相似的分為另一類 特征的類型 1 低層特征 無(wú)序尺度 有明確的數(shù)量和數(shù)值 有序尺度 有先后 好壞的次序關(guān)系 如酒分為上 中 下三個(gè)等級(jí) 名義尺度 無(wú)數(shù)量 無(wú)次序關(guān)系 如有紅 黃兩種顏色2 中層特征 經(jīng)過計(jì)算 變換得到的特征3 高層特征 在中層特征的基礎(chǔ)上有目的的經(jīng)過運(yùn)算形成例如 椅子的重量 體積 比重體積與長(zhǎng) 寬 高有關(guān) 比重與材料 紋理 顏色有關(guān) 這里低 中 高三層特征都有了 方法的有效性 特征選取不當(dāng)特征過少特征過多量綱問題 主要聚類分析技術(shù) 譜系法 系統(tǒng)聚類 層次聚類法 基于目標(biāo)函數(shù)的聚類法 動(dòng)態(tài)聚類 圖論聚類法模糊聚類分析法 2 2模式相似度度量 各種距離表示相似性 絕對(duì)值距離已知兩個(gè)樣本xi xi1 xi2 xi3 xin Txj xj1 xj2 xj3 xjn T 歐幾里德距離 明考夫斯基距離其中當(dāng)q 1時(shí)為絕對(duì)值距離 當(dāng)q 2時(shí)為歐氏距離 切比雪夫距離q趨向無(wú)窮大時(shí)明氏距離的極限情況 馬哈拉諾比斯距離其中xi xj為特征向量 為協(xié)方差 使用的條件是樣本符合正態(tài)分布 夾角余弦為xixj的均值即樣本間夾角小的為一類 具有相似性例 x1 x2 x3的夾角如圖 因?yàn)閤1 x2的夾角小 所以x1 x2最相似 x2 x3 相關(guān)系數(shù)為xixj的均值注意 在求相關(guān)系數(shù)之前 要將數(shù)據(jù)標(biāo)準(zhǔn)化 2 3類的定義和與類間距離 用距離進(jìn)行定義類 書 非監(jiān)督學(xué)習(xí)方法分類 1 基于概率密度函數(shù)估計(jì)的直接方法 不實(shí)用 2 基于樣本間相似性度量的間接聚類方法 兩類間的距離 1 最短距離 兩類中相距最近的兩樣本間的距離 2 最長(zhǎng)距離 兩類中相距最遠(yuǎn)的兩個(gè)樣本間的距離 3 中間距離 最短距離和最長(zhǎng)距離都有片面性 因此有時(shí)用中間距離 設(shè) 1類和 23類間的最短距離為d12 最長(zhǎng)距離為d13 23類的長(zhǎng)度為d23 則中間距離為 上式推廣為一般情況 4 重心距離 均值間的距離5 類平均距離 兩類中各個(gè)元素兩兩之間的距離平方相加后取平均值 6 離差平方和 設(shè)N個(gè)樣品原分q類 則定義第i類的離差平方和為 離差平方和增量 設(shè)樣本已分成 p q兩類 若把 p q合為 r類 則定義離差平方 聚類準(zhǔn)則 類內(nèi)距離越小越好類間距離越大越好一些準(zhǔn)則函數(shù) 聚類分析三要素 相似性測(cè)度聚類準(zhǔn)則聚類算法 2 4聚類的算法 1 根據(jù)相似性閾值和最小距離原則的簡(jiǎn)單聚類法 2 按照最小距離原則不斷進(jìn)行兩類合并的方法 3 依據(jù)準(zhǔn)則函數(shù)的動(dòng)態(tài)動(dòng)態(tài)聚類算法 系統(tǒng)聚類的算法 譜系聚類的算法原理 步驟例 如下圖所示1 設(shè)全部樣本分為6類 2 作距離矩陣D 0 3 求最小元素 4 把 1 3合并 7 1 3 4 6合并 8 4 6 5 作距離矩陣D 1 6 若合并的類數(shù)沒有達(dá)到要求 轉(zhuǎn)3 否則停止 3 求最小元素 4 8 5 2合并 9 2 5 4 6 分解聚類 分解聚類 把全部樣本作為一類 然后根據(jù)相似性 相鄰性分解 目標(biāo)函數(shù)兩類均值方差 N 總樣本數(shù) 1類樣本數(shù) 2類樣本數(shù) 分解聚類框圖 對(duì)分算法 略例 已知21個(gè)樣本 每個(gè)樣本取二個(gè)特征 原始資料矩陣如下表 解 第一次分類時(shí)計(jì)算所有樣本 分別劃到 時(shí)的E值 找出最大的 1 開始時(shí) 2 分別計(jì)算當(dāng)劃入 時(shí)的E值 把劃入 時(shí)有 然后再把劃入時(shí)對(duì)應(yīng)的E值 找出一個(gè)最大的E值 把劃為的E值最大 E 1 56 6 再繼續(xù)進(jìn)行第二 第三次迭代 計(jì)算出E 2 E 3 次數(shù)E值156 6279 16390 904102 615120 116137 157154 108176 159195 2610213 0711212 01 第10次迭代劃入時(shí) E最大 于是分成以下兩類 每次分類后要重新計(jì)算的值 可用以下遞推公式 動(dòng)態(tài)聚類 兼顧系統(tǒng)聚類和分解聚類 一 動(dòng)態(tài)聚類的方法概要 先選定某種距離作為樣本間的相似性的度量 確定評(píng)價(jià)聚類結(jié)果的準(zhǔn)則函數(shù) 給出某種初始分類 用迭代法找出使準(zhǔn)則函數(shù)取極值的最好的聚類結(jié)果 動(dòng)態(tài)聚類框圖 二 代表點(diǎn)的選取方法 代表點(diǎn)就是初始分類的聚類中心數(shù)k 憑經(jīng)驗(yàn)選代表點(diǎn) 根據(jù)問題的性質(zhì) 數(shù)據(jù)分布 從直觀上看來較合理的代表點(diǎn)k 將全部樣本隨機(jī)分成k類 計(jì)算每類重心 把這些重心作為每類的代表點(diǎn) 按密度大小選代表點(diǎn) 以每個(gè)樣本作為球心 以d為半徑做球形 落在球內(nèi)的樣本數(shù)稱為該點(diǎn)的密度 并按密度大小排序 首先選密度最大的作為第一個(gè)代表點(diǎn) 即第一個(gè)聚類中心 再考慮第二大密度點(diǎn) 若第二大密度點(diǎn)距第一代表點(diǎn)的距離大于d1 人為規(guī)定的正數(shù) 則把第二大密度點(diǎn)作為第二代表點(diǎn) 否則不能作為代表點(diǎn) 這樣按密度大小考察下去 所選代表點(diǎn)間的距離都大于d1 d1太小 代表點(diǎn)太多 d1太大 代表點(diǎn)太小 一般選d1 2d 對(duì)代表點(diǎn)內(nèi)的密度一般要求大于T T 0為規(guī)定的一個(gè)正數(shù) 用前k個(gè)樣本點(diǎn)作為代表點(diǎn) 三 初始分類和調(diào)整 選一批代表點(diǎn)后 代表點(diǎn)就是聚類中心 計(jì)算其它樣本到聚類中心的距離 把所有樣本歸于最近的聚類中心點(diǎn) 形成初始分類 再重新計(jì)算各聚類中心 稱為成批處理法 選一批代表點(diǎn)后 依次計(jì)算其它樣本的歸類 當(dāng)計(jì)算完第一個(gè)樣本時(shí) 把它歸于最近的一類 形成新的分類 再計(jì)算新的聚類中心 再計(jì)算第二個(gè)樣本到新的聚類中心的距離 對(duì)第二個(gè)樣本歸類 即每個(gè)樣本的歸類都改變一次聚類中心 此法稱為逐個(gè)處理法 直接用樣本進(jìn)行初始分類 先規(guī)定距離d 把第一個(gè)樣品作為第一類的聚類中心 考察第二個(gè)樣本 若第二個(gè)樣本距第一個(gè)聚類中心距離小于d 就把第二個(gè)樣本歸于第一類 否則第二個(gè)樣本就成為第二類的聚類中心 再考慮其它樣本 根據(jù)樣本到聚類中心距離大于還是小于d 決定分裂還是合并 最佳初始分類 如圖所示 隨著初始分類k的增大 準(zhǔn)則函數(shù)下降很快 經(jīng)過拐點(diǎn)A后 下降速度減慢 拐點(diǎn)A就是最佳初始分類 四 C 平均算法例 已知有20個(gè)樣本 每個(gè)樣本有2個(gè)特征 數(shù)據(jù)分布如下圖 第一步 令C 2 選初始聚類中心為 第三步 根據(jù)新分成的兩類建立新的聚類中心 第四步 轉(zhuǎn)第二步 第二步 重新計(jì)算到z1 2 z2 2 的距離 把它們歸為最近聚類中心 重新分為兩類 第三步 更新聚類中心 第四步 第二步 第三步 更新聚類中心 迭代自組織數(shù)據(jù)分析算法 ISOData 方法步驟 1 任選初始值 中心 C個(gè) 2 將N個(gè)樣本分到C類中 3 計(jì)算距離 4 要求對(duì)中心分裂 合并 新的中心 5 判斷 上機(jī)作業(yè) 已知50個(gè)樣本 隨機(jī)產(chǎn)生 每個(gè)樣本2個(gè)特征 取值在0 10 數(shù)據(jù)如下 用c平均算法和ISODATA算法分類 編程上機(jī) 并畫出分類圖