k-means算法实现

1、#include "ITokeniser.h"#include <map>class TFIDFMeasureprivate:    StrVec _docs;/文档集合，每一行字符串代表一份文档    int _numDocs;/文档数目    int _numTerms;/单词数目    StrVec _terms;/单词集合

2、60;   Int 2DVec _termFreq;/每个单词出现在每份文档中的频率    Double 2DVec  _termWeight;/每个单词在每份文档的权重    Int Vec _maxTermFreq;/记录每一份文档的最大词频    Int Vec _docFreq;/出现单词的文档频率    ITokeniser*  _tok

3、enizer;/分词器    map<string,int> _wordsIndex;/单词映射表，保存每一个单词及其对应的下标public:    TFIDFMeasure(const StrVec& documents,ITokeniser* tokeniser);public:    TFIDFMeasure(void);protected:    void I

4、nit();/初始化TF-IDF计算器    void GenerateTerms(const StrVec& docs,StrVec& terms);/分词处理    void GenerateTermFrequency();/计算词频    void GenerateTermWeight();/计算词的权重    void GetWordFrequ

5、ency(string& input,map<string,int>& freq); /实际统计词频函数    int CountWords(string& word, const StrVec& words);/统计词数    int GetTermIndex(const string& term);/查询词语对应的下标   

6、; double ComputeTermWeight(int term, int doc);/计算词语在指定文档中的权重值    double GetTermFrequency(int term, int doc);/获取词语在指定文档的词频    double GetInverseDocumentFrequency(int term);/计算倒排文件频率public:   &

7、#160;inline int NumTerms()const            return this->_numTerms;        void  GetTermVector(int doc,DoubleVec& vec);/获取项向量;TF-IDF具体实现代码：#include "

8、TFIDFMeasure.h"#include <limits>#include <cmath>using namespace std;TFIDFMeasure:TFIDFMeasure(void)    /销毁分词器    if (this->_tokenizer!=NULL)            del

9、ete _tokenizer;        _tokenizer = NULL;        /清空数据    _docs.clear();    _terms.clear();    _wordsIndex.clear();TFIDFMeasure:TFIDFMeasure(cons

10、t StrVec& documents,ITokeniser* tokeniser)    _docs=documents;    _numDocs=documents.size();    _tokenizer = tokeniser;    this->Init();void TFIDFMeasure:GenerateTerms(const StrV

11、ec& docs,StrVec& terms)    for (int i=0; i < docs.size()  i+)            StrVec words;        _tokenizer->Partition(

12、docsi,words);/分词                for (int j=0; j < words.size(); j+)                    

13、/不在单词表中，则加入            if (find(terms.begin(),terms.end(),wordsj)=terms.end()                          &#

14、160; terms.push_back(wordsj);                        void TFIDFMeasure:Init()/初始化    this->GenerateTerms (_docs,_terms);/分出所有词项  

15、60; this->_numTerms=_terms.size() /所有文档中的词项数目    /准备好存储空间    _maxTermFreq.resize(_numDocs);    _docFreq.resize(_numTerms);    _termFreq.resize(_numTerms);    _termWeight.resize(_numTerms)

16、;    for(int i=0; i < _terms.size()  i+)                        _termWeighti.resize(_numDocs);     

17、60;  _termFreqi.resize(_numDocs)         _wordsIndex_termsi = i;/将单词放入单词映射表中            this->GenerateTermFrequency ();/计算单词频率    this->Generate

18、TermWeight();/计算单词权重void TFIDFMeasure:GetWordFrequency(string& input,map<string,int>& freq)/计算单词频率    transform(input.begin(),input.end(),input.begin(),tolower);    StrVec temp;    this->_tokenizer->P

19、artition(input,temp);/对当前文档分词    unique(temp.begin(),temp.end();    StrVec:iterator iter;    for (iter=temp.begin();iter!=temp.end();+iter)            int count 

20、;= CountWords(*iter, temp);/计算单词在文档中出现的次数        freq*iter = count;/保存单词频率        void  TFIDFMeasure:GetTermVector(int doc,DoubleVec& vec)    vec.resize(thi

21、s->_numTerms);     for (int i=0; i < this->_numTerms; i+)                              

22、;                      veci=_termWeightidoc;/第i个单词在文档doc中的权重/用于字符串比较的仿函数class WordComp public:    WordComp(string& sWord) : word(sWord) 

23、                 bool operator() (const string& lhs)                 return pare(word)=0;  

24、           private:    string word;        int TFIDFMeasure:CountWords(string& word, const StrVec& words)    int nCount

25、60;= 0;    nCount = count_if(words.begin(),words.end(),WordComp(word);    return nCount;    int TFIDFMeasure:GetTermIndex(const string& term)    map<string,int>:iterator 

26、pos = _wordsIndex.find(term);    if (pos!=_wordsIndex.end()            return pos->second;        else        return&

27、#160;-1;void TFIDFMeasure:GenerateTermFrequency()/计算每个单词在每份文档出现的频率    for(int i=0; i < _numDocs   i+)                      

28、0;                     string curDoc=_docsi;/当前待处理的文档        map<string,int> freq;        this->

29、GetWordFrequency(curDoc,freq);        map<string,int>:iterator iter;        _maxTermFreqi=numeric_limits<int>:min();        for (iter = freq.begin()

30、;iter!=freq.end();+iter)                    string word=iter->first;            int wordFreq=iter->second   &

31、#160;         int termIndex=GetTermIndex(word);/单词下标            if(termIndex = -1)                co

32、ntinue;            _termFreq termIndexi=wordFreq;/单词在第i份文档中出现的频率            _docFreqtermIndex+;/出现第termIndex单词的文档频率加          

33、;  if (wordFreq > _maxTermFreqi) _maxTermFreqi=wordFreq;/记录第i份文档中的最大词频                                void&

34、#160;TFIDFMeasure:GenerateTermWeight()/计算每个单词在每份文档中的权重                for(int i=0; i < _numTerms; i+)            for(int j=0;&#

35、160;j < _numDocs  j+)                    _termWeightij=ComputeTermWeight (i, j);              

36、60;     double TFIDFMeasure:GetTermFrequency(int term, int doc)                int freq=_termFreq termdoc;/词频    int maxfreq=_maxTermFreqdoc

37、;                return ( (float) freq/(float)maxfreq );double TFIDFMeasure:ComputeTermWeight(int term, int doc)/计算单词在文档中的权重    float tf=GetTermFrequency&#

38、160;(term, doc);    float idf=GetInverseDocumentFrequency(term);    return tf * idf;double TFIDFMeasure:GetInverseDocumentFrequency(int term)    int df=_docFreqterm;/包含单词term的文档数目   

39、60;return log(float) (_numDocs) / (float) df );分词算法      为了便于使用不同的分词算法，我们定义一个抽象的分词算法接口，具体的分词算法由用户自行实现class ITokeniserpublic:    virtual void Partition(string input,StrVec& retWords)=0;/分词算法; 

40、 这里只实现了一个最简单的空格符分词算法：#include "Tokeniser.h"#include "StopWordsHandler.h"Tokeniser:Tokeniser(void)Tokeniser:Tokeniser(void)void Tokeniser:Partition(string input,StrVec& retWords)/分词算法，input为输入串,retWords为处理后所分开的单词,这里就简单化处理了，以空格符为分隔符进行分词   

41、; transform(input.begin(),input.end(),input.begin(),tolower);    string:iterator pos = input.begin();    StopWordsHandler stopHandler;    do            

42、60;string temp;        pos = find(input.begin(),input.end(),' ');/找到分隔符        copy(input.begin(),pos,back_inserter(temp);        if (!stopHandler.

43、IsStopWord(temp)        /不是停用词则保存            retWords.push_back(temp);/保存分出的单词                if (pos=input.end()&#

44、160;       /最后一个单词了            break;                else           &#

45、160;        input.erase(input.begin(),+pos);             while (pos!=input.end();停用词处理      去掉文档中无意思的词语也是必须的一项工作,这里简单的定义了一些常见的停用词，并根据这些常用停用词在分词时进行判断#include &qu

46、ot;StopWordsHandler.h"string stopWordsList ="的", "我们","要","自己","之","将","“","”","，","（","）","后","应","到","某","后","个&q

47、uot;,"是","位","新","一","两","在","中","或","有","更","好",""/常用停用词int stopWordsLen = sizeof(stopWordsList)/sizeof(stopWordsList0);StopWordsHandler:StopWordsHandler(void) 

48、;   for (int i=0;i<stopWordsLen;+i)            stopWords.push_back(stopWordsListi);    StopWordsHandler:StopWordsHandler(void)bool StopWordsHandler:IsStopWord(string& str)/是否是停用词

49、    transform(str.begin(),str.end(),str.begin(),tolower);/确保小写化    return find(stopWords.begin(),stopWords.end(),str)!=stopWords.end();K-Means算法       k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似

50、度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然 后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。  #include "C

51、ommon.h"class Cluster;class KMeanspublic:    vector<Cluster*> _clusters;/聚类private:    int _coordCount;/数据的数量    Double2DVec _coordinates;/原始数据    int _k;/聚类的数量   &

52、#160;/定义一个变量用于记录和跟踪每个资料点属于哪个群聚类    / _clusterAssignmentsj=i; 表示第j 个资料点对象属于第i 个群聚类    IntVec _clusterAssignments;    / 定义一个变量用于记录和跟踪每个资料点离聚类最近    IntVec _nearestCluster;   

53、; / 定义一个变量，来表示资料点到中心点的距离,    / 其中_distanceCacheij表示第i个资料点到第j个群聚对象中心点的距离；    Double2DVec _distanceCache;    void InitRandom();    static double getDistance(const DoubleVec& 

54、;coord, const DoubleVec& center);    int NearestCluster(int ndx);public:    KMeans(Double2DVec& data, int K);    void Start();public:    KMeans(void);K-Means算法具体实现：#in

55、clude "KMeans.h"#include <time.h>#include "Cluster.h"#include "TermVector.h"#include <limits>KMeans:KMeans(Double2DVec &data, int K)    int i;    this->_coordinates.r

56、esize(data.size();    for (i=0;i<data.size();+i)            copy(datai.begin(),datai.end(),back_inserter(_coordinatesi);        _coordCount = data.size(); &#

57、160;  _k = K;    _clusters.resize(K);    _clusterAssignments.resize(_coordCount);    _nearestCluster.resize(_coordCount);    _distanceCache.resize(_coordCount);    for (i=0;i&

58、lt;_coordCount;+i)            _distanceCachei.resize(_coordCount);        InitRandom();void KMeans:InitRandom()    srand(unsigned(time(NULL);     for&

59、#160;(int i = 0; i < _k; i+)            int temp =  rand()%(_coordCount);/产生随机数        _clusterAssignmentstemp = i; /记录第temp个资料

60、属于第i个聚类        _clustersi = new Cluster(temp,_coordinatestemp);    void KMeans:Start()    int iter = 0,i,j;    while (true)      &

61、#160;     cout<<"Iteration "<<iter+<< ""<<endl;        /1、重新计算每个聚类的均值        for (i = 0; i < _k; i+)

62、60;                   _clustersi->UpdateMean(_coordinates);                /2、计算每个数据和每个聚类中心的距离    

63、0;   for (i = 0; i < _coordCount; i+)                    for (j = 0; j < _k; j+)     

64、;                       double dist = getDistance(_coordinatesi, _clustersj->Mean);             &

65、#160;  _distanceCacheij = dist;                            /3、计算每个数据离哪个聚类最近        for (i 

66、= 0; i < _coordCount; i+)                    _nearestClusteri = this->NearestCluster(i);            

67、;    /4、比较每个数据最近的聚类是否就是它所属的聚类        /如果全相等表示所有的点已经是最佳距离了，直接返回；        int k = 0;        for (i = 0; i < _coordC

68、ount; i+)                    if (_nearestClusteri = _clusterAssignmentsi)                k+;                if (k = _coordCount)            break;