輕量級的文本分類演算法

A. Rocchio演算法的介紹

Rocchio 演算法，是一種高效的分類演算法，廣泛地被應用到文本分類，查詢擴展等領域。它通過構造原型向量的方法得到最優解

B. 文本分類器（基於KNN演算法），語言最好是Matlab的，有測試數據集。。。。

function [ccr,pgroupt]=knnt(x,group,K,dist,xt,groupt)
%#
%# AIM: to classify test set objects or unknown objects with the
%# K Nearest Neighbour method
%#
%# PRINCIPLE: KNN is a supervised, deterministic, non-parametric
%# classification method. It uses the majority rule to
%# assign new objects to a class.
%# It is assumed that the number of objects in each class
%# is similar.
%# There are no assumptions about the data distribution and
%# the variance-covariance matrices of each class.
%# There is no limitation of the number of variables when
%# the Euclidean distance is used.
%# However, when the correlation coefficient is used, the
%# number of variables must be larger than 1.
%# Ref: Massart D. L., Vandeginste B. G. M., Deming S. N.,
%# Michotte Y. and Kaufman L., Chemometrics: a textbook,
%# Chapter 23, 395-397, Elsevier Science Publishers B. V.,
%# Amsterdam 1988.
%#
%# INPUT: x: (mxn) data matrix with m objects and n variables,
%# containing samples of several classes (training set)
%# group: (mx1) column vector labelling the m objects from the
%# training set
%# K: integer, number of nearest neighbours
%# dist: integer,
%# = 1, Euclidean distance
%# = 2, Correlation coefficient, (No. of variables >1)
%# xt: (mtxn) data matrix with mt objects and n variables
%# (test set or unknowns)
%# groupt: (mtx1) column vector labelling the mt objects from
%# the test set
%# --> if the new objects are unknown, input [].
%#
%# OUTPUT: ccr: scalar, correct classification rate
%# pgroupt:row vector, predicted class label for the test set
%# 0 means that the object is not classified to any
%# class
%#
%# SUBROUTINES: sortlab.m: sorts the group label vector into classes
%#
%# AUTHOR: Wen Wu
%# Copyright(c) 1997 for ChemoAc
%# FABI, Vrije Universiteit Brussel
%# Laarbeeklaan 103 1090 Jette
%#
%# VERSION: 1.1 (28/02/1998)
%#
%# TEST: Andrea Candolfi
%#

function [ccr,pgroupt]=knnt(x,group,K,dist,xt,groupt);

if nargin==5, groupt=[]; end % for unknown objects
distance=dist; clear dist % change variable
if size(group,1)>1,
group=group'; % change column vector into row vector
groupt=groupt'; % change column vector into row vector
end;
[m,n]=size(x); % size of the training set

if distance==2 & n<2, error('Number of variables must > 1'),end % to check the number of variables when using correlation coefficient

[mt,n]=size(xt); % size of the test set
dis=zeros(mt,m); % initial values for the distance (matrix of zeros)

% Calculation of the distance for each test set object
for i=1:mt
for j=1:m % between each training set object and each test set object
if distance==1
dis(i,j)=(xt(i,:)-x(j,:))*(xt(i,:)-x(j,:))'; % Euclidian distance
else
r=corrcoef(xt(i,:)',x(j,:)'); % Correlation coefficient matrix
r=r(1,2); % Correlation coefficient
dis(i,j)=1-r*r; % 1 - the power of correlation coefficient
end
end
end

% Finding of the nearest neighbours
lab=zeros(1,mt); % initial values of lab
for i=1:mt % for each test object
[a,b]=sort(dis(i,:)); % sort distances
b=b(find(a<=a(K))); % to find the nearest neighbours indices
b=group(b); % the nearest neighbours objects
[ng,lgroup]=sortlab(b); % calculate the number of objects from each class in the nearest neighbours
a=find(ng==max(ng)); % find the class with the maximum number of objects

if length(a)==1 % only one class
lab(i)=lgroup(a); % class label
else
lab(i)=0; % more than one class
end
end

% Calculation of the success rate
if ~isempty(groupt)
dif=groupt-lab; % difference between predicted class label and known class label
ccr=sum(dif==0)/mt; % success rate
end

pgroupt=lab; % the output vector

C. 文本分類系統的流程及步驟

文本分類系統的總體功能模塊為：

1、預處理：將原始語料格式化為同一格式，便於後續的統一處理。

2、索引：將文檔分解為基本處理單元，同時降低後續處理的開銷。

3、統計：詞頻統計，項（單詞、概念）與分類的相關概率。

4、特徵抽取：從文檔中抽取出反映文檔主題的特徵。

5、分類器：分類器的訓練。

6、評價：分類器的測試結果分析。

(3)輕量級的文本分類演算法擴展閱讀

文本分類已廣泛應用於網路信息過濾、信息檢索和信息推薦等多個方面。數據驅動分類器學習一直是近年來的熱點，方法很多，比如神經網路、決策樹、支持向量機、樸素貝葉斯等。相對於其他精心設計的更復雜的分類演算法，樸素貝葉斯分類演算法是學習效率和分類效果較好的分類器之一。

直觀的文本分類演算法，也是最簡單的貝葉斯分類器，具有很好的可解釋性，樸素貝葉斯演算法特點是假設所有特徵的出現相互獨立互不影響，每一特徵同等重要。

但事實上這個假設在現實世界中並不成立：首先，相鄰的兩個詞之間的必然聯系，不能獨立；其次，對一篇文章來說，其中的某一些代表詞就確定它的主題，不需要通讀整篇文章、查看所有詞。所以需要採用合適的方法進行特徵選擇，這樣樸素貝葉斯分類器才能達到更高的分類效率。

D. 分類和聚類的區別及各自的常見演算法

1、分類和聚類的區別：
Classification (分類)，對於一個classifier，通常需要你告訴它「這個東西被分為某某類」這樣一些例子，理想情況下，一個 classifier 會從它得到的訓練集中進行「學習」，從而具備對未知數據進行分類的能力，這種提供訓練數據的過程通常叫做supervised learning (監督學習)，
Clustering (聚類)，簡單地說就是把相似的東西分到一組，聚類的時候，我們並不關心某一類是什麼，我們需要實現的目標只是把相似的東西聚到一起。因此，一個聚類演算法通常只需要知道如何計算相似度就可以開始工作了，因此 clustering 通常並不需要使用訓練數據進行學習，這在Machine Learning中被稱作unsupervised learning (無監督學習).
2、常見的分類與聚類演算法
所謂分類，簡單來說，就是根據文本的特徵或屬性，劃分到已有的類別中。如在自然語言處理NLP中，我們經常提到的文本分類便就是一個分類問題，一般的模式分類方法都可用於文本分類研究。常用的分類演算法包括：決策樹分類法，樸素貝葉斯分類演算法(native Bayesian classifier)、基於支持向量機(SVM)的分類器，神經網路法，k-最近鄰法(k-nearestneighbor，kNN)，模糊分類法等等。
分類作為一種監督學習方法，要求必須事先明確知道各個類別的信息，並且斷言所有待分類項都有一個類別與之對應。但是很多時候上述條件得不到滿足，尤其是在處理海量數據的時候，如果通過預處理使得數據滿足分類演算法的要求，則代價非常大，這時候可以考慮使用聚類演算法。
而K均值(K-mensclustering)聚類則是最典型的聚類演算法(當然，除此之外，還有很多諸如屬於劃分法K中心點（K-MEDOIDS）演算法、CLARANS演算法；屬於層次法的BIRCH演算法、CURE演算法、CHAMELEON演算法等；基於密度的方法：DBSCAN演算法、OPTICS演算法、DENCLUE演算法等；基於網格的方法：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；基於模型的方法)。

E. textgrocery 怎麼樣

TextGrocery 是一個基於SVM演算法的短文本分類工具，內置了結巴分詞，讓文本分類變得簡單。
示例代碼：
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
>>> from tgrocery import Grocery
# 新開張一個雜貨鋪，別忘了取名！
>>> grocery = Grocery（『sample』）
# 訓練文本可以用列表傳入
>>> train_src = [
（『ecation', 』名師指導托福語法技巧：名詞的復數形式『），
（'ecation', 』中國高考成績海外認可 是「狼來了」嗎？『），
（'sports', 』圖文：法網孟菲爾斯苦戰進16強 孟菲爾斯怒吼『），
（'sports', 』四川丹棱舉行全國長距登山挑戰賽 近萬人參與『）
]
>>> grocery.train（train_src）
# 也可以用文件傳入
>>> grocery.train（'train_ch.txt』）
# 保存模型
>>> grocery.save（）
# 載入模型（名字和保存的一樣）
>>> new_grocery = Grocery（『sample』）
>>> new_grocery.load（）
# 預測
>>> new_grocery.predict（『考生必讀：新托福寫作考試評分標准』）
ecation
# 測試
>>> test_src = [
（『ecation', 』福建春季公務員考試報名18日截止 2月6日考試『），
（'sports', 』意甲首輪補賽交戰記錄：米蘭客場8戰不敗國米10年連勝『），
]
>>> new_grocery.test（test_src）
# 准確率
0.5
# 同樣可以用文本傳入
>>> new_grocery.test（'test_ch.txt』）
# 自定義分詞器
>>> custom_grocery = Grocery（『custom', custom_tokenize=list）

F. 文本分類的6類方法

一、中文分詞：

針對中文文本分類時，很關鍵的一個技術就是中文分詞。特徵粒度為詞粒度遠遠好於字粒度，其大部分分類演算法不考慮詞序信息，基於字粒度的損失了過多的n-gram信息。下面簡單總結一下中文分詞技術:基於字元串匹配的分詞方法、基於理解的分詞方法和基於統計的分詞方法 [1]。

1，基於字元串匹配的分詞方法：
過程：這是一種基於詞典的中文分詞，核心是首先建立統一的詞典表，當需要對一個句子進行分詞時，首先將句子拆分成多個部分，將每一個部分與字典一一對應，如果該詞語在詞典中，分詞成功，否則繼續拆分匹配直到成功。
核心： 字典，切分規則和匹配順序是核心。
分析：優點是速度快，時間復雜度可以保持在O（n）,實現簡單，效果尚可；但對歧義和未登錄詞處理效果不佳。

2，基於理解的分詞方法：基於理解的分詞方法是通過讓計算機模擬人對句子的理解，達到識別詞的效果。其基本思想就是在分詞的同時進行句法、語義分析，利用句法信息和語義信息來處理歧義現象。它通常包括三個部分：分詞子系統、句法語義子系統、總控部分。在總控部分的協調下，分詞子系統可以獲得有關詞、句子等的句法和語義信息來對分詞歧義進行判斷，即它模擬了人對句子的理解過程。這種分詞方法需要使用大量的語言知識和信息。由於漢語語言知識的籠統、復雜性，難以將各種語言信息組織成機器可直接讀取的形式，因此目前基於理解的分詞系統還處在試驗階段。

3，基於統計的分詞方法：
過程：統計學認為分詞是一個概率最大化問題，即拆分句子，基於語料庫，統計相鄰的字組成的詞語出現的概率，相鄰的詞出現的次數多，就出現的概率大，按照概率值進行分詞，所以一個完整的語料庫很重要。
主要的統計模型有： N元文法模型（N-gram），隱馬爾可夫模型（Hidden Markov Model ，HMM），最大熵模型（ME），條件隨機場模型（Conditional Random Fields，CRF）等。

二、文本預處理：

1，分詞： 中文任務分詞必不可少，一般使用jieba分詞，工業界的翹楚。
2，去停用詞：建立停用詞字典，目前停用詞字典有2000個左右，停用詞主要包括一些副詞、形容詞及其一些連接詞。通過維護一個停用詞表，實際上是一個特徵提取的過程，本質 上是特徵選擇的一部分。
3，詞性標註： 在分詞後判斷詞性（動詞、名詞、形容詞、副詞…），在使用jieba分詞的時候設置參數

G. NLP之文本分類

作為NLP領域最經典的使用場景之一，文本分類積累了許多的實現方法。這里我們根據是否使用深度學習方法將文本分類主要分為一下兩個大類：

隨著統計學習方法的發展，特別是在90年代後互聯網在線文本數量增長和機器學習學科的興起，逐漸形成了一套解決大規模文本分類問題的經典玩法，這個階段的主要套路是人工特徵工程+淺層分類模型。整個文本分類問題就拆分成了 特徵工程 和 分類器 兩部分。

這里的特徵工程也就是將文本表示為計算機可以識別的、能夠代表該文檔特徵的特徵矩陣的過程。在基於傳統機器學習的文本分類中，我們通常將特徵工程分為 文本預處理、特徵提取、文本表示 等三個部分。

文本預處理過程是提取文本中的關鍵詞來表示文本的過程 。中文文本預處理主要包括 文本分詞 和 去停用詞 兩個階段。
文本分詞 ，是因為很多研究表明特徵粒度為詞粒度遠好於字粒度（其實很好理解，因為大部分分類演算法不考慮詞序信息，基於字粒度顯然損失了過多「n-gram」信息）。具體到中文分詞，不同於英文有天然的空格間隔，需要設計復雜的分詞演算法。傳統分詞演算法主要有 基於字元串匹配的正向/逆向/雙向最大匹配 ； 基於理解的句法和語義分析消歧 ； 基於統計的互信息/CRF方法 。近年來隨著深度學習的應用， WordEmbedding + Bi-LSTM+CRF方法 逐漸成為主流，本文重點在文本分類，就不展開了。
而 停止詞 是 文本中一些高頻的代詞、連詞、介詞等對文本分類無意義的詞 ，通常維護一個停用詞表，特徵提取過程中刪除停用表中出現的詞，本質上屬於特徵選擇的一部分。

特徵提取包括 特徵選擇 和 特徵權重計算 兩部分。
特徵選擇的基本思路 是 根據某個評價指標獨立的對原始特徵項（詞項）進行評分排序，從中選擇得分最高的一些特徵項，過濾掉其餘的特徵項 。常用的評價有：文檔頻率、互信息、信息增益、χ²統計量等。
特徵權重計算 主要是經典的TF-IDF方法及其擴展方法。 TF-IDF的主要思想 是 一個詞的重要度與在類別內的詞頻成正比，與所有類別出現的次數成反比 。

文本表示的目的是把文本預處理後的轉換成計算機可理解的方式，是決定文本分類質量最重要的部分。傳統做法常用 詞袋模型 （BOW, Bag Of Words）或 向量空間模型 （Vector Space Model），最大的 不足 是忽略文本上下文關系，每個詞之間彼此獨立，並且無法表徵語義信息。

大部分機器學習方法都在文本分類領域有所應用，比如樸素貝葉斯分類演算法（Naïve Bayes）、KNN、SVM、最大熵和神經網路等等。

FastText 是Facebook AI Research在16年開源的一種文本分類器。 其 特點 就是 fast 。相對於其它文本分類模型，如 SVM ， Logistic Regression 等模型，fastText能夠在保持分類效果的同時，大大縮短了訓練時間。

FastText方法包含三部分， 模型架構 ， 層次SoftMax 和 N-gram特徵 。

FastText模型架構和 Word2Vec 中的 CBOW 模型很類似，因為它們的作者都是Facebook的科學家Tomas Mikolov。不同之處在於，FastText 預測標簽 ，而CBOW 模型 預測中間詞 。

TextCNN 是利用卷積神經網路對文本進行分類的演算法，它是由 Yoon Kim 在2014年在 「 Convolutional Neural Networks for Sentence Classification 」 一文中提出的。詳細的原理圖如下。

特徵 ：這里的特徵就是詞向量，有 靜態（static） 和 非靜態（non-static） 方式。static方式採用比如word2vec預訓練的詞向量，訓練過程不更新詞向量，實質上屬於遷移學習了，特別是數據量比較小的情況下，採用靜態的詞向量往往效果不錯。non-static則是在訓練過程中更新詞向量。推薦的方式是 non-static 中的 fine-tunning方式，它是以預訓練（pre-train）的word2vec向量初始化詞向量，訓練過程中調整詞向量，能加速收斂，當然如果有充足的訓練數據和資源，直接隨機初始化詞向量效果也是可以的。

通道（Channels） ：圖像中可以利用 (R, G, B) 作為不同channel，而文本的輸入的channel通常是不同方式的embedding方式（比如 word2vec或Glove），實踐中也有利用靜態詞向量和fine-tunning詞向量作為不同channel的做法。

一維卷積（conv-1d） ：圖像是二維數據，經過詞向量表達的文本為一維數據，因此在TextCNN卷積用的是一維卷積。一維卷積帶來的問題是需要設計通過不同 filter_size 的 filter 獲取不同寬度的視野。

Pooling層： 利用CNN解決文本分類問題的文章還是很多的，比如這篇 A Convolutional Neural Network for Modelling Sentences 最有意思的輸入是在 pooling 改成 (dynamic) k-max pooling，pooling階段保留 k 個最大的信息，保留了全局的序列信息。

參考文獻

H. 求KNN文本分類演算法java實現源代碼【散分了！！！！】

#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
#define NATTRS 5 //number of attributes
#define MAXSZ 1700 //max size of training set
#define MAXVALUE 10000.0 //the biggest attribute's value is below 10000(int)
#define K 5
struct vector {
double attributes[NATTRS];
double classlabel;
};
struct item {
double distance;
double classlabel;
};
struct vector trSet[MAXSZ];//global variable,the training set
struct item knn[K];//global variable,the k-neareast-neighbour set
int curTSize = 0; //current size of the training set
int AddtoTSet(struct vector v)
{
if(curTSize>=MAXSZ) {
cout<<endl<<"The training set has "<<MAXSZ<<" examples!"<<endl<<endl;
return 0;
}
trSet[curTSize] = v;
curTSize++;
return 1;
}
double Distance(struct vector v1,struct vector v2)
{
double d = 0.0;
double tem = 0.0;
for(int i = 0;i < NATTRS;i++)
tem += (v1.attributes[i]-v2.attributes[i])*(v1.attributes[i]-v2.attributes[i]);
d = sqrt(tem);
return d;
}
int max(struct item knn[]) //return the no. of the item which has biggest distance(
//should be replaced)
{
int maxNo = 0;
if(K > 1)
for(int i = 1;i < K;i++)
if(knn[i].distance>knn[maxNo].distance)
maxNo = i;
return maxNo;
}double Classify(struct vector v)//decide which class label will be assigned to
//a given input vetor with the knn method
{
double dd = 0;
int maxn = 0;
int freq[K];
double mfreqC = 0;//the class label appears most frequently
int i;
for(i = 0;i < K;i++)
knn[i].distance = MAXVALUE;
for(i = 0;i < curTSize;i++)
{
dd = Distance(trSet[i],v);
maxn = max(knn);//for every new state of the training set should update maxn
if(dd < knn[maxn].distance) {
knn[maxn].distance = dd;
knn[maxn].classlabel = trSet[i].classlabel;
}
}
for(i = 0;i < K;i++)//freq[i] represents knn[i].classlabel appears how many times
freq[i] = 1;
for(i = 0;i < K;i++)
for(int j = 0;j < K;j++)
if((i!=j)&&(knn[i].classlabel == knn[j].classlabel))
freq[i]+=1;
int mfreq = 1;
mfreqC = knn[0].classlabel;
for(i = 0;i < K;i++)
if(freq[i] > mfreq) {
mfreq = freq[i];//mfreq represents the most frepuences
mfreqC = knn[i].classlabel; //mfreqNo is the item no. with the most frequent
//classlabel
}
return mfreqC;
}
void main()
{ double classlabel;
double c;
double n;
struct vector trExmp;
int i;
ifstream filein("G:\\data\\for knn\\data.txt");
if(filein.fail()){cout<<"Can't open data.txt"<<endl; return;}
while(!filein.eof()) {
filein>>c;
trExmp.classlabel = c;
cout<<trExmp.classlabel<<" "; for(int i = 0;i < NATTRS;i++) {
filein>>n;
trExmp.attributes[i] = n;
cout<<trExmp.attributes[i]<<" ";
} cout<<endl;
if(!AddtoTSet(trExmp))
break;
}filein.close();struct vector testv={{142,188,11,1159,0.5513196},17};
classlabel = Classify(testv);
cout<<"The classlable of the testv is: ";
cout<<classlabel<<endl;
for(i = 0;i < K;i++)
cout<<knn[i].distance<<"\t"<<knn[i].classlabel<<endl;
//cout<<max(knn);
}

I. 文本分類和聚類有什麼區別

文本分類和聚類有什麼區別
簡單點說：分類是將一篇文章或文本自動識別出來，按照已經定義好的類別進行匹配，確定。聚類就是將一組的文章或文本信息進行相似性的比較，將比較相似的文章或文本信息歸為同一組的技術。分類和聚類都是將相似對象歸類的過程。區別是，分類是事先定義好類別，類別數不變。分類器需要由人工標注的分類訓練語料訓練得到，屬於有指導學習范疇。聚類則沒有事先預定的類別，類別數不確定。聚類不需要人工標注和預先訓練分類器，類別在聚類過程中自動生成。分類適合類別或分類體系已經確定的場合，比如按照國圖分類法分類圖書；聚類則適合不存在分類體系、類別數不確定的場合，一般作為某些應用的前端，比如多文檔文摘、搜索引擎結果後聚類(元搜索)等。
分類(classification )是找出描述並區分數據類或概念的模型(或函數)，以便能夠使用模型預測類標記未知的對象類。分類技術在數據挖掘中是一項重要任務,目前商業上應用最多。分類的目的是學會一個分類函數或分類模型(也常常稱作分類器),該模型能把資料庫中的數據項映射到給定類別中的某一個類中。
要構造分類器，需要有一個訓練樣本數據集作為輸入。訓練集由一組資料庫記錄或元組構成，每個元組是一個由有關欄位(又稱屬性或特徵)值組成的特徵向量，此外，訓練樣本還有一個類別標記。一個具體樣本的形式可表示為：(v1,v2,...,vn; c)；其中vi表示欄位值，c表示類別。分類器的構造方法有統計方法、機器學習方法、神經網路方法等等。
不同的分類器有不同的特點。有三種分類器評價或比較尺度：1)預測准確度；2)計算復雜度；3)模型描述的簡潔度。預測准確度是用得最多的一種比較尺度，特別是對於預測型分類任務。計算復雜度依賴於具體的實現細節和硬體環境，在數據挖掘中，由於操作對象是巨量的數據，因此空間和時間的復雜度問題將是非常重要的一個環節。對於描述型的分類任務，模型描述越簡潔越受歡迎。
另外要注意的是，分類的效果一般和數據的特點有關，有的數據雜訊大，有的有空缺值，有的分布稀疏，有的欄位或屬性間相關性強，有的屬性是離散的而有的是連續值或混合式的。目前普遍認為不存在某種方法能適合於各種特點的數據
聚類(clustering)是指根據「物以類聚」原理，將本身沒有類別的樣本聚集成不同的組，這樣的一組數據對象的集合叫做簇，並且對每一個這樣的簇進行描述的過程。它的目的是使得屬於同一個簇的樣本之間應該彼此相似，而不同簇的樣本應該足夠不相似。與分類規則不同，進行聚類前並不知道將要劃分成幾個組和什麼樣的組，也不知道根據哪些空間區分規則來定義組。其目的旨在發現空間實體的屬性間的函數關系，挖掘的知識用以屬性名為變數的數學方程來表示。聚類技術正在蓬勃發展，涉及范圍包括數據挖掘、統計學、機器學習、空間資料庫技術、生物學以及市場營銷等領域，聚類分析已經成為數據挖掘研究領域中一個非常活躍的研究課題。常見的聚類演算法包括：K-均值聚類演算法、K-中心點聚類演算法、CLARANS、BIRCH、CLIQUE、DBSCAN等。關鍵詞：文本分類 文本聚類 數據挖掘 機器學習