简介
ChiMerge是一种监督的、自底向上的数据离散化方法，依赖于卡方分析。
算法流程
初始化
初始化过程分为排序和初始离散化。
首先根据训练样本对被离散属性的值进行排序，在每个样本前后放置一个区间边界。
合并
将具有最小卡方值的相邻区间合并在一起，直到满足确定的停止标准。
卡方值的计算公式：
$ \sum_{1}^{m}\sum_{1}^{k}\frac{(Aij-Eij)^2}{Eij} $
m=2（比较的两个区间）
k为种类数
Aij为第i个区间，第j个种类的样本数
Ri为第i个区间内的样本数
Cj为第j个种类内的样本数
N为总样本数
Eij为Aij的期望频率，计算公式为Ri*Cj/N
分裂点
分裂点是划分区间的点。
具体实现
数据集
示例：5.1,3.5,1.4,0.2,Iris-setosa
分别代表：花萼长度(sepal-length)、花萼宽度(sepal-width)、花瓣长度(petal-length)、花瓣宽度(petal-width)、类别
输入数据处理
输入的类别使用的是字符串，所以先将对类别编码以便后续处理。
使用strcmp()进行处理，该函数是C语言中的字符串比较函数，如果返回值为0则表示两字符串相等。
数据中有四种类型的数据，所以需要计算四次。因此将ChiMerge写成函数调用比较方便。
ChiMerge(A)
为了计算卡方值，需要先计算期望频数（类别样本数*区间样本数/总样本数）
需要注意，在计算期望频数时，如果某个期望频数为0，会导致计算卡方值时分母为0，将会引起错误。所以当期望频数为0时，应该改为一个较小的非零值以保证计算的稳定性。
完整代码
function main
[a,b,c,d,class] = textread('iris.txt','%f,%f,%f,%f,%s');
%花萼长度，花萼宽度，花瓣长度，花瓣宽度，类别
num = size(class);
for i = 1:num(1)
if strcmp(class(i),'Iris-setosa')==1
cls(i,1)=1;
elseif strcmp(class(i),'Iris-versicolor')==1
cls(i,1)=2;
elseif strcmp(class(i),'Iris-virginica')==1
cls(i,1)=3;
end
end
A = [a cls];
B = [b cls];
C = [c cls];
D = [d cls];
disp('sepal-length:');
chimerge(A);
disp('sepal-width:');
chimerge(B);
disp('petal-length:');
chimerge(C);
disp('petal-width:');
chimerge(D);
function X = chimerge(A)
% X矩阵的第一、二行代表两个待合并区间中各个类别的频数，第三行代表每个区间中各个类别的的样本总数，第一列到第三列代表各个类别的频数，第四列到第六列代表各个类别的期望频数，第七列代表每个区间的样本总数
y = sortrows(A,1);%按属性值排序
ys = size(y);
ylen = ys(1);%属性值个数
x = [y(:,1),y(:,1)];%初始化区间矩阵，初始值设置为y的第一列属性值
xs = size(x);
xlen = xs(1);%区间个数
while xlen > 6 %停止条件为最大区间数为6
min = 999999;%保存最小卡方值，初始化为一个较大的值
for j = 1:xlen-1
ans = 0;
X = zeros(3,7);
%对于每个区间，统计在该区间内属于每个类别的样本数，存储在X矩阵中
for i = 1:ylen
if y(i,1)>=x(j,1)&&y(i,1)<=x(j,2)
X(1,y(i,2))=X(1,y(i,2))+1;
elseif y(i,1)>=x(j+1,1)&&y(i,1)<=x(j+1,2)
X(2,y(i,2))=X(2,y(i,2))+1;
end
end
%计算每个类别的样本个数
for i = 1:3
X(3,i) = X(1,i)+X(2,i);
end
%计算每个区间的样本个数，存储在X的第七列中
for i =1:3
X(i,7) = X(i,1)+X(i,2)+X(i,3);
end
%计算期望频数
for i = 1:2 %两个待合并区间
for k = 4:6 %每个类别的期望频数
X(i,k) = X(i,7)*X(3,k-3)/X(3,7);
if X(i,k) == 0%避免零分母的情况
X(i,k) = 0.1;
end
end
end
%计算卡方值
for i = 1:2
for k = 1:3
ans = ans + ((X(i,k)-X(i,k+3))^2)/X(i,k+3);
end
end
if ans <= min
min = ans;
key = j;%记录最小卡方值的区间
end
end
%合并区间，删除合并过的后一个区间
x(key,2) = x(key+1,2);
x(key+1,:) = [];
xlen = xlen-1;%更新区间数
end
x
输出结果
>> ChiMerge
sepal-length:
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
sepal-width:
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
petal-length:
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
petal-width:
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
后记
离散化是一种很重要的处理，因为很多分类算法都需要离散的训练数据。ChiMerge是一种通用且具有鲁棒性的离散化算法。
ChiMerge算法根据卡方检验进行分箱，将连续的值划分为多个区间来实现离散化。
为什么采用卡方检验？
卡方检验确定的是观察到的频数与预期频数之间的偏离程度，最小卡方值确定的也就是最相似的分区。采用这样的方式能够有效地减少离散化过程中的信息损失，保留原始数据的特征
评估ChiMerge算法的一些手段
- 可视化分析
观察离散化后的属性值分布情况，如果离散化合理，不同区间内的数据应该有显著的差异性。 - 信息增益
计算离散化后的属性对目标变量的信息增益。通过比较原始连续属性和离散化后的属性的信息增益，可以判断ChiMerge算法是否能够保留原始数据的重要信息。 - 卡方统计量
计算离散化后相邻区间的卡方值，检验它们之间的差异是否具有统计值意义。如果卡方值显著高于预期阈值，说明离散化后的区间差异明显。 - 分类或回归模型评估
使用离散化后的属性作为输入，训练分类或回归模型，比较模型在原始连续属性和离散化后的属性上的性能指标（如准确率、精确度等）。
参考文献
[1] Randy Kerber, “ChiMerge: Discretization of Numeric Attributes”, AAAI, p.123, 1992.
[2] https://developer.aliyun.com/article/632385