《数据挖掘论文》基于K中心点算法实现讲义

数据挖掘论文 基于K中心点算法实现 算法描述 k中心点算法:首先为每一个簇随意选择一个代表对象;剩余的对象其与代 表的对象的距离分配给最近的一个簇。然后反复的用非代表对象来替代代表对 象,以改进聚类的质量。聚类结果的质量用一个代价函数来估算,该函数度量对 象与其参与对象之间的平均相异度。为了确定非代表对象On是否是当前代表 对象O的好的替代,对于每一个非代表对象P,考虑以下四种情况。 第一种情况:P当前隶属于代表对象O。如果O被Oadm所取代作为代表对象, 并且P离其他代表对象O〔≠)最近,则P重新分配给O。 第二种情况:P当前隶属于代表对象O。如果O,被 Orandi所取代作为代表对象 并且P离其他代表对象Oadm最近,则P重新分配给 prandi 第三种情况:P当前隶属于代表对象O,(≠。如果O1被 Orando所取代作为代表 对象,并且P离其他代表对象O最近,则对象的隶属不发生变化。 第四种情况:P当前隶属于代表对象O,〔≠)。如果O,被Oabm所取代作为代表 对象,并且P离其他代表对象Om最近,则P重新分配给 O 下面是我们这次实现这个k中心点算法的具体描述 输入:结果簇的个数k和包含n个对象的数据集合 输出:k个簇的集合,使得所有对象与其最近中心点的相异度总和最小 方法 (1)从n个对象的集合中随意选取k个对象作为初始化的中心点 (2) repeat

数据挖掘论文 1 基于 K-中心点算法实现 一、 算法描述 k 中心点算法：首先为每一个簇随意选择一个代表对象；剩余的对象其与代 表的对象的距离分配给最近的一个簇。然后反复的用非代表对象来替代代表对 象，以改进聚类的质量。聚类结果的质量用一个代价函数来估算，该函数度量对 象与其参与对象之间的平均相异度。为了确定非代表对象 Orandom 是否是当前代表 对象 Oj 的好的替代，对于每一个非代表对象 P，考虑以下四种情况。 ➢ 第一种情况：P 当前隶属于代表对象 Oj 。如果 Oj 被 Orandom 所取代作为代表对象， 并且 P 离其他代表对象 Oi (i  j)最近，则 P 重新分配给 Oi 。 ➢ 第二种情况：P 当前隶属于代表对象 Oj 。如果 Oj 被 Orandom 所取代作为代表对象， 并且 P 离其他代表对象 Orandom 最近，则 P 重新分配给 Orandom。 ➢ 第三种情况：P 当前隶属于代表对象 Oi ，(i  j)。如果 Oj 被 Orandom 所取代作为代表 对象，并且 P 离其他代表对象 Oi 最近，则对象的隶属不发生变化。 ➢ 第四种情况：P 当前隶属于代表对象 Oi ，(i  j)。如果 Oj 被 Orandom 所取代作为代表 对象，并且 P 离其他代表对象 Orandom 最近，则 P 重新分配给 Orandom。 下面是我们这次实现这个 k 中心点算法的具体描述 输入：结果簇的个数 k 和包含 n 个对象的数据集合 输出：k个簇的集合，使得所有对象与其最近中心点的相异度总和最小 方法： （1） 从 n 个对象的集合中随意选取 k 个对象作为初始化的中心点； （2） repeat；

数据挖掘论文 (3)将每个剩余的对象指派到最近的中心点所代表的簇; 随机地选择一个非代表对象On (5) 计算用O交换代表对象Oj的总代价S (6) IfS //初始化数据库对象 7// DsStaffDataContext DataContext new DsStaffDataContext o 7// ///获取数据库表中数据 7// /// /returns> public List GetStaffo //用链表List初始化数据对象 List aStaff new Listo //查询数据库中的 Staff表

数据挖掘论文 2 （3） 将每个剩余的对象指派到最近的中心点所代表的簇； （4） 随机地选择一个非代表对象 Orandom ; （5） 计算用 Orandom 交换代表对象 Oj 的总代价 S; （6） If S /// 初始化数据库对象 /// DsStaffDataContext DataContext = new DsStaffDataContext(); /// /// 获取数据库表中数据 /// /// public List GetStaff() { //用链表List初始化数据对象 List aStaff = new List(); //查询数据库中的Staff表

数据挖掘论文 var StaffTable from p in DataContext. Staffs select p //遍历查询出来的表,然后将每一条记录放入初始化的链表List对象 aStaff中 oreach (Staff aStaffRow in StaffTable Staff. Add(aStaffRow) return aStaff (2)从n个对象的集合中随意选取k个对象作为初始化的中心点,下面是 实现的函数 //初始化中心点 /×/ summary //分成k簇 //原数据改变后数据 /// public List InitCentainPoint(int k, List OrgionListStaff out List ChangedListStaff) //用链表List初始化数据对象 List Staff new List(k) //随机数生成器 Random ccy new Random O /保持随机数 Listint> randomList new Listo for(int i=0:i< k: i++) /生成一个随机数 nt random ccy Next(OrgionListStaff. Count-1) ∥/当随机数集合中已经存在这个随机数的时候从新筛选,以免重复选择中心点 while (randomList Contains(random)) random ccy Next (OrgionListStaff. Count-1) randomList. Add (random) Staff aStaff OrgionListStaff[random] //属于第几簇 OrgionListStaff[random]. Cluster =i //当前为中心点 OrgionListStaff [random]. Flag =1

数据挖掘论文 3 var StaffTable = from p in DataContext.Staffs select p; //遍历查询出来的表，然后将每一条记录放入初始化的链表List对象aStaff中 foreach (Staff aStaffRow in StaffTable) { aStaff.Add(aStaffRow); } return aStaff; } （2） 从 n 个对象的集合中随意选取 k 个对象作为初始化的中心点，下面是 实现的函数： /// /// 初始化中心点 /// /// 分成k簇 /// 原数据 /// 改变后数据 /// public List InitCentainPoint(int k, List OrgionListStaff, out List ChangedListStaff) { //用链表List初始化数据对象 List _Staff = new List(k); //随机数生成器 Random ccy = new Random(); //保持随机数 List randomList = new List(); for (int i = 0; i < k; i++) { //生成一个随机数 int random = ccy.Next(OrgionListStaff.Count - 1); //当随机数集合中已经存在这个随机数的时候从新筛选，以免重复选择中心点 while (randomList.Contains(random)) { random = ccy.Next(OrgionListStaff.Count - 1); } randomList.Add(random); Staff aStaff = OrgionListStaff[random]; //属于第几簇 OrgionListStaff[random].Cluster = i; //当前为中心点 OrgionListStaff[random].Flag = 1;

数据挖掘论文 Staff. Add (aStaff) ChangedlistStaff OrgionListstaff return Staff (3)将每个剩余的对象指派到最近的中心点所代表的簇 77/ ///指派每个剩余的对象给离它最近的中心点所代表的簇 ///分成k簇 /// param name="ChangedListStaff" >*E //中心点集合/returns> public List SetClusterList(int k, List ChangedListStaff List CentainPoint //得到数据的个数 int count ChangedListstaff. Count: //指派每个剩余的对象给离它最近的中心点所代表的簇 for (int i=0: i temp PointDistance new Listo //如果不是中心点(Fag代表是否为中心点,1为中心点 if (! ChangedListStaff[]. Flag. Equals (1)) //计算剩余的点到每个中心点的距离,然后分到距离最小的那一簇里面 for (int j=0:j<k: j++) double tempAge Math Pow(ChangedListStaff[i] Age value CentainPoint [j] Age Value, 2) double tempHeight =Math. Pow(ChangedListStaff[]. HeightValue CentainPoint [jl. Height value, 2) double tempWeight= Math. Pow(ChangedListStaff[i]. Weight. value CentainPoint [j]. Weight Value, 2) double temp Math Sgrt(tempAgetempHeight+tempWeight) tempPointDistance. Add (temp) double min tempPointDistance Min o int index tempPointDistance. IndexOf (min) ChangedListStaff[i]. Cluster index return Changedliststaff

数据挖掘论文 4 _Staff.Add(aStaff); } ChangedListStaff = OrgionListStaff; return _Staff; } （3） 将每个剩余的对象指派到最近的中心点所代表的簇 /// /// 指派每个剩余的对象给离它最近的中心点所代表的簇 /// /// 分成k簇 /// 数据 /// 中心点集合 /// public List SetClusterList(int k, List ChangedListStaff, List CentainPoint) { //得到数据的个数 int count = ChangedListStaff.Count; //指派每个剩余的对象给离它最近的中心点所代表的簇 for (int i = 0; i tempPointDistance = new List(); //如果不是中心点(Flag代表是否为中心点,1为中心点) if (!ChangedListStaff[i].Flag.Equals(1)) { //计算剩余的点到每个中心点的距离，然后分到距离最小的那一簇里面 for (int j = 0; j < k; j++) { double tempAge = Math.Pow(ChangedListStaff[i].Age.Value - CentainPoint[j].Age.Value, 2); double tempHeight =Math.Pow(ChangedListStaff[i].Height.Value - CentainPoint[j].Height.Value, 2); double tempWeight = Math.Pow(ChangedListStaff[i].Weight.Value - CentainPoint[j].Weight.Value, 2); double temp = Math.Sqrt(tempAge+tempHeight+tempWeight); tempPointDistance.Add(temp); } double min = tempPointDistance.Min(); int index = tempPointDistance.IndexOf(min); ChangedListStaff[i].Cluster = index; } } return ChangedListStaff;

数据挖掘论文 (4)计算用 Random交换代表对象O的总代价S 7// //代价函数 ///可能成为新中心点这个数据的位置 //原有中心点在数据中的位置 //所有数据(用链表形式进行保存) /// public double Gets (int random, int j, List ListStaff) /获取j中心点属于第几簇 int cluster= ListStaffLj] Cluster Value /获取原中心点数据数据项年龄 gAge ListStaff[j] Age value //获取原中心点数据数据项身高 double orgHeight ListStaff [j].Height Value /获取原中心点数据数据项体重 double orgWeight ListStaff[j]. Weight Value /获取可能成为新中心点数据数据项年龄 int randomAge ListStaff [random] Age Value /获取可能成为新中心点数据数据项身高 double randomHeight ListStaff[random]. Height. Value //获取可能成为新中心点数据数据项体重 double randomWeight ListStaff[random]. Weight value double orgCount =0.0 double random Count =0.0 ub=0.0; //获取这一簇里面存在的所有数据 var clusterStaff from p in Liststaff where p Cluster. Equals(cluster //遍历这一簇所有数据 foreach (var cluserRow in clusterStaff) //计算距离 double orgTempAge Math Pow(orgAge - cluserRow Age Value, 2) double orgTempHeight Math Pow(orgHeight cluserRow. Height value, 2) double orgTemp Weight Math Pow(orgWeight luserRow. Weight. Value, 2) double orgDistance = Math. Sgrt(org TempAge org TempHeight ght)

数据挖掘论文 5 } （4） 计算用 Orandom 交换代表对象 Oj 的总代价 S; /// /// 代价函数 /// /// 可能成为新中心点这个数据的位置 /// 原有中心点在数据中的位置 /// 所有数据(用链表形式进行保存) /// public double GetS(int random, int j, List ListStaff) { //获取j中心点属于第几簇 int cluster = ListStaff[j].Cluster.Value; //获取原中心点数据数据项年龄 int orgAge = ListStaff[j].Age.Value; //获取原中心点数据数据项身高 double orgHeight = ListStaff[j].Height.Value; //获取原中心点数据数据项体重 double orgWeight = ListStaff[j].Weight.Value; //获取可能成为新中心点数据数据项年龄 int randomAge = ListStaff[random].Age.Value; //获取可能成为新中心点数据数据项身高 double randomHeight = ListStaff[random].Height.Value; //获取可能成为新中心点数据数据项体重 double randomWeight = ListStaff[random].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 random TempHeight Math Pow (randomHeight cluserRow. Height Value, 2) double randomTempWeight Math Pow (randomWeight Value, 2) double randomDistance Math Sart (random TempAge randomTempHeight randomTempWeight) orgCount + orgDistance: randomCount + randomDistance //得到交换后它们的代价 sub randomCount - orgCount (5)核心函数k中心点算法函数体内调用了上面的函数 7// ///k中心点算法 7//分成k簇 //原数据 /// K method (int k, List OrgionListStaff) /初始化总代价 double s =0 //判断是否所有的中心点不在变化标志 bool Changed true /初始化一个随机数生成器 Random ccy new Random o //得到所有数据的个数 int count OrgionListStaff Count //初始化整个数据变化后保存的链表集合 List ChangedListStaff new Listo //初始化k个中心点保存链表集合 List CentainPoint this InitCentainPoint(k, OrgionListStaff ChangedListStaff) while(Changed) //指派每个剩余的对象给离它最近的中心点所代表的簇 ChangedListStaff this. SetClusterList(k, OrgionListStaff CentainPoint //得到原始的中心点集合 List firstCentainPoint CentainPoint 6

数据挖掘论文 6 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; } （5） 核心函数 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(ChangedListStaff [random]. Flag. Equals (1)) random ccy. Next(count-1) random f (random ==0) random //得到交换中心点的总代价 s= this Gets(random, j, ChangedListStaff) /如果总代价<0 //将 Random换成新的中心点 ChangedListStaff [random]. Flag =1 //原中心点在数据的位置 int OjIndex= ChangedListStaff. IndexOf( CentainPoint [j]) //把以前的中心点变成普通点 ChangedListStaff [OjIndex] Flag =0 CentainPoint [j] ChangedListStaff[random] /如果经过循环后所有中心点中心点都保持不变,循环结束 f(FirstCentainPoint Equals(CentainPoint)) // Changed为 false后循环结束 Changed fal // Changed为true后循环继续 Changed true return Changedliststaff

数据挖掘论文 7 for (int j = 0; j < k; j++) { //得到一个随机数 int random = 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); //如果总代价 < 0 if (s < 0) { //将Orandom换成新的中心点 ChangedListStaff[random].Flag = 1; //原中心点在数据的位置 int OjIndex = ChangedListStaff.IndexOf(CentainPoint[j]); //把以前的中心点变成普通点 ChangedListStaff[OjIndex].Flag = 0; CentainPoint[j] = ChangedListStaff[random]; } } //如果经过循环后所有中心点中心点都保持不变，循环结束 if (FirstCentainPoint.Equals(CentainPoint)) { //Changed为false后循环结束 Changed = false; } else { //Changed为true后循环继续 Changed = true; } } return ChangedListStaff;

数据挖掘论文 主界面解释 (1)下面是我们软件的初始化主界面(图1-1),我们可以看到它是基于k 中心点算法的一个数据挖掘软件,在右边是我们要进行处理的数据,我们将 数据库中所有数据都提取到出来了,我们可以看到每一条记录有四个属性(姓 名、年龄、身高、体重),而我们这个软件主要是针对其中的三个属性(年龄、 身高、体重)进行数据挖掘,将他们进行数据分组,分组后的数据将会呈现在 左边的分簇后数据的文本框中。 05信息计算1班k中心点算法 开始 数据库数据 分簇后数据 身高 体重 海雪 李含瑞 能玉莉 世玉 张海迪 小龙女 (2)下面展示的是软件进行数据处理后的效果(如图1-2) 我们在界面上输入8,将右边所有的数据分成8组,开始后经过数据处理 展示出来的数据呈现在左边的分簇后数据的文本框中

数据挖掘论文 8 } 三、 主界面解释 （1）下面是我们软件的初始化主界面（图 1-1），我们可以看到它是基于 k 中心点算法的一个数据挖掘软件，在右边是我们要进行处理的数据，我们将 数据库中所有数据都提取到出来了，我们可以看到每一条记录有四个属性(姓 名、年龄、身高、体重)，而我们这个软件主要是针对其中的三个属性(年龄、 身高、体重)进行数据挖掘，将他们进行数据分组，分组后的数据将会呈现在 左边的分簇后数据的文本框中。 图 1-1 （2）下面展示的是软件进行数据处理后的效果(如图 1-2) 我们在界面上输入 8，将右边所有的数据分成 8 组，开始后经过数据处理 展示出来的数据呈现在左边的分簇后数据的文本框中

数据挖掘论文 05信息计算1班k中心点算法 数据库数据 分簇后数据 姓名 体重 第1组:1:邬海莹68岁-165厘米一60公斤 沈强 2组:1:歲玉莉1岁-0厘米-13公斤 杨芸妍 第4组:1:沈毅强20岁-172厘米-75公斤 2:杨芸妍38岁-168厘米一66公斤 3:张海迪2岁-173厘米65公斤 李白 白情 第5组:1:小龙女8岁-167厘米60公斤 令孤冲 第组:1:李白情10岁10厘米-4公斤 张海迪 2:方世玉11岁-130厘米-42公斤 小龙女 岳不群 图1-2 仔细分析左边的分簇后数据的文本框中我们可以发现:各组之间我们通过普 通的心算我们可以发现他们各组之间数据在年龄、身高、体重等综合因素比较下 差距是比较大的,而族类之间的差距却是比较小。比如第1组与第2组,第一组 中数据“邬海莹58岁-165厘米60公斤”与第二组数据“熊玉莉1岁-30厘米13 公斤”,不论从年龄、身高和体重上面来说,他们之间的差距是比较大的,而第 六组他们族类之间的数据比较后我们科研发现,不论是从年龄、身高还是体重方 面他们之间的差距是非常小的。这与比较好的验证了k中心算法对于数据分类效 果还是比较好的。 四、附录(源代码) (1)数据库代码 <? xml version="1.0″ encoding="utf-8″ <configuration

数据挖掘论文 9 图 1-2 仔细分析左边的分簇后数据的文本框中我们可以发现：各组之间我们通过普 通的心算我们可以发现他们各组之间数据在年龄、身高、体重等综合因素比较下 差距是比较大的，而族类之间的差距却是比较小。比如第 1 组与第 2 组，第一组 中数据“邬海莹 58 岁-165 厘米-60 公斤”与第二组数据“熊玉莉 1 岁-30 厘米-13 公斤”，不论从年龄、身高和体重上面来说，他们之间的差距是比较大的，而第 六组他们族类之间的数据比较后我们科研发现，不论是从年龄、身高还是体重方 面他们之间的差距是非常小的。这与比较好的验证了 k 中心算法对于数据分类效 果还是比较好的。 四、 附录(源代码) （1） 数据库代码

数据挖掘论文 K/configSections> ConnectionsTring> Kadd name="Kpam Properties Settings. DataMinConnectionString connectionString="Data Source=: Initial Catalog=DataMin: Integrated Security=True providerName="System. Data Sqlclient"/> K/connectionString> Age private System. Nullable Height private System. Nullable Weight ble Flag private System. Nullableint) Cluster public Staff UnCreated o [Column(Storage=" StaffID", Db Type="NVarChar(50) NOT NULL CanBeNull=false, IsPrimarykey=true) public string StaffID get return this. StaffID [Column(Storage="Name", DbType=" NVarChar(50)")] public string Name ge t return this. Name [ Column(Storage="Age", DbType=Int")] 10

数据挖掘论文 10 数据表存储类型 public partial class Staff : INotifyPropertyChanging, INotifyPropertyChanged { private static PropertyChangingEventArgs emptyChangingEventArgs = new PropertyChangingEventArgs(String.Empty); private string _StaffID; private string _Name; private System.Nullable _Age; private System.Nullable _Height; private System.Nullable _Weight; private System.Nullable _Flag; private System.Nullable _Cluster; public Staff() { OnCreated(); } [Column(Storage="_StaffID", DbType="NVarChar(50) NOT NULL", CanBeNull=false, IsPrimaryKey=true)] public string StaffID { get { return this._StaffID; } } [Column(Storage="_Name", DbType="NVarChar(50)")] public string Name { get { return this._Name; } } [Column(Storage="_Age", DbType="Int")]