孙俪最新视频,凹凸美女视频,日本美女热舞视频

基于K-Means的文本聚類算法

TF-IDF（term frequency–inverse document frequency）

這是一種用于信息檢索的一種常用加權技術。它是一種統(tǒng)計方法，用以評估一個字詞對于一個文件集或一個語料庫中的其中一份文件的重要程度。字詞的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時會隨著它在語料庫中出現(xiàn)的頻率成反比下降。

假如一篇文件的總詞語數(shù)是100個，而詞語“母牛”出現(xiàn)了3次，那么“母牛”一詞在該文件中的詞頻就是 0.03 (3/100)。一個計算文件頻率 (DF) 的方法是測定有多少份文件出現(xiàn)過“母牛”一詞，然后除以文件集里包含的文件總數(shù)。所以，如果“母牛”一詞在1,000份文件出現(xiàn)過，而文件總數(shù)是 10,000,000份的話，其文件頻率就是 0.0001 (1000/10,000,000)。最后，TF-IDF分數(shù)就可以由計算詞頻除以文件頻率而得到。以上面的例子來說，“母牛”一詞在該文件集的TF- IDF分數(shù)會是 300 (0.03/0.0001)。這條公式的另一個形式是將文件頻率取對數(shù)。

具體的計算原理，請參考維基百科tf–idf條目。下面簡單介紹下基本的計算步驟：

1,文檔預處理:1）文檔分詞；2）移除停用詞；3）單詞正規(guī)化處理

2，分出的單詞就作為索引項（或單詞表），它們代表的就是向量空間的項向量

3，計算項權值：這包括要計算1）詞頻 ; 2)倒排文件頻率；3）TF-IDF權值

4,計算文檔之間的相似度，一般用余弦相似度(cosine similarity)一同使用于向量空間模型中，用以判斷兩份文件之間的相似性

#include "ITokeniser.h"
#include <map>
class TFIDFMeasure
{
private:
    StrVec _docs;//文檔集合，每一行字符串代表一份文檔
    int _numDocs;//文檔數(shù)目
    int _numTerms;//單詞數(shù)目
    StrVec _terms;//單詞集合
    Int2DVec _termFreq;//每個單詞出現(xiàn)在每份文檔中的頻率
    Double2DVec  _termWeight;//每個單詞在每份文檔的權重
    IntVec _maxTermFreq;//記錄每一份文檔的最大詞頻
    IntVec _docFreq;//出現(xiàn)單詞的文檔頻率
    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& terms);//分詞處理
    void GenerateTermFrequency();//計算詞頻
    void GenerateTermWeight();//計算詞的權重
    void GetWordFrequency(string& input,map<string,int>& freq); //實際統(tǒng)計詞頻函數(shù)
    int CountWords(string& word, const StrVec& words);//統(tǒng)計詞數(shù)
    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);//獲取項向量
};

#include "TFIDFMeasure.h"
#include <limits>
#include <cmath>
using namespace std;
TFIDFMeasure::~TFIDFMeasure(void)
{
    //銷毀分詞器
    if (this->_tokenizer!=NULL)
    {
        delete _tokenizer;
        _tokenizer = NULL;
    }
    //清空數(shù)據(jù)
    _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() ;//所有文檔中的詞項數(shù)目
    //準備好存儲空間
    _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<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!=temp.end();++iter)
    {
        int count = CountWords(*iter, temp);//計算單詞在文檔中出現(xiàn)的次數(shù)
        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中的權重
}
//用于字符串比較的仿函數(shù)
class WordComp
{
public:
    WordComp(string& sWord) : word(sWord)
      {
      }
      bool operator() (const string& lhs)
      {
          return lhs.compare(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<string,int>::iterator pos = _wordsIndex.find(term);
    if (pos!=_wordsIndex.end())
    {
        return pos->second;
    }
    else
        return -1;
}
void TFIDFMeasure::GenerateTermFrequency()
{//計算每個單詞在每份文檔出現(xiàn)的頻率
    for(int i=0; i < _numDocs  ; i++)
    {
        string curDoc=_docs[i];//當前待處理的文檔
        map<string,int> freq;
        this->GetWordFrequency(curDoc,freq);
        map<string,int>::iterator iter;
        _maxTermFreq[i]=numeric_limits<int>::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份文檔中出現(xiàn)的頻率
            _docFreq[termIndex]++;//出現(xiàn)第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的文檔數(shù)目
    return log((float) (_numDocs) / (float) df );
}

分詞算法

為了便于使用不同的分詞算法，我們定義一個抽象的分詞算法接口，具體的分詞算法由用戶自行實現(xiàn)

class ITokeniser
{
public:
virtual void Partition(string input,StrVec& retWords)=0;//分詞算法
};

這里只實現(xiàn)了一個最簡單的空格符分詞算法：

#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());
}

停用詞處理

去掉文檔中無意思的詞語也是必須的一項工作,這里簡單的定義了一些常見的停用詞，并根據(jù)這些常用停用詞在分詞時進行判斷

#include "StopWordsHandler.h"
string stopWordsList[] ={"的", "我們","要","自己","之","將","“","”","，","（","）","后","應","到","某","后",
"個","是","位","新","一","兩","在","中","或","有","更","好",""};//常用停用詞
int stopWordsLen = sizeof(stopWordsList)/sizeof(stopWordsList[0]);

StopWordsHandler::StopWordsHandler(void)
{
    for (int i=0;i<stopWordsLen;++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個數(shù)據(jù)對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”（引力中心）來進行計算的。

k-means 算法的工作過程說明如下：首先從n個數(shù)據(jù)對象任意選擇 k 個對象作為初始聚類中心；而對于所剩下其它對象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標準測度函數(shù)開始收斂為止。一般都采用均方差作為標準測度函數(shù). k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

#include "Common.h"

class Cluster;

class KMeans
{
public:
    vector<Cluster*> _clusters;//聚類
private:
    int _coordCount;//數(shù)據(jù)的數(shù)量
    Double2DVec _coordinates;//原始數(shù)據(jù)
    int _k;//聚類的數(shù)量
    //定義一個變量用于記錄和跟蹤每個資料點屬于哪個群聚類
    // _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);
};

#include "KMeans.h"
#include <time.h>
#include "Cluster.h"
#include "TermVector.h"
#include <limits>
KMeans::KMeans(Double2DVec &data, int K)
{
    int i;
    this->_coordinates.resize(data.size());
    for (i=0;i<data.size();++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);//產(chǎn)生隨機數(shù)
        _clusterAssignments[temp] = i; //記錄第temp個資料屬于第i個聚類
        _clusters[i] = new Cluster(temp,_coordinates[temp]);
    }
}
void KMeans::Start()
{
    int iter = 0,i,j;
    while (true)
    {
        cout<<"Iteration "<<iter++<< "

"<<endl;
        //1、重新計算每個聚類的均值
        for (i = 0; i < _k; i++)
        {
            _clusters[i]->UpdateMean(_coordinates);
        }
        //2、計算每個數(shù)據(jù)和每個聚類中心的距離
        for (i = 0; i < _coordCount; i++)
        {
            for (j = 0; j < _k; j++)
            {
                double dist = getDistance(_coordinates[i], _clusters[j]->Mean);
                _distanceCache[i][j] = dist;
            }
        }
        //3、計算每個數(shù)據(jù)離哪個聚類最近
        for (i = 0; i < _coordCount; i++)
        {
            _nearestCluster[i] = this->NearestCluster(i);
        }
        //4、比較每個數(shù)據(jù)最近的聚類是否就是它所屬的聚類
        //如果全相等表示所有的點已經(jīng)是最佳距離了，直接返回；
        int k = 0;
        for (i = 0; i < _coordCount; i++)
        {
            if (_nearestCluster[i] == _clusterAssignments[i])
                k++;
        }
        if (k == _coordCount)
            break;
        //5、否則需要重新調整資料點和群聚類的關系，調整完畢后再重新開始循環(huán)；
        //需要修改每個聚類的成員和表示某個數(shù)據(jù)屬于哪個聚類的變量
        for (j = 0; j < _k; j++)
        {
            _clusters[j]->CurrentMembership.clear();
        }
        for (i = 0; i < _coordCount; i++)
        {
            _clusters[_nearestCluster[i]]->CurrentMembership.push_back(i);
            _clusterAssignments[i] = _nearestCluster[i];
        }
    }

}

double KMeans::getDistance(const DoubleVec& coord, const DoubleVec& center)
{
    return 1- TermVector::ComputeCosineSimilarity(coord, center);
}
int KMeans::NearestCluster(int ndx)
{
    int nearest = -1;
    double min = numeric_limits<double>::max();
    for (int c = 0; c < _k; c++)
    {
        double d = _distanceCache[ndx][c];
        if (d < min)
        {
            min = d;
            nearest = c;
        }

    }
    return nearest;
}
KMeans::~KMeans(void)
{
    vector<Cluster*>::iterator iter;
    for (iter=this->_clusters.begin();iter!=_clusters.end();++iter)
    {
        delete (*iter);
    }
    _clusters.clear();
}

本站僅提供存儲服務，所有內容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權內容，請點擊舉報。

国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

基于K-Means的文本聚類算法