基于K中心点数据挖掘课程设计论文(原创)
基于K-中心点算法实现
一、 算法描述
k中心点算法：首先为每一个簇随意选择一个代表对象；剩余的对象其与代表的对象的距离分配给最近的一个簇。然后反复的用非代表对象来替代代表对象，以改进聚类的质量。聚类结果的质量用一个代价函数来估算，该函数度量对象与其参与对象之间的平均相异度。为了确定非代表对象
是否是当前代表对象
的好的替代，对于每一个非代表对象P，考虑以下四种情况。
Ø 第一种情况：P当前隶属于代表对象。如果被所取代作为代表对象，并且P离其他代表对象
(i
j)最近，则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 S<0，then 用替换，形成新的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中
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） 将每个剩余的对象指派到最近的中心点所代表的簇
/// <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） 计算用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);
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中心点算法(函数体内调用了上面的函数)
/// <summary>
/// k中心点算法
/// </summary>
/// <param name="k">分成k簇</param>
/// <param name="OrgionListStaff">原数据</param>
/// <returns></returns>
public List<Staff> K_method(int k, List<Staff> OrgionListStaff)
{
//初始化总代价
double s = 0;
//判断是否所有的中心点不在变化标志
bool Changed = true;
//初始化一个随机数生成器
Random ccy = new Random();
//得到所有数据的个数
int count = OrgionListStaff.Count;
//初始化整个数据变化后保存的链表集合
List<Staff> ChangedListStaff = new List<Staff>();
//初始化k个中心点保存链表集合
List<Staff> CentainPoint = this.InitCentainPoint(k, OrgionListStaff, out ChangedListStaff);
while (Changed)
{
//指派每个剩余的对象给离它最近的中心点所代表的簇
ChangedListStaff = this.SetClusterList(k, OrgionListStaff, CentainPoint);
//得到原始的中心点集合
List<Staff> 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);
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中心点算法的一个数据挖掘软件，在右边是我们要进行处理的数据，我们将数据库中所有数据都提取到出来了，我们可以看到每一条记录有四个属性(姓名、年龄、身高、体重)，而我们这个软件主要是针对其中的三个属性(年龄、身高、体重)进行数据挖掘，将他们进行数据分组，分组后的数据将会呈现在左边的分簇后数据的文本框中。
图1-1
（2）下面展示的是软件进行数据处理后的效果(如图1-2)
我们在界面上输入8，将右边所有的数据分成8组，开始后经过数据处理展示出来的数据呈现在左边的分簇后数据的文本框中。
图1-2
仔细分析左边的分簇后数据的文本框中我们可以发现：各组之间我们通过普通的心算我们可以发现他们各组之间数据在年龄、身高、体重等综合因素比较下差距是比较大的，而族类之间的差距却是比较小。比如第1组与第2组，第一组中数据“邬海莹58岁-165厘米-60公斤”与第二组数据“熊玉莉1岁-30厘米-13公斤”，不论从年龄、身高和体重上面来说，他们之间的差距是比较大的，而第六组他们族类之间的数据比较后我们科研发现，不论是从年龄、身高还是体重方面他们之间的差距是非常小的。这与比较好的验证了k中心算法对于数据分类效果还是比较好的。
四、 附录(源代码)
（1） 数据库代码
<?xml version="1.0" encoding="utf-8" ?>
<configuration>
<configSections>
</configSections>
<connectionStrings>
<add name="Kpam.Properties.Settings.DataMinConnectionString"
connectionString="Data Source=.;Initial Catalog=DataMin;Integrated Security=True"
providerName="System.Data.SqlClient" />
</connectionStrings>
</configuration>
数据表存储类型
public partial class Staff : INotifyPropertyChanging, INotifyPropertyChanged
{
private static PropertyChangingEventArgs emptyChangingEventArgs = new PropertyChangingEventArgs(String.Empty);
private string _StaffID;
private string _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="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")]
public System.Nullable<int> Age
{
get
{
return this._Age;
}
}
[Column(Storage="_Height", DbType="Float")]
public System.Nullable<double> Height
{
get
{
return this._Height;
}
}
[Column(Storage="_Weight", DbType="Float")]
public System.Nullable<double> Weight
{
get
{
return this._Weight;
}
}
[Column(Storage="_Flag", DbType="Int")]
public System.Nullable<int> Flag
{
get
{
return this._Flag;
}
}
[Column(Storage="_Cluster", DbType="Int")]
public System.Nullable<int> Cluster
{
get
{
return this._Cluster;
}
}
（2） 基类算法代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace Kpam
{
public class KCentain
{
/// <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中
foreach (Staff aStaffRow in StaffTable)
{
aStaff.Add(aStaffRow);
}
return aStaff;
}
/// <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;
}
/// <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;
}
/// <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);
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;
}
/// <summary>
/// k中心点算法
/// </summary>
/// <param name="k">分成k簇</param>
/// <param name="OrgionListStaff">原数据</param>
/// <returns></returns>
public List<Staff> K_method(int k, List<Staff> OrgionListStaff)
{
//初始化总代价
double s = 0;
//判断是否所有的中心点不在变化标志
bool Changed = true;
//初始化一个随机数生成器
Random ccy = new Random();
//得到所有数据的个数
int count = OrgionListStaff.Count;
//初始化整个数据变化后保存的链表集合
List<Staff> ChangedListStaff = new List<Staff>();
//初始化k个中心点保存链表集合
List<Staff> CentainPoint = this.InitCentainPoint(k, OrgionListStaff, out ChangedListStaff);
while (Changed)
{
//指派每个剩余的对象给离它最近的中心点所代表的簇
ChangedListStaff = this.SetClusterList(k, OrgionListStaff, CentainPoint);
//得到原始的中心点集合
List<Staff> 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);
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;
}
}
}
（3） 界面代码
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;
namespace Kpam
{
public partial class Form1 : Form
{
KCentain kCentain = new KCentain();
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
List<Staff> aStaff = kCentain.GetStaff();
int k = Convert.ToInt32(textBox1.Text);
List<Staff> changeStaff = kCentain.K_method(k, aStaff);
string name = null;
for (int i = 0; i < k; i++)
{
int j = 1;
name = name + "第"+(i+1)+"组：";
foreach (var _staff in changeStaff)
{
if (_staff.Cluster.Equals(i))
{
name +=j.ToString()+":"+ _staff.Name + _staff.Age.ToString()+"岁-"+_staff.Height.ToString()+"厘米-"+_staff.Weight.ToString()+"公斤,";
j++;
}
}
name += "*******；";
}
richTextBox1.Text = name;
}
}
}
-
数据挖掘课程设计报告
ID3算法的改进摘要本文基于ID3算法的原有思路再把属性的重要性程度值纳入了属性选择的度量标准中以期获得更适合实际应用的分类划分结…
-
数据挖掘课程设计
本科课程设计及实验期末成绩评估系统的数据仓库和数据挖掘设计课程名称数据挖掘课程编号08060116学生姓名cwl学号20xx052…
-
数据挖掘课程设计报告正文
目录第1章数据挖掘基本理论211数据挖掘的产生212数据挖掘的概念313数据挖掘的步骤3第2章系统分析421系统用户分析422系统…
-
数据挖掘课程设计报告
数据挖掘课程设计报告题目姓名班级学号关联规则挖掘系统xxxxxx计算机0901xxxxxxxxxxx20xx年6月19日1一设计目…
-
数据挖掘聚类算法课程设计报告
数据挖掘聚类问题PlantsDataSet实验报告1数据源描述11数据特征本实验用到的是关于植物信息的数据集其中包含了每一种植物种…
-
数据挖掘课程设计报告正文
目录第1章数据挖掘基本理论211数据挖掘的产生212数据挖掘的概念313数据挖掘的步骤3第2章系统分析421系统用户分析422系统…
-
数据挖掘课程设计报告
ID3算法的改进摘要本文基于ID3算法的原有思路再把属性的重要性程度值纳入了属性选择的度量标准中以期获得更适合实际应用的分类划分结…
-
数据挖掘课程设计
本科课程设计及实验期末成绩评估系统的数据仓库和数据挖掘设计课程名称数据挖掘课程编号08060116学生姓名cwl学号20xx052…
-
数据挖掘课程设计报告
数据挖掘课程设计报告题目姓名班级学号关联规则挖掘系统xxxxxx计算机0901xxxxxxxxxxx20xx年6月19日1一设计目…
-
数据挖掘课程设计报告
一设计目的1更深的了解关联规则挖掘的原理和算法2能将数据挖掘知识与计算机编程相结合编写出合理的程序3深入了解Apriori算法二设…