《数据挖掘论文》基于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<0,then用O替换O,形成新的k个代表对象的集合 (7) until不发生簇的重新分配 二、算法实现 为了实现k中心点算法我们采用的是语言是C#,开发工具是 Micrsoft visual Stdio2008,数据库 SQL Server2000,为了简单的进行模拟,我们使用了3维数据进 行开发,下面将介绍主要的我们软件的主要实现过程。 1、数据库设计: 为了进行实现k中心点算法进行数据挖掘分类,我们设计了一个非 常简单的数据库,里面主要有一张关于人的分类,我们采用了人的年龄 (age)、身高 height)、体重( weight)三个指标进行算法的模拟。 2、主要算法代码 (1)调用数据库,把数据库中的数据提取出来进行挖掘。下面是代码 7// <summary> //初始化数据库对象 7//</summary> DsStaffDataContext DataContext new DsStaffDataContext o 7//<summary> ///获取数据库表中数据 7//</summary> /// <returns>/returns> public List<Staff> GetStaffo //用链表List初始化数据对象 List<staff> aStaff new List<Staff>o //查询数据库中的 Staff表

数据挖掘论文 2 （3） 将每个剩余的对象指派到最近的中心点所代表的簇； （4） 随机地选择一个非代表对象 Orandom ; （5） 计算用 Orandom 交换代表对象 Oj 的总代价 S; （6） If S<0，then 用 Orandom 替换 Oj ，形成新的 k 个代表对象的集合 （7） until 不发生簇的重新分配。 二、 算法实现 为了实现 k 中心点算法我们采用的是语言是 C#，开发工具是 Micrsoft Visual Stdio 2008,数据库 SQL Server2000，为了简单的进行模拟，我们使用了 3 维数据进 行开发，下面将介绍主要的我们软件的主要实现过程。 1、数据库设计： 为了进行实现 k 中心点算法进行数据挖掘分类，我们设计了一个非 常简单的数据库，里面主要有一张关于人的分类，我们采用了人的年龄 （age）、身高(height)、体重(weight)三个指标进行算法的模拟。 2、主要算法代码 （1） 调用数据库，把数据库中的数据提取出来进行挖掘。下面是代码 /// <summary> /// 初始化数据库对象 /// </summary> DsStaffDataContext DataContext = new DsStaffDataContext(); /// <summary> /// 获取数据库表中数据 /// </summary> /// <returns></returns> public List<Staff> GetStaff() { //用链表List初始化数据对象 List<Staff> aStaff = new List<Staff>(); //查询数据库中的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 //< param name="k">分成k簇</ param> //< param name=" OrgionListstaff">原数据</ paran //< param name=" ChangedListstaff">改变后数据< param> /// <returns></returns> public List<Staff> InitCentainPoint(int k, List<Staff> OrgionListStaff out List<Staff> ChangedListStaff) //用链表List初始化数据对象 List<Staff> Staff new List<Staff>(k) //随机数生成器 Random ccy new Random O /保持随机数 Listint> randomList new List<int>o 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 个对象作为初始化的中心点，下面是 实现的函数： /// <summary> /// 初始化中心点 /// </summary> /// <param name="k">分成k簇</param> /// <param name="OrgionListStaff">原数据</param> /// <param name="ChangedListStaff">改变后数据</param> /// <returns></returns> public List<Staff> InitCentainPoint(int k, List<Staff> OrgionListStaff, out List<Staff> ChangedListStaff) { //用链表List初始化数据对象 List<Staff> _Staff = new List<Staff>(k); //随机数生成器 Random ccy = new Random(); //保持随机数 List<int> randomList = new List<int>(); 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/ <summary> ///指派每个剩余的对象给离它最近的中心点所代表的簇 ///< //< param name="k">分成k簇</ param> /// param name="ChangedListStaff" >*E</param> //< param name=" CentainPoint">中心点集合</ param /// <returns>/returns> public List<Staff> SetClusterList(int k, List<Staff> ChangedListStaff List<Staff> CentainPoint //得到数据的个数 int count ChangedListstaff. Count: //指派每个剩余的对象给离它最近的中心点所代表的簇 for (int i=0: i< count; i++) List<double> temp PointDistance new List<double>o //如果不是中心点(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） 将每个剩余的对象指派到最近的中心点所代表的簇 /// <summary> /// 指派每个剩余的对象给离它最近的中心点所代表的簇 /// </summary> /// <param name="k">分成k簇</param> /// <param name="ChangedListStaff">数据</param> /// <param name="CentainPoint">中心点集合</param> /// <returns></returns> public List<Staff> SetClusterList(int k, List<Staff> ChangedListStaff, List<Staff> CentainPoint) { //得到数据的个数 int count = ChangedListStaff.Count; //指派每个剩余的对象给离它最近的中心点所代表的簇 for (int i = 0; i < count; i++) { List<double> tempPointDistance = new List<double>(); //如果不是中心点(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//<summary> //代价函数 ///< param name=" random">可能成为新中心点这个数据的位置</ param> //< param name="j">原有中心点在数据中的位置</ param> //< param name=" ListStaff">所有数据(用链表形式进行保存)</ param> /// <returns></returns> public double Gets (int random, int j, List<Staff> 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; /// <summary> /// 代价函数 /// </summary> /// <param name="random">可能成为新中心点这个数据的位置</param> /// <param name="j">原有中心点在数据中的位置</param> /// <param name="ListStaff">所有数据(用链表形式进行保存)</param> /// <returns></returns> public double GetS(int random, int j, List<Staff> 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);