利用 ChiMerge 分析鸢尾花数据集基本思想实战函数说明程序运行结果参考文献

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

基本思想

对于精确的离散化,相对类频率在一个区间内应当完全一致。 因此,如果两个相邻的区间具有非常类似的类分布,则这两个区间可以合并;否则,它们应当保持分开。 而低卡方值表明它们具有相似的类分布。

要点

  • 最简单的离散算法: 等宽区间 从最小值到最大值之间,均分为N等份 如此, 若 A, B为min/max, 则每个区间的长度为w=(B-A) / N, 区间边界值为 A+W, A+2W, …. A+(N-1)W
  • 类似的一种算法: 等频区间 间隔边界被选择为使得每个间隔包含大约相同数量的训练示例 因此,如果N = 10,每个区间将包含大约10%的例子

以上两种简单算法有弊端

  • 等宽区间划分,划分为5区间,最高工资50000,则所有工资低于10000的人都被划分到同一区间
  • 等频区间可能正好相反,所有工资高于50000的人都会被划分到50000这一区间中。

这两种算法都忽略了实例所属的类型,落在正确区间里的偶然性很大

  • C4、CART、PVM算法在离散属性时会考虑类信息,但随着算法的运行动态执行,而不是在预处理阶段。 例如,C4算法(ID3决策树系列的一种),将数值属性离散为两个区间,而取这两个区间时,该属性的信息增益是最大的。
  • 评价一个离散算法是否有效很难,因为不知道什么是最高效的分类
  • 离散化的主要目的 除了从训练数据中消除数值之外,还要产生一个简洁的数字属性汇总
  • 高质量的离散化 区间内均匀性,区间间差异
  • ChiMerge算法用卡方统计量来决定相邻区间的频率明显不同,如果它们足够相似以证明合并它们
  • ChiMerge算法包括两步,当满足停止条件的时候,区间合并停止
    • 初始化 根据要离散的属性对实例进行排序:每个实例属于一个区间
    • 合并区间,又包括两步 (1) 计算每一对相邻区间的卡方值 (2) 将卡方值最小的一对区间合并

预先设定一个卡方的阈值,在阈值之下的区间都合并,阈值之上的区间保持分区间

卡方的计算公式

参数说明

  • m=2(每次比较的区间数是2个)
  • k=类的数量
  • Aij=第i区间第j类的实例的数量
  • Ri=第i区间的实例数量
  • Cj=第j类的实例数量
  • N=总的实例数量
  • Eij= Aij的期望频率
  • 卡方阈值的确定 先选择显著性水平,再由公式得到对应的卡方值。 得到卡方值需要指定自由度,自由度比类别数量小1。例如,有3类,自由度为2,则90%置信度(10%显著性水平)下,卡方的值为4.6。 阈值的意义在于,类和属性独立时,有90%的可能性,计算得到的卡方值会小于4.6,这样,大于阈值的卡方值就说明属性和类不是相互独立的,不能合并。如果阈值选的大,区间合并就会进行很多次,离散后的区间数量少、区间大。 用户可以不考虑卡方阈值,此时,用户可以考虑这两个参数:最小区间数,最大区间数。用户指定区间数量的上限和下限,最多几个区间,最少几个区间。
  • ChiMerge算法推荐使用.90、.95、.99置信度,最大区间数取10到15之间以防止 过多的间隔被创建

实战

取鸢尾花数据集作为待离散化的数据集合,使用ChiMerge算法,对四个数值属性分别进行离散化 令停机准则为max_interval=6

下面Python程序

数据集

大致分两步:

整理数据

读入鸢尾花数据集,构造可以在其上使用ChiMerge的数据结构,即, 形如 [ ('4.3', [1, 0, 0]), ('4.4', [3, 0, 0]), ...] 的列表,每一个元素是一个元组,元组的第一项是字符串,表示区间左端点,元组的第二项是一个列表,表示在此区间各个类别的实例数目;

离散化

使用ChiMerge方法对具有最小卡方值的相邻区间进行合并,直到满足最大区间数(max_interval)为6

程序最终返回区间的分裂点

# coding=utf-8
from time import ctime

''' 读取数据'''


def read(irisdata):
    instances = []
    fp = open(irisdata, 'r')
    for line in fp:
        line = line.strip('\n')
        if line != '':
            instances.append(line.split(','))
    fp.close()
    return instances


''' 将第i个特征和类标签组合起来
 如:
    [ 
      [0.2,'Iris-setosa'],
      [0.2,'Iris-setosa'],
                ...
                          ]'''


def split(instances, i):
    log = []
    for line in instances:
        log.append([line[i], line[4]])
    return log


''' 统计每个属性值所具有的实例数量
 [['4.3', 'Iris-setosa', 1], ['4.4', 'Iris-setosa', 3],...]'''


def count(log):
    log_cnt = []
    # 以第0列进行排序的 升序排序
    log.sort(key=lambda attr: attr[0])
    i = 0
    while i < len(log):
        cnt = log.count(log[i])
        record = log[i][:]
        record.append(cnt)
        log_cnt.append(record)
        i += cnt
    return log_cnt


''' log_cnt  是形如: ['4.4', 'Iris-setosa', 3] 
    的统计对于某个属性值,对于三个类所含有的数量
    返回结果形如:{4.4:[0,1,3],...} 
    属性值为4.4的对于三个类的实例数量分别是:0、1、3 '''


def build(log_cnt):
    log_dict = {}
    for record in log_cnt:
        if record[0] not in log_dict.keys():
            log_dict[record[0]] = [0, 0, 0]
        if record[1] == 'Iris-setosa':
            log_dict[record[0]][0] = record[2]
        elif record[1] == 'Iris-versicolor':
            log_dict[record[0]][1] = record[2]
        elif record[1] == 'Iris-virginica':
            log_dict[record[0]][2] = record[2]
        else:
            raise TypeError('Data Exception')
    log_truple = sorted(log_dict.items())
    return log_truple


def collect(instances, i):
    log = split(instances, i)
    log_cnt = count(log)
    log_tuple = build(log_cnt)
    return log_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[:]
    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 = []
    '''第i个区间的实例数'''
    for i in range(m):
        sum = 0
        for j in range(k):
            sum += a[i][j]
        r.append(sum)
    c = []
    '''第j个类的实例数'''
    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
    res = 0.0
    for i in range(m):
        for j in range(k):
            Eij = 1.0 * r[i] * c[j] / n
            if Eij != 0:
                res = 1.0 * res + 1.0 * (a[i][j] - Eij) ** 2 / Eij
    return res


'''ChiMerge 算法'''
'''下面的程序可以看出,合并一个区间之后相邻区间的卡方值进行了重新计算,而原作者论文中是计算一次后根据大小直接进行合并的
下面在合并时候只是根据相邻最小的卡方值进行合并的,这个在实际操作中还是比较好的
'''


def chimerge(log_tuple, max_interval):
    num_interval = len(log_tuple)
    while num_interval > max_interval:
        num_pair = num_interval - 1
        chi_values = []
        ''' 计算相邻区间的卡方值'''
        for i in range(num_pair):
            arr = [log_tuple[i][1], log_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:
                log_tuple[i] = combine(log_tuple[i], log_tuple[i + 1])
                log_tuple[i + 1] = 'Merged'
        while 'Merged' in log_tuple:
            log_tuple.remove('Merged')
        num_interval = len(log_tuple)
    split_points = [record[0] for record in log_tuple]
    return split_points


def discrete(path):
    instances = read(path)
    max_interval = 6
    num_log = 4
    for i in range(num_log):
        log_tuple = collect(instances, i)
        split_points = chimerge(log_tuple, max_interval)
        print split_points


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

函数说明

  • collect(Instances,i) 读入鸢尾花数据集,取第i个特征构造一个数据结构,以便使用ChiMerge算法。这个数据结构 形如 [('4.3', [1, 0, 0]), ('4.4', [3, 0, 0]),...]的列表,每一个元素是一个元组,元组的第一项是字符串,表示区间左端点,元组的第二项是一个列表,表示在此区间各个类别的实例数目
  • ChiMerge(log_tuple,max_interval) ChiMerge算法,返回区间的分裂点

程序运行结果

参考文献

http://www.aaai.org/Papers/AAAI/1992/AAAI92-019.pdf

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数值分析与有限元编程

广义雅可比方法

标准雅可比方法只能求解标准特征值问题。对于广义特征值问题需要采用广义雅可比方法求解。 前面已提到标准Jacobi方法的理论依据是对于实对称阵 A,必有正交阵 ...

33550
来自专栏互联网大杂烩

算法岗面试

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包...

8520
来自专栏nnngu

数据结构01 算法的时间复杂度和空间复杂度

1、算法的概念: 算法 (Algorithm),是对特定问题求解步骤的一种描述。 解决一个问题往往有不止一种方法,算法也是如此。那么解决特定问题的多个算法之间如...

32830
来自专栏C语言及其他语言

【优质题解】题号1174:【计算直线的交点数】 (C语言描述)

题号1174,原题见下图: ? 解题思路: 将n条直线排成一个序列,直线2和直线1最多只有一个交点,直线3和直线1,2最多有两个交点,……,直线n 和其他n...

30160
来自专栏小樱的经验随笔

裴蜀定理(贝祖定理)及证明

在数论中,裴蜀定理是一个关于最大公约数(或最大公约式)的定理 在数论中,裴蜀定理是一个关于最大公约数(或最大公约式)的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀...

32850
来自专栏Vamei实验室

Python标准库12 数学与随机数 (math包,random包)

我们已经在Python运算中看到Python最基本的数学运算功能。此外,math包补充了更多的函数。当然,如果想要更加高级的数学功能,可以考虑选择标准库之外的n...

25880
来自专栏Phoenix的Android之旅

什么是随机和伪随机

互联网公司的年会抽奖环节正常都是用自己写的软件抽奖的, 然后我们经常会看到每年年会期间有些公司会在年会上现场 review抽奖代码, 基本都是觉得他丫的这是不是...

18820
来自专栏机器学习算法与Python学习

【干货】深度学习中的线性代数---简明教程

线性代数对于理解机器学习和深度学习内部原理至关重要,线性代数是有关连续值的数学。许多计算机科学家在此方面经验不足,传统上计算机科学更偏重离散数学。这篇博文主要介...

10630
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (上)

一提到“A*算法”,可能很多人都有"如雷贯耳"的感觉。用最白话的语言来讲:把游戏中的某个角色放在一个网格环境中,并给定一个目标点和一些障碍物,如何让角色快速“绕...

26560
来自专栏猿人谷

rand(),srand()产生随机数

      rand()函数可以用来产生随机数,但是这不是真真意义上的随机数,是一个伪随机数,是根据一个数,我们可以称它为种子,为基准以某个递推公式推算出来的一...

57480

扫码关注云+社区

领取腾讯云代金券