kmeans算法实现.docx
《kmeans算法实现.docx》由会员分享，可在线阅读，更多相关《kmeans算法实现.docx（12页珍藏版）》请在冰点文库上搜索。
kmeans算法实现
#include "ITokeniser.h"
#include
class 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
#include
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* tokeniser）
{
_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（docs[i],words）;//分词
for （int j=0; j < words.size（）; 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 < _terms.size（） ; 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 < this->_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;
}
else
return -1;
}
void TFIDFMeasure:
:
GenerateTermFrequency（）
{//计算每个单词在每份文档出现的频率
for（int i=0; i < _numDocs ; 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 < _numTerms; i++）
{
for（int j=0; j < _numDocs ; 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 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））
{//不是停用词则保存
retWords.push_back（temp）;//保存分出的单词
}
if （pos==input.end（））
{//最后一个单词了
break;
}
else
{
input.erase（input.begin（）,++pos）;
}
} while （pos!
=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个聚类以便使得所获得的聚类满足：
同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。
聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。
k-means算法的工作过程说明如下：
首先从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。
一般都采用均方差作为标准测度函数.k个聚类具有以下特点：
各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
#include "Common.h"
class Cluster;
class KMeans
{
public:
vector _clusters;//聚类
private:
int _coordCount;//数据的数量
Double2DVec _coordinates;//原始数据
int _k;//聚类的数量
//定义一个变量用于记录和跟踪每个资料点属于哪个群聚类
// _clusterAssignments[j]=i; 表示第j 个资料点对象属于第i 个群聚类
IntVec _clusterAssignments;
// 定义一个变量用于记录和跟踪每个资料点离聚类最近
IntVec _nearestCluster;
/// 定义一个变量，来表示资料点到中心点的距离,
/// 其中—_distanceCache[i][j]表示第i个资料点到第j个群聚对象中心点的距离；
Double2DVec _distanceCache;
void InitRandom（）;
static double getDistance（const DoubleVec& coord, const DoubleVec& center）;
int NearestCluster（int ndx）;
public:
KMeans（Double2DVec& data, int K）;
void Start（）;
public:
~KMeans（void）;
};
K-Means算法具体实现：
#include "KMeans.h"
#include
#include "Cluster.h"
#include "TermVector.h"
#include
KMeans:
:
KMeans（Double2DVec &data, int K）
{
int i;
this->_coordinates.resize（data.size（））;
for （i=0;i {
copy（data[i].begin（）,data[i].end（）,back_inserter（_coordinates[i]））;
}
_coordCount = data.size（）;
_k = K;
_clusters.resize（K）;
_clusterAssignments.resize（_coordCount）;
_nearestCluster.resize（_coordCount）;
_distanceCache.resize（_coordCount）;
for （i=0;i<_coordCount;++i）
{
_distanceCache[i].resize（_coordCount）;
}
InitRandom（）;
}
void KMeans:
:
InitRandom（）
{
srand（unsigned（time（NULL）））;
for （int i = 0; i < _k; i++）
{
int temp = rand（）%（_coordCount）;//产生随机数
_clusterAssignments[temp] = i; //记录第temp个资料属于第i个聚类
_clusters[i] = new Cluster（temp,_coordinates[temp]）;
}
}
void KMeans:
:
Start（）
{
int iter = 0,i,j;
while （true）
{
cout<<"Iteration "<"< //1、重新计算每个聚类的均值
for （i = 0; i < _k; i++）
{
_clusters[i]->UpdateMean（_coordinates）;
}
升级会员 