基于K中心点数据挖掘

数据挖掘论文1基于K-中心点算法实现一、算法描述k中心点算法：首先为每一个簇随意选择一个代表对象；剩余的对象其与代表的对象的距离分配给最近的一个簇。然后反复的用非代表对象来替代代表对象，以改进聚类的质量。聚类结果的质量用一个代价函数来估算，该函数度量对象与其参与对象之间的平均相异度。为了确定非代表对象randomO是否是当前代表对象jO的好的替代，对于每一个非代表对象P，考虑以下四种情况。第一种情况：P当前隶属于代表对象jO。如果jO被randomO所取代作为代表对象，并且P离其他代表对象iO(ij)最近，则P重新分配给iO。第二种情况：P当前隶属于代表对象jO。如果jO被randomO所取代作为代表对象，并且P离其他代表对象randomO最近，则P重新分配给randomO。第三种情况：P当前隶属于代表对象iO，(ij)。如果jO被randomO所取代作为代表对象，并且P离其他代表对象iO最近，则对象的隶属不发生变化。第四种情况：P当前隶属于代表对象iO，(ij)。如果jO被randomO所取代作为代表对象，并且P离其他代表对象randomO最近，则P重新分配给randomO。下面是我们这次实现这个k中心点算法的具体描述输入：结果簇的个数k和包含n个对象的数据集合输出：k个簇的集合，使得所有对象与其最近中心点的相异度总和最小方法：（1）从n个对象的集合中随意选取k个对象作为初始化的中心点；（2）repeat；数据挖掘论文2（3）将每个剩余的对象指派到最近的中心点所代表的簇；（4）随机地选择一个非代表对象randomO;（5）计算用randomO交换代表对象Oj的总代价S;（6）IfS0，then用randomO替换jO，形成新的k个代表对象的集合（7）until不发生簇的重新分配。二、算法实现为了实现k中心点算法我们采用的是语言是C#，开发工具是MicrsoftVisualStdio2008,数据库SQLServer2000，为了简单的进行模拟，我们使用了3维数据进行开发，下面将介绍主要的我们软件的主要实现过程。1、数据库设计：为了进行实现k中心点算法进行数据挖掘分类，我们设计了一个非常简单的数据库，里面主要有一张关于人的分类，我们采用了人的年龄（age）、身高(height)、体重(weight)三个指标进行算法的模拟。2、主要算法代码（1）调用数据库，把数据库中的数据提取出来进行挖掘。下面是代码///summary///初始化数据库对象////summaryDsStaffDataContextDataContext=newDsStaffDataContext();///summary///获取数据库表中数据////summary///returns/returnspublicListStaffGetStaff(){//用链表List初始化数据对象ListStaffaStaff=newListStaff();//查询数据库中的Staff表数据挖掘论文3varStaffTable=frompinDataContext.Staffsselectp;//遍历查询出来的表，然后将每一条记录放入初始化的链表List对象aStaff中foreach(StaffaStaffRowinStaffTable){aStaff.Add(aStaffRow);}returnaStaff;}（2）将每个剩余的对象指派到最近的中心点所代表的簇///summary///指派每个剩余的对象给离它最近的中心点所代表的簇////summary///paramname=k分成k簇/param///paramname=ChangedListStaff数据/param///paramname=CentainPoint中心点集合/param///returns/returnspublicListStaffSetClusterList(intk,ListStaffChangedListStaff,ListStaffCentainPoint){//得到数据的个数intcount=ChangedListStaff.Count;//指派每个剩余的对象给离它最近的中心点所代表的簇for(inti=0;icount;i++){ListdoubletempPointDistance=newListdouble();//如果不是中心点(Flag代表是否为中心点,1为中心点)if(!ChangedListStaff[i].Flag.Equals(1)){//计算剩余的点到每个中心点的距离，然后分到距离最小的那一簇里面for(intj=0;jk;j++){doubletempAge=Math.Pow(ChangedListStaff[i].Age.Value-CentainPoint[j].Age.Value,2);doubletempHeight=Math.Pow(ChangedListStaff[i].Height.Value-CentainPoint[j].Height.Value,2);doubletempWeight=Math.Pow(ChangedListStaff[i].Weight.Value-CentainPoint[j].Weight.Value,2);doubletemp=Math.Sqrt(tempAge+tempHeight+tempWeight);tempPointDistance.Add(temp);}doublemin=tempPointDistance.Min();数据挖掘论文4intindex=tempPointDistance.IndexOf(min);ChangedListStaff[i].Cluster=index;}}returnChangedListStaff;}（3）计算用Orandom交换代表对象Oj的总代价S;///summary///代价函数////summary///paramname=random可能成为新中心点这个数据的位置/param///paramname=j原有中心点在数据中的位置/param///paramname=ListStaff所有数据(用链表形式进行保存)/param///returns/returnspublicdoubleGetS(intrandom,intj,ListStaffListStaff){//获取j中心点属于第几簇intcluster=ListStaff[j].Cluster.Value;//获取原中心点数据数据项年龄intorgAge=ListStaff[j].Age.Value;//获取原中心点数据数据项身高doubleorgHeight=ListStaff[j].Height.Value;//获取原中心点数据数据项体重doubleorgWeight=ListStaff[j].Weight.Value;//获取可能成为新中心点数据数据项年龄intrandomAge=ListStaff[random].Age.Value;//获取可能成为新中心点数据数据项身高doublerandomHeight=ListStaff[random].Height.Value;//获取可能成为新中心点数据数据项体重doublerandomWeight=ListStaff[random].Weight.Value;doubleorgCount=0.0;doublerandomCount=0.0;doublesub=0.0;//获取这一簇里面存在的所有数据varclusterStaff=frompinListStaffwherep.Cluster.Equals(cluster)selectp;//遍历这一簇所有数据foreach(varcluserRowinclusterStaff){//计算距离doubleorgTempAge=Math.Pow(orgAge-cluserRow.Age.Value,2);doubleorgTempHeight=Math.Pow(orgHeight-数据挖掘论文5cluserRow.Height.Value,2);doubleorgTempWeight=Math.Pow(orgWeight-cluserRow.Weight.Value,2);doubleorgDistance=Math.Sqrt(orgTempAge+orgTempHeight+orgTempWeight);doublerandomTempAge=Math.Pow(randomAge-cluserRow.Age.Value,2);doublerandomTempHeight=Math.Pow(randomHeight-cluserRow.Height.Value,2);doublerandomTempWeight=Math.Pow(randomWeight-cluserRow.Weight.Value,2);doublerandomDistance=Math.Sqrt(randomTempAge+randomTempHeight+randomTempWeight);orgCount+=orgDistance;randomCount+=randomDistance;}//得到交换后它们的代价sub=randomCount-orgCount;returnsub;}（4）核心函数k中心点算法(函数体内调用了上面的函数)///summary///k中心点算法////summary///paramname=k分成k簇/param///paramname=OrgionListStaff原数据/param///returns/returnspublicListStaffK_method(intk,ListStaffOrgionListStaff){//初始化总代价doubles=0;//判断是否所有的中心点不在变化标志boolChanged=true;//初始化一个随机数生成器Randomccy=newRandom();//得到所有数据的个数intcount=OrgionListStaff.Count;//初始化整个数据变化后保存的链表集合ListStaffChangedListStaff=newListStaff();//初始化k个中心点保存链表集合ListStaffCentainPoint=this.InitCentainPoint(k,OrgionListStaff,outChangedListStaff);while(Changed){数据挖掘论文6//指派每个剩余的对象给离它最近的中心点所代表的簇ChangedListStaff=this.SetClusterList(k,OrgionListStaff,CentainPoint);//得到原始的中心点集合ListStaffFirstCentainPoint=CentainPoint;for(intj=0;jk;j++){//得到一个随机数intrandom=ccy.Next(count-1);//如果这个数据是中心点，重新得到一个新的随机数(Flag是中心点标志)while(ChangedListStaff[random].Flag.Equals(1)){random=ccy.Next(count-1);if(random==count-1){random-=1;}if(random==0){random+=1;}}//得到交换中心点的总代价s=this.GetS(random,j,ChangedListStaff);//如果总代价0if(s0){//将Orandom换成新的中心点ChangedListStaff[random].Fla