《模式識別第2章課件聚類分析v.ppt》由會員分享，可在線閱讀，更多相關(guān)《模式識別第2章課件聚類分析v.ppt（49頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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