基于K中心點數(shù)據(jù)挖掘課程設(shè)計論文

1、基于K-中心點算法實現(xiàn)1、 算法描述k中心點算法：首先為每一個簇隨意選擇一個代表對象；剩余的對象其與代 表的對象的距離分配給最近的一個簇。然后反復的用非代表對象來替代代表對 象，以改進聚類的質(zhì)量。聚類結(jié)果的質(zhì)量用一個代價函數(shù)來估算，該函數(shù)度量對象與其參與對象之間的平均相異度。為了確定非代表對象0.是否是當前代表對象Oj的好的替代，對于每一個非代表對象P,考慮以下四種情況。第一種情況：P當前隸屬于代表對象Oj。如果Oj被Orandom所取代作為代表對象, 并且P離其他代表對象Oi(i#j)最近，則P重新分配給Q。第二種情況：P當前隸屬于代表對象 Oj。如果Oj被Orandom所取代作為代表對象，

2、 并且P離其他代表對象Orandom最近,則P重新分配給Orandom。第三種情況：P當前隸屬于代表對象 Oi , (i # j)。如果Oj被Orandom所取代作為代表 對象，并且P離其他代表對象Oi最近，則對象的隸屬不發(fā)生變化。第四種情況：P當前隸屬于代表對象 Oi , (i#j)。如果Oj被Orandom所取代作為代表 對象，并且P離其他代表對象Orandom最近，則P重新分配給Orandom。下面是我們這次實現(xiàn)這個k中心點算法的具體描述輸入：結(jié)果簇的個數(shù)k和包含n個對象的數(shù)據(jù)集合輸出：k個簇的集合，使得所有對象與其最近中心點的相異度總和最小方法：( 1) 個對象的集合中隨意選取k個對象

3、作為初始化的中心點;( 2) repeat( 3) 將每個剩余的對象指派到最近的中心點所代表的簇；( 4) 隨機地選擇一個非代表對象Orandom ;( 5) 計算用Orandom 交換代表對象Oj 的總代價S;( 6) If S<0, then用0由如替換Oj,形成新的k個代表對象的集合( 7) until 不發(fā)生簇的重新分配。2、 算法實現(xiàn)為了實現(xiàn)k中心點算法我們采用的是語言是C#,開發(fā)工具是Micrsoft VisualStdio 2008數(shù)據(jù)庫,SQL Server200，0 為了簡單的進行模擬，我們使用了3 維數(shù)據(jù)進行開發(fā)，下面將介紹主要的我們軟件的主要實現(xiàn)過程。1、 數(shù) 據(jù)庫

4、設(shè)計：為了進行實現(xiàn)k 中心點算法進行數(shù)據(jù)挖掘分類，我們設(shè)計了一個非常簡單的數(shù)據(jù)庫，里面主要有一張關(guān)于人的分類，我們采用了人的年齡(ag*、身高(height)、體重(weighty個指標進行算法的模擬。2、 主 要算法代碼( 1) 調(diào)用數(shù)據(jù)庫，把數(shù)據(jù)庫中的數(shù)據(jù)提取出來進行挖掘。下面是代碼/ <summary>/ 初始化數(shù)據(jù)庫對象/ </summary>DsStaffDataContext DataContext = new DsStaffDataContext();/ <summary>/ 獲取數(shù)據(jù)庫表中數(shù)據(jù)/ </summary>/ <r

5、eturns></returns>public List<Staff> GetStaff()/ 用鏈表 List 初始化數(shù)據(jù)對象List<Staff> aStaff = new List<Staff>();/ 查詢數(shù)據(jù)庫中的Staff 表var StaffTable = from p in DataContext.Staffsselect p;/ 遍歷查詢出來的表，然后將每一條記錄放入初始化的鏈表List 對象 aStaff 中foreach (Staff aStaffRow in StaffTable)aStaff.Add(aStaffR

6、ow);return aStaff;( 2) 從 n 個對象的集合中隨意選取k 個對象作為初始化的中心點，下面是實現(xiàn)的函數(shù)：/ <summary>/ 初始化中心點/ </summary>/ <param name="k"> 分成 k簇 </param>/ <param name="OrgionListStaff">原數(shù)據(jù) </param>/ <param name="ChangedListStaff">改變后數(shù)據(jù)</param>/ <

7、returns></returns>public List<Staff> InitCentainPoint(int k, List<Staff> OrgionListStaff,out List<Staff> ChangedListStaff)/ 用鏈表 List 初始化數(shù)據(jù)對象List<Staff> _Staff = new List<Staff>(k);/隨機數(shù)生成器Random ccy = new Random();/保持隨機數(shù)List<int> randomList = new List<i

8、nt>();for (int i = 0; i < k; i+)/生成一個隨機數(shù)int random = ccy.Next(OrgionListStaff.Count - 1);/ 當隨機數(shù)集合中已經(jīng)存在這個隨機數(shù)的時候從新篩選，以免重復選擇中心點while (randomList.Contains(random)random = ccy.Next(OrgionListStaff.Count - 1);randomList.Add(random);Staff aStaff = OrgionListStaffrandom;/屬于第幾簇OrgionListStaffrandom.Clu

9、ster = i;/當前為中心點OrgionListStaffrandom.Flag = 1;_Staff.Add(aStaff);ChangedListStaff = OrgionListStaff;return _Staff;( 3) 將每個剩余的對象指派到最近的中心點所代表的簇/ <summary>/ 指派每個剩余的對象給離它最近的中心點所代表的簇/ </summary>/ <param name="k"> 分成 k簇 </param>/ <param name="ChangedListStaff&quo

10、t;>數(shù)據(jù) </param>/ <param name="CentainPoint">中心點集合</param>/ <returns></returns>public List<Staff> SetClusterList(int k, List<Staff> ChangedListStaff,List<Staff> CentainPoint)/得到數(shù)據(jù)的個數(shù)int count = ChangedListStaff.Count;/指派每個剩余的對象給離它最近的中心點所代表的簇

11、for (int i = 0; i < count; i+)List<double> tempPointDistance = new List<double>();/如果不是中心點(Flag 代表是否為中心點,1 為中心點)if (!ChangedListStaffi.Flag.Equals(1)/計算剩余的點到每個中心點的距離，然后分到距離最小的那一簇里面for (int j = 0; j < k; j+)double tempAge = Math.Pow(ChangedListStaffi.Age.Value -CentainPointj.Age.Val

12、ue, 2);doubletempHeight =Math.Pow(ChangedListStaffi.Height.Value- CentainPointj.Height.Value, 2);doubletempWeight = Math.Pow(ChangedListStaffi.Weight.Value- CentainPointj.Weight.Value, 2);double temp = Math.Sqrt(tempAge+tempHeight+tempWeight);tempPointDistance.Add(temp);double min = tempPointDistanc

13、e.Min();int index = tempPointDistance.IndexOf(min);ChangedListStaffi.Cluster = index;return ChangedListStaff;(4)計算用Orandom交換代表對象Oj的總代價S;/ <summary>/ 代價函數(shù)/ </summary>/ <param name="random"> 可能成為新中心點這個數(shù)據(jù)的位置</param>/ <param name="j"> 原有中心點在數(shù)據(jù)中的位置</pa

14、ram>/ <param name="ListStaff">所有數(shù)據(jù)( 用鏈表形式進行保存)</param>/ <returns></returns>public double GetS(int random, int j, List<Staff> ListStaff)/ 獲取 j 中心點屬于第幾簇int cluster = ListStaffj.Cluster.Value;/獲取原中心點數(shù)據(jù)數(shù)據(jù)項年齡int orgAge = ListStaffj.Age.Value;/獲取原中心點數(shù)據(jù)數(shù)據(jù)項身高double

15、 orgHeight = ListStaffj.Height.Value;/獲取原中心點數(shù)據(jù)數(shù)據(jù)項體重double orgWeight = ListStaffj.Weight.Value;/獲取可能成為新中心點數(shù)據(jù)數(shù)據(jù)項年齡int randomAge = ListStaffrandom.Age.Value;/獲取可能成為新中心點數(shù)據(jù)數(shù)據(jù)項身高double randomHeight = ListStaffrandom.Height.Value;/獲取可能成為新中心點數(shù)據(jù)數(shù)據(jù)項體重double randomWeight = ListStaffrandom.Weight.Value;double o

16、rgCount = 0.0;double randomCount = 0.0;double sub = 0.0;/ 獲取這一簇里面存在的所有數(shù)據(jù)var clusterStaff = from p in ListStaffwhere p.Cluster.Equals(cluster) select p;/ 遍歷這一簇所有數(shù)據(jù)foreach (var cluserRow in clusterStaff)/計算距離double orgTempAge = Math.Pow(orgAge - cluserRow.Age.Value, 2);double orgTempHeight = Math.Pow(

17、orgHeight -cluserRow.Height.Value, 2);double orgTempWeight = Math.Pow(orgWeight -cluserRow.Weight.Value, 2);double orgDistance = Math.Sqrt(orgTempAge + orgTempHeight +orgTempWeight);doublerandomTempAge= Math.Pow(randomAge - cluserRow.Age.Value, 2);double randomTempHeight = Math.Pow(randomHeight -clu

18、serRow.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)核心函數(shù)

19、k 中心點算法(函數(shù)體內(nèi)調(diào)用了上面的函數(shù))/ <summary>/ k 中心點算法/ </summary>/ <param name="k">分成 k簇 </param>/ <param name="OrgionListStaff">原數(shù)據(jù) </param>/ <returns></returns>public List<Staff> K_method(int k, List<Staff> OrgionListStaff)/ 初始化總代

20、價double s = 0;/判斷是否所有的中心點不在變化標志bool Changed = true;/初始化一個隨機數(shù)生成器Random ccy = new Random();/得到所有數(shù)據(jù)的個數(shù)int count = OrgionListStaff.Count;/初始化整個數(shù)據(jù)變化后保存的鏈表集合List<Staff> ChangedListStaff = new List<Staff>();/ 初始化k個中心點保存鏈表集合List<Staff> CentainPoint =this.InitCentainPoint(k, OrgionListStaff

21、,out ChangedListStaff);while (Changed)/指派每個剩余的對象給離它最近的中心點所代表的簇ChangedListStaff = this.SetClusterList(k, OrgionListStaff,CentainPoint);/得到原始的中心點集合List<Staff> FirstCentainPoint = CentainPoint;for (int j = 0; j < k; j+)/得到一個隨機數(shù)int random = ccy.Next(count - 1);/如果這個數(shù)據(jù)是中心點，重新得到一個新的隨機數(shù)(Flag 是中心點標

22、志)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);/如果總代價< 0if (s < 0)/將Orandom換成新的中心點ChangedListStaffrandom.Flag = 1;/原中心點在數(shù)據(jù)的位置intOjIndex = ChangedListS

23、taff.IndexOf(CentainPointj);/把以前的中心點變成普通點ChangedListStaffOjIndex.Flag = 0;CentainPointj = ChangedListStaffrandom;/如果經(jīng)過循環(huán)后所有中心點中心點都保持不變，循環(huán)結(jié)束if (FirstCentainPoint.Equals(CentainPoint)/Changed為 false 后循環(huán)結(jié)束Changed = false;else/Changed為 true 后循環(huán)繼續(xù)Changed = true;return ChangedListStaff;三、主界面解釋（1）下面是我們軟件的初

24、始化主界面（圖 1-1）,我們可以看到它是基于 k 中心點算法的一個數(shù)據(jù)挖掘軟件，在右邊是我們要進行處理的數(shù)據(jù)，我們將 數(shù)據(jù)庫中所有數(shù)據(jù)都提取到出來了，我們可以看到每一條記錄有四個屬性（姓 名、年齡、身高、體重），而我們這個軟件主要是針對其中的三個屬性（年齡、 身高、體重）進行數(shù)據(jù)挖掘，將他們進行數(shù)據(jù)分組，分組后的數(shù)據(jù)將會呈現(xiàn)在左邊的分簇后數(shù)據(jù)的文本框中圖1-1（2）下面展示的是軟件進彳T數(shù)據(jù)處理后的效果 （如圖1-2）我們在界面上輸入8,將右邊所有的數(shù)據(jù)分成 8組，開始后經(jīng)過數(shù)據(jù)處理展示出來的數(shù)據(jù)呈現(xiàn)在左邊的分簇后數(shù)據(jù)的文本框中圖1-2仔細分析左邊的分簇后數(shù)據(jù)的文本框中我們可以發(fā)現(xiàn)：各組之間

25、我們通過普通的心算我們可以發(fā)現(xiàn)他們各組之間數(shù)據(jù)在年齡、身高、體重等綜合因素比較下差距是比較大的，而族類之間的差距卻是比較小。比如第 1組與第2組，第一組 中數(shù)據(jù)“鄒?，?8歲-165厘米-60公斤”與第二組數(shù)據(jù)“熊玉莉1歲-30厘米-13 公斤”，不論從年齡、身高和體重上面來說，他們之間的差距是比較大的，而第 六組他們族類之間的數(shù)據(jù)比較后我們科研發(fā)現(xiàn)，不論是從年齡、身高還是體重方面他們之間的差距是非常小的。這與比較好的驗證了 k中心算法對于數(shù)據(jù)分類效 果還是比較好的。四、附錄(源代碼)(1)數(shù)據(jù)庫代碼<?xml version="1.0" encoding="

26、;utf-8" ?><configuration><configSections></configSections><connectionStrings><add name="Kpam.Properties.Settings.DataMinConnectionString"connectionString="Data Source=.;Initial Catalog=DataMin;IntegratedSecurity=True"providerName="System.Da

27、ta.SqlClient" /></connectionStrings></configuration>數(shù)據(jù)表存儲類型public partial class Staff : INotifyPropertyChanging, INotifyPropertyChangedprivate static PropertyChangingEventArgs emptyChangingEventArgs = new PropertyChangingEventArgs(String.Empty);private string _StaffID;private str

28、ing _Name;private System.Nullable<int> _Age;private System.Nullable<double> _Height;private System.Nullable<double> _Weight;private System.Nullable<int> _Flag;private System.Nullable<int> _Cluster;public Staff()OnCreated();Column(Storage="_StaffID", DbType=&qu

29、ot;NVarChar(50) NOT NULL", CanBeNull=false, IsPrimaryKey=true)public string StaffIDgetreturn this._StaffID;Column(Storage="_Name", DbType="NVarChar(50)")public string Namegetreturn this._Name;Column(Storage="_Age", DbType="Int")public System.Nullable<i

30、nt> Agegetreturn this._Age;Column(Storage="_Height", DbType="Float") public System.Nullable<double> Height getreturn this._Height;Column(Storage="_Weight", DbType="Float") public System.Nullable<double> Weight getreturn this._Weight;Column(Stora

31、ge="_Flag", DbType="Int") public System.Nullable<int> Flag getreturn this._Flag;Column(Storage="_Cluster", DbType="Int") public System.Nullable<int> Cluster getreturn this._Cluster;(2)基類算法代碼using System;using System.Collections.Generic;using System

32、.Linq;using System.Text;using System.Collections;namespace Kpampublic class KCentain/ <summary>/ 初始化數(shù)據(jù)庫對象/ </summary>DsStaffDataContext DataContext = new DsStaffDataContext();/ <summary>/ 獲取數(shù)據(jù)庫表中數(shù)據(jù)/ </summary>/ <returns></returns>public List<Staff> GetStaff(

33、)/ 用鏈表 List 初始化數(shù)據(jù)對象List<Staff> aStaff = new List<Staff>();/ 查詢數(shù)據(jù)庫中的Staff 表var StaffTable = from p in DataContext.Staffs select p;/ 遍歷查詢出來的表，然后將每一條記錄放入初始化的鏈表List 對象 aStaff 中foreach (Staff aStaffRow in StaffTable)aStaff.Add(aStaffRow);return aStaff;/ <summary>/ 初始化中心點/ </summary&g

34、t;/ <param name="k"> 分成 k簇 </param>/ <param name="OrgionListStaff">原數(shù)據(jù) </param>/ <param name="ChangedListStaff">改變后數(shù)據(jù)</param>/ <returns></returns>public List<Staff> InitCentainPoint(int k, List<Staff> OrgionLis

35、tStaff, out List<Staff> ChangedListStaff)/ 用鏈表 List 初始化數(shù)據(jù)對象List<Staff> _Staff = new List<Staff>(k);/隨機數(shù)生成器Random ccy = new Random();/保持隨機數(shù)List<int> randomList = new List<int>();for (int i = 0; i < k; i+)/生成一個隨機數(shù)int random = ccy.Next(OrgionListStaff.Count - 1);/ 當隨機數(shù)集

36、合中已經(jīng)存在這個隨機數(shù)的時候從新篩選，以免重復選擇中心點while (randomList.Contains(random)random = ccy.Next(OrgionListStaff.Count - 1);randomList.Add(random);Staff aStaff = OrgionListStaffrandom;/屬于第幾簇OrgionListStaffrandom.Cluster = i;/當前為中心點OrgionListStaffrandom.Flag = 1;_Staff.Add(aStaff);ChangedListStaff = OrgionListStaff;r

37、eturn _Staff;/ <summary>/ 指派每個剩余的對象給離它最近的中心點所代表的簇/ </summary>/ <param name="k"> 分成 k簇 </param>/ <param name="ChangedListStaff">數(shù)據(jù) </param>/ <param name="CentainPoint">中心點集合</param>/ <returns></returns>public Li

38、st<Staff> SetClusterList(int k, List<Staff> ChangedListStaff, List<Staff> CentainPoint)/得到數(shù)據(jù)的個數(shù)int count = ChangedListStaff.Count;/指派每個剩余的對象給離它最近的中心點所代表的簇for (int i = 0; i < count; i+)List<double> tempPointDistance = new List<double>();/如果不是中心點(Flag 代表是否為中心點,1 為中心點)i

39、f (!ChangedListStaffi.Flag.Equals(1)/計算剩余的點到每個中心點的距離，然后分到距離最小的那一簇里面for (int j = 0; j < k; j+)doubletempAge = Math.Pow(ChangedListStaffi.Age.Value CentainPointj.Age.Value, 2);double tempHeight =Math.Pow(ChangedListStaffi.Height.Value - CentainPointj.Height.Value, 2);double tempWeight =Math.Pow(Cha

40、ngedListStaffi.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;/ <summary>/

41、 代價函數(shù)/ </summary>/ <param name="random"> 可能成為新中心點這個數(shù)據(jù)的位置</param>/ <param name="j"> 原有中心點在數(shù)據(jù)中的位置</param>/ <param name="ListStaff">所有數(shù)據(jù)( 用鏈表形式進行保存)</param>/ <returns></returns>public double GetS(int random, int j, List

42、<Staff> ListStaff)/ 獲取 j 中心點屬于第幾簇int cluster = ListStaffj.Cluster.Value;/獲取原中心點數(shù)據(jù)數(shù)據(jù)項年齡int orgAge = ListStaffj.Age.Value;/獲取原中心點數(shù)據(jù)數(shù)據(jù)項身高double orgHeight = ListStaffj.Height.Value;/獲取原中心點數(shù)據(jù)數(shù)據(jù)項體重double orgWeight = ListStaffj.Weight.Value;/獲取可能成為新中心點數(shù)據(jù)數(shù)據(jù)項年齡int randomAge = ListStaffrandom.Age.Value;

43、/獲取可能成為新中心點數(shù)據(jù)數(shù)據(jù)項身高double randomHeight = ListStaffrandom.Height.Value;/獲取可能成為新中心點數(shù)據(jù)數(shù)據(jù)項體重double randomWeight = ListStaffrandom.Weight.Value;double orgCount = 0.0;double randomCount = 0.0;double sub = 0.0;/ 獲取這一簇里面存在的所有數(shù)據(jù)var clusterStaff = from p in ListStaffwhere p.Cluster.Equals(cluster) select p;/ 遍

44、歷這一簇所有數(shù)據(jù)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 + or

45、gTempHeight + orgTempWeight);doublerandomTempAge= 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 + ran

46、domTempHeight + randomTempWeight);orgCount += orgDistance;randomCount += randomDistance;/ 得到交換后它們的代價sub = randomCount - orgCount;return sub;/ <summary>/ k 中心點算法/ </summary>/ <param name="k">分成 k簇 </param>/ <param name="OrgionListStaff">原數(shù)據(jù) </param

47、>/ <returns></returns>public List<Staff> K_method(int k, List<Staff> OrgionListStaff)/ 初始化總代價double s = 0;/判斷是否所有的中心點不在變化標志bool Changed = true;/初始化一個隨機數(shù)生成器Random ccy = new Random();/得到所有數(shù)據(jù)的個數(shù)int count = OrgionListStaff.Count;/初始化整個數(shù)據(jù)變化后保存的鏈表集合List<Staff> ChangedListS

48、taff = new List<Staff>();/ 初始化k個中心點保存鏈表集合List<Staff> CentainPoint =this.InitCentainPoint(k, OrgionListStaff,out ChangedListStaff);while (Changed)/指派每個剩余的對象給離它最近的中心點所代表的簇ChangedListStaff = this.SetClusterList(k, OrgionListStaff, CentainPoint);/得到原始的中心點集合List<Staff> FirstCentainPoint = Cent