模式識別經典演算法

㈠ 圖像識別演算法有幾種

從模式特徵選擇及判別決策方法的不同可將圖像模式識別方法大致歸納為兩類:統計模式(決策理論)識別方法和句法(結構)模式識別方法。此外，近些年隨著對模式識別技術研究的進一步深入，公司模糊模式識別方法和神經網路模式識別方法也開始得到廣泛的應用。江蘇視圖科技演算法提供商。

㈡ 大數據最常用的演算法有哪些

奧地利符號計算研究所(Research Institute for Symbolic Computation，簡稱RISC)的Christoph Koutschan博士在自己的頁面上發布了一篇文章，提到他做了一個調查，參與者大多數是計算機科學家，他請這些科學家投票選出最重要的演算法，以下是這次調查的結果，按照英文名稱字母順序排序。

大數據等最核心的關鍵技術：32個演算法

1、A* 搜索演算法——圖形搜索演算法，從給定起點到給定終點計算出路徑。其中使用了一種啟發式的估算，為每個節點估算通過該節點的最佳路徑，並以之為各個地點排定次序。演算法以得到的次序訪問這些節點。因此，A*搜索演算法是最佳優先搜索的範例。

2、集束搜索(又名定向搜索，Beam Search)——最佳優先搜索演算法的優化。使用啟發式函數評估它檢查的每個節點的能力。不過，集束搜索只能在每個深度中發現最前面的m個最符合條件的節點，m是固定數字——集束的寬度。

3、二分查找(Binary Search)——在線性數組中找特定值的演算法，每個步驟去掉一半不符合要求的數據。

4、分支界定演算法(Branch and Bound)——在多種最優化問題中尋找特定最優化解決方案的演算法，特別是針對離散、組合的最優化。

5、Buchberger演算法——一種數學演算法，可將其視為針對單變數最大公約數求解的歐幾里得演算法和線性系統中高斯消元法的泛化。

6、數據壓縮——採取特定編碼方案，使用更少的位元組數(或是其他信息承載單元)對信息編碼的過程，又叫來源編碼。

7、Diffie-Hellman密鑰交換演算法——一種加密協議，允許雙方在事先不了解對方的情況下，在不安全的通信信道中，共同建立共享密鑰。該密鑰以後可與一個對稱密碼一起，加密後續通訊。

8、Dijkstra演算法——針對沒有負值權重邊的有向圖，計算其中的單一起點最短演算法。

9、離散微分演算法(Discrete differentiation)。

10、動態規劃演算法(Dynamic Programming)——展示互相覆蓋的子問題和最優子架構演算法

11、歐幾里得演算法(Euclidean algorithm)——計算兩個整數的最大公約數。最古老的演算法之一，出現在公元前300前歐幾里得的《幾何原本》。

12、期望-最大演算法(Expectation-maximization algorithm，又名EM-Training)——在統計計算中，期望-最大演算法在概率模型中尋找可能性最大的參數估算值，其中模型依賴於未發現的潛在變數。EM在兩個步驟中交替計算，第一步是計算期望，利用對隱藏變數的現有估計值，計算其最大可能估計值;第二步是最大化，最大化在第一步上求得的最大可能值來計算參數的值。

13、快速傅里葉變換(Fast Fourier transform，FFT)——計算離散的傅里葉變換(DFT)及其反轉。該演算法應用范圍很廣，從數字信號處理到解決偏微分方程，到快速計算大整數乘積。

14、梯度下降(Gradient descent)——一種數學上的最優化演算法。

15、哈希演算法(Hashing)。

16、堆排序(Heaps)。

17、Karatsuba乘法——需要完成上千位整數的乘法的系統中使用，比如計算機代數系統和大數程序庫，如果使用長乘法，速度太慢。該演算法發現於1962年。

18、LLL演算法(Lenstra-Lenstra-Lovasz lattice rection)——以格規約(lattice)基數為輸入，輸出短正交向量基數。LLL演算法在以下公共密鑰加密方法中有大量使用：背包加密系統(knapsack)、有特定設置的RSA加密等等。

19、最大流量演算法(Maximum flow)——該演算法試圖從一個流量網路中找到最大的流。它優勢被定義為找到這樣一個流的值。最大流問題可以看作更復雜的網路流問題的特定情況。最大流與網路中的界面有關，這就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一個流網路中的最大流。

20、合並排序(Merge Sort)。

21、牛頓法(Newton』s method)——求非線性方程(組)零點的一種重要的迭代法。

22、Q-learning學習演算法——這是一種通過學習動作值函數(action-value function)完成的強化學習演算法，函數採取在給定狀態的給定動作，並計算出期望的效用價值，在此後遵循固定的策略。Q-leanring的優勢是，在不需要環境模型的情況下，可以對比可採納行動的期望效用。

23、兩次篩法(Quadratic Sieve)——現代整數因子分解演算法，在實踐中，是目前已知第二快的此類演算法(僅次於數域篩法Number Field Sieve)。對於110位以下的十位整數，它仍是最快的，而且都認為它比數域篩法更簡單。

24、RANSAC——是「RANdom SAmple Consensus」的縮寫。該演算法根據一系列觀察得到的數據，數據中包含異常值，估算一個數學模型的參數值。其基本假設是：數據包含非異化值，也就是能夠通過某些模型參數解釋的值，異化值就是那些不符合模型的數據點。

25、RSA——公鑰加密演算法。首個適用於以簽名作為加密的演算法。RSA在電商行業中仍大規模使用，大家也相信它有足夠安全長度的公鑰。

26、Sch?nhage-Strassen演算法——在數學中，Sch?nhage-Strassen演算法是用來完成大整數的乘法的快速漸近演算法。其演算法復雜度為：O(N log(N) log(log(N)))，該演算法使用了傅里葉變換。

27、單純型演算法(Simplex Algorithm)——在數學的優化理論中，單純型演算法是常用的技術，用來找到線性規劃問題的數值解。線性規劃問題包括在一組實變數上的一系列線性不等式組，以及一個等待最大化(或最小化)的固定線性函數。

28、奇異值分解(Singular value decomposition，簡稱SVD)——在線性代數中，SVD是重要的實數或復數矩陣的分解方法，在信號處理和統計中有多種應用，比如計算矩陣的偽逆矩陣(以求解最小二乘法問題)、解決超定線性系統(overdetermined linear systems)、矩陣逼近、數值天氣預報等等。

29、求解線性方程組(Solving a system of linear equations)——線性方程組是數學中最古老的問題，它們有很多應用，比如在數字信號處理、線性規劃中的估算和預測、數值分析中的非線性問題逼近等等。求解線性方程組，可以使用高斯—約當消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。

30、Strukturtensor演算法——應用於模式識別領域，為所有像素找出一種計算方法，看看該像素是否處於同質區域( homogenous region)，看看它是否屬於邊緣，還是是一個頂點。

31、合並查找演算法(Union-find)——給定一組元素，該演算法常常用來把這些元素分為多個分離的、彼此不重合的組。不相交集(disjoint-set)的數據結構可以跟蹤這樣的切分方法。合並查找演算法可以在此種數據結構上完成兩個有用的操作：

查找：判斷某特定元素屬於哪個組。

合並：聯合或合並兩個組為一個組。

32、維特比演算法(Viterbi algorithm)——尋找隱藏狀態最有可能序列的動態規劃演算法，這種序列被稱為維特比路徑，其結果是一系列可以觀察到的事件，特別是在隱藏的Markov模型中。

以上就是Christoph博士對於最重要的演算法的調查結果。你們熟悉哪些演算法?又有哪些演算法是你們經常使用的?

㈢ 求大神簡述一下LLE演算法（或降維演算法）在模式識別和數據挖掘中是怎樣被應用的呢，謝謝

1. 關於LLE演算法具體的理論部分你可參考http://www.pami.sjtu.e.cn/people/xzj/introcelle.htm

2. Locally linear embedding (LLE)，使用這種演算法可以進行非線性降維，關鍵是其能夠使降維後的數據保持原有拓撲結構

   先給出一張下面演算法得到的圖 ，圖中第一幅

   LLE演算法可以歸結為三步:

   （1）尋找每個樣本點的k個近鄰點；

   （2）由每個樣本點的近鄰點計算出該樣本點的局部重建權值矩陣；

   （3）由該樣本點的局部重建權值矩陣和其近鄰點計算出該樣本點的輸出值。

3. 為原始數據，第三個為降維後的數據，可以看出處理後的低維數據保持了原有的拓撲結構。

4. 另，本人對LLE演算法不是很熟悉，在此介紹一下其他降維演算法的使用，以SVD演算法為例。

   電影推薦。

   （1）假設現在有一個用戶和電影評分的二維矩陣，矩陣內容是用戶對電影的評分，現有得知某個用戶對部分電影的評分，由此為該用戶推薦他可能喜歡的電影。

   （2）假設用戶有100W，電影有100W部，那麼對於任意一種推薦演算法來說，這個數據量都很大，該問題無法在單機上進行運算解決；

   （3）這100W維特徵中必然存在一些幾乎不重要的特徵，這時，我們就需要用降維演算法進行降維，降維的目的就是去掉大量的不重要的特徵，以簡化運算；

   （4）在此例中，可以使用SVD(或SVD++)演算法對矩陣進行降維

圖片相似度

（1）通常，進行圖片相似度判斷首先會將圖片通過傅里葉變換轉換成數值代表的矩陣，矩陣代表著該圖片，一般來說矩陣維數越高越精確

（2）同樣，維數過高的情況下，相似度計算成本很高，因此同樣需要降維，在圖片相似度識別中常用的降維演算法是PCA演算法；

總之，降維的目的就是減少特徵的維數，減少運算的成本。

以上皆為我的拙見，如有疑義請指正。

㈣ 請問，線性判別分析LDA和偏最小二乘判別分析PLSDA有什麼區別

把4維的x向量X=(x1,x2,x3,x4),拓展成14維的向量(x1,x2,x3,x4,x1*x1,x1*x2,x1*x3,x1*x4,x2*x2,x2*x3,x2*x4,x3*x3,x3*x4,x4*x4),可以把原問題化簡為老師提示的問題,從而進行求解. 樓主學過模式識別（Pattern Recognition）里的LDA（Linear Discriminant Analysis）演算法嗎?中文叫線性判別分析.LDA演算法基本就是求解這么個問題： minimize t subject to Ax=-1 (數值) LDA演算法是模式識別里的經典演算法,它有很成熟的解析解,你隨便網上搜搜,就能得到很詳細的解答. 樓主本身的這個問題,算是QDA演算法（Quadratic Discriminant Analysis）,中文叫二次項判別分析.因為QDA帶了二次項,因此比LDA本身要復雜一些. 但是QDA問題可以簡化成LDA演算法,具體方法就是把4維向量X=(x1,x2,x3,x4),擴展成如下的14維向量Y=(x1,x2,x3,x4,x1*x1,x1*x2,x1*x3,x1*x4,x2*x2,x2*x3,x2*x4,x3*x3,x3*x4,x4*x4). 這樣XT*A*X+bT*X+c,就可以化為dT*Y+c的形式了（這個14維向量d和A,b的關系很容易算）,然後套用下現成的LDA演算法求出d,然後反推出A和b,基本就搞定了.

㈤ 人工智慧之模式識別|北京理工大學|Mooc|筆記|更新中

識別的基礎是認知
認知Cognition：獲取某種事物的特徵——概念抽象
識別Re-cognition：根據特徵決定某個具體的事物是不是某種事物——概念歸類
模式：一類事物的共同特徵
識別：對事物進行概念歸類
模式識別：依據事物的特徵進行概念歸類

特徵
相似性
類
特徵空間
向量空間
集合空間

通過訓練（學習）得到分類器模型參數

兩種模式：有監督學習和無監督學習——從訓練集中學習

對於每一個類別都給定一些樣本——形成一個具有類別標簽的訓練樣本集——分類器通過分析每一個樣本去尋找屬於同一類樣本具有哪些共同特徵——從訓練集中學習到具體分類決策規則——有監督的學習

分類器通過有監督學習模式學習到的每個類別樣本的特徵就是關於某個類別概念的知識—— 學習過程就是認知過程

樣本標簽如何得到？——人來給定

有監督學習——從人的經驗中學習分類知識——智能水平有上限

給定訓練樣本集但沒有給每一個樣本貼上類別標簽——屬於同一個類別的樣本之間的相似程度會大於屬於不同類別的樣本之間的相似程度——根據相似程度的大小，按照一些規則把相似程度高的一些樣本作為同一類——將訓練樣本集的一些樣本劃分成不同的類別——再從每一個類別的樣本中去尋找共同特徵，形成分類決策規則——無監督學習

無監督學習——自主地從數據所代表的自然規律中學習關於類別劃分的知識——分類器能達到更高的分類水平——未來模式識別發展的主要方向

屬於同一個類別的樣本之間的相似程度會大於屬於不同類別的樣本之間的相似程度——不同類樣本之間的相似度越小，分類決策規則的裕量也就越大

這樣可以作為評判用於監督學習的帶標簽訓練樣本集以及作為無監督學習結果的樣本集，它的優劣程度的一個指標，稱為「緊致性」准則，即：緊致性好的樣本集樣本的類內相似度遠大於類間相似度。

若要進行定量評判——確定如何度量相似性——可以設置多種指標——如：距離指標（最常用，距離可以定義在任意集合上，只要去計算滿足三條標准：1.正定性：距離是個大於等於0的正實數，當且僅當自己和自己計算距離時才為0；2.對稱性：樣本之間的距離值計算與計算順序無關；3.傳遞性：滿足三角關系——兩個樣本之間的距離一定小於等於分別於第三個樣本之間的距離之和。||在向量空間中可以定義歐氏距離、曼哈頓距離、切比雪夫距離等|| 非向量空間也可以定義距離，如：兩個字元串之間的編輯距離也是一種合法的距離定義）非距離的相似度量標准（如：餘弦相似度——使用向量空間中兩個向量之間的夾角來表達相似程度：cosθ=x ^T y/||x||·||y|| ;皮爾遜相關系數Pxy=cov(x,y)/∆x∆y;Jaccard相似系數）

如果我們希望有緊致性好的樣本集——那麼就希望能有有效的信息能夠將不同類的樣本很好地區分開——增加特徵的種類==增加特徵的維度——特徵的維度越多，用於識別的信息就越豐富，就有越多的細節信息可以將不同的樣本之間的相似度降低，提高樣本集的緊致性

不需要無限制地增加，只要不斷地增加模式識別問題中地特徵維數會產生維數災難（cruse of dimensionality)——當一個問題描述地維度不斷增加時會帶來計算量劇增與解法性能下降等嚴重問題——模式識別中的維數災難：隨著特徵維度的增加分類器的性能將在一段快速增加的區域後急速地下降並且最終無法使用

當特徵空間以同樣密度能夠容納的樣本總數呈指數增長時，而如果給定樣本集中的樣本數量沒有同步按照指數規律增加的話，那麼問題越往高維度特徵空間映射時樣本集中的樣本就越稀疏，從而使得樣本集的緊致性越來越差，因此分類器的性能越來越差。

要解決維數災難問題或者要同步地大量增加樣本集樣本的數量，難以實現，或者盡可能減少問題所使用的特徵維度。

在降低維度的同時盡可能地提升每一個維度在分類中的效能，從而使模式識別問題在較低的維度下解決。

特徵生成+特徵降維 重點領域——其結果直接影響分類器性能的好壞

我們期望分類器能夠從訓練集樣本中發現所要分類的各個類別的普遍特點即找到最優的分類器，使分類器在經過訓練後不僅能將訓練集中的樣本正確分類，而且對於不在訓練集中的新樣本也能夠正確地分類

因為有誤差所以不能同時滿足【正確分類樣本集】和【正確分類未知新樣本】

採集數據時由於數據採集方法的問題或者存在雜訊干擾得到的樣本特徵會存在誤差甚至會出現「異常數據」

如果我們要求分類器必須正確分類則會在分類規則上出現「失真」，從而在面對新的未知樣本進行分類時出現錯誤（使分類器泛化能力降低）====稱為分類器訓練過程中的「過擬合」

「結構風險最小化准則」

分類決策規則是從自動計算中獲取的而不是人工設定的

設計模式識別系統就是設計分類器的模型、所使用的的特徵和分類器參數的調整演算法

通過採集轉換得到計算機能接受和處理的數據

模式採集：感測器、變送器、模數轉換

得到的數據：待識別樣本的原始信息（包含大量干擾和無用數據）

通過各種濾波降噪措施降低干擾的影響，增強有用的信息，在此基礎上生成在分類上具有意義的各種特徵

得到的特徵：可以仍然用數值來表示，也可以用拓撲關系、邏輯結構等其他形式表示

經過一、二環節獲得的模式特徵維數都是很大的

主要方法：特徵選擇和特徵提取

特徵選擇：從已有的特徵中選擇一些特徵，拋棄其他特徵

特徵提取：是對原始的高維特徵進行映射變換，生成一組維數更少的特徵

分類器訓練是由計算機根據樣本的情況自動進行的，分類有監督學習和無監督學習

在分類器訓練結束後，對待分類的樣本按照已建立起來的分類決策規則進行分類的過程，在待分類的樣本在進行分類決策之前，與訓練樣本一樣要完成模式採集、預處理與特徵生成、特徵降維等環節的處理，還要持續不斷地對分類決策的結果進行評估，已改進分類器的性能。

模式識別演算法：統計模式識別（主流）、結構模式識別

統計模式識別：將樣本轉換成多維特徵空間中的點，再根據樣本的特徵取值情況和樣本集的特徵值分布情況確定分類決策規則。

線性分類器：是最基本的統計分類器，它通過尋找線性分類決策邊界來實現特徵空間中的類別劃分

貝葉斯分類器：它的決策規則是基於不同類樣本在特徵空間中的概率分布以逆概率推理的貝葉斯公式來得到類別劃分的決策結果

最近鄰分類器：把學習過程隱藏到了分類決策中，通過尋找訓練集中與待分類樣本最相似的子集來實現分類決策

神經網路分類器：來源於對生物神經網路系統的模擬，它的本質是高度非線性的統計分類器並且隨著計算機技術的發展從淺層網路向深層網路不斷演化

統計聚類分析：是無監督學習的典型代表

聚類分析：是無監督學習的典型代表，目前多採用統計學習的方法。

模糊模式識別：不是一獨立的方法，而是將模糊數學引入模式識別技術後對現有演算法的模糊化改造，它在更精確地描述問題和更有效地得出模式識別結果方面都有許多有價值的思路。

特徵降維：也不是獨立的模式識別演算法，但是是完成模式識別任務的流程中不可缺少的一個步驟，特徵降維通過尋找數量更少對分類更有效的特徵來提升整個模式識別系統的性能。

結構模式識別：

結構聚類演算法：將樣本結構上某些特點作為類別和個體的特徵通過結構上的相似性來完成分類任務。

句法模式識別：利用了形式語言理論中的語法規則，將樣本的結構特徵轉化為句法類型的判定，從而實現模式識別的功能。

一個典型的基於視覺的模式識別工程問題

多分類問題

模板匹配基本原理：為每一個類別建立一個或多個標準的模板，分類決策時將待識別的樣本與每個類別的模板進行比對，根據與模板的匹配程度將樣本劃分到最相似的類別中。

建立模板時依賴人的經驗所以適應性差

「分類決策邊界」

判別函數G(x)=0

如果判別函數是線性函數則稱為線性判別函數

線性判別函數+對應的分類規則=線性分類器

如果特徵空間是一維的，線性分類器的分類決策邊界就是一個點

如果特徵空間是二維的，線性分類器的分類決策邊界是一條直線

如果特徵空間是三維的，線性分類器的分類決策邊界是一個平面

如果維度很高，從數學上可以得到分類決策邊界是一個超平面

是不是任何一個模式識別問題都可以找到線性分類決策邊界呢？

給定一個樣本集，它是線性可分的嗎？

涉及問題：樣本集的線性可分性

如果一個樣本集，它的各個類別樣本的分布區域是相交的，那麼肯定是線性不可分的；如果各個類別樣本的分布區域是互不相交的，並且都是凸集，那麼它一定是線性可分的；如果互不相交但有的是凹集，也不一定是線性可分的，需要找出凹集區域最小的凸集包絡線稱為凸包，如果凸包都不想交，那麼樣本集才是可分的，否則不可分。

線性可分性——異或問題

非線性分類問題轉化為線性分類問題：

當我們將一個模式識別問題從低維特徵空間映射到高維特徵空間時，就將一個非線性分類問題轉化為一個線性分類問題。======》這種方法被稱為「廣義線性化」

需要多個線性判別函數——用二分類問題的組合來確定多分類的分類決策規則

根據一定的邏輯關系構成多分類的線性分類器

絕對可分：對於樣本集中的每一個類都有一個線性判別函數，可以把屬於這一類和不屬於這一類的樣本分開。——帶來的不可識別區域很多，整體分類器的性能不好。

兩兩可分：判別函數並不是用於判別屬於某一個或者不屬於某一個類的樣本，而是在兩個特定的類別中選邊站。減少了不可識別區域，提升了線性分類器的性能。

如果有k個分類，兩兩可分的線性判別一共需要C2k個判別函數，絕對可分的線性判別需要k個判別函數

最大值可分：樣本集中每一個類別對應有一個判別函數，而一個樣本將被劃分到取值最大的那個判別函數所對應的類別中。——不可識別區域消失，判別函數的數量也僅僅與樣本集中的類別數量一樣。

如何求最大值可分的判別函數？——工作量大

判別函數是樣本到決策超平面距離遠近的一種度量

樣本x到決策邊界的距離r正比於判別函數G(x)的值，判別函數的符號代表了距離r的符號，表示該模式位於決策邊界的正側還是負側

權向量w僅代表決策超平面的法向方向，長度不會影響決策邊界在特徵空間中的位置，可以取w為1，此時判別函數的值就是樣本到決策邊界的距離。

線性分類器——由線性判別函數及相應道德分類決策規則構成的

線性判別函數如何得到？——如何設計線性分類器？——訓練問題

線性分類器學習/訓練的一般思路：

G _ij (x)=w ^T x+w ₀

w ^T 權向量

w ₀ 偏置量

解區域中尋找最優解

1.設定一個標量的准則函數J(w,w ₀ ),使其值能夠代表解的優劣程度，准則函數值越小，說明解越符合要求，越好。

2.通過尋找准則函數J(w,w ₀ )的極小值，就能找到最優的一個解，是准則函數取得極小值的增廣權向量w，這就是最優解。 （w,w ₀ ） ^*

訓練集數據的規范化

1.了解感知器模型

感知器（perception）模型是一種神經元模型

多路輸入+單路輸出

將所有輸入信號加權求和後於一個閾值相比較，如果大於閾值，則神經元輸出為1；小於等於閾值，則神經元輸出為0

沒有反饋與內部狀態

只能依靠輸入信號是否超過閾值來決定是否激活神經元的輸出

如果把感知器的輸入信號看作是一個待識別樣本的特徵向量，感知器的數學模型就構成了一個典型的線性分類器，可以做出非常明確的二分類決策

通過樣本集使感知器能夠學習到輸入權重值和輸出的閾值

感知器是一個通過輸入加權和與閾值的比較來決定是否激活輸出的神經元模型，這是一個線性分類器，輸入的權構成了線性分類決策邊界的權向量，激活輸出的閾值 heta就是分類決策邊界的偏置量w ₀

求解目標：對所有樣本，都有w ^T x > 0

感知器演算法設定準則函數的依據：最終分類器要能正確分類所有的樣本

所以J設定為所有錯分樣本的判別函數值之和

X ₀ 是所有錯分樣本的集合

只要存在錯分樣本，准則函數一定大於0，只有當所有樣本正確分類了，准則函數值才能取得極小值0

梯度下降法

w(k+1)=w(k)-p(k+1)∆J(w(k))

對於線性可分的兩類問題其分類決策邊界為一n維特徵空間中的超平面H

一般情況下會有無窮多個解，當我們確定一個解所對應的權向量w，超平面的斜率和朝向就是確定的了，可以在一定范圍內平移超平面H，只要不達到或者越過兩類中距離H最近的樣本，分類決策邊界都可以正確地實現線性分類，所以任何一個求解得到的權向量w都會帶來一系列平行的分類決策邊界，其可平移的范圍具有一定的寬度，稱為分類間隔（Marigin of Classification）。

當我們改變w，使分類決策邊界的斜率和朝向隨之變化時，我們得到的分類間隔是不同的。

分類間隔越大，兩類樣本做決策時的裕量也就越大

找到可以使分類間隔最大的最優權向量 w*——支持向量機的出發點

分類間隔是由距離分類決策邊界最近的少量樣本決定的，這些樣本被稱為「支持向量 support vector」_支撐起了線性分類器在最大分類間隔意義下的最優解

支持向量機的優化求解目標是求取能帶來最大分類間隔的權向量w

分類間隔是支持向量到分類決策邊界的2倍

Max d = max 2|G _ij (x)|/||w|| 支持向量機採用令|G _ij (x)|=1 =>min ||w|| 將求取最大的d的問題轉化為求取權向量的長度最短的問題——為了方便進行二次優化——=>min 1/2 ||w|| ²

求取優化目標要求兩類中的所有樣本到分類決策邊界的距離都應該比支持向量更大，其他樣本的判別函數絕對值都需要大於1，即不等式約束條件為：圖

支持向量機採用拉格朗日乘子法將其轉化為無約束優化問題來求解，即通過將所有約束條件與拉格朗日乘子相乘後添加到優化目標中，在求取拉格朗日乘子最大值的條件下，求取最短的權向量w——凸規劃問題——存在唯一解——其充要條件可以通過拉格朗日函數分別對權向量w和偏置值w0求偏導來得到，即滿足這樣的條件——得到權向量的表達公式

KKT條件

經驗風險:訓練之後的分類器的錯誤分類樣本比例

經驗風險最小化 R_emp==o

只有當訓練集的樣本數趨近於無窮，訓練集中樣本的分布趨近於樣本的真實分布時，經驗風險才會趨近於真實樣本分類的風險

為了從根本上解決「過擬合」問題——提出「結構風險最小化SRM」min(R(w))

結構風險：在一個訓練好的分類器面對未知樣本時分類錯誤的概率

泛化誤差界：R(w)<=Remp(w)+φ(h/l) 置信風險 l是訓練集中的樣本數，h為分類器形式的vc維，而φ置信風險的具體計算公式：圖

如果分類器函數形式已經確定，則樣本數越大，置信風險也就越小；如果訓練集中的樣本數量不夠多，那麼結構風險的大小就受置信風險大小的很大影響，而此時置信風險的大小取決於分類器函數形式本身具有的VC維，函數的VC維h越大，則置信風險也就越大，則相應的結構風險也就越大，分類器的泛化能力越差。

什麼是VC維？一類函數所具有的分類能力

它的值是一類函數能打散兩類樣本集中最大樣本數量

分類器函數形式的階次越低，其VC維也就越小，在樣本集數量有限的情況下，訓練後的分類器結構風險就越小，泛化能力越強。

（支持向量機是階次最低的線性函數）——是支持向量機在不需要大量訓練樣本的情況下也能取得泛化能力特別強的分類器訓練結果的主要原因

所以支持向量機是應用結構風險最小化准則的一個結果

線性不可分問題：1.異常點干擾 2.非線性分類

線性支持向量機是把具有最大分類間隔的最優線性判別函數的求解轉化為求解最短權向量的二次規劃問題

異常點的判別函數值距離一定小於1

可以在約束條件中減去一項正數kesei，使判別函數的絕對值允許小於1，kesei就稱為鬆弛變數

把kesei也作為優化目標，希望kesei越少越好，越小越好。

最理想的情況：絕大多數支持向量外側的樣本包括支持向量對應的鬆弛變數都該為0.只有少數支持向量內側才有一個盡可能小的鬆弛變數。

因此，可以把所有鬆弛變數的和值也作為優化目標的一個分項，即在原來的最短權向量的二次優化目標基礎上再加上一項C乘以所有鬆弛變數的和。C為懲罰因子，表示對分類器中存在異常點的容忍程度。C越小，鬆弛變數的存在對整體優化過程的影響越小，對異常點的容忍度越高。如果C取0，約束條件被破壞。

軟間隔的支持向量機：使用鬆弛變數和懲罰因子的支持向量機

採用——廣義線性化（把低維空間中的非線性問題往高維映射，從而轉化為一個線性分類問題）

㈥ 非監督模式識別的經典方法是聚類，聚類的三個要點是什麼

第一，聚類分析是一種無監督學習的方法。
第二，聚類的對象是沒有分類標記的訓練樣本。
第三，聚類的目的是將數據集劃分為若干個互不相交的子集。

㈦ 數據挖掘十大經典演算法及各自優勢

數據挖掘十大經典演算法及各自優勢

不僅僅是選中的十大演算法，其實參加評選的18種演算法，實際上隨便拿出一種來都可以稱得上是經典演算法，它們在數據挖掘領域都產生了極為深遠的影響。
1. C4.5
C4.5演算法是機器學習演算法中的一種分類決策樹演算法,其核心演算法是ID3演算法. C4.5演算法繼承了ID3演算法的優點，並在以下幾方面對ID3演算法進行了改進：
1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；2) 在樹構造過程中進行剪枝；3) 能夠完成對連續屬性的離散化處理；4) 能夠對不完整數據進行處理。
C4.5演算法有如下優點：產生的分類規則易於理解，准確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致演算法的低效。
2. The k-means algorithm 即K-Means演算法
k-means algorithm演算法是一個聚類演算法，把n的對象根據他們的屬性分為k個分割，k < n。它與處理混合正態分布的最大期望演算法很相似，因為他們都試圖找到數據中自然聚類的中心。它假設對象屬性來自於空間向量，並且目標是使各個群組內部的均 方誤差總和最小。
3. Support vector machines
支持向量機，英文為Support Vector Machine，簡稱SV機（論文中一般簡稱SVM）。它是一種監督式學習的方法，它廣泛的應用於統計分類以及回歸分析中。支持向量機將向量映射到一個更 高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假 定平行超平面間的距離或差距越大，分類器的總誤差越小。一個極好的指南是C.J.C Burges的《模式識別支持向量機指南》。van der Walt 和 Barnard 將支持向量機和其他分類器進行了比較。
4. The Apriori algorithm
Apriori演算法是一種最有影響的挖掘布爾關聯規則頻繁項集的演算法。其核心是基於兩階段頻集思想的遞推演算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。在這里，所有支持度大於最小支持度的項集稱為頻繁項集，簡稱頻集。
5. 最大期望(EM)演算法
在統計計算中，最大期望（EM，Expectation–Maximization）演算法是在概率（probabilistic）模型中尋找參數最大似然 估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variabl）。最大期望經常用在機器學習和計算機視覺的數據集聚（Data Clustering）領域。
6. PageRank
PageRank是Google演算法的重要內容。2001年9月被授予美國專利，專利人是Google創始人之一拉里·佩奇（Larry Page）。因此，PageRank里的page不是指網頁，而是指佩奇，即這個等級方法是以佩奇來命名的。
PageRank根據網站的外部鏈接和內部鏈接的數量和質量倆衡量網站的價值。PageRank背後的概念是，每個到頁面的鏈接都是對該頁面的一次投票， 被鏈接的越多，就意味著被其他網站投票越多。這個就是所謂的「鏈接流行度」——衡量多少人願意將他們的網站和你的網站掛鉤。PageRank這個概念引自 學術中一篇論文的被引述的頻度——即被別人引述的次數越多，一般判斷這篇論文的權威性就越高。
7. AdaBoost
Adaboost是一種迭代演算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然後把這些弱分類器集合起來，構成一個更強的最終分類器 (強分類器)。其演算法本身是通過改變數據分布來實現的，它根據每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的准確率，來確定每個樣本的權 值。將修改過權值的新數據集送給下層分類器進行訓練，最後將每次訓練得到的分類器最後融合起來，作為最後的決策分類器。
8. kNN: k-nearest neighbor classification
K最近鄰(k-Nearest Neighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。
9. Naive Bayes
在眾多的分類模型中，應用最為廣泛的兩種分類模型是決策樹模型(Decision Tree Model)和樸素貝葉斯模型（Naive Bayesian Model，NBC）。 樸素貝葉斯模型發源於古典數學理論，有著堅實的數學基礎，以 及穩定的分類效率。同時，NBC模型所需估計的參數很少，對缺失數據不太敏感，演算法也比較簡單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。 但是實際上並非總是如此，這是因為NBC模型假設屬性之間相互獨立，這個假設在實際應用中往往是不成立的，這給NBC模型的正確分類帶來了一定影響。在屬 性個數比較多或者屬性之間相關性較大時，NBC模型的分類效率比不上決策樹模型。而在屬性相關性較小時，NBC模型的性能最為良好。10. CART: 分類與回歸樹
CART, Classification and Regression Trees。 在分類樹下面有兩個關鍵的思想。第一個是關於遞歸地劃分自變數空間的想法；第二個想法是用驗證數據進行剪枝。

以上是小編為大家分享的關於數據挖掘十大經典演算法及各自優勢的相關內容，更多信息可以關注環球青藤分享更多干貨

㈧ Latent Dirichlet Allocation（潛在狄利克雷分配）和Linear Discriminant Analysis（線性判別分析）

不是同一個東西。
第一個是用於自然語言分析的隱主題模型。LDA是一種文檔主題生成模型，也稱為一個三層貝葉斯概率模型，包含詞、主題和文檔三層結構。文檔到主題服從Dirichlet分布，主題到詞服從多項式分布。睜冊
第二個線性判別式分析（Linear Discriminant Analysis），簡稱為LDA。也稱為Fisher線性判別（Fisher Linear Discriminant，FLD），是模式識別的經典演算法，在1996年由Belhumeur引入悉困宏模式識別和人工智慧領域。
基本思想是將高維的模式樣本投影到最佳鑒別矢量空間，以達到抽取分類信息和壓縮特徵空間維數的效果，投影後保證模式樣本在新的子空間有最大的類間距離和最小的類內距離，即模式在該空間中有最佳尺頃的可分離性。

㈨ 模式識別KMP演算法,懂計算機的朋友幫幫忙

學過數據結構的人，都對KMP演算法印象頗深。尤其是新手，更是難以理解其涵義，搞得一頭霧水。今天我們就來面對它，不將它徹底搞懂，誓不罷休。
如今，大夥基本上都用嚴蔚敏老師的書，那我就以此來講解KMP演算法。(小弟正在備戰考研，為了節省時間，很多課本上的話我都在此省略了，以後一定補上。)

嚴老的《數據結構》79頁講了基本的匹配方法，這是基礎。先把這個搞懂了。
80頁在講KMP演算法的開始先舉了個例子，讓我們對KMP的基本思想有了最初的認識。目的在於指出「由此，在整個匹配的過程中，i指針沒有回溯，」。
我們繼續往下看：
現在討論一般情況。
假設 主串：s: 『s(1) s(2) s(3) ……s(n)』 ; 模式串 ：p: 『p(1) p(2) p(3)…..p(m)』
把課本上的這一段看完後，繼續

現在我們假設 主串第i個字元與模式串的第j(j<=m)個字元『失配』後，主串第i個字元與模式串的第k(k<j)個字元繼續比較

此時，s(i)≠p(j), 有

主串： S(1)…… s(i-j+1)…… s(i-1) s(i) ………….
|| (相配) || ≠(失配)
匹配串： P(1) ……. p(j-1) p(j)

由此，我們得到關系式
『p(1) p(2) p(3)…..p(j-1)』 = 』 s(i-j+1)……s(i-1)』

由於s(i)≠p(j)，接下來s(i)將與p(k)繼續比較，則模式串中的前(k-1)個字元的子串必須滿足下列關系式，並且不可能存在 k』>k 滿足下列關系式：(k<j),
『p(1) p(2) p(3)…..p(k-1)』 = 』 s(i-k+1)s(i-k+2)……s(i-1)』

即：

主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….
|| (相配) || || ?(有待比較)
匹配串： P(1) p(2) …… p(k-1) p(k)

現在我們把前面總結的關系綜合一下

有：

S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……
|| (相配) || || || ≠(失配)
P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)
|| (相配) || || ?(有待比較)
P(1) p(2) ……. p(k-1) p(k)

由上，我們得到關系：
『p(1) p(2) p(3)…..p(k-1)』 = 』 s(j-k+1)s(j-k+2)……s(j-1)』

接下來看「反之，若模式串中存在滿足式(4-4)。。。。。。。」這一段。看完這一段，如果下面的看不懂就不要看了。直接去看那個next函數的源程序。(偽代碼)

K 是和next有關系的，不過在最初看的時候，你不要太追究k到底是多少，至於next值是怎麼求出來的，我教你怎麼學會。
課本83頁不是有個例子嗎？就是 圖4.6
你照著源程序，看著那個例子慢慢的推出它來。看看你做的是不是和課本上正確的next值一樣。
然後找幾道練習題好好練練，一定要做熟練了。現在你的腦子里已經有那個next演算法的初步思想了，再回去看它是怎麼推出來的，如果還看不懂，就繼續做練習，做完練習再看。相信自己！！！

附：

KMP演算法查找串S中含串P的個數count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;

inline void NEXT(const string& T,vector<int>& next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;i<T.size();i++ ){
int j=next[i-1];
while(T[i]!=T[j+1]&& j>=0 )
j=next[j] ; //遞推計算
if(T[i]==T[j+1])next[i]=j+1;
else next[i]=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
//利用模式串T的next函數求T在主串S中的個數count的KMP演算法
//其中T非空，
vector<int> next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index<S.size();++index){
int pos=0;
string::size_type iter=index;
while(pos<T.size() && iter<S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()&&(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S="";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
cout<<count<<endl;

system("PAUSE");
return 0;
}

㈩ 模式識別的發展

模式識別是智能控制中的經典，模式識別技術是人工智慧的基礎技術，21世紀是智能化、信息化御培、計算化、網路化的世紀，在這個以數字計算為特徵拿拆薯的世紀里，作為人工智慧消者技術基礎學科的模式識別技術，必將獲得巨大的發展空間。在國際上，各大權威研究機構，各大公司都紛紛開始將模式識別技術作為公司的戰略研發重點加以重視。 發展潛力無限，在1、語音識別技術。2、生物認證技術 3、數字水印技術等方面前途無量。