数据挖掘算法之k-means算法

系列文章：数据挖掘算法之决策树算法

k-means算法可以说是数据挖掘中十大经典算法之一了，属于无监督的学习。该算法由此衍生出了很多类k-means算法，比如k中心点等等，在数据挖掘领域，很多地方都会用到该算法，他能够把相似的一类很好的聚在一起。一类指的是，他们之间的相似度较高，计算相似度的常用度量有欧氏距离、余弦定理等。本算法采用的是欧式距离度量。这个对理解k-means算法不会造成任何实质性的影响。

为了更好的说明k-means算法是把属于一类的对象聚成一个簇的，下面贴两张图，一张是100个数据对象是，K=2的情况【图1】。

另外一张是1000个数据对象，k=3的情况，希望大家看完图能够加深对K-means算法的理解。

[图1 objectNum=100 k=2]

[图2 objectNum=1000 k=3]

k-means算法的中心思想其实就是迭代，通过不断的迭代，使聚类效果达到局部最优，为什么我们说局部最优呢？因为K-means算法的效果的优劣性和最初选取的中心点是有莫大关系的，我们只能在初始中心点的基础上达到局部最优解。

k-means算法的过程如下：

1）从N个文档随机选取K个文档作为质心（即中心点）

2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类

3）重新计算已经得到的各个类的质心

4）迭代2～3步直至新的质心与原质心相等或小于指定阈值(我们这里实际上用迭代次数代替了阈值的功能)，算法结束

输入：一个数据集dataset,类个数k

输出：k个小的数据集，也就是K个类。

该算法会有一些缺点主要是：

1、计算量大，不断的迭代，不断的计算，计算量大事在所难免了。

2、K值的指定也是一个难点，很多时候我们并不知道k是多少？

3、只能得到局部最优解，这一点我们在前面已经讨论过了。

算法能够一行行读txt数据，当然其他格式数据也是可以的，稍微改动下即可。相当方便实用。本着开源的方式，附上90%代码：void produceData(string fileName,int maxNum,int objectNum);方法代码没有附上，该方法用来产生随机数据。如果需要全部源代码请点赞后留下email地址，我将会在第一时间发到你邮箱，不便之处敬请原谅，毕竟写一篇文章也不是那么容易，我只是想看看到底能帮助到多少人，谢谢理解！

#include<iostream>

#include<fstream>

#include<vector>

#include<random>

#include<time.h>

#include<string.h>

using namespace std;

const int maxNum=0x1<<;

const int repeatMax=;//控制迭代的上限，这里主要从效率的角度来考虑。一般来说迭代50--100次就能达到很好的效果

const int AttributeCount=;//数据属性维度.

const int ClusterK=;//聚成的簇的数量

typedef  double AttributeType;

struct Object{//数据项的数据结构

    AttributeType attribute[AttributeCount];

};

vector<Object> allObj;//保存所有的数据

Object cluster[][ClusterK];//各个簇的数据项，这里假定每个簇的最大量为1000了，可以写成vector的数据结构，

Object oldcenter[ClusterK];//旧的各个中心点

int oldCluObjNum[ClusterK];//旧的各个簇有多少数据量

Object center[ClusterK];//对比旧的中心点

int CluObjNum[ClusterK];//对比旧的各簇的数据量

void getAllobject(ifstream &ifs);//加载所有数据

void kmeans(ifstream &ins);//算法

void produceData(string fileName,int maxNum,int objectNum);//随机产生数据，fileName文件名，maxNum数据的最大数，objectNum数据个数

int cloestCluster(Object obj);//返回当前数据项与哪个簇最近

void initCenter();//初始化各中心点

void updateCluster(int cluK,Object obj);//更新簇结构

bool isChange();//判断迭代之后中心点是否改变，若没有改变可以迭代结束了，得到局部最优解

void copyCenter();//复制到旧的中

void computeCenter();//重新计算中心点

AttributeType Distance(Object obj,Object obj2);//计算两个点之间的距离

int main(){

    //produceData("data2.txt",100,50);

    ifstream ifs;

    ifs.open("data2.txt");

    kmeans(ifs);

    ifs.close();

    system("pause");

}

void kmeans(ifstream &ins){

    getAllobject(ins);

    initCenter();

    for(int i=;i<ClusterK;i++){

        center[i]=allObj[i];

        CluObjNum[i]=;

    }

    int repeat=;

    while(isChange()&&repeat<repeatMax){//一直迭代，直到中心点不再改变，或者达到迭代的上限

        copyCenter();

        for(vector<Object>::iterator begin=allObj.begin();begin<allObj.end();begin++){

            int closestK=cloestCluster(*begin);

            updateCluster(closestK,*begin);

        }

        computeCenter();

        for(int i=;i<ClusterK;i++){

            cout<<"第"<<i<<"个簇,他们之间的中心点是:";

            char file[]={'c','l','u','s','t','e','r',static_cast<char>(i+''),'.','t','x','t','\0'};

            ofstream out;

            out.open(file,ifstream::trunc);//输入到各个簇的文件中保存

            for(int l=;l<AttributeCount;l++){

                cout<<center[i].attribute[l]<<" ";

            }

            cout<<endl;

            for(int m=;m<=CluObjNum[i];m++){

                for(int j=;j<AttributeCount;j++)

                    out<<cluster[m][i].attribute[j]<<" ";

                out<<endl;

            }

            cout<<endl;

            out.close();

        }

        cout<<endl;

        repeat++;

    }

}

void updateCluster(int cluK,Object obj){//把obj更新到cluK簇中，同时项增加1

    cluster[CluObjNum[cluK]+][cluK]=obj;

    CluObjNum[cluK]++;

}

void computeCenter(){

    for(int i=;i<ClusterK;i++){

        for(int m=;m<AttributeCount;m++){

            double sum=;

            for(int j=;j<CluObjNum[i];j++){

                sum+=cluster[j][i].attribute[m];

            }

            center[i].attribute[m]=sum/CluObjNum[i];

        }

    }

}

void copyCenter(){

    for(int i=;i<ClusterK;i++){

        oldCluObjNum[i]=CluObjNum[i];

        CluObjNum[i]=;

        for(int j=;j<AttributeCount;j++){

            oldcenter[i].attribute[j]=center[i].attribute[j];

        }

    }

}

void initCenter(){

    Object obj;

    for(int i=;i<AttributeCount;i++){

        obj.attribute[i]=-;

    }

    for(int i=;i<ClusterK;i++){

            oldcenter[i]=obj;

    }

}

int cloestCluster(Object obj){

    AttributeType sq=maxNum,m=maxNum;

    int theCloest=;

    for(int i=;i<ClusterK;i++){

        m=Distance(obj,center[i]);

        if(m<sq){

            theCloest=i;

            sq=m;

        }

    }

    return theCloest;

}

AttributeType Distance(Object obj,Object obj2){

    AttributeType dis=;

    for(int i=;i<AttributeCount;i++){

        dis+=(obj.attribute[i]-obj2.attribute[i])*(obj.attribute[i]-obj2.attribute[i]);

    }

    return dis;

}

bool isChange(){

    for(int i=;i<ClusterK;i++){

        for(int j=;j<AttributeCount;j++)

            if(oldcenter[i].attribute[j]!=center[i].attribute[j])

                return true;

    }

    return false;

}

void getAllobject(ifstream &ifs){

    while(ifs){

        Object obj;

        for(int i=;i<AttributeCount;i++)

            ifs>>obj.attribute[i];

        allObj.push_back(obj);

    }

}

以下提供我的一个数据集运行的最终结果：

巴特西

数据挖掘算法之k-means算法

最新文章

热门文章