ChiMerge算法：卡方检验+ChiMerge+Python

• 2021 年 1 月 6 日
• AI
• Python, 算法

卡方分布与卡方检验

卡方分布

• 定义
  • 若n个相互独立的随机变量\xi_{1},\xi_{2},\dots,\xi_{n}均服从标准正态分布，则这n个服从标准正态分布的随机变量的平方和Q=\sum_{i=1}^{n}\xi_{i}^{2} 构成一个新的随机变量，其分布规律称为\chi_{2}分布（chi-square distribution），记为Q满足自由度为v的\chi_{2}分布Q \sim \chi^{2}(v)Q \sim \chi^{2}_{v}（其中v=n-k，k为限制条件数）；
  • 卡方分布是由正态分布构造而成的一个新的分布，当自由度v很大时，卡方分布近似为正态分布。
• 概率密度函数
  • 
  • f(x ; k)=\left\{\begin{array}{ll}
    \frac{x^{(k / 2)-1} e^{-x / 2}}{2^{k / 2} \Gamma\left(\frac{k}{2}\right)}, & x \geq 0 \\
    0, & \text { otherwise }
    \end{array}\right.
  • 其中，\Gamma (\frac {k}{2})是伽玛函数；
  • 均值为自由度v，记为 E(\chi^{2})=v；
  • 方差为2倍的自由度:2v，记为D(\chi^{2}=2v。
• 性质
  • \chi_{2}分布在第一象限内，卡方值都是正值，随着参数v的增大，\chi_{2}分布趋近于正态分布；
  • 卡方分布密度曲线下的面积都是1；
  • 随着自由度v的增大，\chi_{2}分布向正无穷方向延伸（因为均值v越来越大），分布曲线也越来越低阔（因为方差2v越来越大）。
  • 不同的自由度决定不同的卡方分布，自由度越小，分布越偏斜；自由度越大，该函数图像越对称；
  • 若\chi_{2}(v_2)，\chi_{2}(v_2)互相独立，则\chi_{2}(v_2)+\chi_{2}(v_2)服从\chi_{2}分布，自由度为v_1+v_2。
• OneMoreThing（有待商榷）：”为什么这里\xi需要正态分布，我的理解是，如果零假设为真，那么观测值和期望值之间的波动程度，应该是正态分布的，或者说“噪声”应该是正态分布的。”源自卡方检验详解

卡方\chi^{2}检验

• 基本原理：卡方检验就是统计样本的实际观测值与理论推断值之间的偏离程度，实际观测值与理论推断值之间的偏离程度就决定卡方值的大小，如果卡方值越大，二者偏差程度越大；反之，二者偏差越小；若两个值完全相等时，卡方值就为0，表明理论值完全符合。
• 首先假设H_0（观察频数与期望频数没有差别）成立，基于此前提计算出\chi^{2}值。如果\chi^{2}值“小”，倾向于接受H_0；如果\chi^{2}值大，就倾向于拒绝H_0。至于\chi^{2}在每个具体研究中究竟要大到什么程度(置信度)才能拒绝\chi^{2}，则要借助于卡方分布与自由度确定所对应的P值。
• \chi^{2}值计算
  • 设A代表某个类别的观察频数，E代表基于H_0计算出的期望频数，A与E之差称为残差；
  • 残差可以表示某一个类别观察值和理论值的偏离程度，由于残差有正有负，相加后会彼此抵消，为此可以将残差平方后求和；
  • 残差大小是一个相对概念，相对于期望频数为10时，期望频数为20的残差非常大，但相对于期望频数为1000时20的残差就很小了，为此，将残差平方除以期望频数再求和，以估计观察频数与期望频数的差别。
  • \chi^{2}=\sum \frac{(A-E)^{2}}{E}=\sum_{i=1}^{k} \frac{\left(A_{i}-E_{i}\right)^{2}}{E_{i}} \quad(i=1,2,3, \ldots, k)
• 检验的应用
  • 拟合优度检验（chi-squared test goodness of fit）
    • 实际执行多次试验得到的观察次数，与期望次数相比较，称为卡方适度检验，即在于检验二者接近的程度，利用样本数据以检验总体分布是否为某一特定分布的统计方法；
    • 零假设：观察分布等于期望分布；
    • \chi^{2}=\sum_{i=1}^{k} \frac{\left(A_{i}-n p_{i}\right)^{2}}{n p_{i}} \quad(i=1,2,3, \ldots, k)
    • 其中，n为总频数，p_i为i水平的期望频率,i水平的期望频数E_i等于总频数n×i水平的期望概率p_i;
    • 确定自由度；选择显著性水平；
    • 比较临界值和统计量（\chi^{2}值），若临界值大于统计量，差异不显著，接受零假设；否则拒绝。
  • 独立性检验（chi-squared test of independence)
    • 卡方独立性检验是用来检验两个属性间是否独立，以一个变量为行，另一个变量为列，组成相依表；
    • 零假设：两者相互独立，这样相依表的分布应该满足乘法公式，即两个独立事件一起发生的概率等于分别发生的概率之积；
    • \chi^{2}=\sum_{i=1}^{c} \sum_{j=1}^{r} \frac{\left(o_{i j}-e_{i j}\right)^{2}}{e_{i j}}，其中o_{i j}是联合事件(A_i,B_j)的观测频度（即实际计数），e_{i j}是(A_i,B_j)的期望频度，e_{i j}=\frac{\operatorname{count}\left(A=a_{i}\right) \times \operatorname{count}\left(B=b_{j}\right)}{n}，其中n是总计数，\operatorname{count}\left(A=a_{i}\right)是A中具有值a_i的个数，\operatorname{count}\left(B=b_{j}\right)是B中具有值b_j的个数；
    • 根据\chi ^2分布的百分点表，查找自由度(r-1)\times(c-1)下的显著水平，计算\chi^{2}值大于该值，拒绝假设，两属性相关，反之独立。
  • 卡方检验的样本量要求：一般认为对于卡方检验中的每一个单元格，要求其最小期望频数均大于1，且至少有4／5的单元格期望频数大于5，此时使用卡方分布计算出的概率值才是准确的。如果数据不符合要求，可以采用确切概率法进行概率的计算。

Python实现

见卡方分布、卡方独立性检验和拟合性检验理论及其python实现

ChiMerge算法

算法原理

• ChiMerge 是监督的、自底向上的(即基于合并的)数据离散化方法。它依赖于卡方\chi^{2}检验：具有最小卡方值的相邻区间合并在一起，直到满足确定的停止准则。
• 高质量的离散化应该是：区间内一致，区间之间区分明显。
• ChiMerge算法流程
  • 初始化：根据要离散的属性对实例进行排序：将数值属性的每个值看作一个区间(左闭右开)；
  • 自底向上区间合并，当满足停止条件的时候（高于预定卡方阈值），停止合并。
    • 计算每一对相邻区间的卡方值；
    • 
    • 将卡方值最小的一对区间合并。
• 卡方阈值的选择：先选择显著性水平，再由公式得到对应的卡方值。得到卡方值需要指定自由度，自由度比类别数量小1。例如，有3类，自由度为2，则90%置信度（10%显著性水平)下，卡方的值为4.6。阈值的意义在于，类别和属性独立时，有90%的可能性，计算得到的卡方值会小于4.6，这样，大于阈值的卡方值就说明属性和类不是相互独立的，不能合并。如果阈值选的大，区间合并就会进行很多次，离散后的区间数量少、区间大。
• ChiMerge算法推荐使用0.90、0.95、0.99置信度，最大区间数取10到15之间。
• 下图以部分iris数据集的sepal-length属性为例，计算不同区间的\chi_{2}值，将其与预定义阈值比较，合并低于预定义阈值的区间。
• 

Python实现

• 数据集：iris数据集，见下图。
• 

from collections import Counter
from time import ctime
 
def read(file):
    list_data=[]
    with open(file, 'r', encoding='utf-8') as fp:
        for line in fp:
            line=line.strip()
            if line!='':
                list_data.append(line.split(','))
    return list_data

def stas_count(list_data,i):
    ''' 统计将每个属性具体对应的类别，
     返回形如[['4.3', 'Iris-setosa', 1], ['4.4', 'Iris-setosa', 3],...]的列表'''
    list_vc=[] # list_value+class
    for r in list_data:
        list_vc.append(str(r[i]+','+r[4]))

    list_vcc=[] # list_value-class-count
    for k,v in dict(Counter(list_vc)).items():
        list_tmp = k.split(',')
        list_tmp.append(v)
        list_vcc.append(list_tmp)
 
    return list_vcc
 
def collect(list_data,i):
    '''根据第i个属性特征构造一个数据结构，以便使用ChiMerge算法。
    这个数据结构是形如 [('4.3', [1, 0, 0]), ('4.4', [3, 0, 0]),...]的列表，
    每一个元素是一个元组，
    元组的第一项是字符串，表示区间左端点，元组的第二项是一个列表，表示在此区间各个类别的实例数目'''
    list_cvv=stas_count(list_data,i)
    log_dic={}
    for record in list_cvv:
        if record[0] not in log_dic.keys():
            log_dic[record[0]]=[0,0,0]
        if record[1]=='Iris-setosa':
            log_dic[record[0]][0]=record[2]
        elif record[1]=='Iris-versicolor':
            log_dic[record[0]][1]=record[2]
        elif record[1]=='Iris-virginica':
            log_dic[record[0]][2]=record[2]
        else:
            raise TypeError("Data Exception")
    list_tuple=sorted(log_dic.items())
    
    return list_tuple
 
 
def combine(a,b):
    '''  a=('4.4', [3, 1, 0]), b=('4.5', [1, 0, 2])
         combine(a,b)=('4.4', [4, 1, 2])  '''
    c=a[:] # c[0]=a[0]
    for i in range(len(a[1])):
        c[1][i]+=b[1][i]
    return c

def chi2(A):
    m=len(A)
    k=len(A[0])
    R=[]
    for i in range(m):
        sum=0
        for j in range(k):
            sum+=A[i][j]
        R.append(sum)
    C=[]
    for j in range(k):
        sum=0
        for i in range(m):
            sum+=A[i][j]
        C.append(sum)
    N=0
    for ele in C:
        N+=ele
    M=0
    for ele in R:
        M+=ele
    assert  M==N
    res=0
    for i in range(m):
        for j in range(k):
            Eij=R[i]*C[j]/N
            if Eij!=0:
                res=res+(A[i][j]-Eij)**2/Eij
    return res

def ChiMerge(list_tuple,max_interval):
    num_interval=len(list_tuple)
    while num_interval>max_interval:               
        num_pair=num_interval-1 # 需两两配对，故减1
        chi_values=[]
        for i in range(num_pair):
            arr=[list_tuple[i][1],list_tuple[i+1][1]]
            chi_values.append(chi2(arr))
        min_chi=min(chi_values) # 最小卡方值
        for i in range(num_pair-1,-1,-1): # 合并最小值相邻区间
            if chi_values[i]==min_chi:
                list_tuple[i]=combine(list_tuple[i],list_tuple[i+1])
                list_tuple[i+1]='Merged'
        while 'Merged' in list_tuple:
            list_tuple.remove('Merged')
        num_interval=len(list_tuple)
    split_points=[record[0] for record in list_tuple]
    
    return split_points


def run(path):
    list_iris =read(path)
    max_interval=6 # 离散化区间个数
    num_attr=4 # 属性类别
    for i in range(num_attr):
        list_tuple=collect(list_iris,i)
        split_points=ChiMerge(list_tuple,max_interval) # discretize data using ChiMerge algorithm 
        print(split_points)
 

if __name__=='__main__':
    print('Start: ' + ctime())
    run('iris.data')
    print('End: ' + ctime())

参考

1. 卡方检验详解 //www.jianshu.com/p/fcfac399de13
2. 卡方检验 //blog.csdn.net/qunxingvip/article/details/50447864
3. 卡方分布、卡方独立性检验和拟合性检验理论及其python实现 //www.cnblogs.com/Yuanjing-Liu/p/9252844.html
4. ChiMerge算法 //markdown.blog.csdn.net/article/details/50449376?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.control&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.control
5. ChiMerge: Discretization of Numeric Attribute //www.aaai.org/Papers/AAAI/1992/AAAI92-019.pdf