云南大学数学与与统计学院
上机实践报告
课程名称：数据挖掘年级：2013上机实践成绩：
指导教师：彭程姓名：陈国静
上机实践名称：Chimege技术学号：20131910084上机实践日期：
2016/4/18
上机实践编号：No.4上机实践时间：15:50
一、实验目的
熟悉Chimege技术，对数据挖掘有一个了解。
二、实验内容
1、最简单的离散算法是：等宽区间。从最小值到最大值之间,，均分为N等份，这样，如果 A, B为最小最大值，则每个区间的长度为w=(B-A) / N, 则区间边界值为 A+W,
A+2W, …. A+(N-1)W.
2、还有一种简单算法，等频区间。区间的边界值要经过选择，使得每个区间包含大致相等的实例数量。比如说 N=10，每个区间应该包含大约10%的实例。
3、以上两种算法有弊端：比如，等宽区间划分，划分为5区间，最高工资为50000，则所有工资低于10000的人都被划分到同一区间。等频区间可能正好相反，所有工资高于50000的人都会被划分到50000这一区间中。这两种算法都忽略了实例所属的类型，落在正确区间里的偶然性很大。
4、C4、CART、PVM算法在离散属性时会考虑类信息，但是是在算法实施的过程中间，而不是在预处理阶段。例如，C4算法（ID3决策树系列的一种），将数值属性离散为两个区间，而取这两个区间时，该属性的信息增益是最大的。
5、评价一个离散算法是否有效很难，因为不知道什么是最高效的分类。
6、离散化的主要目的是：消除数值属性以及为数值属性定义准确的类别。
7、高质量的离散化应该是：区间内一致，区间之间区分明显。
8、ChiMerge算法用卡方统计量来决定相邻区间是否一致或者是否区别明显。如果经过验证，类别属性独立于其中一个区间，则这个区间就要被合并。
9、ChiMerge算法包括2部分：1、初始化，2、自底向上合并，当满足停止条件的时候，区间合并停止。
第一步：初始化
根据要离散的属性对实例进行排序：每个实例属于一个区间
第二步：合并区间，又包括两步骤
(1) 计算每一对相邻区间的卡方值
(2) 将卡方值最小的一对区间合并
预先设定一个卡方的阈值，在阈值之下的区间都合并，阈值之上的区间保持分区间。
卡方的计算公式：
参数说明；
m=2（每次比较的区间数是2个）
k=类别数量
Aij=第i区间第j类的实例的数量
Ri=第i区间的实例数量
Cj=第j类的实例数量
N=总的实例数量
Eij= Aij的期望频率
10、卡方阈值的确定：先选择显著性水平，再由公式得到对应的卡方值。得到卡方值需要指定自由度，自由度比类别数量小1。例如，有3类，自由度为2，则90%置信度（10%显著性水平)下，卡方的值为4.6。阈值的意义在于，类别和属性独立时，有90%的可能性，计算得到的卡方值会小于4.6，这样，大于阈值的卡方值就说明属性和类不是相互独立的，不能合并。如果阈值选的大，区间合并就会进行很多次，离散后的区间数量少、区间大。用户可以不考虑卡方阈值，此时，用户可以考虑这两个参数：最小区间数，最大区间数。用户指定区间数量的上限和下限，最多几个区间，最少几个区间。
11、ChiMerge算法推荐使用.90、.95、.99置信度，最大区间数取10到15之间.
三、实验环境
个人计算机，MATLAB平台
四、实验记录与实验结果分析
（注意记录实验中遇到的问题。实验报告的评分依据之一是实验记录的细致程度、实验过程的真实性、实验结果的解释和分析。如果涉及实验结果截屏，应选择白底黑字。）
程序如下：
%ChiMerge.m:This Program will achieve the ChiMeige function!
%File Read Part:
%格式化读文件：
[a,b,p,q,class] = textread( 'Iris.txt','%f,%f,%f,%f,%s' );
%Data Processing %处理字符串：
t=size(class);
for i=1:t(1,1)
if strcmp(class(i,1),'Iris-setosa')==1
c(i,1)=1;
elseif strcmp(class(i,1),'Iris-versicolor')==1
c(i,1)=2;
elseif strcmp(class(i,1),'Iris-virginica')==1
c(i,1)=3;
end
end
%具体运行
h1=[a c];
h2=[b c];
h3=[p,c];
h4=[q,c];
disp('Case 1:');
chime(h1);
disp('End!');
disp('Case 2:');
chime(h2);
disp('End!');
disp('Case 3:');
chime(h3);
disp('End!');
disp('Case 4:');
chime(h4);
disp('End!');
%建立chime函数用于卡方值的计算及数据离散化操作
function m=chime(h)
%%进行chimerge核心操作，建立区间矩阵，然后通过卡方检验离散化数据！
y=sortrows(h,1);
%排序操作
ty=size(y);
leny=ty(1,1);
x=[y(:,1) y(:,1)];
%初始化区间矩阵
tx=size(x);
lenx=tx(1,1);
while lenx>6 %外层循环，用于结束条件判定
min=9999;
for j=1:lenx-1 %内层循环，用于找出具有最小卡方值的相邻区间
ans=0; m=zeros(3,7);%此（卡方表）矩阵用于保存计算卡方值的相关数据 %后面4个for循环用于卡方表数据的设置
for i=1:leny
if y(i,1)>=x(j,1)&&y(i,1)<=x(j,2)
m(1,y(i,2))=m(1,y(i,2))+1;
elseif y(i,1)>=x(j+1,1)&&y(i,1)<=x(j+1,2)
m(2,y(i,2))=m(2,y(i,2))+1;
end
end
end
for i=1:3
m(3,i)=m(1,i)+m(2,i);
end
for i=1:3
m(i,7)=m(i,1)+m(i,2)+m(i,3);
end
for i=1:2
for k=4:6
m(i,k)=m(i,7)*m(3,k-3)/m(3,7);
if m(i,k)==0 m(i,k)=0.1;
end
end
end
%计算出这两个相邻区间的卡方值
for i=1:2
for k=1:3
ans=ans+((m(i,k)-m(i,k+3))^2)/m(i,k+3); end
end %找出最小卡方值
if ans<=min
min=ans;
key=j;
end
end %相邻区间合并步骤
x(key,2)=x(key+1,2);
x(key+1,:)=[];
lenx=lenx-1;
end
x
Iris.txt
5.1 3.5 1.4 0.2 Iris-setosa
4.9 3.0 1.4 0.2 Iris-setosa
4.7 3.2 1.3 0.2 Iris-setosa
4.6 3.1 1.5 0.2 Iris-setosa
5.0 3.6 1.4 0.2 Iris-setosa
5.4 3.9 1.7 0.4 Iris-setosa
4.6 3.4 1.4 0.3 Iris-setosa
5.0 3.4 1.5 0.2 Iris-setosa
4.4 2.9 1.4 0.2 Iris-setosa
4.9 3.1 1.5 0.1 Iris-setosa
5.4 3.7 1.5 0.2 Iris-setosa
4.8 3.4 1.6 0.2 Iris-setosa
4.8 3.0 1.4 0.1 Iris-setosa
4.3 3.0 1.1 0.1 Iris-setosa
5.8 4.0 1.2 0.2 Iris-setosa
5.7 4.4 1.5 0.4 Iris-setosa
5.4 3.9 1.3 0.4 Iris-setosa
5.1 3.5 1.4 0.3 Iris-setosa
5.7 3.8 1.7 0.3 Iris-setosa
5.1 3.8 1.5 0.3 Iris-setosa
5.4 3.4 1.7 0.2 Iris-setosa
5.1 3.7 1.5 0.4 Iris-setosa
4.6 3.6 1.0 0.2 Iris-setosa
5.1 3.3 1.7 0.5 Iris-setosa
4.8 3.4 1.9 0.2 Iris-setosa
5.0 3.0 1.6 0.2 Iris-setosa
5.0 3.4 1.6 0.4 Iris-setosa
5.2 3.5 1.5 0.2 Iris-setosa
5.2 3.4 1.4 0.2 Iris-setosa
4.7 3.2 1.6 0.2 Iris-setosa
4.8 3.1 1.6 0.2 Iris-setosa
5.4 3.4 1.5 0.4 Iris-setosa
5.2 4.1 1.5 0.1 Iris-setosa
5.5 4.2 1.4 0.2 Iris-setosa
4.9 3.1 1.5 0.1 Iris-setosa
5.0 3.2 1.2 0.2 Iris-setosa
5.5 3.5 1.3 0.2 Iris-setosa
4.9 3.1 1.5 0.1 Iris-setosa
4.4 3.0 1.3 0.2 Iris-setosa
5.1 3.4 1.5 0.2 Iris-setosa
5.0 3.5 1.3 0.3 Iris-setosa
4.5 2.3 1.3 0.3 Iris-setosa
4.4 3.2 1.3 0.2 Iris-setosa
5.0 3.5 1.6 0.6 Iris-setosa
5.1 3.8 1.9 0.4 Iris-setosa
4.8 3.0 1.4 0.3 Iris-setosa
5.1 3.8 1.6 0.2 Iris-setosa
4.6 3.2 1.4 0.2 Iris-setosa
5.3 3.7 1.5 0.2 Iris-setosa
5.0 3.3 1.4 0.2 Iris-setosa
7.0 3.2 4.7 1.4 Iris-versicolor 6.4 3.2 4.5 1.5 Iris-versicolor 6.9 3.1 4.9 1.5 Iris-versicolor 5.5 2.3 4.0 1.3 Iris-versicolor
5.7 2.8 4.5 1.3 Iris-versicolor
6.3 3.3 4.7 1.6 Iris-versicolor 4.9 2.4 3.3 1.0 Iris-versicolor 6.6 2.9 4.6 1.3 Iris-versicolor 5.2 2.7 3.9 1.4 Iris-versicolor 5.0 2.0 3.5 1.0 Iris-versicolor
5.9 3.0 4.2 1.5 Iris-versicolor
6.0 2.2 4.0 1.0 Iris-versicolor 6.1 2.9 4.7 1.4 Iris-versicolor
5.6 2.9 3.6 1.3 Iris-versicolor
6.7 3.1 4.4 1.4 Iris-versicolor 5.6 3.0 4.5 1.5 Iris-versicolor
5.8 2.7 4.1 1.0 Iris-versicolor
6.2 2.2 4.5 1.5 Iris-versicolor 5.6 2.5 3.9 1.1 Iris-versicolor
5.9 3.2 4.8 1.8 Iris-versicolor
6.1 2.8 4.0 1.3 Iris-versicolor 6.3 2.5 4.9 1.5 Iris-versicolor 6.1 2.8 4.7 1.2 Iris-versicolor 6.4 2.9 4.3 1.3 Iris-versicolor 6.6 3.0 4.4 1.4 Iris-versicolor 6.8 2.8 4.8 1.4 Iris-versicolor 6.7 3.0 5.0 1.7 Iris-versicolor 6.0 2.9 4.5 1.5 Iris-versicolor 5.7 2.6 3.5 1.0 Iris-versicolor 5.5 2.4 3.8 1.1 Iris-versicolor 5.5 2.4 3.7 1.0 Iris-versicolor
5.8 2.7 3.9 1.2 Iris-versicolor
6.0 2.7 5.1 1.6 Iris-versicolor
5.4 3.0 4.5 1.5 Iris-versicolor
6.0 3.4 4.5 1.6 Iris-versicolor 6.7 3.1 4.7 1.5 Iris-versicolor 6.3 2.3 4.4 1.3 Iris-versicolor 5.6 3.0 4.1 1.3 Iris-versicolor 5.5 2.5 4.0 1.3 Iris-versicolor
5.5 2.6 4.4 1.2 Iris-versicolor
6.1 3.0 4.6 1.4 Iris-versicolor 5.8 2.6 4.0 1.2 Iris-versicolor 5.0 2.3 3.3 1.0 Iris-versicolor 5.6 2.7 4.2 1.3 Iris-versicolor 5.7 3.0 4.2 1.2 Iris-versicolor
5.7 2.9 4.2 1.3 Iris-versicolor
6.2 2.9 4.3 1.3 Iris-versicolor
5.7 2.8 4.1 1.3 Iris-versicolor
6.3 3.3 6.0 2.5 Iris-virginica 5.8 2.7 5.1 1.9 Iris-virginica
7.1 3.0 5.9 2.1 Iris-virginica 6.3 2.9 5.6 1.8 Iris-virginica
6.5 3.0 5.8 2.2 Iris-virginica
7.6 3.0 6.6 2.1 Iris-virginica 4.9 2.5 4.5 1.7 Iris-virginica 7.3 2.9 6.3 1.8 Iris-virginica
6.7 2.5 5.8 1.8 Iris-virginica
7.2 3.6 6.1 2.5 Iris-virginica 6.5 3.2 5.1 2.0 Iris-virginica 6.4 2.7 5.3 1.9 Iris-virginica 6.8 3.0 5.5 2.1 Iris-virginica 5.7 2.5 5.0 2.0 Iris-virginica
5.8 2.8 5.1 2.4 Iris-virginica
6.4 3.2 5.3 2.3 Iris-virginica
6.5 3.0 5.5 1.8 Iris-virginica
7.7 3.8 6.7 2.2 Iris-virginica 7.7 2.6 6.9 2.3 Iris-virginica 6.0 2.2 5.0 1.5 Iris-virginica 6.9 3.2 5.7 2.3 Iris-virginica 5.6 2.8 4.9 2.0 Iris-virginica 7.7 2.8 6.7 2.0 Iris-virginica 6.3 2.7 4.9 1.8 Iris-virginica
6.7 3.3 5.7 2.1 Iris-virginica
7.2 3.2 6.0 1.8 Iris-virginica 6.2 2.8 4.8 1.8 Iris-virginica 6.1 3.0 4.9 1.8 Iris-virginica
6.4 2.8 5.6 2.1 Iris-virginica
7.2 3.0 5.8 1.6 Iris-virginica 7.4 2.8 6.1 1.9 Iris-virginica 7.9 3.8 6.4 2.0 Iris-virginica 6.4 2.8 5.6 2.2 Iris_virginica 6.3 2.8 5.1 1.5 Iris_virginica
6.1 2.6 5.6 1.4 Iris-virginica
7.7 3.0 6.1 2.3 Iris-virginica 6.3 3.4 5.6 2.4 Iris-virginica 6.4 3.1 5.5 1.8 Iris-virginica 6.0 3.0 4.8 1.8 Iris-virginica 6.9 3.1 5.4 2.1 Iris-virginica 6.7 3.1 5.6 2.4 Iris-virginica 6.9 3.1 5.1 2.3 Iris-virginica
6.8 3.2 5.9 2.3 Iris-virginica
6.7 3.3 5.7 2.5 Iris-virginica
6.7 3.0 5.2 2.3 Iris-virginica
6.3 2.5 5.0 1.9 Iris-virginica
6.5 3.0 5.2 2.0 Iris-virginica
6.2 3.4 5.4 2.3 Iris-virginica
5.9 3.0 5.1 1.8 Iris-virginica
运行结果：
Case 1: x = 4.3000 4.8000 4.9000 4.9000 5.0000 5.4000 5.5000 5.7000 5.8000 7.0000 7.1000 7.9000 End! Case 2: x = 2.0000 2.2000 2.3000 2.4000 2.5000 2.8000 2.9000
2.9000
3.0000 3.3000 3.4000
4.4000 End! Case 3: x =
1.0000 1.9000 3.0000 4.4000 4.5000 4.7000 4.8000
4.9000
5.0000 5.1000 5.2000
6.9000 End! Case 4: x =
0.1000 0.6000 1.0000 1.3000 1.4000 1.6000 1.7000
1.7000 1.8000 1.8000 1.9000
2.5000 End!
结论：
最后区间： a: [4.3 , 4.8],[4.9 , 4.9], [5.0 , 5.4], [5.5 , 5.7], [5.8 , 7.0],
[7.1 , 7.9]. b: [2.0 , 2.2], [2.3 , 2.4], [2.5 , 2.8], [2.9 , 2.9], [3.0 , 3.3], [3.4 , 4.4]. p: [1.0 , 1.9], [3.0 , 4.4], [4.5 , 4.7], [4.8 , 4.9], [5.0 , 5.1], [5.2 , 6.9]. q: [0.1 , 0.6], [1.0 , 1.3], [1.4 , 1.6], [1.7 , 1.7], [1.8 , 1.8], [1.9 , 2.5].
分裂点： a: 4.3, 4.9, 5.0, 5.5, 5.8, 7.1 b: 2.0, 2.3, 2.5, 2.9, 3.0, 3.4 p:
1.0, 3.0, 4.5, 4.8, 5.0, 5.2 q: 0.1, 1.0, 1.4, 1.7, 1.8, 1.9
五、实验体会
ChiMerge是监督的、自底向上的数据离散化方法。它依赖于卡方分析：具有最小卡方值的相
邻区间合并在一起，直到满足确定的停止标准。
基本思想：对于精确的离散化，相对类频率在一个区间内应当完全一致。因此，如果两个相
邻的区间具有非常类似的类分布，则这两个区间可以合并；否则，它们应当保持分开。而低
卡方值表明它们具有相似的类分布
（1）、ChiMerge的工作原理：
ChiMerge算法过程：
第一步：初始化：
根据要离散的属性对实例进行排序；每个实例属于一个区间。
第二步：合并区间，又包括两步骤：
A、计算每一对相邻区间的卡方值；
B、将卡方值最小的一对区间合并。
简化为：
将离散属性值进行升序排序；
将每个实例设置成单独区间；
While（截止条件）
{
循环对每对相邻区间进行卡方计算，找出最小卡方值的相邻区间；
对相邻区间进行合并；
}
（2）、取鸢尾花数据集作为待离散化的数据集合，鸢尾花数据集可以从UCI机器学习数据库得到。使用ChiMerge方法，对四个数值属性分别进行离散化。（令停止条件为：max-interval=6）。需要写一个小程序，以避免麻烦的数值计算。提交你的简要分析和检验结果：分裂点、最终的区间以及源程序文档。
对鸢尾花数值的ChiMerge处理：
输入为：鸢尾花数据集
六、参考文献
1. 数学实验
2.数据挖掘