基于K-Means的文本聚类算法TF-IDF（term frequency–inverse document frequency）这是一种用于信息检索的一种常用加权技术。
它是一种统计方法，用以评估一个字词对于一个文件集或一个语料库中的其中一份文件的重要程度。
字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。
假如一篇文件的总词语数是100个，而词语“母牛”出现了3次，那么“母牛”一词在该文件中的词频就是 0.03 (3/100)。
一个计算文件频率 (DF) 的方法是测定有多少份文件出现过“母牛”一词，然后除以文件集里包含的文件总数。
所以，如果“母牛”一词在1,000份文件出现过，而文件总数是 10,000,000份的话，其文件频率就是 0.0001 (1000/10,000,000)。
最后，TF-IDF分数就可以由计算词频除以文件频率而得到。
以上面的例子来说，“母牛”一词在该文件集的TF- IDF分数会是 300 (0.03/0.0001)。
这条公式的另一个形式是将文件频率取对数。
具体的计算原理，请参考维基百科tf–idf条目。
下面简单介绍下基本的计算步骤：1,文档预处理:1）文档分词；2）移除停用词；3）单词正规化处理2，分出的单词就作为索引项（或单词表），它们代表的就是向量空间的项向量3，计算项权值：这包括要计算1）词频 ; 2)倒排文件频率；3）TF-IDF权值4,计算文档之间的相似度，一般用余弦相似度(cosine similarity)一同使用于向量空间模型中，用以判断两份文件之间的相似性#include "ITokeniser.h"#includeclass TFIDFMeasure{private:StrVec _docs;//文档集合，每一行字符串代表一份文档int _numDocs;//文档数目int _numTerms;//单词数目StrVec _terms;//单词集合Int2DVec _termFreq;//每个单词出现在每份文档中的频率Double2DVec _termWeight;//每个单词在每份文档的权重IntVec _maxTermFreq;//记录每一份文档的最大词频IntVec _docFreq;//出现单词的文档频率ITokeniser* _tokenizer;//分词器map _wordsIndex;//单词映射表，保存每一个单词及其对应的下标public:TFIDFMeasure(const StrVec& documents,ITokeniser* tokeniser);public:~TFIDFMeasure(void);protected:void Init();//初始化TF-IDF计算器void GenerateTerms(const StrVec& docs,StrVec& terms);//分词处理void GenerateTermFrequency();//计算词频void GenerateTermWeight();//计算词的权重void GetWordFrequency(string& input,map& freq); //实际统计词频函数int CountWords(string& word, const StrVec& words);//统计词数int GetTermIndex(const string& term);//查询词语对应的下标double ComputeTermWeight(int term, int doc);//计算词语在指定文档中的权重值double GetTermFrequency(int term, int doc);//获取词语在指定文档的词频double GetInverseDocumentFrequency(int term);//计算倒排文件频率public:inline int NumTerms()const{return this->_numTerms;}void GetTermVector(int doc,DoubleVec& vec);//获取项向量};TF-IDF具体实现代码#include "TFIDFMeasure.h"#include#includeusing namespace std;TFIDFMeasure::~TFIDFMeasure(void){//销毁分词器if (this->_tokenizer!=NULL){delete _tokenizer;_tokenizer = NULL;}//清空数据_docs.clear();_terms.clear();_wordsIndex.clear();}TFIDFMeasure::TFIDFMeasure(const StrVec& documents,ITokeniser* tokeniser) {_docs=documents;_numDocs=documents.size();_tokenizer = tokeniser;this->Init();}void TFIDFMeasure::GenerateTerms(const StrVec& docs,StrVec& terms) {for (int i=0; i{StrVec words;_tokenizer->Partition(docs[i],words);//分词for (int j=0; j{//不在单词表中，则加入if (find(terms.begin(),terms.end(),words[j])==terms.end()){terms.push_back(words[j]);}}}}void TFIDFMeasure::Init(){//初始化this->GenerateTerms (_docs,_terms);//分出所有词项this->_numTerms=_terms.size() ;//所有文档中的词项数目//准备好存储空间_maxTermFreq.resize(_numDocs);_docFreq.resize(_numTerms);_termFreq.resize(_numTerms);_termWeight.resize(_numTerms);for(int i=0; i{_termWeight[i].resize(_numDocs);_termFreq[i].resize(_numDocs) ;_wordsIndex[_terms[i]] = i;//将单词放入单词映射表中}this->GenerateTermFrequency ();//计算单词频率this->GenerateTermWeight();//计算单词权重}void TFIDFMeasure::GetWordFrequency(string& input,map& freq){//计算单词频率transform(input.begin(),input.end(),input.begin(),tolower);StrVec temp;this->_tokenizer->Partition(input,temp);//对当前文档分词unique(temp.begin(),temp.end());StrVec::iterator iter;for (iter=temp.begin();iter!=temp.end();++iter){int count = CountWords(*iter, temp);//计算单词在文档中出现的次数 freq[*iter] = count;//保存单词频率}}void TFIDFMeasure::GetTermVector(int doc,DoubleVec& vec){vec.resize(this->_numTerms);for (int i=0; i _numTerms; i++)vec[i]=_termWeight[i][doc];//第i个单词在文档doc中的权重}//用于字符串比较的仿函数class WordComp{public:WordComp(string& sWord) : word(sWord){}bool operator() (const string& lhs){return pare(word)==0;}private:string word;};int TFIDFMeasure::CountWords(string& word, const StrVec& words) {int nCount = 0;nCount = count_if(words.begin(),words.end(),WordComp(word));return nCount;}int TFIDFMeasure::GetTermIndex(const string& term) {map::iterator pos = _wordsIndex.find(term);if (pos!=_wordsIndex.end()){return pos->second;}elsereturn -1;}void TFIDFMeasure::GenerateTermFrequency(){//计算每个单词在每份文档出现的频率for(int i=0; i{string curDoc=_docs[i];//当前待处理的文档map freq;this->GetWordFrequency(curDoc,freq);map::iterator iter;_maxTermFreq[i]=numeric_limits::min();for (iter = freq.begin();iter!=freq.end();++iter) {string word=iter->first;int wordFreq=iter->second ;int termIndex=GetTermIndex(word);//单词下标if(termIndex == -1)continue;_termFreq [termIndex][i]=wordFreq;//单词在第i份文档中出现的频率_docFreq[termIndex]++;//出现第termIndex单词的文档频率加if (wordFreq > _maxTermFreq[i]) _maxTermFreq[i]=wordFreq;//记录第i份文档中的最大词频}}}void TFIDFMeasure::GenerateTermWeight(){//计算每个单词在每份文档中的权重for(int i=0; i{for(int j=0; j{_termWeight[i][j]=ComputeTermWeight (i, j);}}}double TFIDFMeasure::GetTermFrequency(int term, int doc){int freq=_termFreq [term][doc];//词频int maxfreq=_maxTermFreq[doc];return ( (float) freq/(float)maxfreq );double TFIDFMeasure::ComputeTermWeight(int term, int doc){//计算单词在文档中的权重float tf=GetTermFrequency (term, doc);float idf=GetInverseDocumentFrequency(term);return tf * idf;}double TFIDFMeasure::GetInverseDocumentFrequency(int term){int df=_docFreq[term];//包含单词term的文档数目return log((float) (_numDocs) / (float) df );}分词算法为了便于使用不同的分词算法，我们定义一个抽象的分词算法接口，具体的分词算法由用户自行实现class ITokeniser{public:virtual void Partition(string input,StrVec& retWords)=0;//分词算法};这里只实现了一个最简单的空格符分词算法：#include "Tokeniser.h"#include "StopWordsHandler.h"Tokeniser::Tokeniser(void){Tokeniser::~Tokeniser(void){}void Tokeniser::Partition(string input,StrVec& retWords){//分词算法，input为输入串,retWords为处理后所分开的单词,这里就简单化处理了，以空格符为分隔符进行分词transform(input.begin(),input.end(),input.begin(),tolower);string::iterator start = input.begin();string::iterator end = input.end();StopWordsHandler stopHandler;do{string temp;pos = find(start,input.end(),' ');//找到分隔符copy(start,end,back_inserter(temp));if (!stopHandler.IsStopWord(temp)){//不是停用词则保存retWords.push_back(temp);//保存分出的单词}if (end == input.end()){//最后一个单词了break;}start = ++end;} while (end != input.end());}停用词处理去掉文档中无意思的词语也是必须的一项工作,这里简单的定义了一些常见的停用词，并根据这些常用停用词在分词时进行判断#include "StopWordsHandler.h"string stopWordsList[] ={"的", "我们","要","自己","之","将","“","”","，","（","）","后","应","到","某","后","个","是","位","新","一","两","在","中","或","有","更","好",""};//常用停用词int stopWordsLen = sizeof(stopWordsList)/sizeof(stopWordsList[0]);StopWordsHandler::StopWordsHandler(void){for (int i=0;i{stopWords.push_back(stopWordsList[i]);}}StopWordsHandler::~StopWordsHandler(void){}bool StopWordsHandler::IsStopWord(string& str){//是否是停用词transform(str.begin(),str.end(),str.begin(),tolower);//确保小写化return find(stopWords.begin(),stopWords.end(),str)!=stopWords.end();}K-Means算法k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。
