文本聚類總結

摘要：文本聚類是搜尋引擎和語義web的基本技術，這次本蛙和大家一起學習一下簡單的文本聚類算法，可能不能直接用于實際應用中，但對于想學搜尋技術的初學者還是有一定入門作用的。這裡會用到tf/idf權重，用餘弦夾角計算文本相似度，用方差計算兩個資料間歐式距離，用k-means進行資料聚類等數學和統計知識。關于這些概念可以去google，或者參考文本後的參考連結。

思路：計算兩篇文檔的相似度，最簡單的做法就是用提取文檔的tf/idf權重，然後用餘弦定理計算兩個多元向量的距離。能計算兩個文本間的距離後，用标準的k-means算法就可以實作文本聚類了。

測試：首先我們準備以下資料

===================

奧運 拳擊 入場券 基本 分罄 鄒市明 奪冠 對手 浮出 水面

股民 要 清楚 自己 的 目的

印花稅 之 股民 四季

杭州 股民 放 鞭炮 慶祝 印花稅 下調 

殘疾 女 青年 入圍 奧運 遊泳 比賽 創 奧運 曆史 兩 項 第一

介紹 一 個 asp.net mvc 系列 教程

在 asp.net 中 實作 觀察者 模式 ，或 有 更 好 的 方法 （續）

輸 大錢 的 股民 給 我們 啟迪

asp.net 頁面 執行 流程 分析

運動員 行李 将 “後 上 先 下” 奧運 相關 人員 行李 實名制

asp.net 控件 開發 顯示 控件 内容

奧運 票務 網上 成功 訂票 後 應 及時 到 銀行 代售 網點 付款

某 心理 健康 站 開張 後 首 個 咨詢 者 是 位 新 股民

asp.net 自定義 控件 複雜 屬性 聲明 持久性 淺析

==================

很明顯以上資料可以分為三類：asp.net，奧運和股民，我們就寫程式來實作它，各種算法的原理網上都有，我就大概隻貼代碼，聲明一下，部分代碼是從網上直接抄的，k-means代碼是我從一篇文章的java示例代碼轉換過來的，我給代碼加了不少注釋，希望能幫助大家了解。

以下是入口函數

static void main(string[] args)

{

    //1、擷取文檔輸入

    string[] docs = getinputdocs("input.txt");

    if (docs.length < 1)

    {

        console.writeline("沒有文檔輸入");

        console.read();

        return;

    }

    //2、初始化tfidf測量器，用來生産每個文檔的tfidf權重

    tfidfmeasure tf = new tfidfmeasure(docs, new tokeniser());

    int k = 3; //聚成3個聚類

    //3、生成k-means的輸入資料，是一個聯合數組，第一維表示文檔個數，

    //第二維表示所有文檔分出來的所有詞

    double[][] data = new double[docs.length][];

    int doccount = docs.length; //文檔個數

    int dimension = tf.numterms;//所有詞的數目

    for (int i = 0; i < doccount; i++)

        for (int j = 0; j < dimension; j++)

        {

            data[i] = tf.gettermvector2(i); //擷取第i個文檔的tfidf權重向量

        }

    //4、初始化k-means算法，第一個參數表示輸入資料，第二個參數表示要聚成幾個類

    wawakmeans kmeans = new wawakmeans(data, k);

    //5、開始疊代

    kmeans.start();

    //6、擷取聚類結果并輸出

    wawacluster[] clusters = kmeans.clusters;

    foreach (wawacluster cluster in clusters)

        list<int> members = cluster.currentmembership;

        console.writeline("-----------------");

        foreach (int i in members)

            console.writeline(docs[i]);

    console.read();

}

以下是分詞器的主要代碼

/// <summary>

/// 以空白字元進行簡單分詞，并忽略大小寫，

/// 實際情況中可以用其它中文分詞算法

/// </summary>

/// <param name="input"></param>

/// <returns></returns>

public ilist<string> partition(string input)

 regex r=new regex("([ \\t{}():;. \n])");  

 input=input.tolower() ;

 string [] tokens=r.split(input);          

 list<string> filter=new  list<string>() ;

 for (int i=0; i < tokens.length ; i++)

 {

  matchcollection mc=r.matches(tokens[i]);

  if (mc.count <= 0 && tokens[i].trim().length > 0       

   && !stopwordshandler.isstopword (tokens[i]) )        

   filter.add(tokens[i]) ;

 return filter.toarray();

以下是kmeans算法的基本代碼

public class wawakmeans

    /// <summary>

    /// 資料的數量

    /// </summary>

    readonly int _coordcount;

    /// 原始資料

    readonly double[][] _coordinates;

    /// 聚類的數量

    readonly int _k;

    /// 聚類

    private readonly wawacluster[] _clusters;

    internal wawacluster[] clusters

        get { return _clusters; }

    } 

    /// 定義一個變量用于記錄和跟蹤每個資料點屬于哪個群聚類

    /// _clusterassignments[j]=i;// 表示第 j 個資料點對象屬于第 i 個群聚類

    readonly int[] _clusterassignments;

    /// 定義一個變量用于記錄和跟蹤每個資料點離聚類最近

    private readonly int[] _nearestcluster;

    /// 定義一個變量，來表示資料點到中心點的距離,

    /// 其中—_distancecache[i][j]表示第i個資料點到第j個群聚對象中心點的距離；

    private readonly double[,] _distancecache;

    /// 用來初始化的随機種子

    private static readonly random _rnd = new random(1);

    public wawakmeans(double[][] data, int k)

        _coordinates = data;

        _coordcount = data.length;

        _k = k;

        _clusters = new wawacluster[k];

        _clusterassignments = new int[_coordcount];

        _nearestcluster = new int[_coordcount];

        _distancecache = new double[_coordcount,data.length];

        initrandom();

    public void start()

        int iter = 0;

        while (true)

            console.writeline("iteration " + (iter++) + "

");

            //1、重新計算每個聚類的均值

            for (int i = 0; i < _k; i++)

            {

                _clusters[i].updatemean(_coordinates);

            }

            //2、計算每個資料和每個聚類中心的距離

            for (int i = 0; i < _coordcount; i++)

                for (int j = 0; j < _k; j++)

                {

                    double dist = getdistance(_coordinates[i], _clusters[j].mean);

                    _distancecache[i,j] = dist;

                }

            //3、計算每個資料離哪個聚類最近

                _nearestcluster[i] = nearestcluster(i);

            //4、比較每個資料最近的聚類是否就是它所屬的聚類

            //如果全相等表示所有的點已經是最佳距離了，直接傳回；

            int k = 0;

                if (_nearestcluster[i] == _clusterassignments[i])

                    k++;

            if (k == _coordcount)

                break;

            //5、否則需要重新調整資料點和群聚類的關系，調整完畢後再重新開始循環；

            //需要修改每個聚類的成員和表示某個資料屬于哪個聚類的變量

            for (int j = 0; j < _k; j++)

                _clusters[j].currentmembership.clear();

                _clusters[_nearestcluster[i]].currentmembership.add(i);

                _clusterassignments[i] = _nearestcluster[i];

    /// 計算某個資料離哪個聚類最近

    /// <param name="ndx"></param>

    /// <returns></returns>

    int nearestcluster(int ndx)

        int nearest = -1;

        double min = double.maxvalue;

        for (int c = 0; c < _k; c++)

            double d = _distancecache[ndx,c];

            if (d < min)

                min = d;

                nearest = c;

        if(nearest==-1)

            ;

        return nearest;

    /// 計算某資料離某聚類中心的距離

    /// <param name="coord"></param>

    /// <param name="center"></param>

    static double getdistance(double[] coord, double[] center)

        //int len = coord.length;

        //double sumsquared = 0.0;

        //for (int i = 0; i < len; i++)

        //{

        //    double v = coord[i] - center[i];

        //    sumsquared += v * v; //平方差

        //}

        //return math.sqrt(sumsquared);

        //也可以用餘弦夾角來計算某資料離某聚類中心的距離

        return 1- termvector.computecosinesimilarity(coord, center);

    /// 随機初始化k個聚類

    private void initrandom()

        for (int i = 0; i < _k; i++)

            int temp = _rnd.next(_coordcount);

            _clusterassignments[temp] = i; //記錄第temp個資料屬于第i個聚類

            _clusters[i] = new wawacluster(temp,_coordinates[temp]);

以下是聚類實體類的定義

internal class wawacluster

    public wawacluster(int dataindex,double[] data)

        currentmembership.add(dataindex);

        mean = data;

    /// 該聚類的資料成員索引

    internal list<int> currentmembership = new list<int>();

    /// 該聚類的中心

    internal double[] mean;

    /// 該方法計算聚類對象的均值 

    /// <param name="coordinates"></param>

    public void updatemean(double[][] coordinates)

        // 根據 mcurrentmembership 取得原始資料點對象 coord ，該對象是 coordinates 的一個子集；

        //然後取出該子集的均值；取均值的算法很簡單，可以把 coordinates 想象成一個 m*n 的距陣 ,

        //每個均值就是每個縱向列的取和平均值 , //該值儲存在 mcenter 中

        for (int i = 0; i < currentmembership.count; i++)

            double[] coord = coordinates[currentmembership[i]];

            for (int j = 0; j < coord.length; j++)

                mean[j] += coord[j]; // 得到每個縱向列的和；

            for (int k = 0; k < mean.length; k++)

                mean[k] /= coord.length; // 對每個縱向列取平均值

計算tf/idf和利用餘弦定理計算相似度的代碼見完整版的代碼下載下傳，那兩部分都是外國人寫的，裡面有它的聯系方式，不懂的可以問他，反正我差不多懂了。

下面看看咱們的測試結果：

iteration 0...

iteration 1...

iteration 2...

-----------------

杭州 股民 放 鞭炮 慶祝 印花稅 下調

asp.net 自定義 控件 複雜 屬性 聲明 持久性 淺析聚類聚的非常準确，而且隻疊代了3次，模型就收斂了，當然了這是最理想的效果，其實聚類的結果受好多種因素制約，提取特征的算法，随機初始化函數，kmeans算法的實作等，都有優化的地方，不信你把輸入的資料的順序改改，聚類結果就不一樣了，或者把随機數的種子變一下，結果也不一樣，k-means算法加入一些變異系數的調整，結果也不一樣，提取特征的地方不用tf/idf權重算法用别的，結果肯定也不一樣。

完整代碼裡還有另一組測試資料，結果也很不錯，我的意思是我的算法不是針對一組測試資料，而是針對好多資料都有不錯的結果。

總結：數學和英語真是寫程式之根本呀，弄這個東西遇到了好多英語單詞不會，查還查不出來，也了解不了，最後google一看，是個數學專用詞，再搜尋這個數學專用詞的中文解釋，發現還是了解不了那數學原理。是以還是得多學習數學和英語。

參考連結：

k-means算法

http://beauty9235.javaeye.com/blog/161675

什麼是變異系數

http://zhidao.baidu.com/question/15013015.html

tf/idf實作

http://www.codeproject.com/kb/cs/tfidf.aspx