数据挖掘算法以及其实现--.doc

《数据挖掘》 实验报告
实验一 分类技术及其应用
实习要求： 基于线性回归模型拟合一个班学生的学习成绩，建立预测模型。数据可由自己建立100个学生的学习成绩。
1） 算法思想：
最小二乘法
设经验方程是y=F(x)，方程中含有一些待定系数an，给出真实值{(xi,yi)|i=1,2,...n},将这些x,y值 代入方程然后作差，可以描述误差：yi-F(xi)，为了考虑整体的误差，可以取平方和，之所以要平方是考虑到误差可正可负直接相加可以相互抵消，所以记 误差为：
e=∑(yi-F(xi))^2
它是一个多元函数，有an共n个未知量，现在要求的是最小值。所以必然满足对各变量的偏导等于0，于是得到n个方程：
de/da1=0
de/da2=0
...
de/dan=0
n个方程确定n个未知量为常量是理论上可以解出来的。用这种误差分析的方法进行回归方程的方法就是最小二乘法。
线性回归
如果经验方程是线性的，形如y=ax+b，就是线性回归。按上面的分析，误差函数为：
e=∑(yi-axi-b)^2
各偏导为：
de/da=2∑(yi-axi-b)xi=0
de/db=-2∑(yi-axi-b)=0
于是得到关于a,b的线性方程组：
(∑xi^2)a+(∑xi)b=∑yixi
(∑xi)a+nb=∑yi
设A=∑xi^2,B=∑xi,C=∑yixi,D=∑yi，则方程化为：
Aa+Bb=C
Ba+nb=D
解出a,b得：
a=(Cn-BD)/(An-BB)
b=(AD-CB)/(An-BB)
2） 编程实现算法
C++程序：
#include
#include
using namespace std;
void main()
{
double x,y,A=0.0,B=0.0,C=0.0,D=0.0,delta,a,b;
int n,sno,avgstudy;
cout<<"请拟合输入样本数目"<>n;
for(int i=0;i>sno;
cout<<"请输入学生上自习时间，按照每天小时计算"<>x;
cout<<"请输入学生请输入平均成绩"<>y;
A+=x*x;
B+=x;
C+=x*y;
D+=y;
}
delta=A*n-B*B;
a=((C*n-B*D)/delta);
b=((A*D-C*B)/delta);
cout<<"a="<>avgstudy;
cout<出层次聚类过程中每一步的聚类结果。
实习题2 利用K-均值聚类算法对如下数据进行聚类，其中输入K=3，数据集为
{ 2，4，10，12，3，20，30，11，25，23，34，22} 。
要求输出每个类及其中的元素。
1)算法基本思想的描述
Given k, the k-means algorithm is implemented in four steps:
– Partition objects into k nonempty subsets
– Compute seed points as the centroids of the clusters of the current partition (the centroid is the center, i.e., mean point, of the cluster)
– Assign each object to the cluster with the nearest seed point
– Go back to Step 2, stop when no more new assignment
2)编程实现算法

//***********引入库函数

#include "iostream.h"
#include "math.h"
#include "stdlib.h"
#include "iomanip.h"
#include "time.h"
#include "fstream.h"

//*************定义常量
const int TRUE=1;
const int FALSE=0;
const int MarkovLengh=10000;
const int MaxInnerLoop=10000;
const int MaxOuterLoop=60;
const double CO=0.1;
const double DeclineRate=0.95;
const long MAX=100000;
const int AcceptRate=1;
const double ForceDecline=0.9;

//************定义全局变量

int DataNum; //聚类样本数目
int Dimension; //样本维数
int K; //分类数
double *DataSet; //指向浮点型的指针
int HALT=0;
int Row=3;

//******************************
// 类GETDATA：设定全局变量，维数，样本数，和类别数等 ***
// 随机生成样本或手工输入样本的类 ***
//***************************************************************

class GETDATA{

public:
GETDATA();
void Display();
void Initial();
void Input();
double FRand(double,double);
double rand1,rand2; //随机数的高低值

};

GETDATA::GETDATA()
{
int i,j;
Dimension=2;
DataNum=50;
K=4;
DataSet=new double[Dimension*DataNum];
for(i=0;iAND_MAX)*100);
}
}

//*****************显示当前待聚类的样本(维数，个数，类别数等)

void GETDATA::Display()
{
int i,j;
cout<<" 当前样本集如下:"< }
cout<<" ] ";
if((i+1)%Row==0)
cout<>Dimension;
cout<>DataNum;
cout<>K;
cout< "<>flag;
if(flag=='R'||flag=='r')
{
cout<<" 输入随机数生成范围(最小值和最大值):"
<>rand1;
cout<>rand2;
for(i=0;insion+j]=FRand(rand1,rand2);
}

}
else
if(flag=='H'||flag=='h')
{
for(i=0;i>DataSet[i*Dimension+j];
}
}
else
cout<
//****************初始化聚类样本

void GETDATA::Initial()
{
char ch;
GETDATA::Display();
cout<>ch;
while(!(ch=='A'||ch=='a')&&!(ch=='B'||ch=='b'))
{
cout<>ch;
}

if(ch=='A'||ch=='a')
GETDATA::Input();
}

double GETDATA::FRand(double rand1,double rand2)
{
return rand1+(double)(((double)rand()/(double)RAND_MAX)*(rand2-rand1));
}

//***********************************************************
// 类SSA: K-均值算法的实现 ***
// 功能：根据设定的K,DataNum,Dimension等聚类 ***
//***********************************************************

class SAA
{
public:
struct DataType
{
double *data;
int father;
double *uncle;
};

struct ClusterType
{
double *center;
int sonnum;

};

SAA();
void Initialize();
void KMeans();
void SA( );
void DisPlay();

void GetDataset(DataType *p1,double *p2,int datanum,int dim);
void GetValue(double *str1,double *str2,int dim);
int FindFather(double *p,int k);
double SquareDistance(double *str1,double *str2,int dim);
int Compare(double *p1,double *p2,int dim);
void NewCenterPlus(ClusterType *p1,int t,double *p2,int dim);
void NewCenterReduce(ClusterType *p1,int t,double *p2,int dim);
double MaxFunc();
void Generate(DataType *p1,ClusterType *c1);
double Compare(DataType *p1,ClusterType *c1,DataType *p2,ClusterType *c2);
void CopyStatus(DataType *p1,ClusterType *c1,DataType *p2,ClusterType *c2);
int SecondFather(DataType *p,int t,int k);
double AimFunction(DataType *q,ClusterType *c);
double FRand(double ,double);
void KMeans1();

protected:

double Temp;
//double CO;
//double DeclineRate;
//int MarkovLengh;
//int MaxInnerLoop;
//int MaxOuterLoop;
double AimFunc;

DataType *DataMember, *KResult,*CurrentStatus,*NewStatus;
ClusterType * ClusterMember,*NewCluster,*CurrentCluster;

}; //end of class SAA

//************建立构造函数，初始化保护成员
SAA::SAA()
{
int i;
// DeclineRate=(double)0.9;
// MarkovLengh=1000;
// MaxInnerLoop200;
// MaxOuterLoop=10;
// CO=1;

DataMember=new DataType[DataNum];
ClusterMember=new ClusterType[K];

for(i=0;ion];

GetDataset(DataMember,DataSet,DataNum,Dimension);

}//endSAA

//****************初始化参数，及开始搜索状态

void SAA::Initialize( )
{

//K-均值聚类法建立退火聚类的初始状态
// KMeans();

}

//*******************k-均值法进行聚类
//************接口：数据，数量，维数，类别
//逐点聚类方式

void SAA::KMeans()
{

int i,j,M=1;
int pa,pb,fa;
ClusterType *OldCluster;

//初始化聚类中心

OldCluster=new ClusterType[K];
for(i=0;i
GetValue(OldCluster[i].center,ClusterMember[i].center,Dimension);
}

for(i=0;ice(DataMember[i].data,ClusterMember[j].center,Dimension);
// cout<<" "<"<=K)
{
// cout<pa<<" 类样本数："<"<er,ClusterMember[pa].center,Dimension);
}
}

//开始聚类，直到聚类中心不再发生变化。××逐个修改法××
while(!HALT)
{
//一次聚类循环：.重新归类；.修改类中心
for(i=0;iember[i].uncle[j]=SquareDistance(DataMember[i].data,ClusterMember[j].center,Dimension);
// cout<"<"<er;

if(fa!=FindFather(DataMember[i].uncle,K)&&ClusterMember[fa].sonnum>1)
{

pa=DataMember[i].father;
ClusterMember[pa].sonnum-=1;

pb=DataMember[i].father=FindFather(DataMember[i].uncle,K);
ClusterMember[pb].sonnum+=1;

NewCenterReduce(ClusterMember,pa,DataMember[i].data,Dimension);
NewCenterPlus(ClusterMember,pb,DataMember[i].data,Dimension);

/* cout< "< cout<ion))
break;
if(j==K)
HALT=1;

for(j=0;jnew ClusterType[K];
for(i=0;i0;j1)
{

pa=DataMember[i].father;
ClusterMember[pa].sonnum-=1;

pb=DataMember[i].father=FindFather(DataMember[i].uncle,K);
ClusterMember[pb].sonnum+=1;

NewCenterReduce(ClusterMember,pa,DataMember[i].data,Dimension);
NewCenterPlus(ClusterMember,pb,DataMember[i].data,Dimension);
}

}//endfor

//判断聚类是否完成，HALT=1,停止聚类
HALT=0;
for(j=0;jpe *p1,int t,double *p2,int dim)
{
int i;
for(i=0;i]-p2[i])/(p1[t].sonnum);
}

void SAA::GetDataset(DataType *p1,double *p2,int datanum,int dim)
{
int i,j;
for(i=0;i str1[i]=str2[i];
}

int SAA::FindFather(double *p,int k)
{
int i,N=0;
double min=30000;

for(i=0;i dis=dis+(double)(str1[i]-str2[i])*(str1[i]-str2[i]);
return dis;
}

int SAA::Compare(double *p1,double *p2,int dim)
{
int i;
for(i=0;iAX)*(b-a));

}

void SAA::DisPlay()
{
int i,N,j,t;
ofstream result("聚类过程结果显示.txt",ios::ate);
for(i=0;i"<

result.close();

}//end of Display

double SAA::AimFunction(DataType *q,ClusterType *c)
{
int i,j;
double *p;
p=new double[K];
for(i=0;idata,Dimension);
}
}

AimFunc=0;
for(i=0;i GETDATA getdata;
getdata.Initial();
ofstream file("聚类过程结果显示.txt",ios::trunc); //聚类结果存入“聚类结果显示.txt”文件中

//k-均值聚类方法聚类
SAA saa; //****此行不可与上行互换。

saa.KMeans(); //逐个样本聚类
// saa.KMeans1(); //批处理方式聚类，可以比较saa.KMeans()的区别
cout<