《基于K中心点数据挖掘课程设计论文上课讲义.doc》由会员分享，可在线阅读，更多相关《基于K中心点数据挖掘课程设计论文上课讲义.doc（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Good is good, but better carries it.精益求精，善益求善。基于K中心点数据挖掘课程设计论文-一、 基于K-中心点算法实现算法描述k中心点算法：首先为每一个簇随意选择一个代表对象；剩余的对象其与代表的对象的距离分配给最近的一个簇。然后反复的用非代表对象来替代代表对象，以改进聚类的质量。聚类结果的质量用一个代价函数来估算，该函数度量对象与其参与对象之间的平均相异度。为了确定非代表对象是否是当前代表对象的好的替代，对于每一个非代表对象P，考虑以下四种情况。 第一种情况：P当前隶属于代表对象。如果被所取代作为代表对象，并且P离其他代表对象(ij)最近，则P重新分配给。
2、 第二种情况：P当前隶属于代表对象。如果被所取代作为代表对象，并且P离其他代表对象最近，则P重新分配给。 第三种情况：P当前隶属于代表对象，(ij)。如果被所取代作为代表对象，并且P离其他代表对象最近，则对象的隶属不发生变化。第四种情况：P当前隶属于代表对象，(ij)。如果被所取代作为代表对象，并且P离其他代表对象最近，则P重新分配给。下面是我们这次实现这个k中心点算法的具体描述输入：结果簇的个数k和包含n个对象的数据集合输出：k个簇的集合，使得所有对象与其最近中心点的相异度总和最小方法：（1） 从n个对象的集合中随意选取k个对象作为初始化的中心点；（2） repeat；（3） 将每个剩余的对
3、象指派到最近的中心点所代表的簇；（4） 随机地选择一个非代表对象;（5） 计算用交换代表对象Oj的总代价S;（6） IfS0，then用替换，形成新的k个代表对象的集合（7） until不发生簇的重新分配。二、 算法实现为了实现k中心点算法我们采用的是语言是C#，开发工具是MicrsoftVisualStdio2008,数据库SQLServer2000，为了简单的进行模拟，我们使用了3维数据进行开发，下面将介绍主要的我们软件的主要实现过程。1、 数据库设计：为了进行实现k中心点算法进行数据挖掘分类，我们设计了一个非常简单的数据库，里面主要有一张关于人的分类，我们采用了人的年龄（age）、身高(
4、height)、体重(weight)三个指标进行算法的模拟。2、 主要算法代码调用数据库，把数据库中的数据提取出来进行挖掘。下面是代码/初始化数据库对象/DsStaffDataContextDataContext=newDsStaffDataContext();/获取数据库表中数据/publicListGetStaff()/用链表List初始化数据对象ListaStaff=newList();/查询数据库中的Staff表varStaffTable=frompinDataContext.Staffsselectp;/遍历查询出来的表，然后将每一条记录放入初始化的链表List对象aStaff中fo
5、reach(StaffaStaffRowinStaffTable)aStaff.Add(aStaffRow);returnaStaff;（1） 从n个对象的集合中随意选取k个对象作为初始化的中心点，下面是实现的函数：/初始化中心点/分成k簇/原数据/改变后数据/publicListInitCentainPoint(intk,ListOrgionListStaff,outListChangedListStaff)/用链表List初始化数据对象List_Staff=newList(k);/随机数生成器Randomccy=newRandom();/保持随机数ListrandomList=newLis
6、t();for(inti=0;ik;i+)/生成一个随机数intrandom=ccy.Next(OrgionListStaff.Count-1);/当随机数集合中已经存在这个随机数的时候从新筛选，以免重复选择中心点while(randomList.Contains(random)random=ccy.Next(OrgionListStaff.Count-1);randomList.Add(random);StaffaStaff=OrgionListStaffrandom;/属于第几簇OrgionListStaffrandom.Cluster=i;/当前为中心点OrgionListStaffra
7、ndom.Flag=1;_Staff.Add(aStaff);ChangedListStaff=OrgionListStaff;return_Staff;（2） 将每个剩余的对象指派到最近的中心点所代表的簇/指派每个剩余的对象给离它最近的中心点所代表的簇/分成k簇/数据/中心点集合/publicListSetClusterList(intk,ListChangedListStaff,ListCentainPoint)/得到数据的个数intcount=ChangedListStaff.Count;/指派每个剩余的对象给离它最近的中心点所代表的簇for(inti=0;icount;i+)Listt
8、empPointDistance=newList();/如果不是中心点(Flag代表是否为中心点,1为中心点)if(!ChangedListStaffi.Flag.Equals(1)/计算剩余的点到每个中心点的距离，然后分到距离最小的那一簇里面for(intj=0;jk;j+)doubletempAge=Math.Pow(ChangedListStaffi.Age.Value-CentainPointj.Age.Value,2);doubletempHeight=Math.Pow(ChangedListStaffi.Height.Value-CentainPointj.Height.Value
9、,2);doubletempWeight=Math.Pow(ChangedListStaffi.Weight.Value-CentainPointj.Weight.Value,2);doubletemp=Math.Sqrt(tempAge+tempHeight+tempWeight);tempPointDistance.Add(temp);doublemin=tempPointDistance.Min();intindex=tempPointDistance.IndexOf(min);ChangedListStaffi.Cluster=index;returnChangedListStaff;
10、（3） 计算用Orandom交换代表对象Oj的总代价S;/代价函数/可能成为新中心点这个数据的位置/原有中心点在数据中的位置/所有数据(用链表形式进行保存)/publicdoubleGetS(intrandom,intj,ListListStaff)/获取j中心点属于第几簇intcluster=ListStaffj.Cluster.Value;/获取原中心点数据数据项年龄intorgAge=ListStaffj.Age.Value;/获取原中心点数据数据项身高doubleorgHeight=ListStaffj.Height.Value;/获取原中心点数据数据项体重doubleorgWeigh
11、t=ListStaffj.Weight.Value;/获取可能成为新中心点数据数据项年龄intrandomAge=ListStaffrandom.Age.Value;/获取可能成为新中心点数据数据项身高doublerandomHeight=ListStaffrandom.Height.Value;/获取可能成为新中心点数据数据项体重doublerandomWeight=ListStaffrandom.Weight.Value;doubleorgCount=0.0;doublerandomCount=0.0;doublesub=0.0;/获取这一簇里面存在的所有数据varclusterStaff
12、=frompinListStaffwherep.Cluster.Equals(cluster)selectp;/遍历这一簇所有数据foreach(varcluserRowinclusterStaff)/计算距离doubleorgTempAge=Math.Pow(orgAge-cluserRow.Age.Value,2);doubleorgTempHeight=Math.Pow(orgHeight-cluserRow.Height.Value,2);doubleorgTempWeight=Math.Pow(orgWeight-cluserRow.Weight.Value,2);doubleorg
13、Distance=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(random
14、TempAge+randomTempHeight+randomTempWeight);orgCount+=orgDistance;randomCount+=randomDistance;/得到交换后它们的代价sub=randomCount-orgCount;returnsub;（4） 核心函数k中心点算法(函数体内调用了上面的函数)/k中心点算法/分成k簇/原数据/publicListK_method(intk,ListOrgionListStaff)/初始化总代价doubles=0;/判断是否所有的中心点不在变化标志boolChanged=true;/初始化一个随机数生成器Randomccy
15、=newRandom();/得到所有数据的个数intcount=OrgionListStaff.Count;/初始化整个数据变化后保存的链表集合ListChangedListStaff=newList();/初始化k个中心点保存链表集合ListCentainPoint=this.InitCentainPoint(k,OrgionListStaff,outChangedListStaff);while(Changed)/指派每个剩余的对象给离它最近的中心点所代表的簇ChangedListStaff=this.SetClusterList(k,OrgionListStaff,CentainPoin
16、t);/得到原始的中心点集合ListFirstCentainPoint=CentainPoint;for(intj=0;jk;j+)/得到一个随机数intrandom=ccy.Next(count-1);/如果这个数据是中心点，重新得到一个新的随机数(Flag是中心点标志)while(ChangedListStaffrandom.Flag.Equals(1)random=ccy.Next(count-1);if(random=count-1)random-=1;if(random=0)random+=1;/得到交换中心点的总代价s=this.GetS(random,j,ChangedListS
17、taff);/如果总代价0if(s0)/将Orandom换成新的中心点ChangedListStaffrandom.Flag=1;/原中心点在数据的位置intOjIndex=ChangedListStaff.IndexOf(CentainPointj);/把以前的中心点变成普通点ChangedListStaffOjIndex.Flag=0;CentainPointj=ChangedListStaffrandom;/如果经过循环后所有中心点中心点都保持不变，循环结束if(FirstCentainPoint.Equals(CentainPoint)/Changed为false后循环结束Change
18、d=false;else/Changed为true后循环继续Changed=true;returnChangedListStaff;三、 主界面解释（1）下面是我们软件的初始化主界面（图1-1），我们可以看到它是基于k中心点算法的一个数据挖掘软件，在右边是我们要进行处理的数据，我们将数据库中所有数据都提取到出来了，我们可以看到每一条记录有四个属性(姓名、年龄、身高、体重)，而我们这个软件主要是针对其中的三个属性(年龄、身高、体重)进行数据挖掘，将他们进行数据分组，分组后的数据将会呈现在左边的分簇后数据的文本框中。图1-1（2）下面展示的是软件进行数据处理后的效果(如图1-2)我们在界面上输入8
19、，将右边所有的数据分成8组，开始后经过数据处理展示出来的数据呈现在左边的分簇后数据的文本框中。图1-2四、 仔细分析左边的分簇后数据的文本框中我们可以发现：各组之间我们通过普通的心算我们可以发现他们各组之间数据在年龄、身高、体重等综合因素比较下差距是比较大的，而族类之间的差距却是比较小。比如第1组与第2组，第一组中数据“邬海莹58岁-165厘米-60公斤”与第二组数据“熊玉莉1岁-30厘米-13公斤”，不论从年龄、身高和体重上面来说，他们之间的差距是比较大的，而第六组他们族类之间的数据比较后我们科研发现，不论是从年龄、身高还是体重方面他们之间的差距是非常小的。这与比较好的验证了k中心算法对于数
20、据分类效果还是比较好的。附录(源代码)（1） 数据库代码数据表存储类型publicpartialclassStaff:INotifyPropertyChanging,INotifyPropertyChangedprivatestaticPropertyChangingEventArgsemptyChangingEventArgs=newPropertyChangingEventArgs(String.Empty);privatestring_StaffID;privatestring_Name;privateSystem.Nullable_Age;privateSystem.Nullable_
21、Height;privateSystem.Nullable_Weight;privateSystem.Nullable_Flag;privateSystem.Nullable_Cluster;publicStaff()OnCreated();Column(Storage=_StaffID,DbType=NVarChar(50)NOTNULL,CanBeNull=false,IsPrimaryKey=true)publicstringStaffIDgetreturnthis._StaffID;Column(Storage=_Name,DbType=NVarChar(50)publicstring
22、Namegetreturnthis._Name;Column(Storage=_Age,DbType=Int)publicSystem.NullableAgegetreturnthis._Age;Column(Storage=_Height,DbType=Float)publicSystem.NullableHeightgetreturnthis._Height;Column(Storage=_Weight,DbType=Float)publicSystem.NullableWeightgetreturnthis._Weight;Column(Storage=_Flag,DbType=Int)
23、publicSystem.NullableFlaggetreturnthis._Flag;Column(Storage=_Cluster,DbType=Int)publicSystem.NullableClustergetreturnthis._Cluster;（2） 基类算法代码usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Collections;namespaceKpampublicclassKCentain/初始化数据库对象/DsStaffDataCont
24、extDataContext=newDsStaffDataContext();/获取数据库表中数据/publicListGetStaff()/用链表List初始化数据对象ListaStaff=newList();/查询数据库中的Staff表varStaffTable=frompinDataContext.Staffsselectp;/遍历查询出来的表，然后将每一条记录放入初始化的链表List对象aStaff中foreach(StaffaStaffRowinStaffTable)aStaff.Add(aStaffRow);returnaStaff;/初始化中心点/分成k簇/原数据/改变后数据/p
25、ublicListInitCentainPoint(intk,ListOrgionListStaff,outListChangedListStaff)/用链表List初始化数据对象List_Staff=newList(k);/随机数生成器Randomccy=newRandom();/保持随机数ListrandomList=newList();for(inti=0;ik;i+)/生成一个随机数intrandom=ccy.Next(OrgionListStaff.Count-1);/当随机数集合中已经存在这个随机数的时候从新筛选，以免重复选择中心点while(randomList.Contains
26、(random)random=ccy.Next(OrgionListStaff.Count-1);randomList.Add(random);StaffaStaff=OrgionListStaffrandom;/属于第几簇OrgionListStaffrandom.Cluster=i;/当前为中心点OrgionListStaffrandom.Flag=1;_Staff.Add(aStaff);ChangedListStaff=OrgionListStaff;return_Staff;/指派每个剩余的对象给离它最近的中心点所代表的簇/分成k簇/数据/中心点集合/publicListSetClu
27、sterList(intk,ListChangedListStaff,ListCentainPoint)/得到数据的个数intcount=ChangedListStaff.Count;/指派每个剩余的对象给离它最近的中心点所代表的簇for(inti=0;icount;i+)ListtempPointDistance=newList();/如果不是中心点(Flag代表是否为中心点,1为中心点)if(!ChangedListStaffi.Flag.Equals(1)/计算剩余的点到每个中心点的距离，然后分到距离最小的那一簇里面for(intj=0;jk;j+)doubletempAge=Math.
28、Pow(ChangedListStaffi.Age.Value-CentainPointj.Age.Value,2);doubletempHeight=Math.Pow(ChangedListStaffi.Height.Value-CentainPointj.Height.Value,2);doubletempWeight=Math.Pow(ChangedListStaffi.Weight.Value-CentainPointj.Weight.Value,2);doubletemp=Math.Sqrt(tempAge+tempHeight+tempWeight);tempPointDistan
29、ce.Add(temp);doublemin=tempPointDistance.Min();intindex=tempPointDistance.IndexOf(min);ChangedListStaffi.Cluster=index;returnChangedListStaff;/代价函数/可能成为新中心点这个数据的位置/原有中心点在数据中的位置/所有数据(用链表形式进行保存)/publicdoubleGetS(intrandom,intj,ListListStaff)/获取j中心点属于第几簇intcluster=ListStaffj.Cluster.Value;/获取原中心点数据数据项年
30、龄intorgAge=ListStaffj.Age.Value;/获取原中心点数据数据项身高doubleorgHeight=ListStaffj.Height.Value;/获取原中心点数据数据项体重doubleorgWeight=ListStaffj.Weight.Value;/获取可能成为新中心点数据数据项年龄intrandomAge=ListStaffrandom.Age.Value;/获取可能成为新中心点数据数据项身高doublerandomHeight=ListStaffrandom.Height.Value;/获取可能成为新中心点数据数据项体重doublerandomWeight=
31、ListStaffrandom.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.
32、Pow(orgHeight-cluserRow.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.Val
33、ue,2);doublerandomTempWeight=Math.Pow(randomWeight-cluserRow.Weight.Value,2);doublerandomDistance=Math.Sqrt(randomTempAge+randomTempHeight+randomTempWeight);orgCount+=orgDistance;randomCount+=randomDistance;/得到交换后它们的代价sub=randomCount-orgCount;returnsub;/k中心点算法/分成k簇/原数据/publicListK_method(intk,ListOr
34、gionListStaff)/初始化总代价doubles=0;/判断是否所有的中心点不在变化标志boolChanged=true;/初始化一个随机数生成器Randomccy=newRandom();/得到所有数据的个数intcount=OrgionListStaff.Count;/初始化整个数据变化后保存的链表集合ListChangedListStaff=newList();/初始化k个中心点保存链表集合ListCentainPoint=this.InitCentainPoint(k,OrgionListStaff,outChangedListStaff);while(Changed)/指派每
35、个剩余的对象给离它最近的中心点所代表的簇ChangedListStaff=this.SetClusterList(k,OrgionListStaff,CentainPoint);/得到原始的中心点集合ListFirstCentainPoint=CentainPoint;for(intj=0;jk;j+)/得到一个随机数intrandom=ccy.Next(count-1);/如果这个数据是中心点，重新得到一个新的随机数(Flag是中心点标志)while(ChangedListStaffrandom.Flag.Equals(1)random=ccy.Next(count-1);if(random
36、=count-1)random-=1;if(random=0)random+=1;/得到交换中心点的总代价s=this.GetS(random,j,ChangedListStaff);/如果总代价0if(s0)/将Orandom换成新的中心点ChangedListStaffrandom.Flag=1;/原中心点在数据的位置intOjIndex=ChangedListStaff.IndexOf(CentainPointj);/把以前的中心点变成普通点ChangedListStaffOjIndex.Flag=0;CentainPointj=ChangedListStaffrandom;/如果经过循
37、环后所有中心点中心点都保持不变，循环结束if(FirstCentainPoint.Equals(CentainPoint)/Changed为false后循环结束Changed=false;else/Changed为true后循环继续Changed=true;returnChangedListStaff;（3） 界面代码usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSystem.Windows.Forms;usingSystem.Collections;namespaceKpampublicpartialclassForm1:FormKCentainkCentain=newKCentain();publicForm1()InitializeComponent();privatevoidbutton1_Click(objectsender,EventArgse)List