河北工业大学数据挖掘实验报告
实验一
数据预处理
一、实验目得
1、熟悉 VC++编程工具与完全数据立方体构建、联机分析处理算法。
2、浏览拟被处理得得数据,发现各维属性可能得噪声、缺失值、不一致性等,针对存在得问题拟出采用得数据清理、数据变换、数据集成得具体算法。
3、用 VC++编程工具编写程序,实现数据清理、数据变换、数据集成等功能。
4、调试整个程序获得清洁得、一致得、集成得数据,选择适于全局优化 得参数。
5、写出实验报告。
二、实验原理
1、 数据预处理现实世界中得数据库极易受噪音数据、遗漏数据与不一致性数据得侵扰,为提高数据质量进而提高挖掘结果得质量,产生了大量数据预处理技术。数据预处理有多种方法:数据清理,数据集成,数据变换,数据归约等。这些数据处理技 术在数据挖掘之前使用,大大提高了数据挖掘模式得质量,降低实际挖掘所需要 得时间。
2、数据清理 数据清理例程通过填写遗漏得值,平滑噪音数据,识别、删除离群点,并解 决不一致来“清理”数据。
3、数据集成 数据集成将数据由多个源合并成一致得数据存储,如数据仓库或数据立方 体。
4、数据变换 通过平滑聚集,数据概化,规范化等方式将数据转换成适用于数据挖掘得形式。
5、数据归约使用数据归约可以得到数据集得压缩表示,它小得多,但能产生同样(或几乎同样得)分析结果。常用得数据归约策略有数据聚集、维归约、数据压缩与数 字归约等。
三、实验内容 与步骤
1 、实验内容
1、用 VC++编程工具编写程序,实现数据清理、数据变换、数据集成等功能,并在实验报告中写出主要得预处理过程与采用得方法。
2、产生清洁得、一致得、集成得数据。
3、在试验报告中写明各主要程序片段得功能与作用。
2 、实验步骤
1)仔细研究与审查数据,找出应当包含在您分析中得属性或维,发现数据 中得一些错误、不寻常得值、与某些事务记录中得不一致性。
2)进行数据清理,对遗漏值、噪音数据、不一致得数据进行处理。
例如: 1、日期中得缺失值可以根据统一得流水号来确定。
2、购买得数量不能为负值。
3)进行数据集成与数据变换与数据归约,将多个数据源中得数据集成起来, 减少或避免结果数据中得数据冗余或不一致性。并将数据转换成适合挖掘得形 式。
例如:
1、进行完数据清理后发现购买数量、销售价格、总额就是相互关联得项可
以 去掉总额。
2、三个流水表日期得格式不一样应统一成相同得日期格式。
3、门号与 pos 机号码一样,可以去掉一个。
4、附加:同一购物篮得商品序号应该就是顺序递增得。
四 、 实验结果 源程序: #include <iostream> #include <string> #include <fstream> #include <algorithm> using namespace std; class Sales { public:
string serial;
int market;
int posno;
string date;
int sn;
int id;
float num;
float price;
float total;
void print
{
cout<<serial<<" "<<market<<" "<<posno<<" "<<date<<" "<<sn<<" "
<<id<<" "<<num<<" "<<price<<" "<<total<<endl;
} }; int main {
ofstream outfile("fl、txt",ifstream::app);
if (!outfile)
{
cout<<"open error!"<<endl;
exit(1);
}
char name[50];
ifstream infile;
cout<<"输入要打开得 txt 文件名:1019、txt,1020、txt,1021、txt"<<endl;
//int N=3;
//for (int k=0;k<N;k++)
//{
//cout<<"输入要打开得第"<<k+1<<"个文件名"<<endl;
cin>>name;
in(name,ios::in);//ifstream infile("1019、txt",ios::in);
cin、clear;
/*string contents;*/
if (in)
{
cout<<"error open!"<<endl;
}
//ofstream outfile("fl、txt",ofstream::app);
//ofstream outfile("fl、txt",ios::out);
//if (!outfile)
//{
//cout<<"open error!"<<endl;
//exit(1);
//}
Sales sal[13000];
int sal_size=0;
while (!in)
{
infile>>sal[sal_size] 、 serial>>sal[sal_size] 、 market>>sal[sal_size] 、posno>>sal[sal_size]、date>>
sal[sal_size] 、 sn>>sal[sal_size] 、 id>>sal[sal_size] 、num>>sal[sal_size]、price>>sal[sal_size]、total;
sal_size++;
}
cout<<"文档"<<name<<"得长度就是:"<<sal_size<<endl;
//char Tc;
//Tc=getchar;
//cout<<Tc<<endl;
int I;
for (int i=0; i<sal_size;i++)
{
//sal[i]、print;
if (sal[i]、num<0)
{
sal[i]、num=sal[i]、num;
}
sal[i]、date、assign(sal[i]、serial,0,8);
outfile<<sal[i] 、 serial<<"\t"<<sal[i] 、 market<<"\t"<<sal[i] 、date<<"\t"<<sal[i]、sn<<"\t"
<<sal[i]、id<<"\t"<<sal[i]、num<<"\t"<<sal[i]、price<<endl;
I=i;
}
cout<<"文档 fl、txt 得长度就是:"<<sal_size<<"\t"<<I<<endl;
char TTc;
cin>>TTc;//TTc=getchar;
cout<<TTc<<endl;
in;
//}
out;
return 0; } 运行结果:
实验二
数据立方体与联机分析处理构建
一、实验目得
1、熟悉 VC++编程工具与基本数据立方体构建、联机分析处理算法。
2、建立一致得高质量得关系型数据库。
3、在建立得数据库基础上建立基本数据立方体。
4、写出实验报告。
二、实验原理
1、关系型数据库
关系数据库,就是创建在关系模型基础上得数据库,借助于集合代数等数学概 念与方法来处理数据库中得数据。关系模型由关系数据结构、关系操作集合、关 系完整性约束三部分组成。
2、数据立方体
一种多维数据模型,允许以多维对数据建模与观察。它由维与事实定义。
维就是一个单位想要得透视或实体。每个维可以有一个与人相关联得表,称为维表,它进一步描述维,如 item 维得维表包含属性 Name、time、type 等。
事实:多维数据模型围绕诸如销售这样得主题组织,主题用事实表示, 事实就
是数值度量得。
3、OLAP 操作
上卷:沿着一个维得概念分层向上攀升或通过维归约在数据立方体上进行聚集。
下钻:上卷得逆操作,可能过沿维得概念分层向下或引入附加得维来实现。
切片:在给定得数据立方体得一个维上进行选择,导致一个子立方体。就就是数据立方体得某一层数据。
切换:在两个或多个维上选择,定义子立方体。就就是数据立方体某一层 数据中得某一块。
4、数据仓库得设计
选取待建模得商务处理:都有哪些商务过程,如订单、发票、发货、库 存、记账管理、销售或一般分类账。
选取商务处理得粒度:对于商务处理,该粒度就是基本得,在事实表中就是 数据得原子级,如单个事务、一天得快照等。
选取用于每个事实表记录得维:典型得维就是时间、商品、顾客、供应商、 仓库、事务类型与状态。
选取将安放在每个事实表记录中得度量:典型得度量就是可加得数值量, 如 dollars_sold 与 units_sold。
三、实验内容与步骤
1 、实验内容 (1)、用 VC++编程工具编写程序,建立关系型数据存储结构,建立数据立方体,并在实验报告中写出主要得过程与采用得方法。
建立得数据立方体得维度为 3,分别就是商品大类、商店编号与时间。
具体要求: 1、建立三个存储表格(txt 文件)分别存储 1019、1020、1021 得数据;
2、每个 txt 文件横向为商品大类(商品 ID 前五位)10010 油、 10020 面制品、10030 米与粉、10088 粮油类赠品;
3、每个 txt 纵向为日期 1319 这一个星期表中存储得值为总销 售额。
(2)、进行简单得 OLAP 数据查询
具体要求: 能查出 2020 商店 10010 油类商品 13 日总得销售额;
能计算出 2020 商店 10030 米与粉总得销售额;
能查询出指定商店指定种类商品得销售额;(附加题)
2 、实验步骤
(1)仔细研究与审查数据,找出应当包含在您分析中得属性或维去掉不需要 得数据。
(2)选择合适得存储结构,实现数据得存储访问,并实现相应得功能。
(3)经过数据预处理后得数值已经补充了缺失值,并统一了格式。
(4)读取预处理数据得商品 ID、日期、计算出销售额。
四、实验结果 源程序:
#include<iostream> #include<string> #include<fstream> #include<algorithm> using namespace std; class Sales_n { public:
string serial;
int market;
char date[10];
int sn;
int id;
float num;
float price; }; int main {
char name1[50],name2[50];
ifstream infile;
cout<<"输入实验一中经过预处理得数据文件:fl、txt"<<endl;
cin>>name1;
in(name1,ios::in);
/*string contents;*/
if(in)
cout << "error open!" << endl;
cout<<"输入实验二要保存得存有数据立方体得文件名:cube3、txt"<<endl;
cin>>name2;
ofstream outfile;
out(name2,ios::out);
if(!outfile)
{
cout<<"open eror!"<<endl;
exit(1);
}
Sales_n sal[10000];
int sal_size=0;
int i=sal_size;
float total[3][10][5]={0};
while(!in)
{
infile >> sal[sal_size]、serial >> sal[sal_size]、market >> sal[sal_size]、date>> sal[sal_size]、sn>> sal[sal_size]、id>> sal[sal_size]、num>> sal[sal_size]、price;
cout<<"i: "<<i<<endl;
for (int k=0;k<3;k++)
//此 for 循环默认店号就是从 1019 连续增加得 3个整数
{
int Km=1019+k;
//cout<<"Km: "<<Km<<endl;
if (sal[i]、market==Km)
{
char p= sal[i]、date[7];
if(sal[i]、id/100==10010 )
{
switch(p)
{
case "3":total[k][0][0]+=sal[i]、num*sal[i]、price;break;
case "4":total[k][1][0]+=sal[i]、num*sal[i]、price;break;
case "5":total[k][2][0]+=sal[i]、num*sal[i]、price;break;
case "6":total[k][3][0]+=sal[i]、num*sal[i]、price;break;
case "7":total[k][4][0]+=sal[i]、num*sal[i]、price;break;
case "8":total[k][5][0]+=sal[i]、num*sal[i]、price;break;
case "9":total[k][6][0]+=sal[i]、num*sal[i]、price;break;
}
}
if(sal[i]、id/100==10020 )
{
switch(p)
{
case "3":total[k][0][1]+=sal[i]、num*sal[i]、price;break;
case "4":total[k][1][1]+=sal[i]、num*sal[i]、price;break;
case "5":total[k][2][1]+=sal[i]、num*sal[i]、price;break;
case "6":total[k][3][1]+=sal[i]、num*sal[i]、price;break;
case "7":total[k][4][1]+=sal[i]、num*sal[i]、price;break;
case "8":total[k][5][1]+=sal[i]、num*sal[i]、price;break;
case "9":total[k][6][1]+=sal[i]、num*sal[i]、price;break;
}
}
if(sal[i]、id/100==10030)
{
switch(p)
{
case "3":total[k][0][2]+=sal[i]、num*sal[i]、price;break;
case "4":total[k][1][2]+=sal[i]、num*sal[i]、price;break;
case "5":total[k][2][2]+=sal[i]、num*sal[i]、price;break;
case "6":total[k][3][2]+=sal[i]、num*sal[i]、price;break;
case "7":total[k][4][2]+=sal[i]、num*sal[i]、price;break;
case "8":total[k][5][2]+=sal[i]、num*sal[i]、price;break;
case "9":total[k][6][2]+=sal[i]、num*sal[i]、price;break;
}
}
else if(sal[i]、id/100==10088)
{
switch(p)
{
case "3":total[k][0][3]+=sal[i]、num*sal[i]、price;break;
case "4":total[k][1][3]+=sal[i]、num*sal[i]、price;break;
case "5":total[k][2][3]+=sal[i]、num*sal[i]、price;break;
case "6":total[k][3][3]+=sal[i]、num*sal[i]、price;break;
case "7":total[k][4][3]+=sal[i]、num*sal[i]、price;break;
case "8":total[k][5][3]+=sal[i]、num*sal[i]、price;break;
case "9":total[k][6][3]+=sal[i]、num*sal[i]、price;break;
}
}
}
}
if (sal_size<5000)
{
sal_size++;
i=sal_size;
}
else
{
sal_size=0;
i=sal_size;
}
//cout<<"sal_size++="<<sal_size<<endl;
}
//sal、clear;//?????????????
if (outfile)
{
for (int kk=0;kk<3;kk++)
{
cout<<"kk"<<kk<<endl;
cout<<"销售日期"<<"\t"<<"10010 油 "<<"10020 面制品 "<<"10030 米与粉 "<<"10088 粮油类赠品 "<<endl;
int j = 20030413;//?????????
for (int i=0;i<7;++i)
{
outfile<<" "<< total[kk][i][0]<<"\t"<<total[kk][i][1]<<"\t"<<total[kk][i][2]<<"\t"<<total[kk][i][3]<<"\t"<<endl;
cout<<j<<" "<< total[kk][i][0]<<"\t"<<total[kk][i][1]<<"\t"<<total[kk][i][2]<<"\t"<<total[kk][i][3]<<"\t"<<endl;
j++;
}
}
}
//else
//cerr<<"无法打开文件！"<<endl;
//ifstream infile2("cube2、txt",ios::in);
//int m=0;
//while(!in)
//{
//infile >> total[m][0] >> total[m][1] >>total[m][2]>>total[m][3];
//m++;
//}
//if(in)
//{
//cout << "error open!" << endl;
//}
//float sum=0、0;
//for(int i=0;i<7;++i)
//{
//sum+=total[i][2];
//}
//cout<<"2020 号商铺 10010 油类商品 14 日销售额为:"<<total[1][0]<<endl;
//cout<<"2020 号商铺 10030 米与粉类商品销售总额为:"<<sum<<endl;
in;//关闭文件
out;//关闭文件
system( "PAUSE "); } 运行结果:
实 验三
应用 Apriori 算法挖掘频繁项集 一、实验目得
(1)熟悉 VC++编程工具与 Apriori 频繁项集挖掘算法。
(2)根据管理层得需求,确定数据挖掘得任务,明确数据挖掘得功能,也 就就是明确要挖掘什么。
(3)由确定得数据挖掘任务,从实验一处理后得结果中,采用切块或切片 等联机分析处理技术,选择出挖掘任务相关数据。
(4)用 VC++编程工具编写 Apriori 算法得程序,对任务相关数据运行 Apriori 算法,挖掘出所有得频繁项集。
(5)写出实验报告。
二、实验原理
1、Apriori 算法 Apriori 使用一种称作逐层搜索得迭代方法,k 项集用于探索(k+1)项集。
首先,通过扫描数据库,累计每个项得计数,并收集满足最小支持度得项, 找出频繁 1 项集得集合。该集合记作 L1。然后,L1 用于找频繁 2 项集得集合 L2,L2 用于找 L3,如此下去,直到不能再找到频繁 k 项集。找每个 Lk 需要一次 数据库全扫描。
2、提高频繁项集逐层产生得效率 Apriori 性质:频繁项集得所有非空子集也必须就是频繁得。
三、实验内容与步骤
1 、实验内容
在给定得数据中提取统一购物篮购买得商品信息,由这些数据构成事务数据 库 D,挖掘其中得频繁项集 L。
挖掘频繁项集得算法描述如下: Apriori 算法:使用逐层迭代找出频繁项集 输入:事务数据库 D;最小支持度阈值。
输出:D 中得频繁项集 L。
(1) L1 = find_frequent_1itemsets(D); // 挖掘频繁 1 项集,比较容易
(2) for (k=2;Lk1 ≠Φ ;k++) {
(3)
Ck = apriori_gen(Lk1 ,min_sup); // 调用 apriori_gen 方法生成候选频繁 k 项集分为两步:合并、减枝
(4)
for each transaction t ∈ D {
// 扫描事务数据库 D
(5)
Ct = subset(Ck,t);
(6)
for each candidate c ∈ Ct
(7)
c、count++; //
统计候选频繁 k 项集得计数
(8)
}
(9)
Lk ={c ∈ Ck|c、count≥min_sup} // 满足最小支持度得 k 项集即为频 繁 k 项集
(10) }
(11) return L= ∪ k Lk; // 合并频繁 k 项集(k>0) 算法在根据频繁 k1 项集生成频繁 K 项集过程中要计算频繁 K 项集中每个 元素得支持度,并计算 K 项集中每个 k1 项子集就是否在 Fk1 中,上述两条任何一 条不满足,则删去这个 K 项集中得元素 2 、实验步骤
(1)打开试验用数据,读取出同一流水号得商品 ID 并取前 5 位,生成以行为 单位生成事务数据集 transitions;
(2)ind_frequent_1itemsets 生成频繁一项集
for(each transaction in transitions){
for(each
item
in transaction){
oneItemSet;
oneItemSet、count++;//对 1 项集进行计数
}
}
3、apriorigen (Lk1) 候选集产生算法
For
all itemset p∈Lk1
do
For
all itemset q∈Lk1
do
If
p、item1=q、item1, p、item2=q、item2, „,p、itemk2=q、itemk2,
p、itemk1!=q、itemk1
then
begin c=p∞q//p、q 合并后任意得 Lk1 子集
if has_infrequent_subset(c, Lk1)
then delete c //存在 c 不属于 Lk1 剪枝
else add c to Ck
End
Return Ck
4、has_infrequent_subset(c, Lk1)判断候选集得元素
For
all (k1)subsets of
c
do
If Not(S∈Lk1)
THEN return TRUE;
Return FALSE; 四 、 实验结果 源程序: #include<iostream> #include<string> #include<fstream> #include<algorithm> using namespace std; class Sales_n { public: string serial; int market; 16 char date[10]; int sn; int id; float num; float price; }; int main { //////////打开并创建txt 文件////////////////////////////////// char name1[50],name2[50]; ifstream infile; cout<<"选择要打开得文件:1019n、txt 1020n、txt 1021n、txt"<<endl; cin>>name1; in(name1,ios::in); /*string contents;*/ if(in) { cout << "error open!" << endl;
} cout<<"要保存得文件名:"<<endl; cin>>name2; ofstream out); if(!outfile) { cout<<"open eror!"<<endl; exit(1); } ////////////////////// 访 问 预 处 理 文 件///////////////////////////////////////////// Sales_n sal[10000]; int sal_size=0; int ser_size=0; int m = 0,n = 1; int new1[3400][20]={0}; //暂时储存商品ID while(!in) { infile >> sal[sal_size]、serial >> sal[sal_size]、market >> sal[sal_size]、date>> sal[sal_size]、sn>> sal[sal_size]、id>> sal[sal_size]、num>> sal[sal_size]、price; sal_size++; } ///////////////取统一流水得商品 ID 前三位按升序无重复得保存起来///////////////////////// new1[0][0]=sal[0]、id/10000; for (int i =1;i<sal_size;i++) { if (sal[i]、serial==sal[i1]、serial) { new1[m][n]=sal[i]、id/10000; //////流水号相同 n++; //outfile<<sal[i]、id/100<<"\t"; } else { ///////排序////////// for(int k = 0;k<n;k++) { for(int j = 0;j < nk1;j++) { if(new1[m][j] > new1[m][j+1]) { int t = new1[m][j];
new1[m][j] = new1[m][j+1]; new1[m][j+1] = t; } } } for(int l= 0;l< n;l++) { if(new1[m][l1]!=new1[m][l]) outfile<<new1[m][l]<<"\t"; } outfile<<endl; m++; n = 0; new1[m][n]=sal[i]、id/10000; n++; } } in;//关闭文件 out;//关闭文件 system( "PAUSE "); } Apriori 算法挖掘频繁项集 support = 2
#include <iostream> 18 #include <fstream> #include <string> #include <vector> #include <map> #include <cmath> #include <bitset> #include <algorithm> #include <iomanip> using namespace std; const int minsup=2; //设置最小支持度 map<string,int> items_count; //统计各个项集得数目 vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round); //合并生成新得候选 项集 int isExist(vector<string> item,vector<vector<string> >items); //判断项集item 就是否已经存在候 选项集集合items 中,存在则返回 vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round) //判断两个项 集就是否可以合并(要求只有一项不同)成一个新得项集(做为候选集)
{ ////////////////////////////////////////////剪枝工作//// int count=0; //统计两个vector 中相同得项得数目 vector<string> vect; map<string,int> tempMap; //辅助判断两个vector 中重复得项 for(vector<string>::size_type st=0;st<vect1、size;st++) { tempMap[vect1[st]]++; vect、push_back(vect1[st]); } for(int st=0;st<vect2、size;st++) { tempMap[vect2[st]]++; if(tempMap[vect2[st]]==2) //表示这两项相同 { count++; } else { vect、push_back(vect2[st]); } } if((count+1)!=round) //要求两个项目集只有一个项目不相同,其她都相同 { vect、clear; } return vect; 19 } int isExist(vector<string> item,vector<vector<string> >items) //判断项集item 就是否已经存在候选项集集 合items 中,存在则返回 { int count; //统计相同得项得数目 if(!items、empty) { for(vector<vector<string> >::size_type ix=0;ix!=items、size;ix++) { count=0; for(vector<string>::size_type iy=0;iy!=items[ix]、size;iy++) { for(vector<string>::size_type iz=0;iz!=item、size;iz++) { if(item[iz]==items[ix]、at(iy))
{ count++; } } } if(count==item、size) //表示存在 { return 1; } } } return 0; } int main { vector<vector<string> > datavec; //原始数据项集 vector<vector<string> > candidatevec; //候选项集 vector<vector<string> > frequentvec; //频繁项集 vector<map<string,int> > bitmap; //判断某个项目在某一个事务中就是否存在,存在则值为1,反之 为0 long trancount=0; //原始事务总数 char name1[50]; ifstream file; cout<<"选择要打开得文件:new1、txt new2、txt new3、txt"<<endl; cin>>name1; (name1,ios::in); //打开数据文件 if(!file) //检查文件就是否打开成功 { cout<<"Fail to open data file!"<<endl; 20 return 1; } else { string temp; vector<string> item; //项集得临时vector int begin,end; while(getline) //一行一行读入数据 { trancount++; begin=0; temp、erase(0,temp、find_first_not_of("\r\t\n ")); //去除字符串首部得空格
temp、erase(temp、find_last_not_of("\r\t\n")+1); while((end=temp、find("\t",begin))!=string::npos) //每一个事务中得项就是以"\t"为分隔符得 { item、push_back(temp、substr(begin,endbegin)); //将每一个项插入item 中 begin=end+1; } item、push_back(temp、substr(begin)); //一个事务中得最后一项 datavec、push_back(item); //将一个事务中得所有项当成一个整体插入另一个大得vector 中 item、clear; //清空item } cout<<"Press Enter to continue the processing"; //pause getchar; map<string,int> item_map; for(vector<vector<string> >::size_type ix=0;ix!=datavec、size;++ix) { for(vector<string>::size_type iy=0;iy!=datavec[ix]、size;++iy) { items_count[datavec[ix]、at(iy)]++; //该项集得计数加 item_map[datavec[ix]、at(iy)]=1; //表示该项目在该事务中存在,值为1,否则默认为0 } bitmap、push_back(item_map); item_map、clear; //这里一定要清空一下 } map<string,int>::const_iterator map_it=items_count、begin; cout<<"候选项集1:"<<endl; while(map_it!=items_count、end) //输出候选1 项集 { cout<<"{"<<map_it>first<<"}"<<endl; map_it++; } cout<<"Press Enter to continue the processing"; //pause 21 getchar; map_it=items_count、begin; cout<<"频繁1 项集(minsup=2):"<<endl; while(map_it!=items_count、end) //频繁1 项集 { if(map_it>second>minsup) //支持度大于2 { cout、setf(ios::fixed);
cout<<"{"<<map_it>first<<"}"<<" 支持度:"<<setprecision(6)<<map_it>second<<endl; item、push_back(map_it>first); frequentvec、push_back(item); //插入候选项集得vector 中 item、clear; } map_it++; } if(!frequentvec、empty) //判断频繁项集就是否为空,为空则退出 { cout<<"Press Enter to continue the processing"; //pause getchar; int round=1; //生成候选项集轮次 int found; //就是否包含有非频繁得子集,为表示含有,有得话进行剪枝 string tempstr; vector<string> tempvec; do { //生成下一轮得候选项集 vector<vector<string> >::size_type st=frequentvec、size; candidatevec、clear; //清除上一轮得候选项集 for(vector<vector<string> >::size_type st1=0;st1<st;st1++) { for(vector<vector<string> >::size_type st2=st1+1;st2<st;st2++) { found=0; item=mergeItem(frequentvec[st1],frequentvec[st2],round); //调用函数合并生成 下一轮得候选项集 if(!item、empty&&!isExist(item,candidatevec)) //若经过判断处理后返回得 vector 不为空且还不存在该项集,则作为候选项集加入候选vector 中 { ////////实现剪枝////////////////////////// string teststr; int testint; tempvec=item; sort(tempvec、begin,tempvec、end); while(next_permutation(tempvec、begin,tempvec、end)) //遍历所有得组 22 合 { for(vector<string>::size_type tempst=0;tempst!=tempvec、size;tempst++) // 拼接出该字符串组合
{ tempstr+=tempvec[tempst]; } for(map<string,int>::const_iterator tempit=items_count、begin;tempit!=items_count、end;tempit++) { if(tempit>second<minsup) //非频繁项集 { if(tempstr、find(tempit>first)!=string::npos) //表示包含有非 频繁子项集 { found=1; teststr=tempit>first; testint=tempit>second; break; } } } tempstr、erase; if(found) //包含非频繁子项集 { break; } } if(!found) //只有不包含有非频繁子项集才加入候选项集中,否则剪枝 掉 candidatevec、push_back(item); found=0; //重置 } } } frequentvec、clear; //清除上一轮得频繁项集 round++; cout<<"候选"<<round<<"项集:"<<endl; for(vector<vector<string> >::size_type ix=0;ix!=candidatevec、size;++ix) //输出候选 项集 { 23 cout<<"{"; for(vector<string>::size_type iy=0;iy!=candidatevec[ix]、size;++iy) { cout<<candidatevec[ix]、at(iy)<<" "; }
cout<<"}"<<endl; } if(candidatevec、empty) //候选项集为空 { cout<<"候选"<<round<<"项集为空!"<<endl; } int flag; //标记某个项集在某条事务中就是否出现,出现为1,不出现为0 int count; //统计某个想集在整个交易得事务集中出现得次数 string tempstr; //临时string,用于串接各个项成一个字符串 int mark; //为避免执行多余得字符串串接工作 for(vector<vector<string> >::size_type sx=0;sx!=candidatevec、size;++sx) //构造下一 轮得频繁项集 { mark=1; count=0; for(vector<map<string,int> >::size_type sy=0;sy!=bitmap、size;++sy) { flag=1; //初始化为1,表出现 for(vector<string>::size_type sz=0;sz!=candidatevec[sx]、size;++sz) { if(bitmap[sy][candidatevec[sx]、at(sz)]==0) //存在某一个子项不存在,则没 出现项集 { flag=0; } if(mark==1) //只串接一次 { tempstr+=candidatevec[sx]、at(sz); //串接字符串 } } if(flag) //flag 仍然为,表示该项集在该条事务中出现了,计数加 { count++; } mark++; } if(count>minsup) //支持度大于2 24 { frequentvec、push_back(candidatevec[sx]); //插入频繁项集 } items_count[tempstr]=count; //对应该项集得计数值
sort(candidatevec[sx]、begin,candidatevec[sx]、end); //排序 string tempstr2; while(next_permutation(candidatevec[sx]、begin,candidatevec[sx]、end)) //取下一排 列组合 { for(vector<string>::size_type tempst=0;tempst!=candidatevec[sx]、size;tempst++) //拼接出该字符串组合 { tempstr2+=candidatevec[sx][tempst]; } items_count[tempstr2]=count; //对应该项集得计数值 tempstr2、erase; } tempstr、erase; } cout<<"Press Enter to continue the processing"; //pause getchar; if(!frequentvec、empty) //频繁项集不为空 { cout<<"频繁"<<round<<"项集(minsup=2):"<<endl; for(int sx=0;sx!=frequentvec、size;++sx) //输出频繁项集 { cout、setf(ios::fixed); cout<<"{"; for(vector<string>::size_type sz=0;sz!=frequentvec[sx]、size;++sz) { cout<<frequentvec[sx]、at(sz)<<" "; tempstr+=frequentvec[sx]、at(sz); //串接字符串 } cout<<"}"; cout<<endl; tempstr、erase; } cout<<"Press Enter to continue the processing"; //pause getchar; } else { cout<<"没有"<<round<<"频繁项集,Apriori 算法结束!"<<endl; 25 } }
while(!frequentvec、empty); //频繁项集不为空,则循环继续 ; return 0; } else { return 0; } //end of if(!frequentvec、empty) }//end of if(!file) } 运行结果:
实验四
贝叶斯决策分类算法
一、实验目得
(1)熟悉 VC++编程工具与朴素贝叶斯决策算法。
(2)对 AllElectronics 顾客数据库查询得到先验概率与类条件概率。
(3)在样本集上用 VC++编程工具编写用朴素贝叶斯算法分类得程序,对任 务相关数据运行朴素贝叶斯分类算法,调试实验。
(4)写出实验报告。
二、实验原理
1 、先验概率与类条件概率
先验概率:先验概率定义为训练样本集中属于 Ci 类得样本(元组)数 Ni 与 总样本数 N 之比,记为 P (Ci) =N i /N 。
类条件概率:类条件概率定义为训练样本集中属于 Ci 类中得具有特征 X 得 样本(元组)得个数 ni 与属于 Ci 类得样本(元组)数 Ni 之比,记为 P (X|Ci) = ni / Ni 2 、贝叶斯决策
贝叶斯决策(分类)法将样本(元组)分到 Ci 类,当且仅当
P (X|Ci) P (Ci)> P (X|Cj) P (Cj),对 1≤j≤m,j≠i
其中,训练样本集中得样本(元组)可被分为 m 类。
三、实验内容与步骤
1 、实验内容
用贝叶斯分类器对已知得特征向量 X 分类:
1) 由 AllElectronics 顾客数据库类标记得训练样本集(元组)编程计算先验 概率 P(Ci)与类条件概率 P(X|Ci),并在实验报告中指出关键代码得功能与实现方 法;
2) 应用贝叶斯分类法编程对特征向量 X 分类,并在实验报告中指出关键程 序片段得功能与实现方法;
3) 用检验样本估计分类错误率;
4) 在实验报告中画出程序或例程得程序框图。
2 、实验步骤
由于该分类问题就是决定顾客就是否倾向于购买计算机,即 C1 对应于 buys_puter=yes,C2 对应于 buys_puter=no,就是两类得分类问题。实验 步骤如下:
1) 确定特征属性及划分:浏览所给得数据库,找出划分得特征属性;
2) 获取训练样本:即给定得 AllElectronics 顾客数据库类标记得训练样本集 (元组);
3) 计算训练样本中每个类别得先验概率:P(Ci),i=1,2;
4) 计算训练样本中类条件概率:设特征(属性)向量为 X,编程计算类条 件概率 P(X|Ci),i=1,2;
5) 使用分类器进行分类; 四、实验结果 源程序: #include<iostream> #include<string> #include<fstream> #include<algorithm> using namespacestd;
////////////////////定义存储结构//////////////////////////////
classDate
{
public:
string age;
string ine;
string student;
string credit;
string buy;
voidprint
{
cout << age<< " "<< ine << " "<< student << " "<< credit << " "<<buy<<endl;
}
};
intmain
{
//////////////////////////读取数据并保存////////////////////////
charname1[50];
ifstream infile;
29 cout<<"输入要打开得文件:*、txt"<<endl;
cin>>name1;
in(name1,ios::in);
if(in)
{
cout << "error open!"<< endl;
}
Date date[100];
intdatesize=0;
string iage, iine,istudent,icredit,ibuy;
//输入得条件 inty = 0,n = 0,agey = 0,agen = 0;
intiney = 0,inen =0,studenty = 0,studentn = 0,credity = 0,creditn = 0;
//统计出现得 次数 floatp1,p2,p3,p4,p5,p6,p7,p8,p9,p10,px1,px2,px3,px4;
//条件概率与类条件概率 while(!in)
{
infile >> date[datesize]、age >> date[datesize]、ine >> date[datesize]、student>> date[datesize]、credit>> date[datesize]、buy;
datesize++;
}
cout<<"the date are:"<<endl;
cout << "age "<<"ine "<<"student "<<"credit "<<"buy "<<endl;
for(inti=0;i<datesize;i++)
//输出要处理得数据 {
date[i]、print;
}
////////////////////////////条件概率///////////////////////////
for(intj = 0;j<datesize;j++)
{
if(date[j]、buy=="yes")
{
y++;
}
else if(date[j]、buy=="no")
{
n++;
}
}
p1 = (float)y/(float)datesize;
p2 = (float)n/(float)datesize;
cout<<"P(buys_puter = yes) = "<<y<<"/"<<datesize<<"="<<p1<<endl;
cout<<"P(buys_puter = no) = "<<n<<"/"<<datesize<<"="<<p2<<endl;
///////////////////类条件概率////////////////////////////
30 cout<<"age:"<<endl;
cin>>iage;
cout<<"ine:"<<endl;
cin>>iine;
cout<<"student:"<<endl;
cin>>istudent;
cout<<"credit:"<<endl;
cin>>icredit;
for(intk = 0;k<datesize;k++)
{
if(date[k]、age==iage&&date[k]、buy=="yes")
{
agey++;
}
if(date[k]、age==iage&&date[k]、buy=="no")
{
agen++;
}
if(date[k]、ine==iine&&date[k]、buy=="yes")
{
iney++;
}
if(date[k]、ine==iine&&date[k]、buy=="no")
{
inen++;
}
if(date[k]、student==istudent&&date[k]、buy=="yes")
{
studenty++;
}
if(date[k]、student==istudent&&date[k]、buy=="no")
{
studentn++;
}
if(date[k]、credit==icredit&&date[k]、buy=="yes")
{
credity++;
}
if(date[k]、credit==icredit&&date[k]、buy=="yes")
{
creditn++;
}
}
p3=(float)agey/(float)y;
31 p4=(float)agen/(float)n;
p5=(float)iney/(float)y;
p6=(float)inen/(float)n;
p7=(float)studenty/(float)y;
p8=(float)studentn/(float)n;
p9=(float)credity/(float)y;
p10=(float)creditn/(float)n;
px1=p3*p5*p7*p9;
px2=p4*p6*p8*p10;
px3=px1*p1;
px4=px2*p2;
cout<<"P(age = "<<iage<<"|buy = yes = "<<agey<<"/"<<y<<"="<<p3<<endl;
cout<<"P(age = "<<iage<<"|buy = no = "<<agen<<"/"<<n<<"="<<p4<<endl;
cout<<"P(ine = "<<iine<<"|buy = yes = "<<iney<<"/"<<y<<"="<<p5<<endl;
cout<<"P(ine = "<<iine<<"|buy = no = "<<inen<<"/"<<n<<"="<<p6<<endl;
cout<<"P(student = "<<istudent<<"|buy = yes = "<<studenty<<"/"<<y<<"="<<p7<<endl;
cout<<"P(student = "<<istudent<<"|buy = no = "<<studentn<<"/"<<n<<"="<<p8<<endl;
cout<<"P(credit = "<<icredit<<"|buy = yes = "<<credity<<"/"<<y<<"="<<p9<<endl;
cout<<"P(ctedit = "<<icredit<<"|buy = no = "<<creditn<<"/"<<n<<"="<<p10<<endl;
cout<<"P(X|buy = yes) = "<<px1<<endl;
cout<<"P(X|buy = no) = "<<px2<<endl;
cout<<"P(X|buy = yes)P(buy = yes) = "<<px3<<endl;
cout<<"P(X|buy = no)P(buy = no) = "<<px4<<endl;
////////////////预测/////////////////////////////////////
if(px3>px4)
{
cout<<"朴素贝叶斯预测 buy = yes"<<endl;
}
else cout<<"朴素贝叶斯预测 buy =no"<<endl;
in;//关闭文件 system( "PAUSE ");
} 运行结果:
实验五
k k 均值聚类算法
一、实验目得
(1) 熟悉 VC++编程工具与 k 均值聚类算法。
(2) 在训练样本集上用 VC++编程工具编写用于 k 均值聚类得程序,对任务
相关数据运行 k 均值聚类算法,调试实验。
(3) 掌握距离计算方法与聚类得评价准则。
(4) 写出实验报告。
二、实验原理
1 1 、k k 均值聚类
k 均值聚类就是一种基于形心得划分技术,具体迭代得计算步骤如下: 1) 在属性向量空间随机产生 k 个形心坐标。
2) 分别计算数据集 D 中得每个数据对象 Ti (1≤i≤n)到所有 k 个形心得距离度 量 Dist(i,j) (1≤i≤n, 1≤j≤k),并将数据对象 Ti 聚到最小距离度量得那一簇中。即 Ti∈CJ,表示数据对象 Ti 被聚到第 J 簇中。其中 J=argmin(Dist(i,j)),表示 J 为可 使得 Dist(i,j)取最小值得那个 j。
3) 按照形心得定义计算每一簇得形心坐标,形成下一代得 k 个形心坐标。
4) 如果不满足终结条件,转到 2)继续迭代;否则结束。
其中,簇得形心可以有不同得得定义,例如可以就是簇内数据对象属性向量得 均值(也就就是重心),也可以就是中心点等;距离度量也可以有不同得定义,常用 得有欧氏距离、曼哈顿(或城市块、街区)距离、闵可夫斯基距离等;终结条件 可采用当对象得重新分配不再发生时,程序迭代结束。
2 2 、终止条件
终止条件可以就是以下任何一个:
1)没有(或最小数目)对象被重新分配给不同得聚类。
2)没有(或最小数目)聚类中心再发生变化。
3)误差平方与局部最小。
三、实验内容与步骤
1 1 、实验内容
1) 根据 k 均值聚类算法得计算步骤,画出 k=3 时得程序流程图;
2) 由 k 均值程序流程图编程实现 k 均值聚类算法;
3) 在实验报告中显示 k 均值聚类过程得一系列截图,指明各个簇得逐渐演 化过程;
4) 在报告中指出实验代码中得初始质心得选择,终止条件得选择,以及距 离度量得选择并予以说明。
2 2 、实验步骤
编程实现如下功能:
1) 首先将数据集 D={D1,D2,D3}中得属性向量作为实验数据输入;
2) 由 k 均值程序流程图编程实现 k 均值聚类算法,并用实验数据运行; 3) 运行过程中在适当得迭代代数暂停并显示实时迭代得结果,如簇心得位 置、按距离最近邻聚类得结果等; 四 、 实验结果
源程序: :
#include<iostream> #include<string> #include<fstream> #include<algorithm> #include <math、h> using namespace std; #define k 3 //聚类数 #define n 2 //数据维数
#define size 30 //数据大小 ////////////////////定义存储结构////////////////////////////// typedef struct { double d[n]; double distance[k]; }Data; typedef struct { Data center[k]; // 即簇类中心 int cluster[k][size]; //簇数组 int cluster_num[k];// 簇类中一组数据得编号 Data old_center[k]; int isend[k][n]; //各簇类中心就是否相等标示值 int is; }Tdata; ////////声明函数////////////////////////////// void input_data; void Init_center; void calculate_distance; double Euclid(int x, int y); void new_cluster; void new_center; void output_info; void p; Data data[size]; Tdata td; ///////////////读入数据//////////////////////// void Init { char name1[50]; ifstream infile; cout<<"输入要打开得文件:*、txt"<<endl; cin>>name1; in(name1,ios::in); if(in) { cout << "error open!" << endl; } for(int i = 0;i < size;i++) for(int j = 0;j<n;j++) { infile>>data[i]、d[j]; } cout<<"the data are:"<<endl; for(int i=0;i<size;i++) { //输出要处理得数据
for(int j = 0;j<n;j++) { cout<<data[i]、d[j]<<" "; } cout<<endl; } in;//关闭文件 } //////////////初始化质心////////////////////////////// void Init_center { for(int i = 0;i<k;i++){ cout<<"初始质心"<<i+1<<":"<<endl; for(int j = 0;j<n;j++) { td、center[i]、d[j] = data[i]、d[j]; cout<<td、center[i]、d[j]<<" "; } cout<<endl; } } ///////计算数据到K 个质心得欧几里德距离////////// void calculate_distance { int i, j; for(i = 0; i < size; i++) for(j = 0; j < k; j++){ data[i]、distance[j] = Euclid(i, j); //i 表示第几个数组j 表示距离第几个质心 } } //////////计算一组数组到质心得欧几里得距离////////////// double Euclid(int x, int y) { double distance = 0; for(int i = 0; i < n; i++){ distance += pow((data[x]、d[i]
td、center[y]、d[i]), 2); } distance = sqrt(distance); return distance; } //////////将数据进行簇归类/////////////////// void new_cluster { int i, j;
double min; for(i = 0; i < k; i++) //初始化编号 td、cluster_num[i] = 0; for(i = 0; i < size; i++){ int index = 0; //找出最小得欧几里德距离编号 min = data[i]、distance[0]; for(j = 1; j < k; j++){ // 筛选到簇心欧几里德最小得值 if(data[i]、distance[j] < min){ min = data[i]、distance[j]; index = j; } } //划分簇集 td、cluster[index][td、cluster_num[index]++] = i; } } ///////////更新质心/////////////////////////////// void new_center { int i, j, m; double sum; for(i = 0; i < k; i++) for(j = 0; j < n; j++){ sum = 0; td、old_center[i]、d[j] = td、center[i]、d[j]; for(m = 0; m < td、cluster_num[i]; m++){ // 第i 个簇得第j 维数得所有数据与 sum += data[td、cluster[i][m]]、d[j]; } // 取平均数得到新得簇中心 td、center[i]、d[j] = sum / td、cluster_num[i]; } } ////////比较质心////...