数据挖掘-聚类之K均值算法

数据挖掘--聚类之K均值算法
1.聚类概念聚类是将物理或抽象对象的集合分成相似的对象类的过程。使得同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较高的相异性。簇是数据对象的集合，这些对象与同一簇中的对象彼此相似，而与其他簇的对象相异。

聚类可形式描述为：

    Ｄ={o1, o2, ……, on}表示一个对象集合，

    oi表示第i个对象，i={1,2,……,n}；

    Cx表示第x个簇，CxíＤ，x=1，2，…，k；

    Similarity(oi,oj)表示对象oi与对象oj之间的相似度。

2.K均值算法误差平方和准则：若Nx是第x个簇Cx中的对象数目，mx是这些对象的均值，即：
误差平方和准则J就是所有簇的簇中各个对象与均值间的误差平方和之和，即：

J度量了用k个聚类中心m1,m2,…,mk代表k个簇C1,C2,…,Ck时所产生的总的误差平方和。对于不同的聚类，J的值不同，使J值极小的聚类是误差平方和准则下的最优结果。

核心思想：首先选定k个初始聚类中心，根据最小距离原则将每个数据对象分配到某一簇中，然后不断迭代计算各个簇的聚类中心并依新的聚类中心调整聚类情况，直至收敛（J值不再变化或变化小于指定的阀值）。

    　当存在噪声和离群数据时，k中心点算法比k均值算法效果好，但是k中心点聚类算法的执行代价比k均值算法高。

K均值算法描述如下：

  算法：k均值聚类算法(D，k)

  输入：数据对象集合D，簇数目k

  输出：k个簇的集合

步骤：

　　（1） 从D中随机选取k个不同的数据对象作为k个簇C1，C2，…，Ck的中心m1，m2，…，mk;

　　（2）repeat

  (2.1）for D中每个数据对象o

      (2.1.1） 寻找i，

                 (2.1.2）将o分配给簇Ci

(2.2)for  每个簇

                计算

       //计算新的聚类中心，   　为当前簇   中的对象数目

  3）计算平方误差

3. Until J 不再发生变化

代码实现：

查看更多 下一篇