大数据十大经典算法之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;  
    }