模式識(shí)別詳細(xì)PPT.ppt

《模式識(shí)別詳細(xì)PPT.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《模式識(shí)別詳細(xì)PPT.ppt（712頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1 模式識(shí)別 主講 蔡宣平教授電話 73441 O 73442 H E mail xpcai 單位 電子科學(xué)與工程學(xué)院信息工程系 2 課程對(duì)象 相關(guān)學(xué)科 教學(xué)方法 教學(xué)目標(biāo) 基本要求 教材 參考文獻(xiàn) 關(guān)于本課程的有關(guān)說(shuō)明 3 課程對(duì)象 信息工程專業(yè)本科生的專業(yè)課 學(xué)院碩士研究生的學(xué)位課 學(xué)院博士研究生的必修課之一 4 相關(guān)學(xué)科 統(tǒng)計(jì)學(xué) 概率論 線性代數(shù) 矩陣計(jì)算 形式語(yǔ)言 人工智能 圖像處理 計(jì)算機(jī)視覺(jué)等等 5 教學(xué)方法 著重講述模式識(shí)別的基本概念 基本方法和算法原理 注重理論與實(shí)踐緊密結(jié)合實(shí)例教學(xué) 通過(guò)實(shí)例講述如何將所學(xué)知識(shí)運(yùn)用到實(shí)際應(yīng)用之中 避免引用過(guò)多的 繁瑣的數(shù)學(xué)推導(dǎo) 6 教學(xué)目標(biāo) 掌握模式識(shí)別的基本概念和方法 有效地運(yùn)用所學(xué)知識(shí)和方法解決實(shí)際問(wèn)題 為研究新的模式識(shí)別的理論和方法打下基礎(chǔ) 7 基本要求 基本 完成課程學(xué)習(xí) 通過(guò)考試 獲得學(xué)分 提高 能夠?qū)⑺鶎W(xué)知識(shí)和內(nèi)容用于課題研究 解決實(shí)際問(wèn)題 飛躍 通過(guò)模式識(shí)別的學(xué)習(xí) 改進(jìn)思維方式 為將來(lái)的工作打好基礎(chǔ) 終身受益 8 教材 參考文獻(xiàn) 孫即祥 現(xiàn)代模式識(shí)別 國(guó)防科技大學(xué)出版社 2003年 吳逸飛譯 模式識(shí)別 原理 方法及應(yīng)用 清華大學(xué)出版社 2003年 李晶皎等譯 模式識(shí)別 第三版 電子工業(yè)出版社 2006年 9 講授課程內(nèi)容及安排 第一章引論第二章聚類分析第三章判別域代數(shù)界面方程法第四章統(tǒng)計(jì)判決第五章學(xué)習(xí) 訓(xùn)練與錯(cuò)誤率估計(jì)第六章最近鄰方法第七章特征提取和選擇上機(jī)實(shí)習(xí) 10 第一章引論 1 1概述1 2特征矢量和特征空間1 3隨機(jī)矢量的描述1 4正態(tài)分布 概念 模式識(shí)別 PatternRecognition 確定一個(gè)樣本的類別屬性 模式類 的過(guò)程 即把某一樣本歸屬于多個(gè)類型中的某個(gè)類型 樣本 Sample 一個(gè)具體的研究 客觀 對(duì)象 如患者 某人寫的一個(gè)漢字 一幅圖片等 模式 Pattern 對(duì)客體 研究對(duì)象 特征的描述 定量的或結(jié)構(gòu)的描述 是取自客觀世界的某一樣本的測(cè)量值的集合 或綜合 特征 Features 能描述模式特性的量 測(cè)量值 在統(tǒng)計(jì)模式識(shí)別方法中 通常用一個(gè)矢量表示 稱之為特征矢量 記為 模式類 Class 具有某些共同特性的模式的集合 概念 模式識(shí)別的例子 計(jì)算機(jī)自動(dòng)診斷疾病 獲取情況 信息采集 測(cè)量體溫 血壓 心率 血液化驗(yàn) X光透射 B超 心電圖 CT等盡可能多的信息 并將這些信息數(shù)字化后輸入電腦 當(dāng)然在實(shí)際應(yīng)用中要考慮采集的成本 這就是說(shuō)特征要進(jìn)行選擇的 運(yùn)行在電腦中的專家系統(tǒng)或?qū)Ｓ贸绦蚩梢苑治鲞@些數(shù)據(jù)并進(jìn)行分類 得出正?；虿徽５呐袛?不正常情況還要指出是什么問(wèn)題 14 各類空間 Space 的概念 模式采集 從客觀世界 對(duì)象空間 到模式空間的過(guò)程稱為模式采集 特征提取和特征選擇 由模式空間到特征空間的變換和選擇 類型判別 特征空間到類型空間所作的操作 模式識(shí)別三大任務(wù) 15 1 1概述 模式識(shí)別系統(tǒng) 通常在采集信息過(guò)程中 還要去除所獲取信息中的噪聲 增強(qiáng)有用的信息等工作 這種使信息純化的處理過(guò)程叫做信息的預(yù)處理 分類識(shí)別是根據(jù)事先確定的分類規(guī)則對(duì)前面選取的特征進(jìn)行分類 即識(shí)別 通常能描述對(duì)象的元素很多 為節(jié)約資源和提高處理速度 有時(shí)更為了可行性 在滿足分類識(shí)別正確率要求的條件下 按某種準(zhǔn)則盡量選用對(duì)正確分類識(shí)別作用較大的特征 使得用較少的特征就能完成分類識(shí)別任務(wù) 預(yù)處理這個(gè)環(huán)節(jié)的內(nèi)容很廣泛 與要解決的具體問(wèn)題有關(guān) 例如 從圖象中將汽車車牌的號(hào)碼識(shí)別出來(lái) 就需要先將車牌從圖像中找出來(lái) 再對(duì)車牌進(jìn)行劃分 將每個(gè)數(shù)字分別劃分開(kāi) 做到這一步以后 才能對(duì)每個(gè)數(shù)字進(jìn)行識(shí)別 以上工作都應(yīng)該在預(yù)處理階段完成 數(shù)字化 比特流 16 1 1概述 模式識(shí)別系統(tǒng) 17 1 1概述 模式識(shí)別系統(tǒng) 模式識(shí)別系統(tǒng)的主要環(huán)節(jié) 特征提取 符號(hào)表示 如長(zhǎng)度 波形 特征選擇 選擇有代表性的特征 能夠正確分類學(xué)習(xí)和訓(xùn)練 利用已知樣本建立分類和識(shí)別規(guī)則分類識(shí)別 對(duì)所獲得樣本按建立的分類規(guī)則進(jìn)行分類識(shí)別 18 紙幣識(shí)別器對(duì)紙幣按面額進(jìn)行分類面額 1 1概述 系統(tǒng)實(shí)例 5元10元20元50元100元 19 1 1概述 系統(tǒng)實(shí)例 長(zhǎng)度 mm 寬度 mm 5元1366310元1417020元1467050元15170100元15677 20 1 1概述 系統(tǒng)實(shí)例 磁性金屬條位置 大約 5元有54 8210元有54 8720元有57 8950元有60 91100元有63 93 5元10元20元50元100元 12345678 反射光波形 22 1 1概述 系統(tǒng)實(shí)例 數(shù)據(jù)采集 特征提取 長(zhǎng)度 寬度 磁性 磁性的位置 光反射亮度 光透射亮度等等 特征選擇 長(zhǎng)度 磁性及位置 反射亮度 分類識(shí)別 確定紙幣的面額及真?zhèn)?23 1 1概述 系統(tǒng)實(shí)例 訓(xùn)練集 是一個(gè)已知樣本集 在監(jiān)督學(xué)習(xí)方法中 用它來(lái)開(kāi)發(fā)出模式分類器 測(cè)試集 在設(shè)計(jì)識(shí)別和分類系統(tǒng)時(shí)沒(méi)有用過(guò)的獨(dú)立樣本集 系統(tǒng)評(píng)價(jià)原則 為了更好地對(duì)模式識(shí)別系統(tǒng)性能進(jìn)行評(píng)價(jià) 必須使用一組獨(dú)立于訓(xùn)練集的測(cè)試集對(duì)系統(tǒng)進(jìn)行測(cè)試 24 例 汽車車牌識(shí)別 從攝像頭獲取包含車牌的彩色圖象車牌定位和獲取字符分割和識(shí)別 25 26 27 1 1概述 模式識(shí)別的基本方法 一 統(tǒng)計(jì)模式識(shí)別二 句法模式識(shí)別三 模糊模式識(shí)別四 人工神經(jīng)網(wǎng)絡(luò)法五 人工智能方法 28 1 1概述 模式識(shí)別的基本方法 一 統(tǒng)計(jì)模式識(shí)別 模式描述方法 特征向量模式判定 模式類用條件概率分布P X i 表示 m類就有m個(gè)分布 然后判定未知模式屬于哪一個(gè)分布 29 1 1概述 模式識(shí)別的基本方法 一 統(tǒng)計(jì)模式識(shí)別 理論基礎(chǔ) 概率論 數(shù)理統(tǒng)計(jì)主要方法 線性 非線性分類 Bayes決策 聚類分析主要優(yōu)點(diǎn) 1 比較成熟2 能考慮干擾噪聲等影響3 識(shí)別模式基元能力強(qiáng)主要缺點(diǎn) 1 對(duì)結(jié)構(gòu)復(fù)雜的模式抽取特征困難2 不能反映模式的結(jié)構(gòu)特征 難以描述模式的性質(zhì)3 難以從整體角度考慮識(shí)別問(wèn)題 30 1 1概述 模式識(shí)別的基本方法 二 句法模式識(shí)別 模式描述方法 符號(hào)串 樹 圖模式判定 是一種語(yǔ)言 用一個(gè)文法表示一個(gè)類 m類就有m個(gè)文法 然后判定未知模式遵循哪一個(gè)文法 31 例2 如下圖中一幅圖形 要識(shí)別圖中的物體 選用句法模式識(shí)別方法 1 1概述 模式識(shí)別的基本方法 32 解 圖形結(jié)構(gòu)復(fù)雜 首先應(yīng)分解為簡(jiǎn)單的子圖 背景 物體 構(gòu)成一個(gè)多級(jí)樹結(jié)構(gòu) 1 1概述 模式識(shí)別的基本方法 33 在學(xué)習(xí)過(guò)程中 確定基元與基元之間的關(guān)系 推斷出生成景物的方法 判決過(guò)程中 首先提取基元 識(shí)別基元之間的連接關(guān)系 使用推斷的文法規(guī)則做句法分析 若分析成立 則判斷輸入的景物屬于相應(yīng)的類型 1 1概述 模式識(shí)別的基本方法 34 理論基礎(chǔ) 形式語(yǔ)言 自動(dòng)機(jī)技術(shù)主要方法 自動(dòng)機(jī)技術(shù) CYK剖析算法 Early算法 轉(zhuǎn)移圖法主要優(yōu)點(diǎn) 1 識(shí)別方便 可以從簡(jiǎn)單的基元開(kāi)始 由簡(jiǎn)至繁 2 能反映模式的結(jié)構(gòu)特征 能描述模式的性質(zhì) 3 對(duì)圖象畸變的抗干擾能力較強(qiáng) 主要缺點(diǎn) 當(dāng)存在干擾及噪聲時(shí) 抽取特征基元困難 且易失誤 1 1概述 模式識(shí)別的基本方法 35 1 1概述 模式識(shí)別的基本方法 三 模糊模式識(shí)別 模式描述方法 模糊集合A a a b b n n 模式判定 是一種集合運(yùn)算 用隸屬度將模糊集合劃分為若干子集 m類就有m個(gè)子集 然后根據(jù)擇近原則分類 36 理論基礎(chǔ) 模糊數(shù)學(xué)主要方法 模糊統(tǒng)計(jì)法 二元對(duì)比排序法 推理法 模糊集運(yùn)算規(guī)則 模糊矩陣主要優(yōu)點(diǎn) 由于隸屬度函數(shù)作為樣本與模板間相似程度的度量 故往往能反映整體的與主體的特征 從而允許樣本有相當(dāng)程度的干擾與畸變 主要缺點(diǎn) 準(zhǔn)確合理的隸屬度函數(shù)往往難以建立 故限制了它的應(yīng)用 1 1概述 模式識(shí)別的基本方法 37 1 1概述 模式識(shí)別的基本方法 四 人工神經(jīng)網(wǎng)絡(luò)法 模式描述方法 以不同活躍度表示的輸入節(jié)點(diǎn)集 神經(jīng)元 模式判定 是一個(gè)非線性動(dòng)態(tài)系統(tǒng) 通過(guò)對(duì)樣本的學(xué)習(xí)建立起記憶 然后將未知模式判決為其最接近的記憶 38 理論基礎(chǔ) 神經(jīng)生理學(xué) 心理學(xué)主要方法 BP模型 HOP模型 高階網(wǎng)主要優(yōu)點(diǎn) 可處理一些環(huán)境信息十分復(fù)雜 背景知識(shí)不清楚 推理規(guī)則不明確的問(wèn)題 允許樣本有較大的缺損 畸變 主要缺點(diǎn) 模型在不斷豐富與完善中 目前能識(shí)別的模式類還不夠多 1 1概述 模式識(shí)別的基本方法 39 1 1概述 模式識(shí)別的基本方法 五 邏輯推理法 人工智能法 模式描述方法 字符串表示的事實(shí)模式判定 是一種布爾運(yùn)算 從事實(shí)出發(fā)運(yùn)用一系列規(guī)則 推理得到不同結(jié)果 m個(gè)類就有m個(gè)結(jié)果 40 理論基礎(chǔ) 演繹邏輯 布爾代數(shù)主要方法 產(chǎn)生式推理 語(yǔ)義網(wǎng)推理 框架推理主要優(yōu)點(diǎn) 已建立了關(guān)于知識(shí)表示及組織 目標(biāo)搜索及匹配的完整體系 對(duì)需要眾多規(guī)則的推理達(dá)到識(shí)別目標(biāo)確認(rèn)的問(wèn)題 有很好的效果 主要缺點(diǎn) 當(dāng)樣本有缺損 背景不清晰 規(guī)則不明確甚至有歧義時(shí) 效果不好 1 1概述 模式識(shí)別的基本方法 41 1 1概述 模式識(shí)別的發(fā)展簡(jiǎn)史 1929年G Tauschek發(fā)明閱讀機(jī) 能夠閱讀0 9的數(shù)字 30年代Fisher提出統(tǒng)計(jì)分類理論 奠定了統(tǒng)計(jì)模式識(shí)別的基礎(chǔ) 50年代NoamChemsky提出形式語(yǔ)言理論 傅京蓀提出句法 結(jié)構(gòu)模式識(shí)別 60年代L A Zadeh提出了模糊集理論 模糊模式識(shí)別方法得以發(fā)展和應(yīng)用 42 1 1概述 模式識(shí)別的發(fā)展簡(jiǎn)史 80年代以Hopfield網(wǎng) BP網(wǎng)為代表的神經(jīng)網(wǎng)絡(luò)模型導(dǎo)致人工神經(jīng)元網(wǎng)絡(luò)復(fù)活 并在模式識(shí)別得到較廣泛的應(yīng)用 90年代小樣本學(xué)習(xí)理論 支持向量機(jī)也受到了很大的重視 43 1 1概述 模式識(shí)別的應(yīng)用 舉例 生物學(xué)自動(dòng)細(xì)胞學(xué) 染色體特性研究 遺傳研究天文學(xué)天文望遠(yuǎn)鏡圖像分析 自動(dòng)光譜學(xué)經(jīng)濟(jì)學(xué)股票交易預(yù)測(cè) 企業(yè)行為分析醫(yī)學(xué)心電圖分析 腦電圖分析 醫(yī)學(xué)圖像分析 44 1 1概述 主要實(shí)用系統(tǒng)舉例 文字識(shí)別 CharacterRecognition OCR OpticalCharacterRecognition 智能交通 IntelligentTraffic 車牌 車型 語(yǔ)音識(shí)別 Speechrecognition 翻譯機(jī) 身份識(shí)別等目標(biāo)識(shí)別ATR AutomaicTargetRecognition 45 46 1 2特征矢量和特征空間 47 1 3隨機(jī)矢量的描述 隨機(jī)矢量 在模式識(shí)別過(guò)程中 要對(duì)許多具體對(duì)象進(jìn)行測(cè)量 以獲得許多次觀測(cè)值 每次觀測(cè)值不一定相同 所以對(duì)許多對(duì)象而言 各個(gè)特征分量都是隨機(jī)變量 即許多對(duì)象的特征向量在n維空間中呈隨機(jī)性分布 稱為隨機(jī)矢量 48 1 3隨機(jī)矢量的描述 一 隨機(jī)矢量的分布函數(shù) 設(shè)為隨機(jī)矢量 為確定性矢量 隨機(jī)矢量的聯(lián)合概率分布函數(shù)定義為 式中表示括號(hào)中事件同時(shí)發(fā)生的概率 49 1 3隨機(jī)矢量的描述 一 隨機(jī)矢量的分布函數(shù) 隨機(jī)矢量的聯(lián)合概率密度函數(shù)定義為 50 1 3隨機(jī)矢量的描述 51 1 3隨機(jī)矢量的描述 x p x 52 1 3隨機(jī)矢量的描述 53 1 3隨機(jī)矢量的描述 二 隨機(jī)矢量的數(shù)字特征 其中 的分量 式中 是的第個(gè)分量的邊緣密度 隨機(jī)矢量的均值矢量的各分量是相應(yīng)的各隨機(jī)分量的均值 54 1 3隨機(jī)矢量的描述 二 隨機(jī)矢量的數(shù)字特征 條件期望在模式識(shí)別中 經(jīng)常以類別作為條件 在這種情況下隨機(jī)矢量的條件期望矢量定義為 55 1 3隨機(jī)矢量的描述 隨機(jī)矢量的自協(xié)方差矩陣表征各分量圍繞其均值的散布情況及各分量間的相關(guān)關(guān)系 其定義為 二 隨機(jī)矢量的數(shù)字特征 協(xié)方差矩陣 56 1 3隨機(jī)矢量的描述 57 1 3隨機(jī)矢量的描述 58 1 3隨機(jī)矢量的描述 二 隨機(jī)矢量的數(shù)字特征 相關(guān)系數(shù) 由布尼亞科夫斯基不等式知 相關(guān)系數(shù)矩陣定義為 59 1 3隨機(jī)矢量的描述 60 1 3隨機(jī)矢量的描述 61 1 3隨機(jī)矢量的描述 62 1 3隨機(jī)矢量的描述 63 1 4正態(tài)分布 64 1 4正態(tài)分布 1 一維隨機(jī)變量的正態(tài)分布 65 1 4正態(tài)分布 66 1 4正態(tài)分布 2 隨機(jī)矢量的正態(tài)分布 正態(tài)分布隨機(jī)矢量的概率密度函數(shù)定義為 67 1 4正態(tài)分布 68 1 4正態(tài)分布 2 二維隨機(jī)變量的正態(tài)分布 69 1 4正態(tài)分布 范例木板圖象512 512d 3長(zhǎng)度紋理亮度c 2松木 樺木 維數(shù)無(wú)限有限 很大R有限d不大c 總結(jié) 模式識(shí)別過(guò)程 d R 無(wú)限 71 試證明 對(duì)于正態(tài)分布 不相關(guān)與獨(dú)立是等價(jià)的 試證明 多元正態(tài)隨機(jī)矢量的線性變換仍為多元正態(tài)隨機(jī)矢量 試證明 多元正態(tài)隨機(jī)矢量X的分量的線性組合是一正態(tài)隨機(jī)變量 習(xí)題 72 模式識(shí)別 主講 蔡宣平教授電話 73441 O 73442 H E mail xpcai 單位 電子科學(xué)與工程學(xué)院信息工程系 73 第二章聚類分析 ClusteringAnalysis 2 1聚類分析的概念2 2模式相似性測(cè)度2 3類的定義與類間距離2 4聚類的算法 74 2 1聚類分析的概念 一 聚類分析的基本思想 相似的歸為一類 模式相似性的度量和聚類算法 無(wú)監(jiān)督分類 Unsupervised 二 特征量的類型 物理量 重量 長(zhǎng)度 速度 次序量 等級(jí) 技能 學(xué)識(shí) 名義量 性別 狀態(tài) 種類 第二章聚類分析 75 三 方法的有效性取決于分類算法和特征點(diǎn)分布情況的匹配 2 1聚類分析的概念 分類無(wú)效時(shí)的情況1 特征選取不當(dāng)使分類無(wú)效 第二章聚類分析 76 三 方法的有效性取決于分類算法和特征點(diǎn)分布情況的匹配 2 1聚類分析的概念 分類無(wú)效時(shí)的情況2 特征選取不足可能使不同類別的模式判為一類 第二章聚類分析 77 三 方法的有效性取決于分類算法和特征點(diǎn)分布情況的匹配 2 1聚類分析的概念 分類無(wú)效時(shí)的情況3 特征選取過(guò)多可能無(wú)益反而有害 增加分析負(fù)擔(dān)并使分析效果變差 第二章聚類分析 78 三 方法的有效性取決于分類算法和特征點(diǎn)分布情況的匹配 2 1聚類分析的概念 分類無(wú)效時(shí)的情況4 量綱選取不當(dāng) 第二章聚類分析 79 三 方法的有效性取決于分類算法和特征點(diǎn)分布情況的匹配 2 1聚類分析的概念 分類無(wú)效時(shí)的情況4 量綱選取不當(dāng) 第二章聚類分析 80 三 方法的有效性取決于分類算法和特征點(diǎn)分布情況的匹配 2 1聚類分析的概念 分類無(wú)效時(shí)的情況4 量綱選取不當(dāng) 第二章聚類分析 81 下列是一些動(dòng)物的名稱 羊 sheep 狗 dog 藍(lán)鯊 blueshark 蜥蜴 lizard 毒蛇 viper 貓 cat 麻雀 sparrow 海鷗 seagull 金魚 goldfish 緋鯢鰹 red mullet 蛙 frog 要對(duì)這些動(dòng)物進(jìn)行分類 則不同的特征有不同的分法 特征選取不同對(duì)聚類結(jié)果的影響 第二章聚類分析 82 特征選取不同對(duì)聚類結(jié)果的影響 羊 狗 貓藍(lán)鯊 蜥蜴 毒蛇 麻雀 海鷗 金魚 緋鯢鰹 青蛙 a 按繁衍后代的方式分 哺乳動(dòng)物 非哺乳動(dòng)物 第二章聚類分析 83 金魚緋鯢鰹藍(lán)鯊 羊 狗 貓蜥蜴 毒蛇麻雀 海鷗青蛙 b 按肺是否存在分 無(wú)肺 有肺 特征選取不同對(duì)聚類結(jié)果的影響 第二章聚類分析 84 青蛙 羊 狗 貓蜥蜴 毒蛇麻雀 海鷗 金魚緋鯢鰹藍(lán)鯊 c 按生活環(huán)境分 陸地 水里 兩棲 特征選取不同對(duì)聚類結(jié)果的影響 第二章聚類分析 85 藍(lán)鯊 金魚緋鯢鰹 蜥蜴 毒蛇麻雀 海鷗青蛙 羊 狗 貓 d 按繁衍后代方式和肺是否存在分 非哺乳且有肺 哺乳且無(wú)肺 哺乳且有肺 非哺乳且無(wú)肺 特征選取不同對(duì)聚類結(jié)果的影響 第二章聚類分析 86 距離測(cè)度不同 聚類結(jié)果也不同 數(shù)據(jù)的粗聚類是兩類 細(xì)聚類為4類 第二章聚類分析 87 綜上可見(jiàn) 選擇什么特征 選擇多少個(gè)特征 選擇什么樣的量綱 選擇什么樣的距離測(cè)度 這些對(duì)分類結(jié)果都會(huì)產(chǎn)生極大影響 第二章聚類分析 88 聚類過(guò)程遵循的基本步驟 一 特征選擇 featureselection 盡可能多地包含任務(wù)關(guān)心的信息 二 近鄰測(cè)度 proximitymeasure 定量測(cè)定兩特征如何 相似 或 不相似 三 聚類準(zhǔn)則 clusteringcriterion 以蘊(yùn)涵在數(shù)據(jù)集中類的類型為基礎(chǔ) 四 聚類算法 clusteringalgorithm 按近鄰測(cè)度和聚類準(zhǔn)則揭示數(shù)據(jù)集的聚類結(jié)構(gòu) 五 結(jié)果驗(yàn)證 validationoftheresults 常用逼近檢驗(yàn)驗(yàn)證聚類結(jié)果的正確性 六 結(jié)果判定 interpretationoftheresults 由專家用其他方法判定結(jié)果的正確性 89 聚類應(yīng)用的四個(gè)基本方向 一 減少數(shù)據(jù)許多時(shí)候 當(dāng)數(shù)據(jù)量N很大時(shí) 會(huì)使數(shù)據(jù)處理變得很費(fèi)力 因此可使用聚類分析的方法將數(shù)據(jù)分成幾組可判斷的聚類m m N 來(lái)處理 每一個(gè)類可當(dāng)作獨(dú)立實(shí)體來(lái)對(duì)待 從這個(gè)角度看 數(shù)據(jù)被壓縮了 第二章聚類分析 90 二 假說(shuō)生成在這種情況下 為了推導(dǎo)出數(shù)據(jù)性質(zhì)的一些假說(shuō) 對(duì)數(shù)據(jù)集進(jìn)行聚類分析 因此 這里使用聚類作為建立假說(shuō)的方法 然后用其他數(shù)據(jù)集驗(yàn)證這些假說(shuō) 聚類應(yīng)用的四個(gè)基本方向 第二章聚類分析 91 聚類應(yīng)用的四個(gè)基本方向 三 假說(shuō)檢驗(yàn)用聚類分析來(lái)驗(yàn)證指定假說(shuō)的有效性 例如 考慮這樣的假說(shuō) 大公司在海外投資 要驗(yàn)證這個(gè)假說(shuō)是否正確 就要對(duì)大公司和有代表性的公司按規(guī)模 海外活躍度 成功完成項(xiàng)目的能力等進(jìn)行聚類分析 從而來(lái)支持這個(gè)假說(shuō) 第二章聚類分析 92 四 基于分組的預(yù)測(cè)對(duì)現(xiàn)有數(shù)據(jù)進(jìn)行聚類分析 形成模式的特征 并用特征表示聚類 接下來(lái) 對(duì)于一個(gè)未知模式 就可以用前面的聚類來(lái)確定是哪一類 聚類應(yīng)用的四個(gè)基本方向 例如 考慮被同種疾病感染的病人數(shù)據(jù)集 先按聚類分析進(jìn)行分類 然后對(duì)新的病人確定他適合的聚類 從而判斷他病情 第二章聚類分析 93 2 2模式相似性測(cè)度 用于描述各模式之間特征的相似程度 距離測(cè)度 相似測(cè)度 匹配測(cè)度 第二章聚類分析 94 2 2模式相似性測(cè)度 一 距離測(cè)度 差值測(cè)度 測(cè)度基礎(chǔ) 兩個(gè)矢量矢端的距離測(cè)度數(shù)值 兩矢量各相應(yīng)分量之差的函數(shù) 第二章聚類分析 95 2 2模式相似性測(cè)度 常用的距離測(cè)度有 1 歐氏 Euclidean 距離 第二章聚類分析 96 2 2模式相似性測(cè)度 4 明氏 Minkowski 距離 2 2 4 2 絕對(duì)值距離 街坊距離或Manhattan距離 2 2 2 3 切氏 Chebyshev 距離 2 2 3 第二章聚類分析 97 2 2模式相似性測(cè)度 第二章聚類分析 98 2 2模式相似性測(cè)度 5 馬氏 Mahalanobis 距離 注意 馬氏距離對(duì)一切非奇異線性變換都是不變的 這說(shuō)明它不受特征量綱選擇的影響 并且是平移不變的 上面的V的含義是這個(gè)矢量集的協(xié)方差陣的統(tǒng)計(jì)量 故馬氏距離加入了對(duì)特征的相關(guān)性的考慮 第二章聚類分析 99 2 2模式相似性測(cè)度 第二章聚類分析 100 101 現(xiàn)金識(shí)別例子 歐氏平均距離 數(shù)據(jù)樣本介紹 10個(gè)文本文件文件名 rmb00 txt rmb09 txt每個(gè)文件有4個(gè)幣種的數(shù)據(jù) 分別是 100圓 50圓 20圓 10圓每個(gè)幣種有新舊兩種版本 4個(gè)方向 故有8個(gè)數(shù)據(jù)塊 如100圓的8個(gè)數(shù)據(jù)塊 data100a data100b data100c data100d 老版data100e data100f data100g data100h 新版每個(gè)數(shù)據(jù)塊有8個(gè)傳感器數(shù)據(jù) 傳感器1 傳感器2 傳感器8每個(gè)傳感器有60個(gè)采樣數(shù)據(jù) 數(shù)據(jù)1 數(shù)據(jù)2 數(shù)據(jù)60 102 現(xiàn)金識(shí)別例子 Eucliden 15 000000Manhattan 33 000000Chebyshev 11 000000Minkowski 11 039449 m 8 100元A面第1個(gè)樣本第10點(diǎn)和20點(diǎn)的距離X 75 76 101 83 102 96 91 82 Y 70 74 90 76 99 96 90 86 X Y 5 2 11 7 3 0 1 4 距離測(cè)度rmbdis 103 現(xiàn)金識(shí)別例子 歐式平均距離 100a 100a 2 65 49 66 24 41100a 100b 16 37 55 87 33 97100a 100c 3 87 58 34 29 41100a 100d 6 86 53 74 33 04100a 100e 3 87 62 12 27 51100a 100f 13 60 67 61 34 67100a 100g 11 40 68 56 32 27100a 100h 11 27 68 61 34 43100a 50a 18 76 76 20 40 72100a 20a 13 23 81 28 42 87100a 10a 12 45 90 91 54 99 104 現(xiàn)金識(shí)別例子 100圓A面的馬式矩陣SW為 43 553 964 852 752 752 346 837 953 9132 0137 5107 859 674 052 131 564 8137 5165 9124 174 684 167 637 152 7107 8124 1105 557 567 254 535 252 759 674 657 576 271 765 857 952 374 084 167 271 773 162 855 046 852 167 654 565 862 859 651 937 931 537 135 257 955 051 954 7 105 現(xiàn)金識(shí)別例子 SW的逆矩陣為 0 3 0 00 1 0 1 0 1 0 1 0 20 2 0 00 3 0 1 0 10 1 0 60 30 20 1 0 10 3 0 1 0 0 0 2 0 30 4 0 1 0 1 0 10 20 10 3 0 1 0 2 0 10 1 0 00 10 7 0 7 0 40 2 0 1 0 6 0 20 3 0 72 2 0 0 1 0 0 20 3 0 3 0 1 0 4 0 01 2 0 50 20 20 4 0 20 2 1 0 0 51 0 106 現(xiàn)金識(shí)別例子 馬式平均距離 100a 7 46 80 05 39 73100b 26 75 179 86 91 89100c 14 50 231 44 103 76100d 11 69 155 28 78 58100e 5 65 2968 84 247 42100f 39 19 2191 91 108 10100g 10 68 2875 99 265 16100h 9 41 2673 54 107 5650a 22 78 221 07 101 4120a 22 51 343 26 162 9010a 20 93 975 67 256 38 107 現(xiàn)金識(shí)別例子 馬式平均距離 a 39 73101 41162 90256 38b 91 89230 25288 69659 47c 103 76135 94257 57724 96d 78 58171 10330 97675 90e 247 42443 46333 93218 71f 108 10328 11305 19607 51g 265 16956 58818 83348 42h 107 56339 64387 10628 88 100圓50圓20圓10圓 其中馬式矩陣為100圓A面的 上面是各面到100圓A面的均值點(diǎn)的平均馬式距離 108 現(xiàn)金識(shí)別例子 100圓A面的傳感器1到其它各面?zhèn)鞲衅?的街坊距離 109 2 2模式相似性測(cè)度 二 相似測(cè)度測(cè)度基礎(chǔ) 以兩矢量的方向是否相近作為考慮的基礎(chǔ) 矢量長(zhǎng)度并不不重要 設(shè) 1 角度相似系數(shù) 夾角余弦 2 2 11 注意 坐標(biāo)系的旋轉(zhuǎn)和尺度的縮放是不變的 但對(duì)一般的線形變換和坐標(biāo)系的平移不具有不變性 110 現(xiàn)金識(shí)別例子 100圓A面?zhèn)鞲衅?與其它各面的相似系數(shù) 111 2 2模式相似性測(cè)度 二 相似測(cè)度2 相關(guān)系數(shù)它實(shí)際上是數(shù)據(jù)中心化后的矢量夾角余弦 2 2 12 112 現(xiàn)金識(shí)別例子 100圓A面?zhèn)鞲衅?與其它各面的相關(guān)系數(shù) 113 2 2模式相似性測(cè)度 二 相似測(cè)度3 指數(shù)相似系數(shù) 2 2 13 式中為相應(yīng)分量的協(xié)方差 為矢量維數(shù) 它不受量綱變化的影響 114 現(xiàn)金識(shí)別例子 100圓A面?zhèn)鞲衅?與其它各面的相關(guān)系數(shù) 115 2 2模式相似性測(cè)度 當(dāng)特征只有兩個(gè)狀態(tài) 0 1 時(shí) 常用匹配測(cè)度 0表示無(wú)此特征1表示有此特征 故稱之為二值特征 對(duì)于給定的x和y中的某兩個(gè)相應(yīng)分量xi與yj若xi 1 yj 1 則稱xi與yj是 1 1 匹配 若xi 1 yj 0 則稱xi與yj是 1 0 匹配 若xi 0 yj 1 則稱xi與yj是 0 1 匹配 若xi 0 yj 0 則稱xi與yj是 0 0 匹配 二 匹配測(cè)度 116 2 2模式相似性測(cè)度 117 2 2模式相似性測(cè)度 三 匹配測(cè)度 1 Tanimoto測(cè)度 118 例2 2 2 可以看出 它等于共同具有的特征數(shù)目與分別具有的特征種類總數(shù)之比 這里只考慮 1 1 匹配而不考慮 0 0 匹配 設(shè) 則 2 2模式相似性測(cè)度 119 現(xiàn)金識(shí)別例子 100圓A面與其它各面的匹配系數(shù)Tanimoto 120 2 2模式相似性測(cè)度 三 匹配測(cè)度 2 Rao測(cè)度 注 1 1 匹配特征數(shù)目和所選用的特征數(shù)目之比 121 現(xiàn)金識(shí)別例子 100圓A面與其它各面的匹配系數(shù)Rao 122 2 2模式相似性測(cè)度 三 匹配測(cè)度 3 簡(jiǎn)單匹配系數(shù) 注 上式分子為 1 1 匹配特征數(shù)目與 0 0 匹配特征數(shù)目之和 分母為所考慮的特征數(shù)目 123 現(xiàn)金識(shí)別例子 100圓A面與其它各面的匹配系數(shù)Simple 124 2 2模式相似性測(cè)度 三 匹配測(cè)度 4 Dice系數(shù) 5 Kulzinsky系數(shù) 125 現(xiàn)金識(shí)別例子 100圓A面與其它各面的匹配系數(shù)dice 126 現(xiàn)金識(shí)別例子 100圓A面與其它各面的匹配系數(shù)Kulzinsky 127 作業(yè) P44 2 1 2 3 128 2 3類的定義與類間距離 2 3 1類的定義 定義之1設(shè)集合S中任意元素xi與yj間的距離dij有dij h其中h為給定的閥值 稱S對(duì)于閥值h組成一類 類的定義有很多種 類的劃分具有人為規(guī)定性 這反映在定義的選取及參數(shù)的選擇上 一個(gè)分類結(jié)果的優(yōu)劣最后只能根據(jù)實(shí)際來(lái)評(píng)價(jià) 書中的其它定義方法請(qǐng)大家自行參考學(xué)習(xí) 129 2 3類的定義與類間距離 2 3 2類間距離測(cè)度方法 最近距離法 最遠(yuǎn)距離法 中間距離法 重心距離法 平均距離法 離差平方和法 130 2 3類的定義與類間距離 2 3 2類間距離測(cè)度方法 最近距離法 最遠(yuǎn)距離法 中間距離法 重心距離法 平均距離法 離差平方和法 131 現(xiàn)金識(shí)別例子 100圓A面與其它各面的最小距離 132 2 3類的定義與類間距離 2 3 2類間距離測(cè)度方法 最近距離法 最遠(yuǎn)距離法 中間距離法 重心距離法 平均距離法 離差平方和法 133 現(xiàn)金識(shí)別例子 100圓A面與其它各面的最大距離 134 2 3類的定義與類間距離 2 3 2類間距離測(cè)度方法 最近距離法 最遠(yuǎn)距離法 中間距離法 重心距離法 平均距離法 離差平方和法 p q k 135 2 3類的定義與類間距離 2 3 2類間距離測(cè)度方法 最近距離法 最遠(yuǎn)距離法 中間距離法 重心距離法 平均距離法 離差平方和法 np nq分別為類wp和wq的樣本個(gè)數(shù) 136 2 3類的定義與類間距離 2 3 2類間距離測(cè)度方法 最近距離法 最遠(yuǎn)距離法 中間距離法 重心距離法 平均距離法 離差平方和法 137 現(xiàn)金識(shí)別例子 100圓A面與其它各面的平均距離 138 2 3類的定義與類間距離 2 3 2類間距離測(cè)度方法 最近距離法 最遠(yuǎn)距離法 中間距離法 重心距離法 平均距離法 離差平方和法 分別為對(duì)應(yīng)類的重心 類內(nèi)離差平方和 遞推公式為 139 140 2 3類的定義與類間距離 2 3 3聚類的準(zhǔn)則函數(shù) 判別分類結(jié)果好壞的一般標(biāo)準(zhǔn) 類內(nèi)距離小 類間距離大 某些算法需要一個(gè)能對(duì)分類過(guò)程或分類結(jié)果的優(yōu)劣進(jìn)行評(píng)估的準(zhǔn)則函數(shù) 如果聚類準(zhǔn)則函數(shù)選擇得好 聚類質(zhì)量就會(huì)高 聚類準(zhǔn)則往往是和類的定義有關(guān)的 是類的定義的某種體現(xiàn) 141 2 3 3聚類的準(zhǔn)則函數(shù) 一 類內(nèi)距離準(zhǔn)則設(shè)有待分類的模式集在某種相似性測(cè)度基礎(chǔ)上被劃分為類 類內(nèi)距離準(zhǔn)則函數(shù)定義為 表示類的模式均值矢量 2 3 20 2 3類的定義與類間距離 142 2 3類的定義與類間距離 143 加權(quán)類內(nèi)距離準(zhǔn)則 2 3 22 2 3 23 144 2 3類的定義與類間距離 145 加權(quán)類間距離準(zhǔn)則 2 3 25 146 2 3類的定義與類間距離 147 的類內(nèi)離差陣定義為 2 3 28 2 3類的定義與類間距離 式中為類的模式均值矢量 2 3 29 148 149 例2 3 1證明 2 3類的定義與類間距離 150 聚類的基本目的是使或 利用線形代數(shù)有關(guān)矩陣的跡和行列式的性質(zhì) 可以定義如下4個(gè)聚類的準(zhǔn)則函數(shù) 2 3類的定義與類間距離 151 2 3類的定義與類間距離 由它們的構(gòu)造可以看出 為得到好的聚類結(jié)果 應(yīng)該使它們盡量的大 這類準(zhǔn)則也大量用在特征提取和選擇中 152 2 3類的定義與類間距離 J1 7 60886J2 0 0010397J3 15 6089J4 62 9116 用紙幣數(shù)據(jù)計(jì)算獲得的結(jié)果 153 作業(yè) P44 2 4 2 5 2 6 154 2 4聚類的算法 2 4 1聚類的技術(shù)方案 聚類分析有很多具體的算法 有的比較簡(jiǎn)單 有的相對(duì)復(fù)雜和完善 但歸納起來(lái)就是三大類 1 按最小距離原則簡(jiǎn)單聚類方法2 按最小距離原則進(jìn)行兩類合并的方法3 依據(jù)準(zhǔn)則函數(shù)動(dòng)態(tài)聚類方法 155 2 4聚類的算法 1 簡(jiǎn)單聚類方法 針對(duì)具體問(wèn)題確定相似性閾值 將模式到各聚類中心間的距離與閾值比較 當(dāng)大于閾值時(shí)該模式就作為另一類的類心 小于閾值時(shí)按最小距離原則將其分劃到某一類中 這類算法運(yùn)行中模式的類別及類的中心一旦確定將不會(huì)改變 156 2 4聚類的算法 首先視各模式自成一類 然后將距離最小的兩類合并成一類 不斷地重復(fù)這個(gè)過(guò)程 直到成為兩類為止 2 按最小距離原則進(jìn)行兩類合并的方法 這類算法運(yùn)行中 類心不斷地修正 但模式類別一旦指定后就不再改變 就是模式一旦劃為一類后就不再被分劃開(kāi) 這類算法也稱為譜系聚類法 157 2 4聚類的算法 3 依據(jù)準(zhǔn)則函數(shù)動(dòng)態(tài)聚類法 設(shè)定一些分類的控制參數(shù) 定義一個(gè)能表征聚類結(jié)果優(yōu)劣的準(zhǔn)則函數(shù) 聚類過(guò)程就是使準(zhǔn)則函數(shù)取極值的優(yōu)化過(guò)程 算法運(yùn)行中 類心不斷地修正 各模式的類別的指定也不斷地更改 這類方法有 C均值法 ISODATA法等 158 2 4聚類的算法 簡(jiǎn)單聚類方法 159 2 4聚類的算法 簡(jiǎn)單聚類方法 160 2 4聚類的算法 簡(jiǎn)單聚類方法 161 2 4聚類的算法 簡(jiǎn)單聚類方法 這類算法的突出優(yōu)點(diǎn)是算法簡(jiǎn)單 但聚類過(guò)程中 類的中心一旦確定將不會(huì)改變 模式一旦指定類后也不再改變 算法特點(diǎn) 從算法的過(guò)程可以看出 該算法結(jié)果很大程度上依賴于距離門限T的選取及模式參與分類的次序 如果能有先驗(yàn)知識(shí)指導(dǎo)門限T的選取 通?？色@得較合理的效果 也可考慮設(shè)置不同的T和選擇不同的次序 最后選擇較好的結(jié)果進(jìn)行比較 162 2 4聚類的算法 簡(jiǎn)單聚類方法 簡(jiǎn)單聚類圖例 163 例2 4 1 初始條件不同的簡(jiǎn)單聚類結(jié)果 初始中心不同 12345 12345 12345 12345 1098 1098 876 876 1167 1167 91011 91011 164 2 4聚類的算法 簡(jiǎn)單聚類法程序 simpleclustering 165 2 4聚類的算法 最大最小距離法 166 2 4聚類的算法 最大最小距離法 算法原理步驟 167 計(jì)算未被作為聚類中心的各模式特征矢量 與 之間的距離 并求出它們之中的最小值 為表述簡(jiǎn)潔 雖然某些模式已選做聚類中心 但上面仍將所有模式下角標(biāo)全部列寫出來(lái) 因這并不影響算法的正確性 即 168 169 170 2 4聚類的算法 最大最小距離法程序 maxminclustering 171 2 4聚類的算法 層次聚類法 HierarchicalClusteringMethod 系統(tǒng)聚類法 譜系聚類法 按最小距離原則不斷進(jìn)行兩類合并 2 4 3譜系聚類法 172 2 4聚類的算法 層次聚類法 HierarchicalClusteringMethod 系統(tǒng)聚類法 譜系聚類法 按最小距離原則不斷進(jìn)行兩類合并 算法思想首先將N個(gè)模式視作各自成為一類 然后計(jì)算類與類之間的距離 選擇距離最小的一對(duì)合并成一個(gè)新類 計(jì)算在新的類別分劃下各類之間的距離 再將距離最近的兩類合并 直至所有模式聚成兩類為止 2 4 3譜系聚類法 173 2 4聚類的算法 2 4 3譜系聚類法 174 2 4聚類的算法 2 4 3譜系聚類法 175 例2 4 3 如下圖所示1 設(shè)全部樣本分為6類 2 作距離矩陣D 0 3 求最小元素 4 把 1 3合并 7 1 3 4 6合并 8 4 6 5 作距離矩陣D 1 D 0 176 例2 4 3 如下圖所示1 設(shè)全部樣本分為6類 2 作距離矩陣D 0 3 求最小元素 4 把 1 3合并 7 1 3 4 6合并 8 4 6 5 作距離矩陣D 1 D 1 177 6 若合并的類數(shù)沒(méi)有達(dá)到要求 轉(zhuǎn)3 否則停止 3 求最小元素 4 8 5 2合并 9 2 5 4 6 178 179 2 4聚類的算法 譜系聚類法程序 Hierarchicalclustering 180 2 4聚類的算法 最大距離和層次聚類算法的一個(gè)共同特點(diǎn)是某個(gè)模式一旦劃分到某一類之后 在后繼的算法過(guò)程中就不改變了 而簡(jiǎn)單聚類算法中類心一旦選定后在后繼算法過(guò)程中也不再改變了 因此 這些方法效果一般不會(huì)太理想 181 2 確定評(píng)估聚類質(zhì)量的準(zhǔn)則函數(shù) 3 確定模式分劃及聚類合并或分裂的規(guī)則 2 4聚類的算法 動(dòng)態(tài)聚類算法要點(diǎn) 182 2 4聚類的算法 動(dòng)態(tài)聚類的基本步驟 建立初始聚類中心 進(jìn)行初始聚類 計(jì)算模式和類的距離 調(diào)整模式的類別 計(jì)算各聚類的參數(shù) 刪除 合并或分裂一些聚類 從初始聚類開(kāi)始 運(yùn)用迭代算法動(dòng)態(tài)地改變模式的類別和聚類的中心使準(zhǔn)則函數(shù)取得極值或設(shè)定的參數(shù)達(dá)到設(shè)計(jì)要求時(shí)停止 183 2 4聚類的算法 動(dòng)態(tài)聚類的框圖 產(chǎn)生初始聚類中心 聚類 檢驗(yàn)聚類合理性 待分類模式 184 條件及約定設(shè)待分類的模式特征矢量集為 類的數(shù)目C是事先取定的 2 4聚類的算法 2 4 3動(dòng)態(tài)聚類法 C 均值法 算法思想該方法取定C個(gè)類別和選取C個(gè)初始聚類中心 按最小距離原則將各模式分配到C類中的某一類 之后不斷地計(jì)算類心和調(diào)整各模式的類別 最終使各模式到其判屬類別中心的距離平方之和最小 185 2 4聚類的算法 2 4 3動(dòng)態(tài)聚類法 C 均值法 186 2 4聚類的算法 2 4 3動(dòng)態(tài)聚類法 C 均值法 187 選代表點(diǎn) 4 動(dòng)態(tài)聚類框圖 2 4聚類的算法 2 4 3動(dòng)態(tài)聚類法 C 均值法 188 例2 4 2使用聚類算法實(shí)現(xiàn)圖像分割 在散射圖上形成了兩個(gè)聚類 利用模式識(shí)別的方法將其分開(kāi) 就實(shí)現(xiàn)了圖象的分割 189 例2 4 3 已知有20個(gè)樣本 每個(gè)樣本有2個(gè)特征 數(shù)據(jù)分布如下圖 使用C 均值法實(shí)現(xiàn)樣本分類 C 2 第一步 令C 2 選初始聚類中心為 190 191 0 0 第二步 192 193 194 195 第三步 更新聚類中心 196 197 第四步 第二步 第三步 更新聚類中心 198 199 clustering 2 4聚類的算法 2 4 3動(dòng)態(tài)聚類法 C 均值法程序 200 作業(yè) P45 2 7 2 8 201 2 4聚類的算法 2 4 3動(dòng)態(tài)聚類法 C 均值法 關(guān)于C 均值法收斂性的分析 202 2 4聚類的算法 2 4 3動(dòng)態(tài)聚類法 C 均值法 當(dāng)模式分布呈現(xiàn)類內(nèi)團(tuán)聚狀 C 均值算法是能達(dá)到很好的聚類結(jié)果 故應(yīng)用較多 從算法的迭代過(guò)程看 C 均值算法是能使各模式到其所判屬的類別中心距離 平方 之和為最小的最佳聚類 203 2 4聚類的算法 2 4 3動(dòng)態(tài)聚類法 C 均值法的改進(jìn) 在類別數(shù)未知的情況下 可使類數(shù)C由較小值逐步增加 對(duì)于每個(gè)選定的C分別使用該算法 顯然準(zhǔn)則函數(shù)J是隨C的增加而單調(diào)減少 C的調(diào)整作一條C一J曲線 其曲率變化的最大點(diǎn)對(duì)應(yīng)的類數(shù)是比較接近最優(yōu)的類數(shù) 在增加過(guò)程中 總會(huì)出現(xiàn)使本來(lái)較密集的類再拆開(kāi)的情況 此時(shí)J雖減小 但減小速度將變緩 如果作一條C一J曲線 其曲率變化的最大點(diǎn)對(duì)應(yīng)的類數(shù)是比較接近最優(yōu)的類數(shù) 然而在許多情況下 曲線并無(wú)明顯的這樣的點(diǎn) 204 2 4聚類的算法 2 4 3動(dòng)態(tài)聚類法 C 均值法的改進(jìn) 初始聚類中心的選取 憑經(jīng)驗(yàn)選擇初始類心 將模式隨機(jī)地分成C類 計(jì)算每類中心 以其作為初始類心 最大密度 求以每個(gè)特征點(diǎn)為球心 某一正數(shù)d0為半徑的球形域中特征點(diǎn)個(gè)數(shù) 這個(gè)數(shù)稱為該點(diǎn)的密度 選取密度最大的特征點(diǎn)作為第一個(gè)初始類心Z1 然后在與Z1大于某個(gè)距離d的那些特征點(diǎn)中選取具有 最大 密度的特征點(diǎn)作為第二個(gè)初始類心Z2 如此進(jìn)行 選取C個(gè)初始聚類中心 205 2 4聚類的算法 2 4 3動(dòng)態(tài)聚類法 C 均值法的改進(jìn) 初始聚類中心的選取 用相距最遠(yuǎn)的C個(gè)特征點(diǎn)作為初始類心 具體地講 是按前述的最大最小距離算法求取C個(gè)初始聚類中心 當(dāng)N較大時(shí) 先隨機(jī)地從N個(gè)模式中取出一部分模式用譜系聚類法聚成C類 以每類的重心作為初始類心 設(shè)已標(biāo)準(zhǔn)化的待分類模式集為希望將它們分為C類 206 設(shè)已標(biāo)準(zhǔn)化的待分類模式集為希望將它們分為C類 設(shè) 計(jì)算 顯然0 ai C 若ai最接近整數(shù)j 則把xi分劃至中wj 對(duì)所有樣本都實(shí)行上述處理 就可實(shí)現(xiàn)初始分類 從而產(chǎn)生初始聚類中心 207 2 4聚類的算法 2 4 3動(dòng)態(tài)聚類法 C 均值法的改進(jìn) 用類核代替類心 前面的算法存在一個(gè)不足 即只用一個(gè)聚類中心點(diǎn)作為一類的代表 但一個(gè)點(diǎn)往往不能充分地反映該類的模式分布結(jié)構(gòu) 從而損失了很多有用的信息 當(dāng)類的分布不是球狀或近似球狀時(shí) 這種算法很難有較好的效果 此時(shí) 可用類核代替類心 類核可以是一個(gè)函數(shù) 一個(gè)點(diǎn)集或其他適當(dāng)?shù)哪Ｐ?比如前面我們講過(guò)的馬式距離 208 3 動(dòng)態(tài)聚類法 ISODATA算法 IterativeSelf OrganizingDataAnalysisTechniquesAlgorithm迭代自組織數(shù)據(jù)分析 特點(diǎn) 啟發(fā)性推理 分析監(jiān)督 控制聚類結(jié)構(gòu)及人機(jī)交互 算法思想 在每輪迭代過(guò)程中 樣本重新調(diào)整類別之后計(jì)算類內(nèi)及類間有關(guān)參數(shù) 并和設(shè)定的門限比較 確定是兩類合并為一類還是一類分裂為兩類 不斷地 自組織 以達(dá)到在各參數(shù)滿足設(shè)計(jì)要求條件下 使各模式到其類心的距離平方和最小 209 ISODATA算法原理步驟 預(yù)置 設(shè)定聚類分析控制參數(shù) 預(yù)期的類數(shù) 每一類中允許的最少模式數(shù)目 初始聚類中心個(gè)數(shù) 可以不等于c 類內(nèi)各分量分布的距離標(biāo)準(zhǔn)差上界 分裂用 兩類中心間的最小距離下界 合并用 在每次迭代中可以合并的類的最多對(duì)數(shù) 允許的最多迭代次數(shù) 210 ISODATA算法原理步驟 211 ISODATA算法原理步驟 212 ISODATA算法原理步驟 計(jì)算各類的中心 計(jì)算分類后的參數(shù) 各類中心 類內(nèi)平均距離及總體平均距離 計(jì)算各類中模式到類心的平均距離 計(jì)算各個(gè)模式到其類內(nèi)中心的總體平均距離 213 ISODATA算法原理步驟 214 ISODATA算法原理步驟 計(jì)算各類類內(nèi)距離的標(biāo)準(zhǔn)差矢量 式中 為分量編號(hào) 為類的編號(hào) 為矢量維數(shù) 是的第個(gè)分量 是的第個(gè)分量 215 ISODATA算法原理步驟 216 ISODATA算法原理步驟 217 ISODATA算法原理步驟 218 ISODATA算法原理步驟 219 220 ISODATA算法舉例 二維 1 初始值設(shè)定 類間距離上限 距離標(biāo)準(zhǔn)差上界 最少模式數(shù)目 合并的類的最多對(duì)數(shù) 221 ISODATA算法舉例 2 聚類 只有一個(gè)中心 222 ISODATA算法舉例 3 因 無(wú)合并 4 計(jì)算聚類中心 類內(nèi)平均距離和總的平均距離 223 ISODATA算法舉例 5 因不是最后一步迭代 且 轉(zhuǎn)至 6 求的標(biāo)準(zhǔn)差矢量 224 ISODATA算法舉例 7 算得 6 因且將分裂成兩類 取 則 且轉(zhuǎn) 2 225 ISODATA算法舉例 2 聚類 兩個(gè)中心 3 因 無(wú)合并 226 ISODATA算法舉例 4 計(jì)算聚類中心 類內(nèi)平均距離和總的平均距離 5 因這是偶次迭代 滿足算法原理步驟 中 的條件 故轉(zhuǎn) 227 ISODATA算法舉例 11 因不是最后一次迭代 題設(shè) 判斷是否修改參數(shù) 由上面結(jié)果可知 已獲得所要求類別數(shù)目 類間距離大于類內(nèi)距離 每類樣本數(shù)都有樣本總數(shù)的足夠大的百分比 因此不改變參數(shù) 228 2 4 計(jì)算結(jié)果與前一次迭代結(jié)果相同 7 分裂條件不滿足 轉(zhuǎn)至 無(wú)新的變化 轉(zhuǎn)至 6 計(jì)算和的標(biāo)準(zhǔn)差矢量 5 沒(méi)有任一種情況被滿足 到 與前一次迭代結(jié)果相同 無(wú)合并發(fā)生 229 與前一次迭代結(jié)果相同 因是最后一次迭代 令 轉(zhuǎn)至 同前 因 無(wú)合并發(fā)生 因是最后一次迭代 結(jié)束 230 ISODATA流程 231 232 233 輸入樣本數(shù)據(jù) 置c Nc 選初始類心zj j 1 2 Nc 1 置控制參數(shù) n s D L I 2 聚類 ifdil min D xi z1 D xi z2 D xi zNc thenxi l 3 合并判決 nj n N Y Nc Nc 1 4 計(jì)算分類后的參數(shù) 類心zj 類內(nèi)平均距離dj 總類內(nèi)平均距離d 234 作業(yè) P45 2 9 2 10 235 模式識(shí)別 主講 蔡宣平教授電話 73441 O 73442 H E mail xpcai 單位 電子科學(xué)與工程學(xué)院信息工程系 236 第三章判別域代數(shù)界面方程法 3 1用判別域界面方程分類的概念 3 2線性判別函數(shù) 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 3 4Fisher線性判別 3 5一次準(zhǔn)則函數(shù)及梯度下降法 3 6二次準(zhǔn)則函數(shù)及其解法 3 9廣義線性判別函數(shù) 3 10二次判別函數(shù) 3 12位勢(shì)函數(shù)分類法 237 3 1用判別域界面方程分類的概念 238 兩類的分類問(wèn)題 它們的邊界線就是一個(gè)判別函數(shù) 239 兩類問(wèn)題中線性不可分的實(shí)例 240 三類的分類問(wèn)題 它們的邊界線也是一個(gè)判別函數(shù) 241 3 1用判別域界面方程分類的概念 第三章判別域代數(shù)界面方程法 242 3 2線性判別函數(shù) 第三章判別域代數(shù)界面方程法 243 244 245 多類問(wèn)題圖例 第一種情況 不確定區(qū)域 246 1 第一種情況 續(xù) 判別規(guī)則為 如果 則判 比如對(duì)圖的三類問(wèn)題 如果對(duì)于任一模式如果它的則該模式屬于 1類 247 1 第一種情況 續(xù) 如果某個(gè)X使二個(gè)以上的判別函數(shù)di 0 則此模式X就無(wú)法作出確切的判決 如圖 另一種情況是IR2區(qū)域 判別函數(shù)都為負(fù)值 IR1 IR2 IR3 IR4 都為不確定區(qū)域 248 1 第一種情況 續(xù) 解 三個(gè)判別邊界分別為 249 1 第一種情況 續(xù) 結(jié)論 因?yàn)樗运鼘儆?2類 250 1 第一種情況 續(xù) 251 252 2 第二種情況 續(xù) 多類問(wèn)題圖例 第二種情況 253 254 d12 x d21 x x1 x2 5 0 d12 x 為正 兩分法例題圖示 d21 x 為正 255 d23 x d32 x x1 x2 0 d32 x 為正 d23 x 為正 256 d13 x d31 x x1 3 0 d31 x 為正 d13 x 為正 257 3類判別區(qū)域d31 x 0d32 x 0 258 259 3 第三種情況 續(xù) 多類問(wèn)題圖例 第三種情況 260 261 上述三種方法小結(jié) 方法 判別函數(shù)的數(shù)目和方法 相同 但沒(méi)有不確定區(qū) 分析簡(jiǎn)單 是最常用的一種方法 262 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 第三章判別域代數(shù)界面方程法 263 此方程表示一超平面 它有以下三個(gè)性質(zhì) 1 系數(shù)矢量 是該平面的法矢量 2 判別函數(shù)的絕對(duì)值正比于到超平面的距離 3 判別函數(shù)值的正負(fù)表示出特征點(diǎn)位于哪個(gè)半空間中 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 第三章判別域代數(shù)界面方程法 264 圖3 3 1點(diǎn)面距離及界面的正負(fù)側(cè)示意圖 265 266 267 268 證明 判別函數(shù)值的正負(fù)表示出特征點(diǎn)位于哪個(gè)半空間中 269 這說(shuō)明判別函數(shù)值的正負(fù)表示出特征點(diǎn)位于哪個(gè)半空間中 或者換句話說(shuō) 表示特征點(diǎn)位于界面的哪一側(cè) 270 例3 3 1 利用判別函數(shù)的鑒別意義 試分析d x1 x2 x1 x2 1 271 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 272 2 解矢量 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 273 2 解矢量 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 274 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 275 3 解空間 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 先看一個(gè)簡(jiǎn)單的情況 設(shè)一維數(shù)據(jù)1 2屬于w1 1 2屬于w2求將w1和w2區(qū)分開(kāi)的w0 w1 276 3 解空間 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 先看一個(gè)簡(jiǎn)單的情況 設(shè)一維數(shù)據(jù)1 2屬于w1 1 2屬于w2求將w1和w2區(qū)分開(kāi)的w0 w1 w0 w1 277 3 解空間 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 先看一個(gè)簡(jiǎn)單的情況 設(shè)一維數(shù)據(jù)1 2屬于w1 1 2屬于w2求將w1和w2區(qū)分開(kāi)的w0 w1 w0 w1 278 3 解空間 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 先看一個(gè)簡(jiǎn)單的情況 設(shè)一維數(shù)據(jù)1 2屬于w1 1 2屬于w2求將w1和w2區(qū)分開(kāi)的w0 w1 w0 w1 279 3 解空間 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 先看一個(gè)簡(jiǎn)單的情況 設(shè)一維數(shù)據(jù)1 2屬于w1 1 2屬于w2求將w1和w2區(qū)分開(kāi)的w0 w1 w0 w1 280 3 解空間 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 先看一個(gè)簡(jiǎn)單的情況 設(shè)一維數(shù)據(jù)1 2屬于w1 1 2屬于w2求將w1和w2區(qū)分開(kāi)的w0 w1 w0 w1 281 3 解空間 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 282 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 每一個(gè)訓(xùn)練模式都對(duì)解區(qū)提供一個(gè)約束 訓(xùn)練模式越多 解區(qū)的限制就越多 解區(qū)就越小 就越靠近解區(qū)的中心 解矢量就越可靠 由它構(gòu)造的判別函數(shù)錯(cuò)分的可能性就越小 283 4 余量 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 284 4 余量 3 3 2權(quán)空間 解矢量與解空間 3 3判別函數(shù)值的鑒別意義 權(quán)空間及解空間 引入了余量可有效地避免量測(cè)的誤差 引入的誤差以及某些算法求得的解矢量收斂于解區(qū)的邊界上 從而提高了解的可靠性 285 設(shè)一3類問(wèn)題有如下判決函數(shù)d1 x x1d2 x x1 x2 1d3 x x1 x2 1試畫出下列各種情況的判決邊界及各類的區(qū)域 1 滿足3 4 2節(jié)中的第一種情況 2 滿足3 4 2節(jié)中的第二種情況 且令d12 x d1 x d13 x d2 x d23 x d3 x 3 滿足3 4 2節(jié)中的第三種情況 作業(yè) 286 3 4Fisher線性判別 第三章判別域代數(shù)界面方程法 287 二維模式向一維空間投影示意圖 288 二維模式向一維空間投影示意圖 289 二維模式向一維空間投影示意圖 o x y o x y 290 1 求解Fish準(zhǔn)則函數(shù) 291 292 類間離差度為 293 并使其最大 上式稱為Fisher準(zhǔn)則函數(shù) 294 利用二次型關(guān)于矢量求導(dǎo)的公式可得 2 求解Fisher最佳鑒別矢量 令 可得 295 296 上式右邊后兩項(xiàng)因子的乘積為一標(biāo)量 令其為 于是可得式中為一標(biāo)量因子 其不改變軸的方向 可以取為1 于是有 297 此時(shí)的可使Fisher準(zhǔn)則函數(shù)取最大值 即是n維空間到一維空間投影軸的最佳方向 由 和 JF最大值為 298 即稱為Fisher變換函數(shù) JF 299 由于變換后的模式是一維的 因此判別界面實(shí)際上是各類模式所在軸上的一個(gè)點(diǎn) 所以可以根據(jù)訓(xùn)練模式確定一個(gè)閾值yt 于是Fisher判別規(guī)則為 3 求解Fisher判別函數(shù) 判別閾值可取兩個(gè)類心在u方向上軸的投影連線的中點(diǎn)作為閾值 即 300 301 7 計(jì)算 8 計(jì)算yt 9 對(duì)未知模式x判定模式類 302 以100元A面數(shù)據(jù)和50元A面數(shù)據(jù)