数据挖掘中基于可辨识矩阵的连续属性离散化方法

数据挖掘

第２４卷第４期２００７年４月

统计研究

Ｓｔａｔｉｓｔｉｃａｌ

Ｒｅｓｅａｒｃｈ

Ｖ０１．弘。№．４

Ａｐｔ．２００７

数据挖掘中基于可辨识矩阵的

连续属性离散化方法

刘云霞

曾五一

内容提要：连续属性的离散化在数据挖掘中有着非常重要的作用。本文基于可辨识矩阵提出一种连续属性离散化的方法，并利用平均互信息量对离散化结果进行修正。该方法通过统计模拟取得了良好的效果。

关键词：数据挖掘；可辨识矩阵；连续属性；离散化中图分类号：Ｃ８１２

文献标识码：Ａ

文章编号：１００２—４５６５（２００７）０４—０００８—０３

ＤｉｓｃｒｅｔｉｚａｔｉｏｎｏｆＣｏｎｔｉｎｕｏｕｓＰｒｏｐｅｒｔｉｅｓＢａｓｅｄ

ｏｎ

Ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ

Ｍａｔｒｉｘ

ｉｎＤａｔａ

Ｍｉｎｉｎｇ

ＬｉｕＹｕｎｆｉａ＆ＺｅｎｇＷｕｙｉ

Ａｂｓｔｒａｃｔ：Ｔｈｅｄｉｓｃｒｅｔｉｚａｔｉｏｎｏｆ

ｃｏｎｔｉｎｕｏｕｓ

ｏｎ

ｐｒｏｐｅｒｔｉｅｓｉｓ

ｖｅｒｙ

ｉｍｐｏｒｔａｎｔｉｎｄａｔａｍｉｎｉｎｇ．Ｔｈｅｐａｐｅｒ

ｐｕｌｓ

ｆｏｒｗａｒｄ

ａ

ｍｅｔｈｏｄｏｆ

ｄｉｓｃｒｅｔｉｚａｔｉｏｎｏｆｃｏｎｔｉｎｕｏｕｓｐｒｏｐｅｒｔｉｅｓｂａｓｅｄｄｉｓｃｅｒｎｉｂｉｌｉｔｙｍａｔｒｉｘａｎｄｒｅｖｉｓｅｓｔｈｅｄｉｓｃｒｅｔｅｒｅｓｕｌｔｂｙ

ａｖｅｒａｇｅ

ｍｕｔｕａｌｉｎｆｏｒｍａｔｉｏｎ．

Ｃ．ｏｅｄｅｆｆｅｃｔｓ

ａｒｅ

ａｃｈｉｅｖｅｄｔｈｒｏｕｇｈｔｈｉｓｍｅｔｈｏｄｂｙｓｔａｔｉｓｔｉｃａｌｓｉｍｕｌａｔｉｏｎ．

Ｋｅｙｗｏｒｄｓ：Ｄａｔａｍｉｎｉｎｇ；ｄｉｓｃｅｍｉｂｉｈｔｙｍａｔｒｉｘ；ｃｏｎｔｉｎｕｏｕｓｐｒｏｐｅｒｔｉｅｓ；ｄｉｓｃｒｅｔｉｚａｔｉｏｎ

一、分类及问题的提出

寻找离散化处理方法以及相应的划分停止标准是连续属性离散化的主要研究内容。离散化方法主要有以下几种分类：有监督和无监督、全局和局部、动态和静态等…。这些分类中，有监督与无监督离散化的区别在于离散化时是否考虑了信息分类。

有监督离散化算法要求应尽量减少离散化过程中的信息损耗，或者说应该在保持决策表中分类能力不变的条件下，用尽可能少的断点将属性空间划分为尽可能少的子空间。其实质是把露维空间划分成有限个区域，使得每个区域中的对象的决策值相同，即要保持区间内的一致性和区间之间的差异性。另外，在离散化问题中，应该兼顾信息质量和统计质量幢１。目前对有监督离散化方法的研究主要是从遗传算法、统计检验、粗糙集和信息熵等方面进行的。

Ｃｈｉ２算法是最基本的一种基于独立性假设检验的离散化方法。它依据的是“区间内的一致性和区间之间的差异性”准则，要求区间内类属性的频数分

布大约一致，相邻两个区间中类属性的频数分布不大相同。也就是说，如果合并前相邻区间内类属性的概率分布相同，说明这两相邻区间与目标类的分布是完全独立的，那么它们合并后将不会影响目标类的概率分布。Ｃｈｉ２算法的不足表现在：在列联表中，如果每格期望频率小于某些最小值时，Ｃｈｉ２值的独立性假设检验是不可靠的拉１；每次循环只能归并两个区间，并且当样本规模较大时离散化速度较慢‘３｜。

本文就此提出一种基于可辨识矩阵的离散化方法，该方法既能够反映“区间内的一致性和区间之间的差异性”的原则又能够较好地克服Ｃｈｉ２算法的不足。

二、离散化算法的基本思路

（一）基于可辨识矩阵的离散化

在粗糙集理论中，可辨识矩阵的定义如下：令决策表系统为Ｓ＝（Ｕ，Ｒ，ｙ，，），Ｒ＝ＰＵＤ，Ｐ＝｛吼

Ｉ

ｆ＝１，…，肘｝为条件属性集，Ｄ＝｛ｄ。｝为决策属性

集（或称为类属性集），ｄ。表示决策属性ｍ个类中的

万方数据　

数据挖掘

第Ｍ卷第４期刘云■■五一：数据挖掘中基于可辨识矩阵的连续属性离散化方法

９

第Ｚ个类；Ｕ＝｛茗。，茗：，…，石Ⅳ｝是论域（或称为样本集），ｎ．（茹，）是样本ｘｊ在属性ａ；上的取值。

ｃＤ（ｉ’ｊ）《ｌ

ａｋ

Ｉ

ａｋ

Ｅ。Ｐ，ｈ小Ｊ纠“动｝’捌铡（１）

其中，ｉ，．『＝１，…，肘。

式（１）描述的是当两个样本的决策属性取值相同时，它们所对应的可辨识矩阵元素的取值为０；当两个样本的决策属性不同且可以通过某些条件属性的取值不同加以区分时，它们所对应的可辨识矩阵元素的取值为这两个样本属性值不同的条件属性集合，即可以区分这两个样本的条件属性集合；当两个样本发生冲突时，即所有的条件属性取值相同而决策属性的取值不同时，则它们所对应的可辨识矩阵中的元素取值为空集。因此，可辨识矩阵元素中是否包含空集元素可以作为判定决策表系统中是否包含不一致信息的依据ＨＪ。

对上述可辨识矩阵产生的规则进行修改，不是辨识两个样本的决策值是否相同，而是在初始区间与类属性形成的列联表中，辨识相邻初始区间之间类属性的分布结构是否相同，即由如下的规则产生可辨识矩阵：

％㈠加譬糍黧嚣孺㈤

其中，‘，ｔ为算法中构造的初始区间。式（２）可以这样理解：只要两个区间都包含有相同的类别即在辨识矩阵中相应的位置处以０表示，例如，如果，，，，Ｉ两个区间中都包含有３个类别中的第一和第二类则两区间在矩阵中的对应位置处的标号为０；如果一个区间包含第一和第二类，另一个区间只包含第一类，则两区间在矩阵中对应位置的标号为声。笔者认为将包含的类别相同的相邻区间合并，同将类属性概率分布相同的区间合并一样，都能够反映“区间内的一致性和区间之间的差异性”的原则，因此，可以将可辨识矩阵的思想作为算法中初始区间合并的基础。

（二）平均互信息量对离散化结果的修正在信息论中定义离散随机变量ｘ和ｌ，之间的互信息日（Ｘ：ｙ）为

日（Ｘ：ｌ，）＝Ｈ（Ｘ）一Ｈ（ＸＩ

Ｙ）（３）

也可以用概率表示为

以ｎ

ｙ）＝蚤蚤Ｐｈ确）ｌｏｇ揣（４）

万　

方数据它表示已知ｙ后盖“残留”的不确定度。这样，在了解ｙ以后，Ｘ的不确定度的减少量为日（Ｘ）一日（Ｘ：ｙ），这个差值实际上也是已知ｙ的取值后所提供的有关ｘ的信息。互信息量日（ｘ：ｙ）是统计依存程度的信息量度，表示它们之间存在的统计依赖关系瞪１。

之所以在本文中提到平均互信息量的概念，是因为根据式（２）进行合并后的结果可能存在区间样本数很小的情况。为避免过度拟合，需要对这些样本数小于阀值的区间再次合并，那么就有应该合并到前一个还是后一个区间的问题。根据平均互信息量的定义知道，如果两区间的平均互信息量小就表

明两区间与类属性的依赖程度小，两区间的合并对

类属性分布的影响也就小，因此可以合并。

设，Ｉ、，Ｉ＋。和，Ｉ＋：是相邻区间，区间‘、ｔ＋。与类属性的平均互信息量以及区间‘＋。、，Ｉ＋：与类属性的平均互信息量分别是

见（¨）＝善ｔ＋ｌ苫Ｐ（，，，ｄ１）ｌｏｇ揣（５）

乩（副）－，萎，∑Ｉ＝１

，＝¨ｌ

Ｐ（，，，ｄ１）ｌｏｇ揣（ …… 此处隐藏：1911字，全部文档内容请下载后查看。喜欢就下载吧 ……