文本分类、聚类算法中,最常见的障碍就是高维矩阵。对于具有一定规模的文本聚类很轻易会遇到维度成千上万的矩阵,如果按照常规计算方法,耗时将不可估量。而非负矩阵分解则是非常好的降维理论,利用非负矩阵分解我们可以将高维矩阵分解为可接受的小维矩阵,并保持其原矩阵的特征。这篇文章将介绍如何利用非负矩阵分解做文本聚类。非负矩阵分解英文全称是 Non-negative matrix factorization(NMF)。请您记住本文只做文本聚类,并不介绍如何中文分词。
下面的引用是Wikipedia对NMF的历史介绍:
Early work on non-negative matrix factorizations was performed by a Finnish group of researchers in the middle of the 1990s under the name positive matrix factorization. It became more widely known as non-negative matrix factorization after Lee and Seung investigated the properties of the algorithm and published some simple and useful algorithms for two types of factorizations. [Read →][1]
好了废话我不多说,相信对这篇文章感兴趣的人对NMF也应该有所了解。
我根据实际的情况来写这个工作过程。从我手头有的资料说起:
- 用于训练的样本数据,也就是已经做好分词的中文文本,类别已经标注 file1.txt~file50.txt 每10篇代表一大类(环境、教育、经济、体育、政治)
- 停用词表(如果您还没有,请在google里搜索)
- 待测试文本,属于上述5大类的文本,也是已经做好分词处理的
- 开发环境(可编译c代码即可)
整个文本分类可以分为3大部分:
- 文本的处理
- 利用NMF做矩阵分解
- 利用NMF得到的降维特征矩阵和相关数据分类待分类文本
注:请从宏观角度记住着3大部分
第一:建立VSM
实际上第一步文本的处理无非就是找到VSM (Vector space model) 向量空间模型。利用TF-IDF(term frequency–inverse document frequency)求出每个词的权重。这步的目的就是生成一个所有文章,所有词的一个矩阵。这个矩阵带有这些文本的特点。(tf-idf也就是 词频-逆文频率指数) 公式如下:
- TF=某词在一文本中出现次数/这篇文本总词数
- IDF=log(文本集合总数/这个词出现的文本个数)
- TF*IDF就是这个词在特征矩阵的权重。
关于这个google数学之美系列中有很生动的介绍请自行研读, 我这里简单介绍,tf就是一个词在文本中出现的频率,idf则可以反映出这个词在整个文本集里的广泛程度。如果一个词出现的越广泛那么它的主题相关性就越低。就像google数学之美系列中介绍的一样“原子能 的 应用”这句话里“原子能”的广泛度应该比“应用”低,这个是个常识,至于“的”,由于它太广泛所以沦落到停用此表里了。
这个生成的矩阵大概是个什么样子呢?我随便写一个样子把。数据我瞎写的看看样子而已。
1 2 3 4 |
文本1 文本2 文本3 词1 0.3 0.3 0.0 词2 0.7 0.1 0.8 词3 0.0 0.6 0.2 |
这里面的每个数据都是TF*IDF得到的。好下面我吧第一部分求VSM的代码贴一下:
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 |
/************************************************** * VSM by keefo 2008.05.26 **************************************************/ #include <stdio.h> #include <math.h> #include <map> #include <string> #include <vector> using namespace std; #define FILENUM 50 #define isDigit(ch) ((ch)>='0' && (ch)<='9') #define isAlpha(ch) (((ch)>='a' && (ch)<='z') || ((ch)>='A' && (ch)<='Z')) #define isSign(ch) (((ch)<127 && (ch)>=0)?signindex[ch]:0) map<string, int> dic; //全局词典。文本集里出现过的词全部保存在这里 map<string, int> filedic[FILENUM]; map<string, int> stopword;//停用词表 vector<string> diclist;//单篇文档词典 int signindex[200]={0};//符号hash表用来去除文章里的符号 int loadstopword() //加载停用词到stopword中 { FILE *fp; char str[32]; stopword.clear(); fp=fopen("stopwords.txt","r"); if(fp==NULL) { printf("Can't open stopword file.\n"); system("pause"); return 1; } printf("Loading stopword..."); while(fscanf(fp,"%s",str)!=EOF) stopword[str]=1; fclose(fp); printf("OK!\n"); return 0; } int trimfile() { int i; char ch,name[128],word[128]; FILE *fp1,*fp2; printf("Create trim file waiting...\n"); //去除符号 for(i=0;i<FILENUM;i++) { sprintf(name,"file/file%d.txt",i+1);//训练数据保存在file目录下 fp1=fopen(name,"r"); if(fp1==NULL){ printf("Open file %s error!\n",name); system("pause"); return 1; } sprintf(name,"trim%d.txt",i+1); fp2=fopen(name,"w+"); if(fp2==NULL){ printf("Create file %s error!\n",name); system("pause"); return 1; } ch=fgetc(fp1); while(ch!=EOF) { if(!(isDigit(ch) || isAlpha(ch) || isSign(ch))) { fputc(ch,fp2); } ch=fgetc(fp1); } fclose(fp1); fclose(fp2); } //去除停用词 for(i=0;i<FILENUM;i++) { sprintf(name,"trim%d.txt",i+1); fp1=fopen(name,"r+"); if(fp1==NULL){ printf("Can't open file %s!\n",name); system("pause"); return 1; } sprintf(name,"file%d.txt",i+1); printf("%d ",i+1); fp2=fopen(name,"w"); if(fp2==NULL) { printf("Create file %s error!\n",name); system("pause"); return 1; } while(fscanf(fp1,"%s",word)!=EOF) { if(!stopword[word]) fprintf(fp2,"%s ",word); } fclose(fp1); fclose(fp2); } printf("\n"); system("del trim*.txt");//删除临时文件 return 0; } void initsign()//初始化符号表 { memset(signindex,0,sizeof(signindex)); signindex[33]=1; signindex[34]=1; signindex[37]=1; signindex[38]=1; signindex[40]=1; signindex[41]=1; signindex[42]=1; signindex[43]=1; signindex[44]=1; signindex[45]=1; signindex[46]=1; signindex[47]=1; signindex[58]=1; signindex[59]=1; signindex[60]=1; signindex[61]=1; signindex[62]=1; signindex[63]=1; signindex[91]=1; signindex[93]=1; signindex[95]=1; signindex[123]=1; signindex[125]=1; signindex[126]=1; } int allwordnum,process[11]={0}; void processing(int k)//显示计算进度 { float s=(float)k/allwordnum*100; int ca=(int)s/10; if(!process[ca]) { if(ca==10) printf("%d%% OK!",ca*10); else printf("%d%% ",ca*10); process[ca]=1; } } int main(int argc,char *argv[]) { FILE *fp; char name[128],word[128]; int i,j,filewordnum[FILENUM]; initsign(); if(loadstopword()) return 1; if(trimfile()) return 1; //计算tf-idf建立向量空间模型 printf("Create VSM waiting ...\n"); diclist.clear(); dic.clear(); for(i=0;i<FILENUM;i++) //按顺序打开处理好的文本,统计词 { filedic[i].clear(); sprintf(name,"file%d.txt",i+1); printf("%d ",i+1); fp=fopen(name,"r"); if(fp == NULL){ printf("Processing file %d error!",i+1); system("pause"); continue; } filewordnum[i]=0; while(fscanf(fp,"%s",word) != EOF) //循环查找该文件内所有单词 { if(filedic[i][word]) { //如果在filedic[i]里发现这个单词,出现个数增加,总字典内个数增加 filedic[i][word]++; dic[word]++; } else { filedic[i][word]=1;//没出现过的新单词加入filedic[i] if(dic[word]==0) { //如果也不在dic里,同样加入dic和diclist内。 diclist.push_back(word); dic[word]=1; } else { //在总字典里出现过,出现个数增加 dic[word]++; } } filewordnum[i]++; } fclose(fp); } system("del file*.txt");//删除临时文件 fp=fopen("T_v.txt","w"); if(fp == NULL){ printf("Create v file error."); system("pause"); return 1; } allwordnum=diclist.size(); printf("\n计算&打印VSM T_v.txt\n"); printf("一共有 %d 个词需要计算 waiting ... \n",allwordnum); fprintf(fp,"%d %d\n",FILENUM,allwordnum); int knum; string key; double tf,idf; FILE *fpword; fpword=fopen("T_word.txt","w"); fprintf(fpword,"%d\n",allwordnum); for(i=0;i<allwordnum;i++) { key=diclist[i]; fprintf(fpword,"%s\n",key.c_str()); for(knum=j=0;j<FILENUM;j++) if(filedic[j][key]) knum++;//knum出现该词的文档数 idf=log((double)FILENUM/knum);//逆文频率指数,这里注意要排除全局都出现的关键词。log(1)=0 会导致后期迭代失败 for(j=0;j<FILENUM;j++) { tf=(double)filedic[j][key]/filewordnum[j];//词频 fprintf(fp,"%.8lf ", tf*idf); } fprintf(fp,"\n"); processing(i+1);//显示计算进度 } fclose(fp); fclose(fpword); return 0; } |
截图显示该程序运行结果如下:
经过这个程序会把50篇训练样本变成一个T_v.txt文件也就是这50篇文章的VSM,还有一个T_word.txt这个全部的词表。这是很好的开始,我们已经把一篇篇文章变成可以计算的数字了。
第二:VSM做NMF分解
接下来第2大步骤用NMF分解矩阵。这个步骤目的很简单,给VSM降维。因为VSM太庞大了,文本分类速度会很慢。NMF可以把一个非负矩阵X分解成2个非负矩阵B、H,满足X≈BH。矩阵分解的数学研究有很长历史,大家可以自己慢慢学习。至于矩阵分解后为何可以做文本分类,呵呵大家可以后悔自己上学的时候为什么没好好学习线性代数了,不过可以简单的理解为分解后的矩阵带有原矩阵的特点
第二步可以使用不同的矩阵分解方法,例如PCA(主成分分析)、ICA(独立成分分析)、SVD(奇异值分解)、VQ(矢量量化)等,它们各有特点。不过都是对原矩阵没有约束的,NMF则有非负这个约束条件。
NMF算法3个输入参数分别是X,R,IterateNum 。X是哪个大矩阵,R是降维后的B的秩,IterateNum 是NMF的迭代次数。NMF是迭代计算的,需要迭代次数。生成的BH会收敛。迭代次数越多BH越接近X。至于迭代多少次就可以自己可以测试,满足精度就可以了,否则NMF迭代计算比较费时间。
NMF算法2个输出分别是B和H。算法描述如下:
1 2 3 4 5 6 |
1. 初始化矩阵B,H为非负数,同时对U的每一列数据归一化 2. for i=1 to IterateNum a:H = H .* ( B' * ( X ./ ( B * H ) ) ) b:B = B .* ( ( X ./ ( B * H ) ) * H' ) c:B 归一化 3. end |
对上面这个伪代码做个解释。先说B,H的大小原矩阵X(w,h)的话 B(R,Xh) H(Xw,R) (注:w表示矩阵宽度,h表示高度)
初始化B,H是将2个矩阵的数据随机赋值,正浮点数范围(1.0~10.0)就可以了。接着第一步里B需要归一化,归一化的意思就是把B变成一个特殊的矩阵,特殊之处在于,B的每一列相加正好等于1。
第二步迭代IterateNum次,其中U’表示矩阵转置,.表示点乘就是矩阵对应位置数据相乘 ./就是点除对应位置相除。就是矩阵乘法。
下面贴一下NMF 的代码:
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 |
/************************************************** * NMF by keefo 2008.05.26 **************************************************/ #include <stdio.h> #include <string.h> #include <memory.h> #include <stdlib.h> #include <time.h> #define ARRAY2D(VTYPE,X,Y) (VTYPE **) malloc2d(X, Y, sizeof(VTYPE)) #define MATRIX(NAME,X,Y) matrix NAME;NAME.p=ARRAY2D(double,X,Y);NAME.x=X;NAME.y=Y; #define FREE(X) free2d(&X) typedef struct{ double **p; int x,y; } matrix; void** malloc2d(int W, int H, int size) { int j,rowSize=W*size,colSize=H*sizeof(void *); void **a = (void **)malloc(colSize+H*rowSize); char *begin=(char *)a+colSize; for(j=0;j<H;j++) a[j]=begin+j*rowSize; return a; } void free2d(matrix *M) { free(M->p); M->p=0; M->x=M->y=0; } matrix RandomMatrix(int x,int y) //生成随机矩阵 { int i,j; MATRIX(A,x,y); srand((int)time(NULL)); for(i=0;i<y;i++) { for(j=0;j<x;j++) { A.p[i][j]=((double)rand()/((double)RAND_MAX+1))*10; } } return A; } matrix ONES(int x,int y) //生成全为1的矩阵 { int i,j; MATRIX(A,x,y); for(i=0;i<A.y;i++) { for(j=0;j<A.x;j++) A.p[i][j]=1.0; } return A; } void SUM(matrix A,matrix *B) { int i,j; double sum; for(i=0;i<A.x;i++) { sum=0.0; for(j=0;j<A.y;j++) sum+=A.p[j][i]; B->p[0][i]=sum; } } void DOTMUL(matrix A,matrix B,matrix *C) //矩阵点乘 { int i,j; if(A.x!=B.x || A.y!=B.y) return; for(i=0;i<A.y;i++) for(j=0;j<A.x;j++) C->p[i][j]=A.p[i][j]*B.p[i][j]; } void MUL(matrix A,matrix B,matrix *C) //矩阵相乘 { int i,j,k; double sum; if(A.x!=B.y) return; for(i=0;i<A.y;i++) { for(j=0;j<B.x;j++) { sum=0.0; for(k=0;k<A.x;k++) sum+=A.p[i][k]*B.p[k][j]; C->p[i][j]=sum; } } } void DOTDIV(matrix A,matrix B,matrix *C) //矩阵点除 { int i,j; if(A.x!=B.x || A.y!=B.y) return; for(i=0;i<A.y;i++) for(j=0;j<A.x;j++) C->p[i][j]=A.p[i][j]/B.p[i][j]; } void T(matrix S,matrix *D) //矩阵转置 { int i,j; for(i=0;i<S.y;i++) { for(j=0;j<S.x;j++) { D->p[j][i]=S.p[i][j]; } } } void fprint(char name[128],matrix m) { int i,j; FILE *fp; fp=fopen(name,"w"); fprintf(fp,"%d %d\n",m.x,m.y); if(m.p){ for(i=0;i<m.y;i++){ for(j=0;j<m.x;j++) fprintf(fp,"%.8f ",m.p[i][j]); fprintf(fp,"\n"); } } fclose(fp); } int main(int argc, char * argv[]) { int i,j,x,y,r,iteratenum; char word[128]; FILE *fp; fp=fopen("config.ini","r"); if(fp==NULL){ printf("Can't open file config.ini!\n"); system("pause"); return 1; } fscanf(fp,"%s %d",word,&r); fscanf(fp,"%s %d",word,&iteratenum); fclose(fp); fp=fopen("T_v.txt","r"); if(fp==NULL){ printf("Can't open file T_v.txt!\n"); system("pause"); return 1; } fscanf(fp,"%d %d",&x,&y); MATRIX(X,x,y); for(i=0;i<y;i++) for(j=0;j<x;j++) fscanf(fp,"%lf",&X.p[i][j]); fclose(fp); printf("r=%d\n",r); matrix B=RandomMatrix(r,X.y); //初始化B,为随机非负数 matrix H=RandomMatrix(X.x,r); //初始化H,为随机非负数 /*************定义中间变量*************/ matrix one=ONES(1,X.y); MATRIX(XX,X.x,X.y); MATRIX(TB,B.y,B.x); MATRIX(BB,B.x,B.y); MATRIX(TH,H.y,H.x); MATRIX(HH,H.x,H.y); MATRIX(BH,H.x,B.y); MATRIX(SB,B.x,1); /*************归一化B的每一列*************/ SUM(B,&SB); MUL(one,SB,&BB); DOTDIV(B,BB,&B); /*************开始迭代计算*************/ printf("共%d次迭代计算\n",iteratenum); for(i=0;i<iteratenum;i++) { printf("%d ",i+1); // a:H = H .* ( B' * ( X ./ ( B * H ) ) ) MUL(B,H,&BH); DOTDIV(X,BH,&XX); T(B,&TB); MUL(TB,XX,&HH); DOTMUL(H,HH,&H); // b:B = B .* ( ( X ./ ( B * H ) ) * H' ) T(H,&TH); MUL(B,H,&BH); DOTDIV(X,BH,&XX); MUL(XX,TH,&BB); DOTMUL(B,BB,&B); // c:B 归一化 SUM(B,&SB); MUL(one,SB,&BB); DOTDIV(B,BB,&B); } //MUL(B,H,&XX);//测试计算出来的BH相乘是否接近X //fprint("BxH.txt",XX); T(B,&TB); MUL(TB,X,&HH); printf("\n计算完成!\n"); printf("写入数据 T_eigenvector.txt...\n"); fprint("T_eigenvector.txt",HH); fprint("T_B.txt",TB); FREE(B); FREE(H); FREE(X); FREE(one); FREE(BB); FREE(HH); FREE(TB); FREE(TH); FREE(SB); FREE(XX); return 0; } |
现在虽然代码已经贴出来了,但是有些细节还没介绍。NMF程序计算完,它把VSM生成的T_v.txt这个矩阵分解,生成了B和H。但是第3步的文本分类并不是直接利用生成的B、H,而是需要使用 B’ 和 B’ * X 。所以 T_B.txt 和 T_eigenvector.txt 这2个文件,T_B.txt 是分解出的矩阵B的转置,T_eigenvector.txt 则是 B’ * X 。所以保存这2个矩阵。
第三:文本文类
从实际角度考虑文本分类传入的参数应该是一个待分类的文本,输出是它属于哪个类别。这样需要计算的就是这个文本和哪个类别的相似度最高。
从程序计算的角度考虑,现在已经拥有的数据是训练样本生成的特征矩阵T_eigenvector.txt和B的转置T_B.txt 。所以待分类文本也需要做处理才能用于计算,当然是生成待分类文本的特征查询向量q,注意是q查询向量,也就是一个1xW的矩阵。这个向量应该在第一步建立的表征词表T_word.txt的基础上。因为这样才能保证待分类向量和训练样本在同一个语义集合。请仔细理解这里。
例如上面的例子中,我建立的表征词共8109个,那么如果要分类一个文件ABC.t×t 那么需要建立的这个向量便是ABC内的词映射到这8109个词上的统计表,使用tf计算权重。这个向量也是1×8109的。
接下来我就说明如何计算这个查询向量q和训练出来的特征矩阵的相似度。使用余弦距离计算2个向量的距离。T_eigenvector.txt的每一列表示一个训练文件的特征向量。余弦距离计算,传入的参数是2个同维的向量,而T_eigenvector.txt的每一列是个R维的向量,当然我们的这个查询向量q则有8109维。这时候大家应该想的了,需要第2步生成的哪个B’ ,也就是T_B.txt 。公式如下:
1 2 |
q = q * B' |
这个公式把查询向量q转化成R维。这样就可以计算这个查询向量和哪个训练文本相似度高了。
把q分别和T_eigenvector.txt的50列计算余弦距离。然后每10列求平均值,得到5列,这5列就是查询向量和5大类文本的相似度,越大的相似度越高。
下面写出代码:
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 |
/************************************************** * Class by keefo 2008.05.26 **************************************************/ #include <stdio.h> #include <string.h> #include <time.h> #include <math.h> #include <map> #include <string> #include <vector> using namespace std; #define FILENUM 50 #define isDigit(ch) ((ch)>='0' && (ch)<='9') #define isAlpha(ch) (((ch)>='a' && (ch)<='z') || ((ch)>='A' && (ch)<='Z')) #define isSign(ch) (((ch)<127 && (ch)>=0)?signindex[ch]:0) #define ARRAY2D(VTYPE,X,Y) (VTYPE **) malloc2d(X, Y, sizeof(VTYPE)) #define MATRIX(NAME,X,Y) matrix NAME;NAME.p=ARRAY2D(double,X,Y);NAME.x=X;NAME.y=Y; #define FREE(X) free2d(&X) map<string, int> dic; map<string, int> filedic[FILENUM]; map<string, int> stopword; vector<string> diclist; int filewordnum[FILENUM]; typedef struct{ double **p; int x,y; } matrix; int signindex[200]={0}; int loadstopword() //加载停用词到stopword中 { FILE *fp; char str[32]; stopword.clear(); fp=fopen("stopwords.txt","r"); if(fp==NULL) { printf("Can't open stopword file.\n"); system("pause"); return 1; } printf("Loading stopword...OK!\n"); while(fscanf(fp,"%s",str)!=EOF) stopword[str]=1; fclose(fp); return 0; } int trimfile() { int i; char ch,name[128],word[128]; FILE *fp1,*fp2; printf("Create trim file waiting...\n"); for(i=0;i<FILENUM;i++) { sprintf(name,"data/file%d.txt",i+1); fp1=fopen(name,"r"); if(fp1==NULL){ printf("Open file %s error!\n",name); system("pause"); return 1; } sprintf(name,"trim%d.txt",i+1); fp2=fopen(name,"w"); if(fp2==NULL){ printf("Create file %s error!\n",name); system("pause"); return 1; } ch=fgetc(fp1); while(ch!=EOF) { if(!(isDigit(ch) || isAlpha(ch) || isSign(ch))) { fputc(ch,fp2); } ch=fgetc(fp1); } fclose(fp1); fclose(fp2); } for(i=0;i<FILENUM;i++) { sprintf(name,"trim%d.txt",i+1); fp1=fopen(name,"r"); if(fp1==NULL){ printf("Can't open file %s!\n",name); system("pause"); return 1; } sprintf(name,"file%d.txt",i+1); printf("%d ",i+1); fp2=fopen(name,"w"); if(fp2==NULL) { printf("Create file %s error!\n",name); system("pause"); return 1; } while(fscanf(fp1,"%s",word)!=EOF) { if(!stopword[word]) fprintf(fp2,"%s ",word); } fclose(fp1); fclose(fp2); } printf("\n"); system("del trim*.txt"); return 0; } void initsign() { memset(signindex,0,sizeof(signindex)); signindex[33]=1; signindex[34]=1; signindex[37]=1; signindex[38]=1; signindex[40]=1; signindex[41]=1; signindex[42]=1; signindex[43]=1; signindex[44]=1; signindex[45]=1; signindex[46]=1; signindex[47]=1; signindex[58]=1; signindex[59]=1; signindex[60]=1; signindex[61]=1; signindex[62]=1; signindex[63]=1; signindex[91]=1; signindex[93]=1; signindex[95]=1; signindex[123]=1; signindex[125]=1; signindex[126]=1; } void** malloc2d(int W, int H, int size) { int j,rowSize=W*size,colSize=H*sizeof(void *); void **a = (void **)malloc(colSize+H*rowSize); char *begin=(char *)a+colSize; for(j=0;j<H;j++) a[j]=begin+j*rowSize; return a; } void free2d(matrix *M) { free(M->p); M->p=0; M->x=M->y=0; } double SIM(matrix A,matrix B,int i,int j) //计算余弦距离 { int m; double molecule=0.0,denominatorA=0.0,denominatorB=0.0; if(A.y!=B.y || i>=A.x || j>=B.x) return -1.0; for(m=0;m<A.y;m++) { molecule+=(A.p[m][i]*B.p[m][j]); denominatorA+=(A.p[m][i]*A.p[m][i]); denominatorB+=(B.p[m][j]*B.p[m][j]); } denominatorA=sqrt(denominatorA*denominatorB); return molecule/denominatorA; } void MUL(matrix A,matrix B,matrix *C) //矩阵相乘 { int i,j,k; double sum; if(A.x!=B.y) return; for(i=0;i<A.y;i++) { for(j=0;j<B.x;j++) { sum=0.0; for(k=0;k<A.x;k++) sum+=A.p[i][k]*B.p[k][j]; C->p[i][j]=sum; } } } void disprint(char name[128],matrix m) { int i,j,k,maxindex=0; double classes[5],max=-1.0; char CLASS[5][32]={"环境","教育","经济","政治","体育"}; FILE *fp; fp=fopen(name,"w"); fprintf(fp,"%d %d\n",m.x,m.y); printf("\n打印分类表 waiting...\n"); for(i=0;i<FILENUM;i++) { max=-1.0; maxindex=0; j=0; k=j+10; while(k<=FILENUM){ double avg=0.0; while(1) { avg=avg+m.p[i][j]; j++; if(j==k)break; } if(avg/10.0>max){ maxindex=j/10-1; max=avg/10.0; } classes[j/10-1]=avg/10.0; k=j+10; } fprintf(fp,"File%2d.txt ",i+1); for(k=0;k<5;k++) { if(k==maxindex){ fprintf(fp,"\t|%s|",CLASS[k]); } else{ fprintf(fp,"\t %s ",CLASS[k]); } } fprintf(fp,"\n"); } fclose(fp); } int processingdata() { FILE *fp,*fpv; char name[128],word[128]; int i,j,wordnum; initsign(); if(loadstopword()) return 1; if(trimfile()) return 1; fp=fopen("T_word.txt","r"); if(fp==NULL){ printf("Can't open file T_word.txt!\n"); system("pause"); return 1; } fscanf(fp,"%d",&wordnum); for(i=0;i<wordnum;i++){ fscanf(fp,"%s",word); dic[word]=1; diclist.push_back(word); } fclose(fp); fpv=fopen("dis_v.txt","w"); if(fpv == NULL){ printf("Create dis_v.txt file error!"); system("pause"); return 1; } fprintf(fpv,"%d\n",FILENUM); printf("Processing data file ...\n",i+1); for(i=0;i<FILENUM;i++) //按顺序打开文件,统计单词 { filedic[i].clear(); sprintf(name,"file%d.txt",i+1); printf("%d ",i+1); fp=fopen(name,"r"); if(fp == NULL){ printf("Processing data file %d error!",i+1); system("pause"); continue; } filewordnum[i]=0; while(fscanf(fp,"%s",word) != EOF) //循环查找该文件内所有单词 { if(dic[word]) { if(filedic[i][word]) filedic[i][word]++; else filedic[i][word]=1; } else{ filedic[i][word]=0; } filewordnum[i]++; } fclose(fp); fprintf(fpv,"%d\n",wordnum); string key; int thisfilewordnum; thisfilewordnum=filewordnum[i]; for(j=0;j<wordnum;j++) { key=diclist[j]; fprintf(fpv,"%.8lf ",(double)filedic[i][key]/thisfilewordnum); } fprintf(fpv,"\n"); } fclose(fpv); printf("\n"); system("del file*.txt"); return 0; } int main(int argc, char* argv[]) { FILE *fp; int x,y,i,j; printf("共%d篇文章需要分类 waiting...\n",FILENUM); if(processingdata()) //generate dis_v.txt return 1; fp=fopen("T_eigenvector.txt","r"); if(fp==NULL){ printf("Can't open file T_eigenvector.txt!\n"); system("pause"); return 1; } fscanf(fp,"%d %d",&x,&y); MATRIX(EV,x,y); for(i=0;i<y;i++) for(j=0;j<x;j++) fscanf(fp,"%lf",&EV.p[i][j]); fclose(fp); fp=fopen("T_B.txt","r"); if(fp==NULL){ printf("Can't open file T_B.txt!\n"); system("pause"); return 1; } fscanf(fp,"%d %d",&x,&y); MATRIX(TB,x,y); for(i=0;i<y;i++) for(j=0;j<x;j++) fscanf(fp,"%lf",&TB.p[i][j]); fclose(fp); fp=fopen("dis_v.txt","r"); if(fp==NULL){ printf("Can't open file dis_v.txt!\n"); system("pause"); return 1; } fscanf(fp,"%d",&x); MATRIX(X,1,TB.x); MATRIX(XX,X.x,TB.y); MATRIX(DIS,FILENUM,FILENUM); printf("计算距离 waiting...\n",FILENUM); for(i=0;i<FILENUM;i++) { printf("%d ",i); fscanf(fp,"%d",&x); for(j=0;j<x;j++) { fscanf(fp,"%lf",&X.p[j][0]); } MUL(TB,X,&XX); for(j=0;j<FILENUM;j++) { DIS.p[i][j]=SIM(XX,EV,0,j); } } fclose(fp); system("del dis_v.txt"); disprint("分类表.txt",DIS); FREE(DIS); FREE(EV); FREE(TB); FREE(X); FREE(XX); return 0; } |
这样通过上面的程序我们就实现了最后的分类部分。下面是一次试验结果R=80 IterateNum=80。
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
50 50 file 1.txt |环境| 教育 经济 政治 体育 file 2.txt |环境| 教育 经济 政治 体育 file 3.txt |环境| 教育 经济 政治 体育 file 4.txt |环境| 教育 经济 政治 体育 file 5.txt |环境| 教育 经济 政治 体育 file 6.txt |环境| 教育 经济 政治 体育 file 7.txt |环境| 教育 经济 政治 体育 file 8.txt |环境| 教育 经济 政治 体育 file 9.txt |环境| 教育 经济 政治 体育 file10.txt |环境| 教育 经济 政治 体育 file11.txt 环境 |教育| 经济 政治 体育 file12.txt 环境 |教育| 经济 政治 体育 file13.txt 环境 |教育| 经济 政治 体育 file14.txt 环境 |教育| 经济 政治 体育 file15.txt 环境 |教育| 经济 政治 体育 file16.txt 环境 |教育| 经济 政治 体育 file17.txt 环境 |教育| 经济 政治 体育 file18.txt 环境 |教育| 经济 政治 体育 file19.txt 环境 |教育| 经济 政治 体育 file20.txt 环境 |教育| 经济 政治 体育 file21.txt 环境 教育 |经济| 政治 体育 file22.txt 环境 教育 |经济| 政治 体育 file23.txt 环境 教育 |经济| 政治 体育 file24.txt 环境 教育 |经济| 政治 体育 file25.txt 环境 教育 |经济| 政治 体育 file26.txt 环境 教育 经济 |政治| 体育 <-错误 file27.txt 环境 教育 |经济| 政治 体育 file28.txt 环境 教育 |经济| 政治 体育 file29.txt 环境 教育 |经济| 政治 体育 file30.txt 环境 教育 |经济| 政治 体育 file31.txt 环境 教育 |经济| 政治 体育 file32.txt 环境 教育 经济 政治 |体育| file33.txt 环境 教育 经济 政治 |体育| file34.txt 环境 教育 经济 政治 |体育| file35.txt 环境 |教育| 经济 政治 体育 <-错误 file36.txt 环境 教育 经济 政治 |体育| file37.txt 环境 教育 经济 政治 |体育| file38.txt 环境 教育 经济 政治 |体育| file39.txt 环境 教育 经济 政治 |体育| file40.txt 环境 教育 经济 政治 |体育| file41.txt 环境 教育 经济 |政治| 体育 file42.txt 环境 教育 经济 |政治| 体育 file43.txt 环境 教育 经济 |政治| 体育 file44.txt 环境 教育 经济 |政治| 体育 file45.txt 环境 教育 经济 |政治| 体育 file46.txt 环境 教育 经济 |政治| 体育 file47.txt 环境 教育 经济 |政治| 体育 file48.txt 环境 教育 经济 |政治| 体育 file49.txt 环境 教育 经济 |政治| 体育 file50.txt 环境 教育 经济 |政治| 体育 |
可以看到有2篇分类错误。而经济类文章被分入政治类,体育类被分入教育类,也是可以理解的。这些话题有很多重合的地方。