k-means算法实现

1、#include ITokeniser .h #include class TFIDFMeasure private : StrVec _docs; /文档集合，每一行字符串代表一份文档 int _numDocs; / 文档数目 int _numTerms; / 单词数目 StrVec _terms; / 单词集合 Int 2DVec _termFreq; /每个单词出现在每份文档中的频率 Double 2DVec _termWeight; /每个单词在每份文档的权重 Int Vec _maxTermFreq; /记录每一份文档的最大词频 Int Vec _docFreq; /出现单词的文档频

2、率 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 Generate

3、TermFrequency(); 计算词频 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); / 计算词语

4、在指定文档中的权重 值 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 #in

5、clude using 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* tokenise r) _docs=documents; _numDocs=docu

6、ments.size(); _tokenizer = tokeniser; this -Init(); void TFIDFMeasure:GenerateTerms( const StrVec& docs,StrVec& terms) for (int i= 0; i Partition(docsi,words); / 分词 for ( int j= 0 ; j GenerateTerms (_docs,_terms); / 分出所有词项 this -_numTerms=_terms.size() ; / 所有文档中的词项数目 /准备好存储空间 _maxTermFreq.re

7、size(_numDocs); _docFreq.resize(_numTerms); _termFreq.resize(_numTerms); _termWeight.resize(_numTerms); for (int i= 0; i GenerateTermFrequency (); / 计算单词频率 this -GenerateTermWeight(); / 计算单词权重 void TFIDFMeasure:GetWordFrequency( string & input,map& freq) (/计算单词频率 transform(input.begin(),inpu

8、t.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:GetT

9、ermVector( int doc,DoubleVec& vec) ( vec.resize( this -_numTerms); for (int i= 0; i _numTerms; i+) veci=_termWeightidoc; /第i个单词在文档 doc中的权重 /用于字符串比较的仿函数 class WordComp ( public : WordComp( string & sWord) : word(sWord) ( bool operator () ( const string & lhs) return pare(word)= private :

10、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!=_wordsInd

11、ex.end() ( return pos-second; else return - 1 ; void TFIDFMeasure:GenerateTermFrequency() (计算每个单词在每份文档出现的频率 for (int i= 0; i _numDocs ; i+) ( string curDoc=_docsi; /当前待处理的文档 map freq; this -GetWordFrequency(curDoc,freq); map:iterator iter; _maxTermFreqi=numeric_limits:min(); for (iter = freq.begin()

12、;iter!=freq.end();+iter) ( string word=iter-first; int wordFreq=iter-second ; int termIndex=GetTermIndex(word); / 单词下标 if(termIndex = - 1) continue ; _termFreq termIndexi=wordFreq; 单词在第i份文档中出现的频率 _docFreqtermIndex+; /出现第termIndex 单词的文档频率加 if (wordFreq _maxTermFreqi) _maxTermFreqi=wordFreq; / 记录 第i份文

13、档中的最大词频 void TFIDFMeasure:GenerateTermWeight() (计算每个单词在每份文档中的权重 for (int i= 0; i _numTerms; i+) ( for ( int j= 0 ; j _numDocs ; j+) 0; ( _termWeightij=ComputeTermWeight (i, j); double TFIDFMeasure:GetTermFrequency( int term, int doc) ( int freq=_termFreq termdoc; / 词频 int maxfreq=_maxTermFreqdoc; re

14、turn ( ( 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=_docFreqterm; /包含单

15、词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:Tokenis

16、er( void ) ( Tokeniser:Tokeniser( void ) ( void Tokeniser:Partition( string input,StrVec& retWords) 分词算法，input为输入串，retWords 为处理后所分开的单词，这里就简单化处理了， 以 空格符为分隔符进行分词 transform(input.begin(),input.end(),input.begin(),tolower); string :iterator pos = input.begin(); StopWordsHandler stopHandler; do strin

17、g temp; pos = find(input.begin(),input.end(), copy(input.begin(),pos,back_inserter(temp); );/找到分隔符 if (!stopHandler .IsStopWord(temp) /不是停用词则保存 retWords.push_back(temp); / 保存分出的单词 if (pos=input.end() /最后一个单词了 break ; else input.erase(input.begin(),+pos); while (pos!=input.end(); 停用词处理 去掉文档中无意思的词语也是必

18、须的一项工作 ，这里简单的定义了一些常见的停用词，并根 据这些常用停用词在分词时进行判断 #include StopWordsHandler .h string stopWordsList = 的,我们,要,自己,之,将,，,，”,”(”,”), 后,应,到,某”，”后”， 个”，”是,位,新, - ,两”，”在,中”,”或,有,更,好,; /常用停用词 int stopWordsLen = sizeof (stopWordsList)/ sizeof (stopWordsList 0); StopWordsHandler:StopWordsHandler( void ) for (int i

19、= 0;istopWordsLen;+i) stopWords.push_back(stopWordsListi); 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 K- -

20、Means Means 算法 k k- -m eansm eans 算法接受输入量 k k ；然后将 n n 个数据对象划分为 k k 个聚类以便使得所获得的 聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用 各聚类中对象的均值所获得一个 中心对象（引力中心）来进行计算的。 k k- - meansmeans 算法的工作过程说明如下：首先从 n n 个数据对象任意选择 k k 个对象作为初始 聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们 分配给与其最相似的（聚类中心所代表的）聚类；然 后再计算每个所获新聚类的聚类中心（

21、该 聚类中所有对象的均值） ；不断重复这一过程直到标准测度函数开始收敛为止。 一般都采用均方 差作为标准测度函数.k.k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能 的分开。 #include Common.h class Cluster; class KMeans public : vector _clusters; / 聚类 private : int _coordCount; / 数据的数量 Double2DVec _coordinates; 原始数据 int _k; /聚类的数量 /定义一个变量用于记录和跟踪每个资料点属于哪个群聚类 / _clusterAssign

22、mentsj=i; 表示第j个资料点对象属于第 i个群聚类 IntVec _clusterAssignments; /定义一个变量用于记录和跟踪每个资料点离聚类最近 IntVec _nearestCluster; /定义一个变量，来表示资料点到中心点的距离 /其中一_distanceCacheij 表示第i个资料点到第j Double2DVec _distanceCache; void InitRandom(); static double getDistance( const DoubleVec& coord, r); int NearestCluster( int ndx); pu

23、blic : KMeans(Double2DVec& data, int K); void Start(); public : KMeans( void ); ;个群聚对象中心点的距离; const DoubleVec& cente K K- -MeansMeans算法具体实现： #include KMeans.h #include #include Cluster .h #include TermVector .h #include KMeans:KMeans(Double2DVec &data, int K) int i; this -_coordinates.re

24、size(data.size(); for (i= 0;idata.s ize();+i) copy(datai.begin(),datai.end(),back_inserter(_coordinatesi); _coordCount = data.size(); _k = K; _clusters.resize(K); _clusterAssignments.resize(_coordCount); _nearestCluster .resize(_coordCount); _distanceCache.resize(_coordCount); for (i= 0;i_coordCount

25、;+i) _distanceCachei.resize(_coordCount); InitRandom(); void KMeans:InitRandom() srand(unsigned(time(NULL); for (int i = 0; i _k; i+) int temp = rand()%(_coordCount); / 产生随机数 _clusterAssignmentstemp = i; /记录第 temp 个资料属于第 i个聚类 _clustersi = new Cluster(temp,_coordinatestemp); void KMeans:Start() int iter = 0 ,i,j; while (true ) cout Iteration iter+ endl; /1、重新计算每个聚类的均值 for (i = 0; i UpdateMean(_coordinates); /2、计算每个数据和每个聚类中心的距离 for (i = 0; i _coordCount; i+) ( for (j = 0; j Mean); _distanceCacheij = dist; /3、计算每个数据离哪个聚类最近 for (i = 0; i NearestCluster(i); /4、