数据处理实战：对ChiMerge问题的分析与实现

青旅半醒 2022-08-11 00:51 174阅读 0赞

此问题与数据挖掘中的ChiMerge算法相关，用matlab程序实现。

**问题描述**

ChiMerge是监督的、自底向上的数据离散化方法。它依赖于卡方分析：具有最小卡方值的相邻区间合并在一起，直到满足确定的停止标准。

（1）简述ChiMerge如何工作。

（2）取鸢尾花数据集作为待离散化的数据集合，鸢尾花数据集可以从UCI机器学习数据库得到。使用ChiMerge方法，对四个数值属性分别进行离散化。（令停止条件为：max-interval=6）。你需要写一个小程序，以避免麻烦的数值计算。提交你的简要分析和检验结果：分裂点、最终的区间以及源程序文档。

**问题分析及回答**

（1）ChiMerge的工作原理

ChiMerge算法过程：

第一步：初始化： 根据要离散的属性对实例进行排序；每个实例属于一个区间。 第二步：合并区间，又包括两步骤： A、计算每一对相邻区间的卡方值； B、将卡方值最小的一对区间合并。 可简化为： 将离散属性值进行升序排序； 将每个实例设置成单独区间； while（截止条件） { 循环对每对相邻区间进行卡方计算，找出最小卡方值的相邻区间； 对相邻区间进行合并； }

（2）对鸢尾花数值的ChiMerge处理

输入：鸢尾花数据集（[http://archive.ics.uci.edu/ml/datasets/Iris][http_archive.ics.uci.edu_ml_datasets_Iris]）

*ChiMerge.m*

%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.m*

%建立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
            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

**运行结果：**

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

[http_archive.ics.uci.edu_ml_datasets_Iris]: http://archive.ics.uci.edu/ml/datasets/Iris