基于K中心点数据挖掘.doc

数据挖掘论文基于K-中心点算法实现一、 算法描述k中心点算法：首先为每一个簇随意选择一个代表对象；剩余的对象其与代表的对象的距离分配给最近的一个簇。然后反复的用非代表对象来替代代表对象，以改进聚类的质量。聚类结果的质量用一个代价函数来估算，该函数度量对象与其参与对象之间的平均相异度。为了确定非代表对象是否是当前代表对象的好的替代，对于每一个非代表对象P，考虑以下四种情况。 第一种情况：P当前隶属于代表对象。如果被所取代作为代表对象，并且P离其他代表对象(ij)最近，则P重新分配给。 第二种情况：P当前隶属于代表对象。如果被所取代作为代表对象，并且P离其他代表对象最近，则P重新分配给。 第三种情况：P当前隶属于代表对象，(ij)。如果被所取代作为代表对象，并且P离其他代表对象最近，则对象的隶属不发生变化。 第四种情况：P当前隶属于代表对象，(ij)。如果被所取代作为代表对象，并且P离其他代表对象最近，则P重新分配给。下面是我们这次实现这个k中心点算法的具体描述输入：结果簇的个数k和包含n个对象的数据集合输出：k个簇的集合，使得所有对象与其最近中心点的相异度总和最小方法：（1） 从n个对象的集合中随意选取k个对象作为初始化的中心点；（2） repeat；（3） 将每个剩余的对象指派到最近的中心点所代表的簇；（4） 随机地选择一个非代表对象;（5） 计算用交换代表对象Oj的总代价S;（6） If S0，then 用替换，形成新的k个代表对象的集合（7） until 不发生簇的重新分配。二、 算法实现为了实现k中心点算法我们采用的是语言是C#，开发工具是Micrsoft Visual Stdio 2008,数据库SQL Server2000，为了简单的进行模拟，我们使用了3维数据进行开发，下面将介绍主要的我们软件的主要实现过程。1、 数据库设计：为了进行实现k中心点算法进行数据挖掘分类，我们设计了一个非常简单的数据库，里面主要有一张关于人的分类，我们采用了人的年龄（age）、身高(height)、体重(weight)三个指标进行算法的模拟。2、 主要算法代码（1） 调用数据库，把数据库中的数据提取出来进行挖掘。下面是代码 / / 初始化数据库对象 / DsStaffDataContext DataContext = new DsStaffDataContext(); / / 获取数据库表中数据 / / public List GetStaff() /用链表List初始化数据对象 List aStaff = new List(); /查询数据库中的Staff表 var StaffTable = from p in DataContext.Staffs select p; /遍历查询出来的表，然后将每一条记录放入初始化的链表List对象aStaff中 foreach (Staff aStaffRow in StaffTable) aStaff.Add(aStaffRow); return aStaff; （2） 将每个剩余的对象指派到最近的中心点所代表的簇 / / 指派每个剩余的对象给离它最近的中心点所代表的簇 / / 分成k簇 / 数据 / 中心点集合 / public List SetClusterList(int k, List ChangedListStaff, List CentainPoint) /得到数据的个数 int count = ChangedListStaff.Count; /指派每个剩余的对象给离它最近的中心点所代表的簇 for (int i = 0; i count; i+) List tempPointDistance = new List(); /如果不是中心点(Flag代表是否为中心点,1为中心点) if (!ChangedListStaffi.Flag.Equals(1) /计算剩余的点到每个中心点的距离，然后分到距离最小的那一簇里面 for (int j = 0; j k; j+) double tempAge = Math.Pow(ChangedListStaffi.Age.Value - CentainPointj.Age.Value, 2); double tempHeight =Math.Pow(ChangedListStaffi.Height.Value - CentainPointj.Height.Value, 2); double tempWeight = Math.Pow(ChangedListStaffi.Weight.Value - CentainPointj.Weight.Value, 2); double temp = Math.Sqrt(tempAge+tempHeight+tempWeight); tempPointDistance.Add(temp); double min = tempPointDistance.Min(); int index = tempPointDistance.IndexOf(min); ChangedListStaffi.Cluster = index; return ChangedListStaff; （3） 计算用Orandom交换代表对象Oj的总代价S; / / 代价函数 / / 可能成为新中心点这个数据的位置 / 原有中心点在数据中的位置 / 所有数据(用链表形式进行保存) / public double GetS(int random, int j, List ListStaff) /获取j中心点属于第几簇 int cluster = ListStaffj.Cluster.Value; /获取原中心点数据数据项年龄 int orgAge = ListStaffj.Age.Value; /获取原中心点数据数据项身高 double orgHeight = ListStaffj.Height.Value; /获取原中心点数据数据项体重 double orgWeight = ListStaffj.Weight.Value; /获取可能成为新中心点数据数据项年龄 int randomAge = ListStaffrandom.Age.Value; /获取可能成为新中心点数据数据项身高 double randomHeight = ListStaffrandom.Height.Value; /获取可能成为新中心点数据数据项体重 double randomWeight = ListStaffrandom.Weight.Value; double orgCount = 0.0; double randomCount = 0.0; double sub = 0.0; /获取这一簇里面存在的所有数据 var clusterStaff = from p in ListStaff where p.Cluster.Equals(cluster) select p; /遍历这一簇所有数据 foreach (var cluserRow in clusterStaff) /计算距离 double orgTempAge = Math.Pow(orgAge - cluserRow.Age.Value, 2); double orgTempHeight = Math.Pow(orgHeight - cluserRow.Height.Value, 2); double orgTempWeight = Math.Pow(orgWeight - cluserRow.Weight.Value, 2); double orgDistance = Math.Sqrt(orgTempAge + orgTempHeight + orgTempWeight); double randomTempAge = Math.Pow(randomAge - cluserRow.Age.Value, 2); double randomTempHeight = Math.Pow(randomHeight - cluserRow.Height.Value, 2); double randomTempWeight = Math.Pow(randomWeight - cluserRow.Weight.Value, 2); double randomDistance = Math.Sqrt(randomTempAge + randomTempHeight + randomTempWeight); orgCount += orgDistance; randomCount += randomDistance; /得到交换后它们的代价 sub = randomCount - orgCount; return sub; （4） 核心函数k中心点算法(函数体内调用了上面的函数) / / k中心点算法 / / 分成k簇 / 原数据 / public List K_method(int k, List OrgionListStaff) /初始化总代价 double s = 0; /判断是否所有的中心点不在变化标志 bool Changed = true; /初始化一个随机数生成器 Random ccy = new Random(); /得到所有数据的个数 int count = OrgionListStaff.Count; /初始化整个数据变化后保存的链表集合 List ChangedListStaff = new List(); /初始化k个中心点保存链表集合 List CentainPoint = this.InitCentainPoint(k, OrgionListStaff, out ChangedListStaff); while (Changed) /指派每个剩余的对象给离它最近的中心点所代表的簇 ChangedListStaff = this.SetClusterList(k, OrgionListStaff, CentainPoint); /得到原始的中心点集合 List FirstCentainPoint = CentainPoint; for (int j = 0; j k; j+) /得到一个随机数 int random = 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, ChangedListStaff); /如果总代价 0 if (s 0) /将Orandom换成新的中心点 ChangedListStaffrandom.Flag = 1; /原中心点在数据的位置 int OjIndex = ChangedListStaff.IndexOf(CentainPointj); /把以前的中心点变成普通点 ChangedListStaffOjIndex.Flag = 0; CentainPointj = ChangedListStaffrandom; /如果经过循环后所有中心点中心点都保持不变，循环结束 if (FirstCentainPoint.Equals(CentainPoint) /Changed为false后循环结束 Changed = false; else /Changed为true后循环继续 Changed = true; return ChangedListStaff; 三、 主界面解释（1）下面是我们软件的初始化主界面（图1-1），我们可以看到它是基于k中心点算法的一个数据挖掘软件，在右边是我们要进行处理的数据，我们将数据库中所有数据都提取到出来了，我们可以看到每一条记录有四个属性(姓名、年龄、身高、体重)，而我们这个软件主要是针对其中的三个属性(年龄、身高、体重)进行数据挖掘，将他们进行数据分组，分组后的数据将会呈现在左边的分簇后数据的文本框中。图1-1（2）下面展示的是软件进行数据处理后的效果(如图1-2) 我们在界面上输入8，将右边所有的数据分成8组，开始后经过数据处理展示出来的数据呈现在左边的