叶志伟数据挖掘实验指导书（算法编程部分）

《数据挖掘与数据仓库》实验指导书

2013年

计算机学院计算应用

实验1 Apriori算法实现

一、实验目的

1、掌握Apriori算法对于关联规则挖掘中频繁集的产生以及关联规则集合的产生过程； 2、根据算法描述编程实现算法，调试运行。并结合相关实验数据进行应用，得到分析结果。 数据和删除数据的操作。 实验类型：综合 计划课间：2学时

二、实验内容

1、频繁项集的生成与Apriori算法实现；

2、关联规则的生成过程与Rule-generate算法实现； 3、结合样例对算法进行分析；

三、实验步骤

编写程序完成下列算法： 1、Apriori算法

输入： 数据集D；最小支持数minsup_count； 输出： 频繁项目集L L1={large 1-itemsets} For (k=2; Lk-1≠Φ; k++)

Ck=apriori-gen (Lk-1); // Ck是k个元素的候选集 For all transactions t∈D do

begin Ct=subset(Ck,t); //Ct是所有t包含的候选集元素 for all candidates c ∈Ct do c.count++; end

Lk={c ∈Ck| c.count ≧ minsup_count } End L=∪Lk;

2、apriori-gen (Lk-1) 候选集产生算法 输入： (k-1)-频繁项目集Lk-1 输出： k-频繁项目集Ck

For all itemset p∈Lk-1 do For all itemset q∈Lk-1 do

If p.item1=q.item1, p.item2=q.item2, …,p.itemk-2=q.itemk-2, p.itemk-1

if has_infrequent_subset(c, Lk-1) then delete c else add c to Ck End Return Ck

3、has_infrequent_subset(c, Lk-1) 功能：判断候选集的元素

输入： 一个k-频繁项目集Lk-1 ，(k-1)-频繁项目集Lk-1 输出：c是否从候选集中删除的布尔判断 For all (k-1)-subsets of c do If Not(S∈Lk-1) THEN return TRUE; Return FALSE;

4、Rule-generate(L,minconf) 输入：频繁项目集；最小信任度 输出：强关联规则 算法：

FOR each frequent itemset lk in L generules(lk,lk);

5、Genrules递归算法：

Genrules(lk:frequent k-itemset, xm:frequent m-itemset) X={(m-1)-itemsets xm-1 | xm-1 in xm}; For each xm-1 in X

BEGIN conf=support(lk)/support(xm-1); IF (conf≧minconf) THEN

BEGIN

输出规则:xm-1->(lk-xm-1),support,confidence; IF (m-1)>1) THEN genrules(lk,xm-1); END; END;

结合相关样例数据对算法进行调试，并根据相关实验结果对数据进行分析， 四、实验报告要求

1、用C语言或者其他语言实现上述相关算法。

2、实验操作步骤和实验结果，实验中出现的问题和解决方法。 五、注意事项

1、集合的表示及相关操作的实现； 2、项目集的数据结构描述；

参考核心代码如下：（相关的测试main函数可以自己书写。根据频繁k项集生成关联规则相对简单，只需要计算最小置信度即可从频繁K项集中找到所有的满足条件的关联规则。）

//对事物进行第一次扫描，生成频繁一项集，并返回一项集中个数 int init_pass(char *item,char tran[len_t][len],int len,char res_item[len_t][len],float min_sup) {

float t_sup; int number=0;

for(int i=0;i

int count=0;

for(int j=0;j

for(int k=0;k

if(item[i]==tran[j][k]) { }

count++; break;

}

}

}

break;

t_sup=count*1.0/len; if(t_sup>=min_sup)

res_item[number++][0]=item[i];

return number-1;

//生成候选K项集，返回k项集中事物的个数

int candidate_gen(char ktran[len][k],char kktran[len][k+1]) {

char temp[k],temp1[k],ktemp[k+1]; int number=0;

for(int i=0;i

strcpy(temp,ktran[i]); bool flag;

for(j=i+1;j

strcpy(temp1,ktran[i]); for(int m=0;m

if((m

flag=false; break; continue; flag=true;

}

}

}

{ }

if(temp[k-1]>temp1[k-1]) { } else { } break;

strcpy(ktemp,temp); ktemp[k]=temp1[k-1] strcpy(ktemp,temp1); ktemp[k]=temp[k-1];

flag=judge(kemp,ktran[len][k]); if(flag==true)

strcpy(kktran[number++],ktemp);

return number-1;

//判断子集是否在k项集中

bool judge(char *srcstr,char desstr[len][k]) {

char temp[k]; int count=0;

for(int i=0;i

for(int j=0;j

temp[j]=srcstr[j];

for(int j=i+1;j

temp[j]=srcstr[j];

for(int p=0;p

}

}

if(strcmp(temp,desstr[i])==0) { }

count++; break;

if(count==k-1)

return true;

return false;

//apriori算法

int apriori(char item[len],char tran[length][len],char res_tran[length][len],float min_sup) {

char ttran[length][len]; int number,count,t_num; for(int i=0;i

for(int j=0;j

ttran[i][j]='0';

number=init_pass(item,tran[length][len],len,ttran[length][len],min_sup); for(int i=0i

res_tran[i][0]=ttran[i][0];

for(int k=2;number!=0;k++) {

t_num=number;

number=candidate_gen(res_item[number][k-1],ttran[number][k]); if(k==2)

continue;

else {

count=0;

for(int i=0;i

}

}

{ }

char temp[k];

strcpy(temp,ttran[i]); bool t_flag=false; for(int j=0;j

{//求出候选K项集中每个事物的支持计数 }

if(count/length > min_sup)

strcpy(res_item[i],temp); int t_k=0;

for(int n=0;n

if(t_flag==true)

count++;

bool m_flag=false for(int g=t_k;g

if(m_flag==true && n==k-1)

t_flag=true;

if(temp[k]==tran[j][g]) { }

m_flag=true; t_k=g; break;

flag = false;

count=0;

return t_num; }

实验2-1 ID3算法实现

一、实验目的

通过编程实现决策树算法，信息增益的计算、数据子集划分、决策树的构建过程。加深对相关算法的理解过程。 实验类型：综合 计划课间：4学时

二、实验内容

1、分析决策树算法的实现流程；

2、分析信息增益的计算、数据子集划分、决策树的构建过程； 3、根据算法描述编程实现算法，调试运行；

三、实验方法

算法描述：

以代表训练样本的单个结点开始建树；

若样本都在同一个类，则该结点成为树叶，并用该类标记；

否则，算法使用信息增益作为启发信息，选择能够最好地将样本分类的属性； 对测试属性的每个已知值，创建一个分支，并据此划分样本； 算法使用同样的过程，递归形成每个划分上的样本决策树 递归划分步骤，当下列条件之一成立时停止： 给定结点的所有样本属于同一类；

没有剩余属性可以进一步划分样本，在此情况下，采用多数表决进行

四、实验步骤

1、算法实现过程中需要使用的数据结构描述： Struct

{int Attrib_Col; // 当前节点对应属性 int Value; // 对应边值 Tree_Node* Left_Node; // 子树

Tree_Node* Right_Node // 同层其他节点 Boolean IsLeaf; // 是否叶子节点 int ClassNo; // 对应分类标号 }Tree_Node;

2、整体算法流程 主程序：

InputData();

T=Build_ID3(Data,Record_No, Num_Attrib); OutputRule(T); 释放内存; 3、相关子函数： 3.1、 InputData()

{

输入属性集大小Num_Attrib; 输入样本数Num_Record;

分配内存Data[Num_Record][Num_Attrib];

输入样本数据Data[Num_Record][Num_Attrib]； 获取类别数C(从最后一列中得到); }

3.2、Build_ID3(Data,Record_No, Num_Attrib)

{

Int Class_Distribute[C];

If (Record_No==0) { return Null }

N=new tree_node();

计算Data中各类的分布情况存入Class_Distribute Temp_Num_Attrib=0;

For (i=0;i

If (Data[0][i]>=0) Temp_Num_Attrib++; If Temp_Num_Attrib==0 {

N->ClassNo=最多的类； N->IsLeaf=TRUE;

N->Left_Node=NULL;N->Right_Node=NULL; Return N;

}

If Class_Distribute中仅一类的分布大于0 {

N->ClassNo=该类； N->IsLeaf=TRUE;

N->Left_Node=NULL;N->Right_Node=NULL; Return N; }

InforGain=0;CurrentCol=-1;

For i=0;i

TempGain=Compute_InforGain(Data,Record_No,I,Num_Attrib); If (InforGain

{ InforGain=TempGain; CurrentCol=I;} }

N->Attrib_Col=CurrentCol;

//记录CurrentCol所对应的不同值放入DiferentValue[]； I=0;Value_No=-1; While i

For (k=0;k

if (DiferentValu[k]=Data[i][CurrentCol]) flag=true; if (flag==false)

{Value_No++;DiferentValue[Value_No]=Data[i][CurrentCol] } I++; }

SubData=以Data大小申请内存空间； For (i=0;i

k=-1;

for (j=0;j

if (Data[j][CurrentCol]==DiferentValu[i]) {k=k++;

For(int i1=0;i1

If (i1<>CurrentCol)SubData[k][i1]=Data[j][i1]; Else SubData[k][i1]=-1; }

N->Attrib_Col=CurrentCol; N->Value=DiferentValu[i]; N->Isleaf=false; N->ClassNo=0;

N->Left_Node=Build_ID3(SubData,k+1, Num_Attrib); N->Right_Node=new Tree_Node; N=N->Right_Node; } }

3.3、计算信息增益

Compute_InforGain(Data,Record_No, Col_No, Num_Attrib)

{

Int DifferentValue[MaxDifferentValue]; Int Total_DifferentValue;

Int s[ClassNo][MaxDifferentValue];

s=0;// 数组清0;

Total_DifferentValue=-1; For (i=0;i

J=GetPosition(DifferentValue,

Total_DifferentValue,Data[i][Col_no]); If (j<0) {Total_DifferentValue++;

DifferentValue[Total_DifferentValue]=Data[i][Col_no]; J=Total_DifferentValue;}

S[Data[i][Num_Attrib-1]][j]++; }

Total_I=0;

For (i=0;i

Sum=0;

For(j=0;j

For (i=0;i

{ temp=0;sj=0; //sj是数据子集中属于类j的样本个数； For (j=0;j

For (j=0;j

EA+=sj/Record_No*Compute_PI(s[j][i]/sj); }

Return total_I-EA; }

3.4、得到某数字在数组中的位置 GetPosition(Data, DataSize,Value) {

For (i=0;i

3.5、计算Pi*LogPi

Float Compute_PI(float pi) {

If pi<=0 then return 0; If pi>=1 then return 0; Return 0-pi*log2(pi); }

五、实验报告要求

1、用C语言或者其他语言实现上述相关算法。

2、实验操作步骤和实验结果，实验中出现的问题和解决方法。

六、注意事项

1、信息增益的计算；

2、选择相关字段后根据相关字段的取值对数据集合进行划分。 3、决策树构建的终止条件

数据挖掘实验指导书

实验2-2 贝叶斯算法实现

一、实验目的

通过对贝叶斯算法的编程实现，加深对贝叶斯算法的理解，同时利用贝叶斯算法对简单应用实现预测分类 实验类型：综合 计划课间：2学时

二、实验内容

1、分析贝叶斯算法； 2、计算条件概率； 3、预测精度的计算与评估；

4、编程实现贝叶斯分类算法，并对简单应用样本数据实现预测分类

5. 参考实验数据http://archive.ics.uci.edu/ml/machine-learning-databases/wine/

三、实验方法

1、 实现贝叶斯算法

2、 利用实验数据对贝叶斯算法进行检测 3、 求解精确度计算 4、 调试程序

5、 完成整个分类与评估的过程

四、实验步骤

4.1 算法过程描述：

1）输入训练数据，将数据保存在DataBase二维数组中(数组的最后一个属性对应类别标号) 2）设定训练数据集与测试数据集大小(指定从数组下标0开始到TrainSetSize-1所对应的数据为训练数据，其余为测试数据)；

3）计算训练数据集数据中各属性在各类中的概率分布情况； 4）利用测试数据计算贝叶斯算法的分类精度； 5）输出分类结果； 4.2 数据处理

第14页

数据挖掘实验指导书

A、实验数据 RID 1 2 3 4 5 6 7 8 9 10 11 12 13 14 age ≦30 ≦30 31~40 >40 >40 >40 31~40 ≦30 ≦30 >40 ≦30 31~40 31~40 >40 income High High High med Low Low Low Med Low Med Med Med High med student Credit_rating No No No No Yes Yes Yes No Yes Yes Yes No Yes No Fair Excellent Fair Fair Fair Excellent Excellent Fair Fair Fair Excellent Excellent Fair Excellent BuyComputer No No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes No B、对数据中的枚举类型数据进行转换以便于数据处理：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0 0 1 2 2 2 1 0 0 2 0 1 1 2 1 0 0 0 1 2 2 2 1 2 1 1 1 0 1 2 0 0 0 0 1 1 1 0 1 1 1 0 1 0 3 0 1 0 0 0 1 1 0 0 0 1 1 0 1 ClassNo 0 0 1 1 1 0 1 0 1 1 1 1 1 0 4.3 计算训练数据集数据中各属性在各类中的概率分布情况如图3-1所示 4.4 利用测试数据计算贝叶斯算法的分类精度如图3-2所示

第15页

数据挖掘实验指导书

No AttributeDistribute[i][DataBase[j][i]][DataBase[j][AttSetSize-1]]++ AttributeDistribute[i][0][DataBase[j][AttSetSize-1]]++ Yes No j 图3-1 训练数据集各属性的概率分布计算

第16页

数据挖掘实验指导书

申请ClassSize*ClassSize个空间?Precise Presize?0 ; AttrClassDis?0 For (i=0;i

图3-2 贝叶斯算法的分类精度计算

4.5 输出分类结果

For (i=0;i

For (j=0;j

printf(“\\n\\nTotal Correct is%d”,TotalCorrect);

五、注意事项

注意单个样例数据的概率计算与各字段的概率计算的关系

第17页

数据挖掘实验指导书

参考代码 (对参考数据的代码)

BayesianClassifier.h #include #include #include #include #include #include #include

// 4) Alcalinity of ash // 5) Magnesium // 6) Total phenols // 7) Flavanoids

// 8) Nonflavanoid phenols // 9) Proanthocyanins // 10)Color intensity // 11)Hue

// 12)OD280/OD315 of diluted wines // 13)Proline int TrainNum = 130; 训练数据的范围 int TestNum = 48;

struct OriginalData { double A1; double A2; double A3; double A4; double A5; double A6; double A7; double A8; double A9; double A10; double A11; double A12; double A13; double A14; };

BayesianClassifier.cpp #include #include #include

#include %using namespace std;

const int Shuxing=13;//属性总数 ifstream f;

vector trainData; //存放训练数据

第18页

//所有

数据挖掘实验指导书

vector testData; //存放测试数据 double A[3]; //先验概率 int m;

//存放每一类型，每种属性中某数值的概率 map C1_map[Shuxing]; map C2_map[Shuxing]; map C3_map[Shuxing]; //从文件中读取数值

void DataRead(vector &data, const char* fileName) { f.open(fileName); int ZHjiang; if (fileName[0] == 'w') ZHjiang = TrainNum; else ZHjiang = TestNum; string line; OriginalData wine; for (int i = 0; i < ZHjiang; i++) { f >> line; while (line.find(',') > 0 && line.find(',') < line.length()) { line[line.find(',')] = ' '; } istringstream stream(line); stream >> wine.A1 >> wine.A2 >> wine.A3 >> wine.A4 >> wine.A5 >> wine.A6 >> wine.A7 >> wine.A8 >> wine.A9 >> wine.A10 >> wine.A11 >> wine.A12 >> wine.A13 >> wine.A14; data.push_back(wine); } f.close(); }

void bayes() { int count1 = 0, count2 = 0, count3 = 0; int i; for(i = 0; i < TrainNum ; i++) { if(trainData[i].A1 == 1) { count1 ++; } if(trainData[i].A1 == 2) { count2 ++; } if(trainData[i].A1 == 3) { count3 ++; }//统计三类数据,各自求和 }

第19页

数据挖掘实验指导书

A[0] = (double)count1/(double)TrainNum; //求先验概率 A[1] = (double)count2/(double)TrainNum; A[2] = (double)count3/(double)TrainNum; map::iterator pipei; for(i = 0 ; i < TrainNum; i++) { if(trainData[i].A1 == 1) //求P(Xk|C1) 中Xk的个数 { int j=0; for(;j< 13 ;j++) { double temp = *(&trainData[i].A2+j); pipei = C1_map[j].find(temp); if(pipei == C1_map[j].end()) { C1_map[j].insert(map::value_type(temp,1)); } else { double j = pipei->second; pipei->second = j + 1; } } } if(trainData[i].A1 == 2) //求P(Xk|C2) 中Xk的个数 { int j = 0; for(;j< 13 ;j++) { double temp = *(&trainData[i].A2+j); pipei = C2_map[j].find(temp); if(pipei == C2_map[j].end()) { C2_map[j].insert(map::value_type(temp,1)); } else { double j = pipei->second; pipei->second = j + 1; } } } if(trainData[i].A1 == 3) //求P(Xk|C3) 中Xk的个数 { int j = 0; for(;j< 13 ;j++) { double temp = *(&trainData[i].A2+j); pipei = C3_map[j].find(temp); if(pipei == C3_map[j].end()) { C3_map[j].insert(map::value_type(temp,1));

第20页

数据挖掘实验指导书

} else { double j = pipei->second; pipei->second = j + 1; } } } } //概率 for(i = 0; i < Shuxing; i++) { for(pipei=C1_map[i].begin(); pipei!=C1_map[i].end(); ++pipei) { double num = pipei->second; pipei->second = (double)num/(double)count1; } for(pipei=C2_map[i].begin(); pipei!=C2_map[i].end(); ++pipei) { double num = pipei->second; pipei->second = (double)num/(double)count2; } for(pipei=C3_map[i].begin(); pipei!=C3_map[i].end(); ++pipei) { double num = pipei->second; pipei->second = (double)num/(double)count3; } } }

void houyan()//计算后验分布,找出最大值 { int i,j,k; double p[3]; for(i = 0; i::iterator pipei; //计算p(X|C1) for(k = 0; k < Shuxing; k++) { pipei = C1_map[k].find(*(&testData[i].A2+k)); if(pipei != C1_map[k].end()) { pXC[0] =pXC[0] + pipei->second; } } p[0] = A[0] * pXC[0]; //计算p(X|C2) for(k = 0; k < Shuxing; k++) {

第21页

数据挖掘实验指导书

pipei = C2_map[k].find(*(&testData[i].A2+k)); if(pipei != C2_map[k].end()) { pXC[1] =pXC[1] + pipei->second; } } p[1] = A[1]*pXC[1]; //计算p(X|C3) for(k = 0; k < Shuxing; k++) { pipei = C3_map[k].find(*(&testData[i].A2+k)); if(pipei != C3_map[k].end()) { pXC[2] =pXC[2] + pipei->second; } } p[2] = A[2]*pXC[2]; } //找出最大值 if(p[0] > p[1] && p[0] >p[2]) { cout< p[2]) { cout<

void main() { double tp,fp; cout<<\概率最大值 \<<\所属类别\<

第22页

数据挖掘实验指导书

cout<<\错误率为：\<

实验3-1 C-Means聚类算法实现

一、实验目的

通过分析C-Means聚类算法的聚类原理，利用Vc编程工具(或者其他编程工具)实现C-Means和FCM聚类算法，并通过对样本数据的聚类过程，加深对该聚类算法的理解与应用过程。 实验类型：综合 计划课间：6学时

二、实验内容

1、分析C-Means聚类算法和FCM； 2、分析距离计算方法； 3、分析聚类的评价准则；

4、编程完成C-Means聚类算法和FCM，并基于相关实验数据实现聚类过程；

三、实验方法

1、C-means聚类算法原理

C-means聚类算法以C为参数，把n个对象分为C个簇，以使簇内的具有较高的相似度。相似度的计算根据一个簇中对象的平均值来进行。 算法描述：

输入：簇的数目C和包含n个对象的数据库

输出：使平方误差准则最小的C个簇 过程：

任选C个对象作为初始的簇中心； Repeat

for j=1 to n DO

根据簇中对象的平均值，将每个对象赋给最类似的簇 for i=1 to C DO 更新簇的平均值 计算E

Unitl E不再发生变化

第23页

数据挖掘实验指导书

按簇输出相应的对象

2、聚类评价准则： E的计算为：E?

??|x?xi?1x?Ciki|2

四、实验步骤 4.1 实验数据

见实验数据集Wine 和Iris数据

4.2初始簇中心的选择 选择k个样本作为簇中心 For (i=0;i

For (j=0;j

ClusterCenter[i][j]=DataBase[i][j]

4.3 数据对象的重新分配

Sim=某一较大数；ClusterNo=-1;

For (i=0;i

If (Distance(DataBase[j],ClusterCenter[i])

ClusterNo=i;}

ObjectCluster[j]=ClusterNo;

4.4 簇的更新

For (i=0;i

{Temp=0;Num=0; For (j=0;j

If (ObjectCluster[j]==i){Num++; Temp+=DataBase[j];} If (ClusterCenter[i]!=Temp) HasChanged=TRUE; ClusterCenter[i]=Temp; }

4.5 结果的输出

第24页

数据挖掘实验指导书

For (i=0;i

Printf(“输出第%d个簇的对象:”，i); For (j=0;j

If (ObjectCluster[j]==i) printf(“%d ”,j); Printf(“\\n”);

Printf(“\\t\\t\\t 簇平均值为(%d,%d)\\n”, ClusterCenter[i][0], ClusterCenter[i][1]); }

五、注意事项 1、距离函数的选择 2、评价函数的计算

算法描述

模糊C均值聚类算法的步骤还是比较简单的，模糊C均值聚类（FCM），即众所周知的模糊ISODATA，是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1973年，Bezdek提出了该算法，作为早期硬C均值聚类（HCM）方法的一种改进。

FCM把n个向量xi（i=1,2,?,n）分为c个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。FCM与HCM的主要区别在于FCM用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U允许有取值在0，1间的元素。不过，加上归一化规定，一个数据集的隶属度的和总等于1：

?ui?1cij?1,?j?1,...,n (6.9)

ccnj那么，FCM的价值函数（或目标函数）就是式（6.2）的一般化形式：

m2J(U,c1,...,cc)??Ji???uijdij， (6.10)

i?1i?1这里uij介于0，1间；ci为模糊组I的聚类中心，dij=||ci-xj||为第I个聚类中心与

第j个数据点间的欧几里德距离；且m??1,??是一个加权指数。

构造如下新的目标函数，可求得使（6.10）式达到最小值的必要条件：

J(U,c1,...,cc,?1,...,?n)?J(U,c1,...,cc)??j?1?j(?uij?1)i?1m2???uijdij???j(?uij?1)i?1jj?1i?1cnncnc (6.11)

第25页

数据挖掘实验指导书

这里?j，j=1到n，是（6.9）式的n个约束式的拉格朗日乘子。对所有输入参量求导，使式（6.10）达到最小的必要条件为：

?uci?和

j?1nj?1nmijxj (6.12)

?u1mij?dij??????k?1?dkj?由上述两个必要条件，模糊C均值聚类算法是一个简单的迭代过程。在批处理方式运行时，FCM用下列步骤确定聚类中心ci和隶属矩阵U[1]：

步骤1：用值在0，1间的随机数初始化隶属矩阵U，使其满足式（6.9）中的约束条件

步骤2：用式（6.12）计算c个聚类中心ci，i=1,?,c。

步骤3：根据式（6.10）计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数值的改变量小于某个阀值，则算法停止。

步骤4：用（6.13）计算新的U矩阵。返回步骤2。

上述算法也可以先初始化聚类中心，然后再执行迭代过程。由于不能确保FCM收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用另外的快速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次运行FCM。

模糊c均值聚类算法如下： Reapeat for l=1 2 3??..

Step 1:compute the cluseter prototypes(means):

cuij?2/(m?1) (6.13)

Step 2:compete the distance:

Step 3:Update the partition matrix:

第26页

数据挖掘实验指导书

算法实现

·采用VC++进行编写

文档的读取

#include \//函数定义

double **DataRead(char*name,int row,int col) {

double **p=new double* [row];

ifstream infile;

infile.open(name,ios::in); for(int i=0;i

p[i]=new double[col]; for(int j=0;j

infile>>p[i][j]; } }

infile.close();

第27页

数据挖掘实验指导书

cout<<\成功读取数据文件:\

return p;

//释放内存

for(i=0;i

delete[]p[i]; }

delete[]p; }

文档的保存

#include \

void DataSave(double**data,int row,int col,char*name) {

int i,j;

ofstream outfile;

//打开文件，输出数据

outfile.open(name,ios::out); outfile.setf(ios::fixed); outfile.precision(4);

for(i=0;i

for(j=0;j

outfile<

outfile<

outfile<

outfile.close(); }

第28页

数据挖掘实验指导书

数据标准化处理 #include \

double **Standardize(double **data,int row,int col) {

int i,j;

double* a=new double[col]; //矩阵每列的最大值 double* b=new double[col]; //矩阵每列的最小值 double* c=new double[row]; //矩阵列元素

for(i=0;i

//取出数据矩阵的各列元素 for(j=0;j

c[j]=Data[j][i]; }

a[i]=c[0],b[i]=c[0];

for(j=0;j

//取出该列的最大值 if(c[j]>a[i]) {

a[i]=c[j]; }

//取出该列的最小值 if(c[j]

b[i]=c[j]; } } }

//数据标准化

for(i=0;i

第29页

数据挖掘实验指导书

for(j=0;j

data[i][j]=(data[i][j]-b[j])/(a[j]-b[j]); } }

cout<<\完成数据极差标准化处理!\\n\ delete[]a; delete[]b; delete[]c;

return data; }

生成样本虑属矩阵 #include \

void Initialize(double **u, int k, int row) {

int i,j;

//初始化样本隶属度矩阵 srand(time(0)); for(i=0;i

for(j=0;j

u[i][j]=(double)rand()/RAND_MAX;//得到一个小于1的小数隶属度 }//rand()函数返回0和RAND_MAX之间的一个伪随机数 } }

数据归一化处理 #include \

void Normalize(double **u,int k,int col) {

int i,j;

double *sum=new double[col]; //矩阵U的各列元素之和 for(j=0;j

double dj=0; for(i=0;i

第30页

数据挖掘实验指导书

dj=dj+U[i][j];

sum[j]=dj;//隶属度各列之和 } }

for(i=0;i

for(j=0;j

u[i][j]=U[i][j]/sum[j]; }//规一化处理(每列隶属度之和为1) } }

迭代过程

#include \

#include \对模糊C均值进行迭代运算,并返回有效性评价函数的值 double Update(double**u,double**data,double**center,int row,int col, int k) {

int i,j,t;

double **p=NULL;

for(i=0;i

for(j=0;j

//模糊指数取2

u[i][j]=pow(u[i][j],2); } }

//根据隶属度矩阵计算聚类中心

p=MatrixMul(u,k,row,data,row,col);

for(i=0;i

//计算隶属度矩阵每行之和 double si=0;

第31页

数据挖掘实验指导书

}

for(j=0;j

si+=u[i][j]; }

for(t=0;t

center[i][t]=p[i][t]/si; //类中心 }

//计算各个聚类中心i分别到所有点j的距离矩阵dis(i,j) double* a=new double[col]; //第一个样本点 double* b=new double[col]; //第二个样本点

double**dis=new double*[k]; //中心与样本之间距离矩阵

for(i=0;i

dis[i]=new double[row]; }

for(i=0; i

//聚类中心

for(t=0; t

a[t]=center[i][t]; //暂存类中心 }

//数据样本

for(j=0; j

for(t=0; t

b[t]=data[j][t];//暂存一样本 }

double d=0;

第32页

数据挖掘实验指导书

//中心与样本之间距离的计算 for(t=0; t

d+=(a[t]-b[t])*(a[t]-b[t]); //d为一中心与所有样本的距离的平方和

}

dis[i][j]=sqrt(d); //距离 } }

//根据距离矩阵计算隶属度矩阵 for(i=0;i

for(j=0;j

double temp=0; for(t=0;t

//dis[i][j]依次除以所在列的各元素,加和； //模糊指数为2.0

temp+=pow(dis[i][j]/dis[t][j],2/(2.0-1));//一个类中心和一个元素的距离平方与 }

u[i][j]=1/temp;//所有类与该元素距离平方的和的商

}

}

//计算聚类有效性评价函数 double func1=0; for(i=0;i

double func2=0; for(j=0;j

第33页

数据挖掘实验指导书

func2+=pow(u[i][j],2.0)*pow(dis[i][j],2); }

func1+=func2; }

double obj_fcn=1/(1+func1);

return obj_fcn;

//内存释放 delete[]a; delete[]b;

for(i=0;i

delete[]dis[i]; }

delete[]dis; }

详细过程

#include \#include \#include \

//全局变量定义

double **Data; //double **Center; //double **U; //

int m; //int n; //int k; //

第34页

数据矩阵 聚类中心矩阵 样本隶属度矩阵 样本总数 样本属性数

设定的划分类别数 数据挖掘实验指导书

int main() {

int Lab; //数据文件标号 int num; //算法运行次数

/////////////////////////////////////////////////////////////// cout<<\模糊C均值聚类算法:\ cout<<\ 2-wine.txt; 3-ASD_12_2.txt; 4-ASD_14_2.txt\

cout<<\请选择数据集: Lab=\ cin>>Lab;

cout<<\设定运行次数: mum=\ cin>>num;

//各次运行结束后的目标函数

double* Index=new double[num]; //各次运行结束后的聚类正确率 double* R=new double [num];

//num次运行的平均目标函数及平均正确率 double M_Index=0; double M_R=0;

//FCM聚类算法运行num次，并保存记录与结果 for(int i=0;i

int j;

double epsilon=1e-4; int e=0; int nx=0;

//记录连续无改进次数 int E[200]={0};

if(i>0) {

cout<

cout<

第35页

数据挖掘实验指导书

}

cout<<\第\次运行记录:\

//读取数据文件 if(Lab==1) {

m=150; n=4; k=3;

Data=DataRead(\}

else if(Lab==2) {

m=178; n=13; k=3;

Data=DataRead(\}

else if(Lab==3) {

m=535; n=2; k=12;

Data=DataRead(\}

else if(Lab==4) {

m=685; n=2; k=14;

Data=DataRead(\}

//数据极差标准化处理

Data=Standardize(Data,m,n);

第36页

数据挖掘实验指导书

//聚类中心及隶属度矩阵,内存分配 Center=new double*[k]; U=new double *[k]; for(j=0;j

Center[j]=new double[n]; U[j]=new double[m]; }

//隶属度矩阵的初始化 Initialize(U, k, m);

//对隶属度矩阵进行归一化 Normalize(U,k,m);

//历次迭代过程中的目标函数 double Objfcn[100]={0};

cout<<\第\次运行记录:\cout<<\开始迭代过程!\

cout<<\

//输出精度为小数点后5位 cout.precision(5); //固定格式

cout.setf(ios::fixed);

//目标函数连续20代无改进，停止该次聚类迭代过程 while(e<20) {

nx++;

//聚类迭代过程

Objfcn[nx]=Update(U,Data,Center,m,n,k);

//统计目标函数连续无改进次数e

if(nx>0 && Objfcn[nx]-Objfcn[nx-1]

第37页

数据挖掘实验指导书

e++; } else {

e=0; }

E[nx]=e; }

//输出结果到文件，保存

ofstream outfile(\运行记录.txt\

outfile<<\第\次运行记录:\ outfile<<\开始迭代过程!\

outfile<<\

outfile.precision(5); outfile.setf(ios::fixed); for(int n1=1;n1<=nx;n1++) {

cout<<\ <

outfile<<\Objfcn[\

<

cout<

//本次运行的最大目标函数 Index[i]=Objfcn[nx];

//保存聚类正确率，输出聚类结果： R[i]=Result(Lab, U, k, m, i);

第38页

数据挖掘实验指导书

//内存释放

for(j=0;j

delete[]Center[j]; delete[]U[j]; }

delete[]Center; delete[]U; }

//////////////////////////统计平均/////////////////////////////////// double temp1=0, temp2=0; for(i=0;i

temp1+=Index[i]; temp2+=R[i]; }

//计算各次结果的统计平均 M_Index=(double)temp1/num; M_R=(double)temp2/num;

cout<<\/\

cout<

//输出精度为小数点后6位 cout.precision(6); //固定格式

cout.setf(ios::fixed);

cout<<\平均目标函数: \

//统计结果文件保存

ofstream resultfile(\聚类结果.txt\

resultfile<<\///////\

第39页

数据挖掘实验指导书

resultfile<

//输出精度为小数点后6位 resultfile.precision(6); //固定格式

resultfile.setf(ios::fixed);

resultfile<<\平均目标函数: \

return 0;

}

第40页

本文来源：https://www.bwwdw.com/article/18xx.html