作者:finallyliuyu(轉載請注明原作者和出處)

（代碼暫不發布源碼下載版，以后會發布）

??? KNN文本分類算法又稱為(k nearest neighhor)。它是一種基于事例的學習方法，也稱懶惰式學習方法。

??? 它的大概思路是：對于某個待分類的樣本點，在訓練集中找離它最近的k個樣本點，并觀察這k個樣本點所屬類別。看這k個樣本點中，那個類別出現的次數多，則將這類別標簽賦予該待分類的樣本點。

?? 通過上面的描述，可以看出KNN算法在算法實現上是很簡單的，并不十分困難。

給出代碼之前，先給出實驗條件。

1。語料庫格式：

語料庫存放在MSSQLSERVER2000的數據庫的表單中，表單格式如下：

(fig 1)

2。如何獲得該形式的語料庫？

你可以從搜狗lab下載2008年的數據，并且用我的程序對這批數據進行處理，抽取出新聞。處理程序見《菜鳥學習C++練筆之整理搜狗2008版語料庫--獲取分類語料庫》或者去下載我上傳到博客園的語料資源見《獻給熱衷于自然語言處理的業余愛好者的中文新聞分類語料庫之二》

3。分割出訓練語料庫與測試語料庫（訓練語料庫和測試語料庫也是MSSQL表單，格式同fig1）。關于MSSQLSERVER的一些表復制的技巧見：《MSSQL語句備份》

下面開始給出C++代碼：

如果一些函數代碼沒有給出，請您參閱《菜鳥進階：C++實現Chi-square 特征詞選擇算法》以及K-means文本聚類系列（已經完成）

建立VSM模型（考慮到效率問題對訓練樣本集合與測試樣本集采用不同的函數建立VSM模型）

1。對訓練集建立VSM模型。

*****************以下函數輔助完成聚類功能*********************************************************************8**********************/ /************************************************************************/ /* 建立文檔向量模型 */ /************************************************************************/ map<int,vector<double> > Preprocess::VSMConstruction(map<string,vector<pair<int,int>>> &mymap) { clock_t start,finish;double totaltime;start=clock();int corpus_N=endIndex-beginIndex+1;map<int,vector<double>> vsmMatrix;vector<string> myKeys=GetFinalKeyWords();vector<pair<int,int> >maxTFandDF=GetfinalKeysMaxTFDF(mymap);for(int i=beginIndex;i<=endIndex;i++){ vector<pair<int,double> >tempVSM;vector<double>tempVSM2;for(vector<string>::size_type j=0;j<myKeys.size();j++){//vector<pair<int,int> >::iterator findit=find_if(mymap[myKeys[j]].begin(),mymap[myKeys[j]].end(),PredTFclass(i));double TF=(double)count_if(mymap[myKeys[j]].begin(),mymap[myKeys[j]].end(),PredTFclass(i));TF=0.5+(double)TF/(maxTFandDF[j].first);TF*=log((double)corpus_N/maxTFandDF[j].second);tempVSM.push_back(make_pair(j,TF));}if(!tempVSM.empty()){tempVSM=NormalizationVSM(tempVSM);//for(vector<pair<int,double> >::iterator it=tempVSM.begin();it!=tempVSM.end();it++){tempVSM2.push_back(it->second);}vsmMatrix[i]=tempVSM2;}tempVSM.clear();tempVSM2.clear();}finish=clock();totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"為訓練語料庫集合建立VSM模型共用了"<<totaltime<<endl;return vsmMatrix;}

2。對測試集建立VSM模型。

這里值得一提的是在tf-idf計算特征VSM模型特征詞權重的時候，tf:計算的是該詞在該篇文章中出現的次數。idf:用的是訓練集計算出的idf值。原因在于：在一個分類系統，我們假設代分類的文檔是一篇一篇進入分類系統中來的。

/************************************************************************/ /* 獲得待分類文檔集合的VSM模型 */ /************************************************************************/ map<int,vector<double>> Preprocess::GetManyVSM(int begin,int end,map<string,vector<pair<int,int>>> &mymap) {map<int,vector<double> > testingVSMMatrix;vector<string>keywords=GetFinalKeyWords();char * selectbySpecificId=new char [1000];memset(selectbySpecificId,0,1000);sprintf_s(selectbySpecificId,1000,"select ArticleId,CAbstract from Article where ArticleId between %d and %d",begin,end);set<string>stopwords=MakeStopSet();if(!ICTCLAS_Init()){printf("ICTCLAS INIT FAILED!\n");string strerr("there is a error");}ICTCLAS_SetPOSmap(ICT_POS_MAP_SECOND);//導入用戶詞典后printf("\n導入用戶詞典后：\n");int nCount = ICTCLAS_ImportUserDict("dict.txt");//覆蓋以前的用戶詞典//保存用戶詞典ICTCLAS_SaveTheUsrDic();printf("導入%d個用戶詞。\n", nCount);CoInitialize(NULL);_ConnectionPtr pConn(__uuidof(Connection));_RecordsetPtr pRst(__uuidof(Recordset));pConn->ConnectionString="Provider=SQLOLEDB.1;Password=xxxx;Persist Security Info=True; User ID=sa;Initial Catalog=ArticleCollection";pConn->Open("","","",adConnectUnspecified);pRst=pConn->Execute(selectbySpecificId,NULL,adCmdText);while(!pRst->rsEOF){string rawtext=(_bstr_t)pRst->GetCollect("CAbstract");if(rawtext!=""){string tempid=(_bstr_t)pRst->GetCollect("ArticleId");int articleid=atoi(tempid.c_str());vector<string>wordcollection=goodWordsinPieceArticle(rawtext,stopwords);//表示這篇文章的詞vector<pair<int,int> >maxTFandDF=GetfinalKeysMaxTFDF(mymap);int corpus_N=endIndex-beginIndex+1;vector<pair<int,double> >tempVSM;vector<double>vsm;for(vector<string>::size_type j=0;j<keywords.size();j++){double TF=(double)count_if(wordcollection.begin(),wordcollection.end(),GT_cls(keywords[j]));TF=0.5+(double)TF/(maxTFandDF[j].first);TF*=log((double)corpus_N/maxTFandDF[j].second);tempVSM.push_back(make_pair(j,TF));}if(!tempVSM.empty()){tempVSM=NormalizationVSM(tempVSM);for(vector<pair<int,double> >::iterator it=tempVSM.begin();it!=tempVSM.end();it++){vsm.push_back(it->second);}testingVSMMatrix[articleid]=vsm;}}pRst->MoveNext();}pRst->Close();pConn->Close();pRst.Release();pConn.Release();CoUninitialize();delete []selectbySpecificId;ICTCLAS_Exit();return testingVSMMatrix;}

?

對VSM序列化和反序列化的操作

/************************************************************************/ /* 將VSM模型序列化到本地硬盤 */ /************************************************************************/ void Preprocess::SaveVSM(map<int,vector<double> >&VSMmatrix,char* dest) { clock_t start,finish;double totaltime;start=clock();ofstream ofile(dest,ios::binary);for(map<int,vector<double> >::iterator it=VSMmatrix.begin();it!=VSMmatrix.end();++it){ofile<<it->first<<endl;vector<double>::iterator subit;ofile<<it->second.size()<<endl;for(subit=(it->second).begin();subit!=(it->second).end();++subit){ofile<<*subit<<" ";}ofile<<endl;}ofile.close();finish=clock();totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"將語料庫集合的VSM模型為序列化到硬盤的時間為"<<totaltime<<endl;}/************************************************************************/ /* 加載VSM模型到內存 */ /************************************************************************/ void Preprocess::LoadVSM(map<int,vector<double> >&VSMmatrix,char* dest) { clock_t start,finish;double totaltime;start=clock();ifstream ifile(dest,ios::binary);int articleId;//文章id；int lenVec;//id對應的vsm的長度double val;//暫存數據vector<double>vsm;while(!ifile.eof()){ifile>>articleId;ifile>>lenVec;for(int i=0;i<lenVec;i++){ifile>>val;vsm.push_back(val);}VSMmatrix[articleId]=vsm;vsm.clear();}ifile.close();finish=clock();totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"加載VSM模型到內存的時間為"<<totaltime<<endl;}

?

對一篇文章用KNN方法進行分類的函數（這里距離的定義采用余弦相似度）：

?

?

/************************************************************************/ /* 對一篇文章分類獲取其類別標簽 N為KNN中的N的取值 */ /************************************************************************/ string Preprocess:: KNNClassificationCell( int N,vector<double>vsm,vector<string>categorization,map<string,vector<pair<int,int>>> &mymap,map<int,vector<double> >&trainingsetVSM){clock_t start,finish;double totaltime;start=clock();string classLabel;//map<int,vector<double> >trainingsetVSM=VSMConstruction(mymap);//vector<double>toBeClassifyDoc=GetSingleVSM(articleId,mymap);vector<pair<int,double> >SimilaritySore;//保存待分類樣本與訓練樣本集的測試得分//計算相似度得分for(map<int,vector<double> >::iterator it=trainingsetVSM.begin();it!=trainingsetVSM.end();it++){double score=CalCosineofVectors(vsm,it->second);SimilaritySore.push_back(make_pair(it->first,score));}//將相似度運算結果從高到底排序stable_sort(SimilaritySore.begin(),SimilaritySore.end(),isLarger2);ostringstream out;string articleIds;out<<"(";int putComma=0;for(vector<pair<int ,double> >::size_type j=0;j<N;j++){out<<SimilaritySore[j].first;if(putComma<N-1){out<<",";}putComma++;}out<<")";articleIds=out.str();//獲得和待分類文檔距離最近的前N個文檔的id字符串vector<string> labels=GetClassification(articleIds);for(vector<string>::iterator it=labels.begin();it!=labels.end();it++){trim(*it," ");}vector<pair<string,int> >vectorAssit;for(int i=0;i<categorization.size();i++){int num=count_if(labels.begin(),labels.end(),GT_cls(categorization[i]));vectorAssit.push_back(make_pair(categorization[i],num));}stable_sort(vectorAssit.begin(),vectorAssit.end(),isLarger);finish=clock();totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"對一篇文章進行KNN分類的時間為"<<totaltime<<endl;return vectorAssit[0].first;} 根據articleid 讀取數據庫獲取類別的函數 ************************************************************************/ /* 獲得訓練語料庫中文章的類別標簽 */ /************************************************************************/ vector<string> Preprocess::GetClassification(string ArticleIds) { vector<string>labels;char * selectCategorization=new char[5000];memset(selectCategorization,50,5000);sprintf_s(selectCategorization,5000,"select Categorization from Article where ArticleId in%s",ArticleIds.c_str());CoInitialize(NULL);_ConnectionPtr pConn(__uuidof(Connection));_RecordsetPtr pRst(__uuidof(Recordset));pConn->ConnectionString=dbconnection;pConn->Open("","","",adConnectUnspecified);pRst=pConn->Execute(selectCategorization,NULL,adCmdText);delete []selectCategorization;while(!pRst->rsEOF){string label=(_bstr_t) pRst->GetCollect("Categorization");labels.push_back(label);pRst->MoveNext();}pRst->Close();pConn->Close();pRst.Release();pConn.Release();CoUninitialize();return labels;}

對訓練文檔集合用KNN進行分類

/************************************************************************/ /* KNN分類器 */ /************************************************************************/ vector<pair<int,string> > Preprocess::KNNclassifier(map<string,vector<pair<int,int>>> &mymap,map<int,vector<double> >&trainingsetVSM,map<int,vector<double> >&testingsetVSM,vector<string>catigorization,int N) {vector<pair<int,string>>classifyResults;for(map<int,vector<double> >::iterator it=trainingsetVSM.begin();it!=testingsetVSM.end();it++){string label=KNNClassificationCell(N,it->second,catigorization,mymap,trainingsetVSM);pair<int,string> temp=make_pair(it->first,label);classifyResults.push_back(temp);}return classifyResults;}

總結

以上是生活随笔為你收集整理的菜鸟进阶： C++实现KNN文本分类算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。