模式識別_第三章_判別函數(shù)PPT課件

《模式識別_第三章_判別函數(shù)PPT課件》由會員分享，可在線閱讀，更多相關《模式識別_第三章_判別函數(shù)PPT課件（134頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第三章判別函數(shù)及幾何分類法 第三章判別函數(shù) 3 1判別函數(shù)3 2線性判別函數(shù)3 3廣義線性判別函數(shù)3 4線性判別函數(shù)的幾何性質3 5感知器算法3 6梯度法3 7最小平方誤差算法3 8非線性判別函數(shù) 3 1判別函數(shù) 聚類分析法 第二章 判決函數(shù)法 幾何分類法 確定性事件分類 第三章 概率分類法 隨機事件分類 第四章 線性判決函數(shù)法 統(tǒng)計決策方法 非線性判決函數(shù)法 復習與引申 3 1判別函數(shù) 1 判別函數(shù)定義 用判別函數(shù)分類的概念模式識別系統(tǒng)的主要作用判別各個模式所屬的類別對一個兩類問題的判別 就是將模式x劃分成 1和 2兩類 3 1判別函數(shù) 1 定義 用判別函數(shù)分類的概念描述 兩類問題的判別函數(shù) 若分屬于 1 2的兩類模式可用一方程d X 0來劃分 那么稱d X 為判別函數(shù) 或稱判決函數(shù) 決策函數(shù) 3 1判別函數(shù) discriminantfunction 直接用來對模式進行分類的準則函數(shù) 例 一個二維的兩類判別問題 模式分布如圖示 這些分屬于 1 2兩類的模式可用一直線方程d X 0來劃分 為坐標變量 為方程參數(shù) 式中 圖3 2兩類二維模式的分布 1 判別函數(shù)的定義 具體描述 若 則 若 則類 若 則類 或拒絕 將某一未知模式X代入 維數(shù) 3時 判別邊界為一平面 維數(shù) 3時 判別邊界為一超平面 d X 表示的是一種分類的標準 它可以是1 2 3維的 也可以是更高維的 判別界面的正負側 是在訓練判別函數(shù)的權值時確定的 2 判別函數(shù)正負值的確定 圖3 3判別函數(shù)正負的確定 1 判決函數(shù)d X 的幾何性質 它可以是線性的或非線性的函數(shù) 維數(shù)在特征提取時已經(jīng)確定 如 已知三維線性分類 判決函數(shù)的性質就確定了判決函數(shù)的形式 3 確定判別函數(shù)的兩個因素 例 非線性判決函數(shù) 2 判決函數(shù)d X 的系數(shù) 用所給的模式樣本確定 3 2線性判別函數(shù) 3 2 1線性判別函數(shù)的一般形式 將二維模式推廣到n維 線性判別函數(shù)的一般形式為 3 2 式中 權向量 即參數(shù)向量 增廣向量的形式 式中 為增廣權向量 為增廣模式向量 3 2 2線性判別函數(shù)的性質 1 兩類情況 對M個線性可分模式類 1 2 M 有三種劃分方式 2 多類情況 兩分法 兩分法 兩分法特例 3 2線性判別函數(shù) 3 2 2線性判別函數(shù)的性質分類問題多類情況1判別函數(shù)圖例 例子 用線性判別函數(shù)將屬于 i類的模式與其余不屬于 i類的模式分開 識別分類時 對某一模式區(qū) di X 0的條件超過一個 或全部的di X 0 分類失效 相當于不確定區(qū) indefiniteregion IR 此法將M個多類問題分成M個兩類問題 識別每一類均需M個判別函數(shù) 識別出所有的M類仍是這M個函數(shù) 例3 1設有一個三類問題 其判別式為 現(xiàn)有一模式 X 7 5 T 試判定應屬于哪類 并畫出三類模式的分布區(qū)域 解 將X 7 5 T代入上三式 有 三個判別界面分別為 圖示如下 步驟 a 畫出界面直線 b 判別界面正負側 找特殊點帶入 c 找交集 例3 2已知di X 的位置和正負側 分析三類模式的分布區(qū)域 一個判別界面只能分開兩個類別 不能把其余所有的類別都分開 判決函數(shù)為 這里 則類 而在判別類模式時不起作用 如 對一個三類問題 如果 識別分類時 判別函數(shù)性質 與值無關 例3 3一個三類問題 三個判決函數(shù)為 解 計算得 可寫成 x2 x1 d23 X 0 d12 X 0 d13 X 0 5 5 3 0 分類時 每分離出一類 需要與I有關的M 1個判決函數(shù) 要分開M類模式 共需M M 1 2個判決函數(shù) 對三類問題需要3 3 1 2 3個判決函數(shù) 即 每次從M類中取出兩類的組合 例3 4已知dij X 的位置和正負側 分析三類模式的分布區(qū)域 當 i j兩分法中的判別函數(shù)dij X 可以分解為 時 那么di X dj X 就相當于多類情況2中的dij X 0 因此對具有判別函數(shù) 的M類情況 判別函數(shù)性質為 或 識別分類時 判別界面需要做差值 對 i類 應滿足 di 其他所有d 除邊界區(qū)外 沒有不確定區(qū)域 特點 是第二種情況的特例 由于dij X di X dj X 若在第三種情況下可分 則在第二種情況下也可分 但反過來不一定 把M類情況分成了 M 1 個兩類問題 并且類的判別界面全部與類的判別界面相鄰 向無窮遠處延伸的區(qū)域除外 例3 5一個三類模式 M 3 分類器 其判決函數(shù)為 試判斷X0 1 1 T屬于哪一類 且分別給出三類的判決界面 解 判決界面如圖所示 類的判決函數(shù) 類的判決函數(shù) 例3 6已知判決界面的位置和正負側 分析三類模式的分布區(qū)域 3 2線性判別函數(shù) 3 2 2線性判別函數(shù)的性質及分類方法3 小結明確概念 線性可分模式分類若可用任一個線性函數(shù)來劃分 則這些模式就稱為線性可分的 否則就是非線性可分的 一旦線性函數(shù)的系數(shù)wk被確定 這些函數(shù)就可用作模式分類的基礎 3 2線性判別函數(shù) 3 2 2線性判別函數(shù)的性質及分類方法多類情況1和多類情況2 的比較對于M類模式的分類 多類情況1需要M個判別函數(shù) 而多類情況2需要M M 1 2個判別函數(shù) 當M 3時 后者需要更多個判別式 缺點 采用多類情況1時 每一個判別函數(shù)都要把一種類別的模式與其余M 1種類別的模式分開 而不是將一種類別的模式僅于另一種類別的模式分開 由于一種模式的分布要比M 1種模式的分布更為聚集 因此多類情況2受到的限制條件少 對模式的線性可分的可能性比多類情況1更大一些 這是多類情況2的一個優(yōu)點 3 3廣義線性判別函數(shù) 出發(fā)點線性判別函數(shù)簡單 容易實現(xiàn) 非線性判別函數(shù)復雜 不容易實現(xiàn) 若能將非線性判別函數(shù)轉換為線性判別函數(shù) 則有利于模式分類的實現(xiàn) 3 3廣義線性判別函數(shù) 基本思想設有一個訓練用的模式集 x 在模式空間x中線性不可分 但在模式空間x 中線性可分 其中x 的各個分量是x的單值實函數(shù) x 的維數(shù)k高于x的維數(shù)n 即若取x f1 x f2 x fk x k n則分類界面在x 中是線性的 在x中是非線性的 此時只要將模式x進行非線性變換 使之變換后得到維數(shù)更高的模式x 就可以用線性判別函數(shù)來進行分類 描述 1 非線性多項式函數(shù)非線性判別函數(shù)的形式之一是非線性多項式函數(shù) 3 3廣義線性判別函數(shù) 目的 對非線性邊界 通過某映射 把模式空間X變成X 以便將X空間中非線性可分的模式集 變成在X 空間中線性可分的模式集 設一訓練用模式集 X 在模式空間X中線性不可分 非線性判別函數(shù)形式如下 3 9 式中是模式X的單值實函數(shù) fi X 取什么形式及d X 取多少項 取決于非線性邊界的復雜程度 廣義形式的模式向量定義為 3 10 這里X 空間的維數(shù)k高于X空間的維數(shù)n 3 9 式可寫為 上式是線性的 討論線性判別函數(shù)并不會失去一般性的意義 3 11 隨著小樣本學習理論和支持向量機的迅速發(fā)展 廣義線性判別函數(shù)的 維數(shù)災難 問題在一定程度上找到了解決的辦法 非線性變換可能非常復雜 問題 維數(shù)大大增加 維數(shù)災難 例3 7假設X為二維模式向量 fi X 選用二次多項式函數(shù) 原判別函數(shù)為 定義 d X 線性化為 即 廣義線性判別函數(shù) 3 4線性判別函數(shù)的幾何性質 3 4 1模式空間與超平面 模式空間 以n維模式向量X的n個分量為坐標變量的歐氏空間 模式向量的表示 點 有向線段 線性分類 用d X 進行分類 相當于用超平面d X 0把模式空間分成不同的決策區(qū)域 2 討論 1 概念 式中 設判別函數(shù) 超平面 1 模式向量X1和X2在超平面上 W0是超平面的法向量 方向由超平面的負側指向正側 設超平面的單位法線向量為U 2 X不在超平面上 將X向超平面投影得向量Xp 構造向量R r X到超平面的垂直距離 有 r 判別函數(shù)d X 正比于點X到超平面的代數(shù)距離 X到超平面的距離 點X到超平面的代數(shù)距離 帶正負號 正比于d X 函數(shù)值 3 X在原點 得 超平面的位置由閾值權wn 1決定 wn 1 0時 原點在超平面的正側 wn 1 0時 原點在超平面負側 wn 1 0時 超平面通過原點 3 4 2權空間與權向量解 1 概念 權空間 以的權系數(shù)為坐標變量的 n 1 維歐氏空間 增廣權向量的表示 點 有向線段 2 線性分類 判別函數(shù)形式已定 只需確定權向量 類 X11 X12 X1p 類 X21 X22 X2q 設增廣樣本向量 使d X 將 1和 2分開 需滿足 給 2的q個增廣模式乘以 1 統(tǒng)一為 其中 樣本的規(guī)范化過程 對每個已知的X d X 0在權空間確定一個超平面 共 p q 個 在權空間中尋找向量W使判別函數(shù)d X 能把 1類和 2類分開 就是尋找一個權向量 其在 p q 個超平面的正側的交迭區(qū)域里 W的解區(qū) X 規(guī)范化增廣樣本向量 例 二維權空間 超平面的方程為 超平面 過原點的直線 陰影部分 解區(qū) 3 4 3二分法 二分法 Dichotomies 用判別函數(shù)d X 將給定的N個模式分成兩類的方法 是一種基本的分類方法 判別函數(shù)的不同分類能力可以通過二分法總數(shù)衡量 若不限制判別函數(shù)的形式 N個n維模式用判別函數(shù)分成兩類的二分法總數(shù)為2N 若限定用線性判別函數(shù) 并且樣本在模式空間是良好分布的 即在n維模式空間中沒有 n 1 個模式位于 n 1 維子空間中 可以證明 N個n維模式用線性判別函數(shù)分成兩類的方法總數(shù) 即線性二分法總數(shù)為 或線性二分法概率 只要模式的個數(shù)N小于或等于增廣模式的維數(shù) n 1 模式類總是線性可分的 例 4個良好分布的2維模式 若用線性判別函數(shù)分類 線性二分法總數(shù) 線性二分法概率 圖3 14線性二分法的概率 將 2時的N值定義為閾值N0 稱為二分法能力 即 通過N0 可以對任意N個樣本的線性可分性進行粗略估計 3 5感知器算法 出發(fā)點一旦判別函數(shù)的形式確定下來 不管它是線性的還是非線性的 剩下的問題就是如何確定它的系數(shù) 在模式識別中 系數(shù)確定的一個主要方法就是通過對已知樣本的訓練和學習來得到 感知器算法就是通過訓練樣本模式的迭代和學習 產(chǎn)生線性 或廣義線性 可分的模式判別函數(shù) 3 5感知器算法 基本思想采用感知器算法 PerceptionApproach 能通過對訓練模式樣本集的 學習 得到判別函數(shù)的系數(shù) 說明這里采用的算法不需要對各類別中模式的統(tǒng)計性質做任何假設 因此稱為確定性的方法 3 5感知器算法 背景 感知器 一詞出自于20世紀50年代中期到60年代中期人們對一種分類學習機模型的稱呼 它是屬于有關動物和機器學習的仿生學領域中的問題 當時的一些研究者認為感知器是一種學習機的強有力模型 后來發(fā)現(xiàn)估計過高了 但發(fā)展感知器的一些相關概念仍然沿用下來 3 5感知器算法 1 概念理解 訓練 用已知類別的模式樣本指導機器對分類規(guī)則進行反復修改 最終使分類結果與已知類別信息完全相同的過程 1 訓練與學習 只要求出權向量 分類器的設計即告完成 本節(jié)開始介紹如何通過各種算法 利用已知類別的模式樣本訓練出權向量W 對線性判別函數(shù) 當模式維數(shù)已知時 判別函數(shù)的形式實際上已經(jīng)確定 如 三維時 3 感知器對一種分類學習機模型的稱呼 屬于有關機器學習的仿生學領域中的問題 由于無法實現(xiàn)非線性分類而下馬 但 賞罰概念 reward punishmentconcept 得到廣泛應用 2 確定性分類器 處理確定可分情況的分類器 通過幾何方法將特征空間分解為對應不同類的子空間 又稱為幾何分類器 2 感知器算法 perceptionapproach 兩類線性可分的模式類 設 其中 應具有性質 對樣本進行規(guī)范化處理 即 2類樣本全部乘以 1 則有 感知器算法通過對已知類別的訓練樣本集的學習 尋找一個滿足上式的權向量 感知器算法步驟 1 選擇N個分屬于 1和 2類的模式樣本構成訓練樣本集 X1 XN 構成增廣向量形式 并進行規(guī)范化處理 任取權向量初始值W 1 開始迭代 迭代次數(shù)k 1 2 用全部訓練樣本進行一輪迭代 計算WT k Xi的值 并修正權向量 分兩種情況 更新權向量的值 c 正的校正增量 分類器對第i個模式做了錯誤分類 權向量校正為 統(tǒng)一寫為 3 分析分類結果 只要有一個錯誤分類 回到 2 直至對所有樣本正確分類 分類正確時 對權向量 賞 這里用 不罰 即權向量不變 分類錯誤時 對權向量 罰 對其修改 向正確的方向轉換 感知器算法是一種賞罰過程 3 收斂性 收斂性 經(jīng)過算法的有限次迭代運算后 求出了一個使所有樣本都能正確分類的W 則稱算法是收斂的 可以證明感知器算法是收斂的 收斂條件 模式類別線性可分 例3 8已知兩類訓練樣本 解 所有樣本寫成增廣向量形式 進行規(guī)范化處理 屬于 2的樣本乘以 1 用感知器算法求出將模式分為兩類的權向量解和判別函數(shù) 任取W 1 0 取c 1 迭代過程為 第一輪 有兩個WT k Xi 0的情況 錯判 進行第二輪迭代 第二輪 第三輪 第四輪 該輪迭代的分類結果全部正確 故解向量 相應的判別函數(shù)為 當c W 1 取其他值時 結果可能不一樣 所以感知器算法的解不是單值的 判別界面d X 0如圖示 采用多類情況3的方法時 應有 4 感知器算法用于多類情況 對于M類模式應存在M個判決函數(shù) 算法主要內容 設有M種模式類別 設其權向量初值為 第k次迭代時 一個屬于 i類的模式樣本X被送入分類器 計算所有判別函數(shù) 訓練樣本為增廣向量形式 但不需要規(guī)范化處理 分二種情況修改權向量 若第l個權向量使 則相應的權向量作調整 即 可以證明 只要模式類在情況3判別函數(shù)時是可分的 則經(jīng)過有限次迭代后算法收斂 c為正的校正增量 例3 9設有三個線性可分的模式類 三類的訓練樣本分別為 若則權向量不變 現(xiàn)采用多類情況3的方式分類 試用感知器算法求出判別函數(shù) 解 增廣向量形式 注意 這里任一類的樣本都不能乘以 1 任取初始權向量 c 1 第一次迭代 三個權向量都需要修改 第二次迭代 第三次迭代 修改為權向量 以上進行的一輪迭代運算中 三個樣本都未正確分類 進行下一輪迭代 第四次迭代 在第五 六 七迭代中 對所有三個樣本都已正確分類 權向量的解 判別函數(shù) 4 采用感知器算法的多類模式的分類 討論這里的分類算法都是通過模式樣本來確定判別函數(shù)的系數(shù) 但一個分類器的判斷性能最終要受并未用于訓練的那些未知樣本來檢驗 要使一個分類器設計完善 必須采用有代表性的訓練數(shù)據(jù) 它能夠合理反映模式數(shù)據(jù)的整體 4 采用感知器算法的多類模式的分類 討論要獲得一個判別性能好的線性分類器 究竟需要多少訓練樣本 直觀上是越多越好 但實際上能收集到的樣本數(shù)目會受到客觀條件的限制 過多的訓練樣本在訓練階段會使計算機需要較長的運算時間 一般來說 合適的樣本數(shù)目可如下估計 若k是模式的維數(shù) 令C 2 k 1 則通常選用的訓練樣本數(shù)目約為C的10 20倍 3 6梯度法 定義梯度是一個向量 它的最重要性質就是指出了函數(shù)f在其自變量y增加時最大增長率的方向 負梯度指出f的最陡下降方向利用這個性質 可以設計一個迭代方案來尋找函數(shù)的最小值 設函數(shù)f Y 是向量的函數(shù) 則f Y 的梯度定義為 3 6梯度法 梯度的方向是函數(shù)f Y 在Y點增長最快的方向 梯度的模是f Y 在增長最快的方向上的增長率 增長率最大值 1 梯度概念 梯度向量的最重要性質之一 指出函數(shù)f在其自變量增加時 增長最快的方向 3 6 1梯度法基本原理 顯然 負梯度指出了最陡下降方向 梯度算法的依據(jù) 即 2 梯度算法 設兩個線性可分的模式類 1和 2的樣本共N個 2類樣本乘 1 將兩類樣本分開的判決函數(shù)d X 應滿足 梯度算法的目的仍然是求一個滿足上述條件的權向量 主導思想是將聯(lián)立不等式求解W的問題 轉換成求準則函數(shù)極小值的問題 N個不等式 準則函數(shù)的選取原則 具有唯一的最小值 并且這個最小值發(fā)生在WTXi 0時 用負梯度向量的值對權向量W進行修正 實現(xiàn)使準則函數(shù)達到極小值的目的 定義一個對錯誤分類敏感的準則函數(shù)J W X 在J的梯度方向上對權向量進行修改 一般關系表示成從W k 導出W k 1 其中c是正的比例因子 1 將樣本寫成規(guī)范化增廣向量形式 選擇準則函數(shù) 設置初始權向量W 1 括號內為迭代次數(shù)k 1 權向量修正為 迭代次數(shù)k加1 輸入下一個訓練樣本 計算新的權向量 直至對全部訓練樣本完成一輪迭代 3 在一輪迭代中 如果有一個樣本使 回到 2 進行下一輪迭代 否則 W不再變化 算法收斂 2 依次輸入訓練樣本X 設第k次迭代時輸入樣本為Xi 此時已有權向量W k 求 3 6梯度法 采用梯度法求解的基本思想對感知器算法式中的w k xk隨迭代次數(shù)k而變 是變量 定義一個對錯誤分類敏感的準則函數(shù)J w x 先任選一個初始權向量w 1 計算準則函數(shù)J的梯度 然后從w 1 出發(fā) 在最陡方向 梯度方向 上移動某一距離得到下一個權向量w 2 從w k 導出w k 1 的一般關系式 3 6梯度法 討論若正確地選擇了準則函數(shù)J w x 則當權向量w是一個解時 J達到極小值 J的梯度為零 由于權向量是按J的梯度值減小 因此這種方法稱為梯度法 最速下降法 為了使權向量能較快地收斂于一個使函數(shù)J極小的解 C值的選擇是很重要的 若C值太小 則收斂太慢 若C值太大 則搜索可能過頭 引起發(fā)散 例3 10選擇準則函數(shù) 簡單地考慮X為一維增廣模式的情況X 1 此時W w 兩者均為標量 錯誤分類時 對權向量校正 正確分類時 對權向量不做修正 隨著權向量W向理想值接近 準則函數(shù)關于W的導數(shù) 越來越趨近于零 這意味著準則函數(shù)J越來越接近最小值 當最終時 J達到最小值 此時W不再改變 算法收斂 將感知器算法中聯(lián)立不等式求解W的問題 轉換為求函數(shù)J極小值的問題 c 梯度算法是求解權向量的一般解法 算法的具體計算形式取決于準則函數(shù)J W X 的選擇 J W X 的形式不同 得到的具體算法不同 a b c值的選擇很重要 如c值太小 收斂太慢 但若太大 搜索又可能過頭 甚至引起發(fā)散 3 6 2固定增量法 準則函數(shù) 求W k 的遞推公式 1 求J的梯度 方法 函數(shù)對向量求導 函數(shù)對向量的分量求導 即 該準則函數(shù)有唯一最小值 0 且發(fā)生在的時候 設 部分 首先求 另 矩陣論中有 其中 由 的結論有 將代入 得 由此可以看出 感知器算法是梯度法的特例 即 梯度法是將感知器算法中聯(lián)立不等式求解W的問題 轉換為求函數(shù)J極小值的問題 將原來有多個解的情況 變成求最優(yōu)解的情況 上式即為固定增量算法 與感知器算法形式完全相同 即 只要模式類是線性可分的 算法就會給出解 3 6 2固定增量法 過程說明 設已由前一步迭代得到w k 的值 讀入模式樣本xk 判別wT k xk是否大于0 xk界定的判別界面為wT k xk 0 當w k 在判別界面的負區(qū)域時 wT k xk 0 校正 w k 1 w k xk 這里取C 1 校正后 w k 1 向量比w k 向量更接近于模式xk所決定的正區(qū)域 3 6 2固定增量法 討論若模式是線性可分的 選擇合適的準則函數(shù)J w x 算法就能給出解 若模式不是線性可分的 算法的結果就會來回擺動 得不到收斂 3 7最小平方誤差算法 leastmeansquareerror LMSE 亦稱Ho Kashyap算法 出發(fā)點感知器算法只是當被分模式可用一個特定的判別界面分開時才收斂 在不可分情況下 只要計算程序不終止 它就始終不收斂 即使在模式可分的情況下 也很難事先算出達到收斂時所需要的迭代次數(shù) 這樣 在模式分類過程中 有時候會出現(xiàn)一次又一次迭代卻不見收斂的情況 白白浪費時間 為此需要知道 發(fā)生遲遲不見收斂的情況時 到底是由于收斂速度過慢造成的呢 還是由于所給的訓練樣本集不是線性可分造成的呢 最小平方誤差 LMSE 算法 除了對可分模式是收斂的以外 對于類別不可分的情況也能指出來 1 分類器的不等式方程 上式分開寫為 寫成矩陣形式為 令N n 1 的長方矩陣為X 則變?yōu)?式中 0為零向量 感知器算法是通過解不等式組 求出W 2 LMSE算法 1 原理 的求解 式中 兩式等價 為各分量均為正值的矢量 LMSE算法把對滿足XW 0的求解 改為滿足 準則函數(shù)定義為 最小二乘 最小 使方程組兩邊誤差最小 也即使J最小 二乘 次數(shù)為2 乘了兩次 考察向量 XW B 有 可以看出 當函數(shù)J達到最小值 等式XW B有最優(yōu)解 即又將問題轉化為求準則函數(shù)極小值的問題 因為J有兩個變量W和B 有更多的自由度供選擇求解 故可望改善算法的收斂速率 XW B的近似解也稱 最優(yōu)近似解 使方程組兩邊所有誤差之和最小 即最優(yōu) 的解 準則函數(shù) 使J對W求最小 令 得 2 推導LMSE算法遞推公式 與問題相關的兩個梯度 3 46 3 47 由 3 47 式可知 只要求出B 就可求出W 求遞推公式 1 求W的遞推關系 X為N n 1 長方陣 X 為 n 1 N長方陣 稱為X的偽逆 式中 3 45 2 求B k 1 的迭代式 3 46 代入 得 令 定義 3 49 3 50 3 求W k 1 的迭代式 將 3 50 代入 3 47 式W X B有 總結 設初值B 1 各分量均為正值 括號中數(shù)字代表迭代次數(shù) W k 1 B k 1 互相獨立 先后次序無關 求出B W后 再迭代出下一個e 從而計算出新的B W 或另一算法 先算B k 1 再算W k 1 3 模式類別可分性判別 如果e k 0 表明XW k B k 0 隱含有解 繼續(xù)迭代 可使e k 0 如果e k 0 所有分量為負數(shù)或零 但不全為零 停止迭代 無解 此時若繼續(xù)迭代 數(shù)據(jù)不再發(fā)生變化 可以證明 當模式類線性可分 且校正系數(shù)c滿足時 該算法收斂 可求得解W 理論上不能證明該算法到底需要迭代多少步才能達到收斂 通常在每次迭代計算后檢查一下XW k 和誤差向量e k 從而可以判斷是否收斂 如果e k 0 表明XW k B k 0 有解 分以下幾種情況 情況 分析 e k 0 綜上所述 只有當e k 中有大于零的分量時 才需要繼續(xù)迭代 一旦e k 的全部分量只有0和負數(shù) 則立即停止 事實上 往往早在e k 全部分量都達到非正值以前 就能看出其中有些分量向正值變化得極慢 可及早采取對策 通過反證法可以證明 在線性可分情況下 算法進行過程中不會出現(xiàn)e k 的分量全為負的情況 若出現(xiàn)e k 的分量全為負 則說明模式類線性不可分 4 LMSE算法描述 1 根據(jù)N個分屬于兩類的樣本 寫出規(guī)范化增廣樣本矩陣X 2 求X的偽逆矩陣 3 設置初值c和B 1 c為正的校正增量 B 1 的各分量大于零 迭代次數(shù)k 1 開始迭代 計算 4 計算 進行可分性判別 如果e k 0 線性可分 若進入 5 可使e k 0 得最優(yōu)解 如果e k 0 線性不可分 停止迭代 無解 算法結束 如果e k 0 線性可分 解為W k 算法結束 否則 說明e k 的各分量值有正有負 進入 5 5 計算W k 1 和B k 1 方法1 分別計算 方法2 先計算 再計算 迭代次數(shù)k加1 返回 4 3 算法特點 1 算法盡管略為復雜一些 但提供了線性可分的測試特征 2 同時利用N個訓練樣本 同時修改W和B 故收斂速度快 3 計算矩陣復雜 但可用迭代算法計算 例3 11已知兩類模式訓練樣本 試用LMSE算法求解權向量 解 1 寫出規(guī)范化增廣樣本矩陣 Aij是aij的代數(shù)余子式 注意兩者的行和列的標號互換 2 求偽逆矩陣 求逆矩陣 劃去aij所在的行和列的元素 余下元素構成的行列式做aij的余子式 記作Mij 將叫做元素aij的代數(shù)余子式 例 代數(shù)余子式定義 行列式 3 取和c 1開始迭代 解為W 1 判斷函數(shù)為 圖示如下 例3 12已知模式訓練樣本 2 求 解 1 規(guī)范化增廣樣本矩陣 3 取和c 1 迭代 用LMSE算法求解權向量 e 1 全部分量為負 無解 停止迭代 為線性不可分模式 小結 1 感知器法 梯度法 最小平方誤差算法討論的分類算法都是通過模式樣本來確定判別函數(shù)的系數(shù) 所以要使一個分類器設計完善 必須采用有代表性的數(shù)據(jù) 訓練判別函數(shù)的權系數(shù) 它們能合理反映模式數(shù)據(jù)的總體 2 要獲得一個有較好判別性能的線性分類器 所需要的訓練樣本的數(shù)目的確定 用指標二分法能力N0來確定訓練樣本的數(shù)目 通常訓練樣本的數(shù)目不能低于N0 選為N0的5 10倍左右 二維 不能低于6個樣本 最好選在30 60個樣本之間 三維 不能低于8個樣本 最好選在40 80個樣本之間 n為模式維數(shù) 如 3 8非線性判別函數(shù)3 8 1分段線性判別函數(shù) 出發(fā)點線性判別函數(shù)在進行分類決策時是最簡單有效的 但在實際應用中 常常會出現(xiàn)不能用線性判別函數(shù)直接進行分類的情況 采用廣義線性判別函數(shù)的概念 可以通過增加維數(shù)來得到線性判別 但維數(shù)的大量增加會使在低維空間里在解析和計算上行得通的方法在高維空間遇到困難 增加計算的復雜性 引入分段線性判別函數(shù)的判別過程 它比一般的線性判別函數(shù)的錯誤率小 但又比非線性判別函數(shù)簡單 3 8 1分段線性判別函數(shù) 特點 基本組成為超平面 相對簡單 能逼近各種形狀的超曲面 圖例 用判別函數(shù)分類可用一個二次判別函數(shù)來分類也可用一個分段線性判別函數(shù)來逼近這個二次曲線 1 一般分段線性判別函數(shù) 設有M類模式 將 i類 i 1 2 M 劃分為li個子類 其中第n個子類的判別函數(shù) i類的判別函數(shù)定義為 M類的判決規(guī)則 用各類判別函數(shù)進行分類判決實際是用各類選出的子類判別函數(shù)進行判決 判別面由各子類的判別函數(shù)決定 若 i類的第n個子類和 j類的第m個子類相鄰 判別界面方程為 子類之間的判別界面組成各類之間的判別界面 類間判別界面分段線性 2 基于距離的分段線性判別函數(shù) 設 1類均值向量 2類均值向量 N1 N2 兩類樣本數(shù) 任一模式X到M1和M2的歐氏距離平方 判決規(guī)則 判別界面方程 1 最小距離分類器 化簡得 X的線性方程 確定一個超平面 最小距離分類器 2 分段線性距離分類器 設 M類模式 其中 i類劃分為li個子類 第n個子類的均值向量為 每個子類的判別函數(shù) 每類的判別函數(shù) 判決規(guī)則 若 則 3 8 2分段線性判別函數(shù)的學習方法 1 已知子類劃分時的學習方法 每個子類看成獨立的類 在一類范圍內根據(jù)多類情況3 學習各子類判別函數(shù) 繼而得到各類判別函數(shù) 2 已知子類數(shù)目時的學習方法 用類似于固定增量算法的錯誤修正算法學習分段線性判別函數(shù) 3 未知子類數(shù)目時的學習方法 樹狀分段線性分類器 樹狀分段線性分類器判別函數(shù)的學習及分類過程 3 8 3勢函數(shù)法 一種確定性的非線性分類方法 目的用勢函數(shù)的概念來確定判別函數(shù)和劃分類別界面 基本思想假設要劃分屬于兩種類別 1和 2的模式樣本 這些樣本可看成是分布在n維模式空間中的點xk 把屬于 1的點比擬為某種能源點 在點上 電位達到峰值 隨著與該點距離的增大 電位分布迅速減小 即把樣本xk附近空間x點上的電位分布 看成是一個勢函數(shù)K x xk 對于屬于 1的樣本集群 其附近空間會形成一個 高地 這些樣本點所處的位置就是 山頭 同理 用電位的幾何分布來看待屬于 2的模式樣本 在其附近空間就形成 凹地 只要在兩類電位分布之間選擇合適的等高線 就可以認為是模式分類的判別函數(shù) 一維情況示例 3 8 3勢函數(shù)法 一種確定性的非線性分類方法 2 勢函數(shù)法判別函數(shù)的產(chǎn)生模式分類的判別函數(shù)可由分布在模式空間中的許多樣本向量 xk k 1 2 和 的勢函數(shù)產(chǎn)生 任意一個樣本所產(chǎn)生的勢函數(shù)以K x xk 表征 則判別函數(shù)d x 可由勢函數(shù)序列K x x1 K x x2 來構成 序列中的這些勢函數(shù)相應于在訓練過程中輸入機器的訓練模式樣本x1 x2 在訓練狀態(tài) 模式樣本逐個輸入分類器 分類器就連續(xù)計算相應的勢函數(shù) 在第k步迭代時的積累位勢決定于在該步前所有的單獨勢函數(shù)的累加 以K x 表示積累位勢函數(shù) 若加入的訓練樣本xk 1是錯誤分類 則積累函數(shù)需要修改 若是正確分類 則不變 依次輸入樣本 利用勢函數(shù)逐步積累勢能的過程 判別函數(shù)由模式空間中樣本向量的勢函數(shù)K X Xk 累加產(chǎn)生 分類器計算積累勢K X 最后取d X K X 設初始積累勢函數(shù) 下標為迭代次數(shù) 勢函數(shù)法 第一步 加入訓練樣本X1 K1 X 描述了加入第一個樣本后的邊界劃分 第二步 加第二個訓練樣本X2 分三種情況 分類正確 勢函數(shù)不變 錯誤分類 修改勢函數(shù) 第k步 設Kk X 為加入訓練樣本X1 X2 Xk后的積累勢函數(shù) 則加入第k 1個樣本 有 以上決定積累位勢的迭代算法可寫為 其中rk 1為校正項系數(shù) 定義為 3 57 3 58 從所給的訓練樣本集中略去不使積累勢發(fā)生變化的那些樣本 可得一簡化樣本序列 校正錯誤的樣本 算法可歸納為 即 由 k 1 個訓練樣本產(chǎn)生的積累勢 等于兩類中校正錯誤的樣本的總勢能之差 式中 3 59 3 60 從勢函數(shù)算法可看出 積累勢函數(shù)起著判別函數(shù)的作用 因此可直接用作判別函數(shù) 故取d X K X 由 3 57 式得 式中rk 1按 3 58 式取值 也可簡寫成 式中取值同 3 60 3 61 從勢函數(shù)可以看出 積累位勢起著判別函數(shù)的作用當xk 1屬于 1時 Kk xk 1 0 當xk 1屬于 2時 Kk xk 1 0 則積累位勢不做任何修改就可用作判別函數(shù) 由于一個模式樣本的錯誤分類可造成積累位勢在訓練時的變化 因此勢函數(shù)算法提供了確定 1和 2兩類判別函數(shù)的迭代過程 判別函數(shù)表達式取d x K x 則有 dk 1 x dk x rk 1K x xk 1 兩個n維向量X和Xk的函數(shù)K X Xk 如同時滿足下列三個條件 都可做為勢函數(shù) 3 勢函數(shù)的選擇 當向量X與Xk的距離趨于無窮時 K X Xk 趨于零 K X Xk 是光滑函數(shù) 且是X與Xk之間距離的單調下降函數(shù) 1 勢函數(shù)應具備的條件 2 構成勢函數(shù)的兩種方法 式中 在模式定義域內應為正交函數(shù)集 型勢函數(shù) 用對稱的有限項多項式展開 即 a 內積 定義為 是一個實數(shù) 正交函數(shù) 概念 已知函數(shù)y x 和z x b 正交 滿足 y z 0 例 將這類勢函數(shù)代入 3 61 式 有判別函數(shù) 型勢函數(shù) 直接選擇雙變量X和Xk的對稱函數(shù)作為勢函數(shù) 即 如 3 67 3 68 曲線c含有正弦函數(shù) 具有振蕩特點 只有第一個振蕩周期可用 式中為正常數(shù) 3 66 圖3 25一維 型勢函數(shù)舉例 例3 14設兩類訓練樣本集 樣本分布如圖所示 用 型勢函數(shù)進行分類 求判別函數(shù) 解 兩類模式不是線性可分的 這里選擇指數(shù)型的勢函 二維情況下勢函數(shù)為 開始迭代 式中 第一步 第二步 分類正確 不修正 第三步 分類錯誤 修正 第四步 分類錯誤 修正 第五步 不修正 第六步 修正 第七步 不修正 第八步 不修正 第九步 不修正 第十步 不修正 從X7至X10的四次迭代中 所有訓練樣本皆被正確分類 故算法已收斂于判別函數(shù) 分類器設計完畢 判別函數(shù) 判別界面 d X 0 第七步 第八步 3 勢函數(shù)的選擇討論用第二類勢函數(shù) 當訓練樣本維數(shù)和數(shù)目都較高時 需要計算和存儲的指數(shù)項較多 正因為勢函數(shù)由許多新項組成 因此有很強的分類能力 結束 同學們 來學校和回家的路上要注意安全 同學們 來學校和回家的路上要注意安全