k-means算法实现

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

2、docFreq; /出现单词的文档频率 ITokeniser* _tokenizer; / 分词器map< string ,int > _wordsIndex;/单词映射表，保存每一个单词及其对应的下标public :TFIDFMeasure( const StrVec& documents,ITokeniser* tokeniser); public :TFIDFMeasure( void ); protected :void Init(); / 初始化 TF-IDF 计算器void GenerateTerms( const StrVec& docs,StrVec

3、& terms);分词处理void GenerateTermFrequency(); 计算词频void GenerateTermWeight(); / 计算词的权重void GetWordFrequency( string & input,map< string ,int >& freq); /实际统计词 频函数int CountWords( string & word, const StrVec& words);统计词数int GetTermIndex( const string & term); /查询词语对应的下标double

4、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

5、具体实现代码:#include "TFIDFMeasure.h"#include <limits>#include <cmath> using namespace std; TFIDFMeasure:TFIDFMeasure( void ) 销毁分词器if (this ->_tokenizer!=NULL)delete _tokenizer;_tokenizer = NULL;/清空数据_docs.clear();_terms.clear();_wordsIndex.clear();TFIDFMeasure:TFIDFMeasure( cons

6、t StrVec& documents,ITokeniser* tokenise r) _docs=documents;_numDocs=documents.size();_tokenizer = tokeniser; this ->Init();void TFIDFMeasure:GenerateTerms( const StrVec& docs,StrVec& terms)for (int i= 0; i < docs.size() ; i+)StrVec words;_tokenizer->Partition(docsi,words);/ 分词f

7、or ( int j= 0 ; j < words.size(); j+)/不在单词表中，则加入if (find(terms.begin(),terms.end(),wordsj)=terms.end()terms.push_back(wordsj); void TFIDFMeasure:Init()(/初始化this ->GenerateTerms (_docs,_terms);/ 分出所有词项this ->_numTerms=_terms.size() ;/ 所有文档中的词项数目/准备好存储空间_maxTermFreq.resize(_numDocs);_docFreq.

8、resize(_numTerms);_termFreq.resize(_numTerms);_termWeight.resize(_numTerms);for (int i= 0; i < _terms.size() ; i+)(_termWeighti.resize(_numDocs);_termFreqi.resize(_numDocs) ;_wordsIndex_termsi = i;/将单词放入单词映射表中this ->GenerateTermFrequency ();/ 计算单词频率this ->GenerateTermWeight(); / 计算单词权重void

9、TFIDFMeasure:GetWordFrequency( string & input,map< string ,int >& 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!

10、=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 < this ->_numTerms; i+)veci=_termWeightidoc;/第i个单词在文档 doc中的权重/用于字符串比较的仿函数 class WordCom

11、p(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

12、 TFIDFMeasure:GetTermIndex( const string & term)(map< string ,int >:iterator pos = _wordsIndex.find(term);if (pos!=_wordsIndex.end()(return pos->second;elsereturn - 1 ;void TFIDFMeasure:GenerateTermFrequency()(计算每个单词在每份文档出现的频率for (int i= 0; i < _numDocs ; i+)(string curDoc=_docsi; /当

13、前待处理的文档map< string , int > freq;this ->GetWordFrequency(curDoc,freq);map< string , int >:iterator iter;_maxTermFreqi=numeric_limits<int >:min();for (iter = freq.begin();iter!=freq.end();+iter)(string word=iter->first;int wordFreq=iter->second ;int termIndex=GetTermIndex(wo

14、rd);/ 单词下标if(termIndex = -1)continue ;_termFreq termIndexi=wordFreq;单词在第i份文档中出现的频率_docFreqtermIndex+;/出现第termIndex单词的文档频率加if (wordFreq > _maxTermFreqi) _maxTermFreqi=wordFreq;/ 记录第i份文档中的最大词频void TFIDFMeasure:GenerateTermWeight()(计算每个单词在每份文档中的权重for (int i= 0; i < _numTerms; i+)(for ( int j= 0 ;

15、 j < _numDocs ; j+)(_termWeightij=ComputeTermWeight (i, j);double TFIDFMeasure:GetTermFrequency( int term, int doc)(int freq=_termFreq termdoc;/ 词频int maxfreq=_maxTermFreqdoc;return ( ( float ) freq/( float )maxfreq );double TFIDFMeasure:ComputeTermWeight(int term, int doc)(计算单词在文档中的权重float tf=Ge

16、tTermFrequency (term, doc);float idf=GetInverseDocumentFrequency(term);return tf * idf;double TFIDFMeasure:GetInverseDocumentFrequency(int term)(int df=_docFreqterm; /包含单词term 的文档数目return log( float ) (_numDocs) / ( float ) df );分词算法为了便于使用不同的分词算法，我们定义一个抽象的分词算法接口，具体的分词算法由用户自行实现class ITokeniser(public

17、 :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为处

18、理后所分开的单词，这里就简单化处理了，以空格符为分隔符进行分词transform(input.begin(),input.end(),input.begin(),tolower);string :iterator pos = input.begin();StopWordsHandler stopHandler; do);/找到分隔符string temp;pos = find(input.begin(),input.end(),copy(input.begin(),pos,back_inserter(temp);if (!stopHandler .IsStopWord(temp) /不是停用词

19、则保存retWords.push_back(temp);/ 保存分出的单词if (pos=input.end() /最后一个单词了break ;elseinput.erase(input.begin(),+pos); while (pos!=input.end();停用词处理去掉文档中无意思的词语也是必须的一项工作，这里简单的定义了一些常见的停用词，并根据这些常用停用词在分词时进行判断#include "StopWordsHandler .h"string stopWordsList ="的","我们","要",&

20、quot;自己","之","将","，","，”,”(”,”)","后","应","到","某”，”后”，"个”，”是","位","新","两”，”在","中”,”或","有","更","好","" /常用停用词int stopWordsLen = sizeo

21、f (stopWordsList)/ sizeof (stopWordsList 0);StopWordsHandler:StopWordsHandler(void )for (int i= 0;i<stopWordsLen;+i)stopWords.push_back(stopWordsListi);StopWordsHandler:StopWordsHandler(void )bool StopWordsHandler:IsStopWord( string & str)/是否是停用词transform(str .begin(),str .end(),str .begin(),

22、tolower); / 确保小写化return find(stopWords.begin(),stopWords.end(),str)!=stopWords.end();K-Means 算法k-m eans算法接受输入量k ；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用 各聚类中对象的均值所获得一个中心对象"（引力中心）来进行计算的。k- means算法的工作过程说明如下：首先从 n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它

23、们 分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数.k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能 的分开。#include "Common.h"class Cluster;class KMeanspublic :vector<Cluster*> _clusters;/ 聚类private :int _coordCount; / 数据的数量Double2DVec _coordinates;原始数据int _k

24、; /聚类的数量/定义一个变量用于记录和跟踪每个资料点属于哪个群聚类/ _clusterAssignmentsj=i;表示第j个资料点对象属于第i个群聚类IntVec _clusterAssignments;/定义一个变量用于记录和跟踪每个资料点离聚类最近IntVec _nearestCluster;/定义一个变量，来表示资料点到中心点的距离个群聚对象中心点的距离;const DoubleVec& cente/其中一_distanceCacheij表示第i个资料点到第jDouble2DVec _distanceCache;void InitRandom();static double

25、getDistance( const DoubleVec& coord, r);int NearestCluster( int ndx);public :KMeans(Double2DVec& data, int K);void Start();public :KMeans( void );K-Means算法具体实现：#include "KMeans.h"#include <time.h>#include "Cluster .h"#include "TermVector .h"#include <li

26、mits>KMeans:KMeans(Double2DVec &data,int K)int i;this ->_coordinates.resize(data.size();for (i= 0;i<data.s ize();+i)copy(datai.begin(),datai.end(),back_inserter(_coordinatesi);_coordCount = data.size();_k = K;_clusters.resize(K);_clusterAssignments.resize(_coordCount);_nearestCluster .r

27、esize(_coordCount);_distanceCache.resize(_coordCount);for (i= 0;i<_coordCount;+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个聚

28、类_clustersi = new Cluster(temp,_coordinatestemp);void KMeans:Start()int iter =0 ,i,j;while (true )cout<< "Iteration "<<iter+<<" " <<endl;/1、重新计算每个聚类的均值for (i = 0; i < _k; i+)(_clustersi->UpdateMean(_coordinates);/2、计算每个数据和每个聚类中心的距离for (i = 0; i < _coordCount; i+)(for (j = 0; j < _k; j+)(double dist = getDistance(_coordinatesi, _clustersj->Mean);_distanceCacheij = dist;/3、计算每个数据离哪个聚类最近for (i = 0; i < _coordCount; i+)(_nearestClusteri =this ->NearestCluster(i);/4