模式識別演算法

⑴ 模式識別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;
}

⑵ 模式識別演算法

matlab 程序
http://www.cs.tut.fi/sgn/m2obsi/ex/kmeans.m
更多資源查看http://people.revole.com/kardi/tutorial/kMean/Resources.htm
幫你過來。
% kmeans.m : K-means clustering algorithm % Copyright (c) 2002 - 2003 % Jussi Tohka % Institute of Signal Processing % Tampere University of Technology % P.O. Box 553 FIN-33101 % Finland % [email protected] % ------------------------------- % Permission to use, , modify, and distribute this software % for any purpose and without fee is hereby % granted, provided that the above right notice appear in all % copies. The author and Tampere University of Technology make no representations % about the suitability of this software for any purpose. It is % provided "as is" without express or implied warranty. % ***************************************************************** % [c,costfunctionvalue, datalabels] = kmeans(data,k,c_init,max_iter) % Input: % data is the n x m matrix, where n is the number of data points % and m is their dimensionality. % k is the number of clusters % c_init is the initializations for cluster centres. This must be a % k x m matrix. (Optional, can be generated randomly). % max_iter is the maximum number of iterations of the algorithm % (Default 50). % Output: % c is the k x m matrix of final cluster centres. % costfunctionvalue is the value of cost function after each % iteration. % datalabels is a n x 1 vector of labeling of data. function [c,costfunctionvalue, datalabels,inter] = kmeans(data,k,varargin); datasize = size(data); n = datasize(1); m = datasize(2); if n < m fprintf(1,'Error: The number of datapoints must be greater than \n'); fprintf(1,'their dimension. \n'); return; end if length(varargin) > 0 c_init = varargin{1}; else % First, select k random numbers from 1 to n WITHOUT repetition randomindex = zeros(k,1); for i = 1:k randomindex(i) = unidrnd(n + 1 - i); randomindex(i) = randomindex(i) + sum(randomindex(1:i-1) <= ... randomindex(i)); end c_init = data(randomindex,:); end if size(c_init) ~= [k m]; fprintf(1,'Error: The size of c_init is incorrect.'); end if length(varargin) > 1 max_iter = varargin{2}; else max_iter = 50; end % Start the algorithm iter = 0; changes = 1; distances = zeros(n,k); costfunctionvalue = zeros(max_iter + 1,1); c = c_init; datalabels = zeros(n,1); while iter < max_iter & changes iter = iter + 1; fprintf(1,'#'); old_datalabels = datalabels; % Compute the distances between cluster centres and datapoints for i = 1:k dist(:,i) = sum((data - repmat(c(i,:),n,1)).^2,2); end % Label data points based on the nearest cluster centre [tmp,datalabels] = min(dist,[],2); % compute the cost function value costfunctionvalue(iter) = sum(tmp); % calculate the new cluster centres for i = 1:k c(i,:) = mean(data(find(datalabels == i),:)); end % study whether the labels have changed changes = sum(old_datalabels ~= datalabels); inter(iter).datalabels = datalabels; inter(iter).c = c; end for i = 1:k dist(:,i) = sum((data - repmat(c(i,:),n,1)).^2,2); end [tmp,datalabels] = min(dist,[],2); % compute the cost function value costfunctionvalue(iter + 1) = sum(tmp); fprintf(1,'\n');

希望對您有所幫助

⑶ 模式識別，機器學習，神經網路，演算法之類的資料。 比如：馬爾可夫模型，隨機森林，

pattern recognition and machine learning，bishop 2006這本書不錯，講的很清楚。
中文翻譯版據說草稿三年前就提交上去了，不過還沒審批通過。但看英文版有看英文版的好處，搜一下愛問有pdf。

⑷ 請問現在哪種模式識別演算法（機器學習，數據挖掘）在對高維度數據進行分類時效果較好，例如速度和准確率。

鑒於你做的研究項目和我的一模一樣，我就不多說了，PSO還是不錯吧。

⑸ 研究生研究方向：數據挖掘、模式識別、啟發演算法這三者哪個有前途

我去年也是這個時候糾結這個問題，也是以數據挖掘為研究方向要定讀研的高校。南大的周志華很厲害，他們實驗室在數據挖掘上的研究一直被國內認可，而且很低調。
我覺得這個是首推的。數據挖掘在國內好像沒有國家重點實驗室，但是有兩個教育部重點實驗室，分別是吉大和人大。如果你要去北京的高校，建議是中科院（自動化所和計算所），清華，北大，人大。北航和北郵的計算機都不是以數據挖掘為優勢吧，呵呵。

⑹ 模式識別和圖像處理中的演算法和演算法導論中的演算法有什麼區別

模式識別與圖像處理中的演算法是針對圖像識別與分類的，演算法作用對象是像素，用於提取特徵、識別目標等；而演算法導論中的演算法針對的是程序本身，是用於改善程序結構與運行速度的，演算法導論中幾乎包括了所有數據結構的東西，哪種編程語言都能用。

⑺ 機器學習和模式識別有什麼區別看教材，發現它們的演算法都差不多一樣啊。。。

一、方式不同

1、機器學習：是通過計算機用數學技術方法來研究模式的自動處理和判讀。

2、模式識別：專門研究計算機怎樣模擬或實現人類的學習行為，以獲取新的知識或技能，重新組織已有的知識結構使之不斷改善自身的性能。

二、研究過程不同

1、機器學習：學習是一項復雜的智能活動，學習過程與推理過程是緊密相連的，按照學習中使用推理的多少，機器學習所採用的策略大體上可分為4種——機械學習、通過傳授學習、類比學習和通過事例學習。

2、模式識別：指對表徵事物或現象的各種形式的(數值的、文字的和邏輯關系的)信息進行處理和分析，以對事物或現象進行描述、辨認、分類和解釋的過程，是信息科學和人工智慧的重要組成部分。

三、應用前景不同

1、機器學習：繼專家系統之後人工智慧應用的又一重要研究領域，也是人工智慧和神經計算的核心研究課題之一。現有的計算機系統和人工智慧系統沒有什麼學習能力，至多也只有非常有限的學習能力，因而不能滿足科技和生產提出的新要求。

對機器學習的討論和機器學習研究的進展，必將促使人工智慧和整個科學技術的進一步發展 。

2、模式識別：一是研究生物體(包括人)是如何感知對象的，屬於認識科學的范疇，二是在給定的任務下，如何用計算機實現模式識別的理論和方法。前者是生理學家、心理學家、生物學家和神經生理學家的研究內容。

⑻ 模式識別的演算法一般用什麼編程語言實現

matlab
產品一般用C++實現