文本分类、聚类算法中，最常见的障碍就是高维矩阵。对于具有一定规模的文本聚类很轻易会遇到维度成千上万的矩阵，如果按照常规计算方法，耗时将不可估量。而非负矩阵分解则是非常好的降维理论，利用非负矩阵分解我们可以将高维矩阵分解为可接受的小维矩阵，并保持其原矩阵的特征。这篇文章将介绍如何利用非负矩阵分解做文本聚类。非负矩阵分解英文全称是 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

词1 0.3 0.3 0.0

词2 0.7 0.1 0.8

词3 0.0 0.6 0.2

这里面的每个数据都是TF*IDF得到的。好下面我吧第一部分求VSM的代码贴一下：

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;

}

截图显示该程序运行结果如下：

nmf1

经过这个程序会把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. 初始化矩阵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 的代码：

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大类文本的相似度，越大的相似度越高。

下面写出代码:

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。

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篇分类错误。而经济类文章被分入政治类，体育类被分入教育类，也是可以理解的。这些话题有很多重合的地方。

Lianxu

I make Mac software

非负矩阵分解的文本聚类

第一：建立VSM

第二：VSM做NMF分解

第三：文本文类