大數據十大經典算法之k-means

k均值算法基本思想：

K均值算法是基于質心的技術。它以K為輸入參數，把n個對象集合分為k個簇，使得簇內的相似度高，簇間的相似度低。

處理流程：

1、為每個聚類確定一個初始聚類中心，這樣就有k個初始聚類中心；

2、將樣本按照最小距離原則分配到最鄰近聚類

3、使用每個聚類中的樣本均值作為新的聚類中心

4、重復步驟2直到聚類中心不再變化

5、結束，得到K個聚類

劃分聚類方法對數據集進行聚類時的要點：

1、選定某種距離作為數據樣本間的相似性度量，通常選擇歐氏距離。

2、選擇平價聚類性能的準則函數

用誤差平方和準則函數來評價聚類性能。

3、相似度的計算分局一個簇中對象的平均值來進行

K均值算法的優點：

如果變量很大，K均值比層次聚類的計算速度較快（如果K很?。?；

與層次聚類相比，K均值可以得到更緊密的簇，尤其是對于球狀簇；

對于大數據集，是可伸縮和高效率的；

算法嘗試找出使平方誤差函數值最小的k個劃分。當結果簇是密集的，而簇與簇之間區別明顯的時候，效果較好。

K均值算法缺點：

最后結果受初始值的影響。解決辦法是多次嘗試取不同的初始值。

可能發生距離簇中心m最近的樣本集為空的情況，因此m得不到更新。這是一個必須處理的問題，但我們忽略該問題。

不適合發現非凸面形狀的簇，并對噪聲和離群點數據較敏感，因為少量的這類數據能夠對均值產生較大的影響。

K均值算法的改進：

樣本預處理。計算樣本對象量量之間的距離，篩掉與其他所有樣本那的距離和最大的m個對象。

初始聚類中心的選擇。選用簇中位置最靠近中心的對象，這樣可以避免孤立點的影響。

K均值算法的變種：

K眾數（k-modes）算法，針對分類屬性的度量和更新質心的問題而改進。

EM（期望最大化）算法

k-prototype算法

這種算法不適合處理離散型屬性，但是對于連續型具有較好的聚類效果。

k均值算法用途：

圖像分割；

衡量足球隊的水平；

下面給出代碼：

    #include <iostream>  
    #include <vector>  
    //auther archersc  
    //JLU  
    namespace CS_LIB  
    {  
    using namespace std;  
    class Kmean  
    {  
    public:  
       //輸入格式  
       //數據數量N 維度D  
       //以下N行，每行D個數據  
       istream& loadData(istream& in);  
       //輸出格式  
       //聚類的數量CN  
       //中心維度CD  
       //CN行，每行CD個數據  
       //數據數量DN  
       //數據維度DD  
       //以下DN組，每組的第一行兩個數值DB, DDis  
       //第二行DD個數值  
       //DB表示改數據屬于一類，DDis表示距離改類的中心的距離  
       ostream& saveData(ostream& out);  
       //設置中心的數量  
       void setCenterCount(const size_t count);  
       size_t getCenterCount() const;  
       //times最大迭代次數， maxE ,E(t)表示第t次迭代后的平方誤差和，當|E(t+1) - E(t)| < maxE時終止  
       void clustering(size_t times, double maxE);  
      
    private:  
       double calDistance(vector<double>& v1, vector<double>& v2);  
      
    private:  
       vector< vector<double> > m_Data;  
       vector< vector<double> > m_Center;  
       vector<double> m_Distance;  
       vector<size_t> m_DataBelong;  
       vector<size_t> m_DataBelongCount;  
    };  
    }  
    #include "kmean.h"  
      
    #include <ctime>  
    #include <cmath>  
    #include <cstdlib>  
    //auther archersc  
    //JLU  
      
    namespace CS_LIB  
    {  
    template<class T>  
    void swap(T& a, T& b)  
    {  
       T c = a;  
       a = b;  
       b = c;  
    }  
      
    istream& Kmean::loadData(istream& in)  
    {  
       if (!in){  
        cout << "input error" << endl;  
        return in;  
       }  
       size_t dCount, dDim;  
       in >> dCount >> dDim;  
       m_Data.resize(dCount);  
       m_DataBelong.resize(dCount);  
       m_Distance.resize(dCount);  
       for (size_t i = 0; i < dCount; ++i){  
        m_Data[i].resize(dDim);  
        for (size_t j = 0; j < dDim; ++j){  
         in >> m_Data[i][j];  
        }  
       }  
       return in;  
    }  
    ostream& Kmean::saveData(ostream& out)  
    {  
       if (!out){  
        cout << "output error" << endl;  
        return out;  
       }  
       out << m_Center.size();  
       if (m_Center.size() > 0)  
        out << ' ' << m_Center[0].size();  
       else  
        out << ' ' << 0;  
       out << endl << endl;  
       for (size_t i = 0; i < m_Center.size(); ++i){  
        for (size_t j = 0; j < m_Center[i].size(); ++j){  
         out << m_Center[i][j] << ' ';  
        }  
        out << endl;  
       }  
       out << endl;  
       out << m_Data.size();  
       if (m_Data.size() > 0)  
        out << ' ' << m_Data[0].size();  
       else  
        out << ' ' << 0;  
       out << endl << endl;  
       for (size_t i = 0; i < m_Data.size(); ++i){  
        out << m_DataBelong[i] << ' ' << m_Distance[i] << endl;  
        for (size_t j = 0; j < m_Data[i].size(); ++j){  
         out << m_Data[i][j] << ' ';  
        }  
        out << endl << endl;  
       }  
       return out;  
    }  
    void Kmean::setCenterCount(const size_t count)  
    {  
       m_Center.resize(count);  
       m_DataBelongCount.resize(count);  
    }  
    size_t Kmean::getCenterCount() const  
    {  
       return m_Center.size();  
    }  
    void Kmean::clustering(size_t times, double maxE)  
    {  
       srand((unsigned int)time(NULL));  
       //隨機從m_Data中選取m_Center.size()個不同的樣本點作為初始中心。  
       size_t *pos = new size_t[m_Data.size()];  
       size_t i, j, t;  
       for (i = 0; i < m_Data.size(); ++i){  
        pos[i] = i;  
       }  
       for (i = 0; i < (m_Data.size() << 1); ++i){  
        size_t s1 = rand() % m_Data.size();  
        size_t s2 = rand() % m_Data.size();  
        swap(pos[s1], pos[s2]);  
       }  
       for (i = 0; i < m_Center.size(); ++i){  
        m_Center[i].resize(m_Data[pos[i]].size());  
        for (j = 0; j < m_Data[pos[i]].size(); ++j){  
         m_Center[i][j] = m_Data[pos[i]][j];  
        }  
       }  
       delete []pos;  
       double currE, lastE;  
       for (t = 0; t < times; ++t){  
        for (i = 0; i < m_Distance.size(); ++i)  
         m_Distance[i] = LONG_MAX;  
        for (i = 0; i < m_DataBelongCount.size(); ++i)  
         m_DataBelongCount[i] = 0;  
        currE = 0.0;  
        for (i = 0; i < m_Data.size(); ++i){  
         for (j = 0; j < m_Center.size(); ++j){  
          double dis = calDistance(m_Data[i], m_Center[j]);  
          if (dis < m_Distance[i]){  
           m_Distance[i] = dis;  
           m_DataBelong[i] = j;  
          }  
         }  
         currE += m_Distance[i];  
         m_DataBelongCount[m_DataBelong[i]]++;  
        }  
        cout << currE << endl;  
        if (t == 0 || fabs(currE - lastE) > maxE)  
         lastE = currE;  
        else  
         break;  
        for (i = 0; i < m_Center.size(); ++i){  
         for (j = 0; j < m_Center[i].size(); ++j)  
          m_Center[i][j] = 0.0;  
          
        }  
        for (i = 0; i < m_DataBelong.size(); ++i){  
         for (j = 0; j < m_Data[i].size(); ++j){  
          m_Center[m_DataBelong[i]][j] += m_Data[i][j] / m_DataBelongCount[m_DataBelong[i]];  
         }  
        }   
       }  
    }  
    double Kmean::calDistance(vector<double>& v1, vector<double>& v2)  
    {  
       double result = 0.0;  
       for (size_t i = 0; i < v1.size(); ++i){  
        result += (v1[i] - v2[i]) * (v1[i] - v2[i]);  
       }  
       return pow(result, 1.0 / v1.size());  
    //return sqrt(result);  
    }  
    }  
    #include <iostream>  
    #include <fstream>  
    #include "kmean.h"  
    using namespace std;  
    using namespace CS_LIB;  
      
    int main()  
    {  
    ifstream in("in.txt");  
    ofstream out("out.txt");  
    Kmean kmean;  
    kmean.loadData(in);  
    kmean.setCenterCount(4);  
    kmean.clustering(1000, 0.000001);  
    kmean.saveData(out);  
      
    return 0;  
    }