大數(shù)據(jù)十大經(jīng)典算法之k-means

k均值算法基本思想：

K均值算法是基于質(zhì)心的技術(shù)。它以K為輸入?yún)?shù)，把n個(gè)對(duì)象集合分為k個(gè)簇，使得簇內(nèi)的相似度高，簇間的相似度低。

處理流程：

1、為每個(gè)聚類(lèi)確定一個(gè)初始聚類(lèi)中心，這樣就有k個(gè)初始聚類(lèi)中心；

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

3、使用每個(gè)聚類(lèi)中的樣本均值作為新的聚類(lèi)中心

4、重復(fù)步驟2直到聚類(lèi)中心不再變化

5、結(jié)束，得到K個(gè)聚類(lèi)

劃分聚類(lèi)方法對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)時(shí)的要點(diǎn)：

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

2、選擇平價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù)

用誤差平方和準(zhǔn)則函數(shù)來(lái)評(píng)價(jià)聚類(lèi)性能。

3、相似度的計(jì)算分局一個(gè)簇中對(duì)象的平均值來(lái)進(jìn)行

K均值算法的優(yōu)點(diǎn)：

如果變量很大，K均值比層次聚類(lèi)的計(jì)算速度較快（如果K很?。?；

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

對(duì)于大數(shù)據(jù)集，是可伸縮和高效率的；

算法嘗試找出使平方誤差函數(shù)值最小的k個(gè)劃分。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯的時(shí)候，效果較好。

K均值算法缺點(diǎn)：

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

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

不適合發(fā)現(xiàn)非凸面形狀的簇，并對(duì)噪聲和離群點(diǎn)數(shù)據(jù)較敏感，因?yàn)樯倭康倪@類(lèi)數(shù)據(jù)能夠?qū)诞a(chǎn)生較大的影響。

K均值算法的改進(jìn)：

樣本預(yù)處理。計(jì)算樣本對(duì)象量量之間的距離，篩掉與其他所有樣本那的距離和最大的m個(gè)對(duì)象。

初始聚類(lèi)中心的選擇。選用簇中位置最靠近中心的對(duì)象，這樣可以避免孤立點(diǎn)的影響。

K均值算法的變種：

K眾數(shù)（k-modes）算法，針對(duì)分類(lèi)屬性的度量和更新質(zhì)心的問(wèn)題而改進(jìn)。

EM（期望最大化）算法

k-prototype算法

這種算法不適合處理離散型屬性，但是對(duì)于連續(xù)型具有較好的聚類(lèi)效果。

k均值算法用途：

圖像分割；

衡量足球隊(duì)的水平；

下面給出代碼：

    #include <iostream>  
    #include <vector>  
    //auther archersc  
    //JLU  
    namespace CS_LIB  
    {  
    using namespace std;  
    class Kmean  
    {  
    public:  
       //輸入格式  
       //數(shù)據(jù)數(shù)量N 維度D  
       //以下N行，每行D個(gè)數(shù)據(jù)  
       istream& loadData(istream& in);  
       //輸出格式  
       //聚類(lèi)的數(shù)量CN  
       //中心維度CD  
       //CN行，每行CD個(gè)數(shù)據(jù)  
       //數(shù)據(jù)數(shù)量DN  
       //數(shù)據(jù)維度DD  
       //以下DN組，每組的第一行兩個(gè)數(shù)值DB, DDis  
       //第二行DD個(gè)數(shù)值  
       //DB表示改數(shù)據(jù)屬于一類(lèi)，DDis表示距離改類(lèi)的中心的距離  
       ostream& saveData(ostream& out);  
       //設(shè)置中心的數(shù)量  
       void setCenterCount(const size_t count);  
       size_t getCenterCount() const;  
       //times最大迭代次數(shù)， maxE ,E(t)表示第t次迭代后的平方誤差和，當(dāng)|E(t+1) - E(t)| < maxE時(shí)終止  
       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));  
       //隨機(jī)從m_Data中選取m_Center.size()個(gè)不同的樣本點(diǎn)作為初始中心。  
       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;  
    }