模式識別詳細PPT.ppt

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