《EBNC一种扩展的Bayes网络分类挖掘算法》由会员分享，可在线阅读，更多相关《EBNC一种扩展的Bayes网络分类挖掘算法（3页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 2 V 0 1 2 9 N 9 8E B N C ：一种扩展的B a y e s 网络分类挖掘算法E B N C ! A nE x t e n d e dA l g o r i t h mo fB a y e s i a nN e t w o r kf o rC l a s s i f i c a t i o nM i n i n g刘震袁晴晴陈良剐汪卫施伯乐 ( 复旦大学计算机与信息技术系上海2 0 0 4 3 3 )A b s t r a c tC l a s s i f i c a t i o ni Sa ni m p o r t a n td a t am i n
2、 i n gp r o b l e ma n di ti sw e l l s t u d i e d D e c i s i o nT r e e sa n dB a y e s i a nN e t w o r k sa r et W Ob a s i ct e c h n i q u e sf o rd a t ac l a s s i f i c a t i o n A l t h o u g ht h es i m p l e s ta n da l s ot h em o s tw i d e l yu s e da p p r o a c hi sD e c i s i o nT
3、 r e e s ，B a y e s i a nN e t w o r k sa r em o r ea c c u r a t et h a nD e c i s i o nT r e e si nc l a s s i f i c a t i o n ，w h i c hi n t e g r a t et h eb a c k g r o u n dk n o w l e d g eo ft h ee x p e r t s w i t ht h ei n f o r m a t i o ni nt r a i n i n gd a t as e t s U n f o r t u n
4、 a t e l y ，m o s tB a y e s i a nN e t w o r km e t h o d sc a no n l yh a n d l ed e c i s i o na t t r i b u t e sw i t hd i s c r e t ev a l u e s I nt h i sp a p e r ，w ep r o p o s ea ne x t e n d e da l g o r i t h mo fB a y e s i a nN e t w o r k sc a l l e dE B N C ，w h i c hc a np r o c e
5、s sb o t hd i s c r e t ea n dc o n t i n u ev a l u e da t t r i b u t e s K e y w o r d sD a t am i n i n g ，C l a s s i f i c a t i o n ，B a y e s i a nn e t w o r k1 引言分类技术是一种数据分析形式，它被人们公认 为是新兴的数据挖掘领域中的一个重要问题 1 。分 类技术可以用于抽取描述重要数据类的模型。人们已对它进行了广泛深入的研究。分类问题中最基本的两种方法是决策树方法和B a y e s i a n 网络方法。目前，国际
6、上比较精确的分类预测方法是神经网络方 法，它比决策树方法准确，但却需要更长的学习时间比 ，从而使用最广泛的仍然是决策树方法。本文提出一种B a y e s 网络的算法，称之为E B N C 。 国际上当前使用最广泛的方法是B a y e s 方法。 大多数从数据中学习B a y e s 网络的算法由两个部分组成：一个评分标准和一个查找程序。评分标准为每 一种B a y e ，S 网络结构计算一个分数，该分数反映这个结构和数据相吻合程度。查找程序用来找出获得 高分的网络结构。每当输入一个训练样本，B a y e s 网 络结构就要根据该样本信息调整自己的参数，这使 得学习的过程变得非常的漫长。E
7、 B N C 没有采用一般训练B a y e s 网络算法的这两个组成部分。它首先 使用g i n i 系数来二分连续属性的取值范围，使之离散化，并且求出依次考虑节点的顺序；之后利用基于 信息论中的互信息的依赖系数，来度量节点之间的 相互依赖关系，从而建立B a y e s 网络的结构。由于一 次处理的是所有数据集合中的数据，因此训练B a y e s 网络的速度比一般的算法快。2 基本概念及B a y e s 网络简介在2 1 节中，我们先来回顾一下概率统计及信息* ) 本文褥列国家自然科学基金重点硬目的资助( 编号：6 9 9 3 3 0 1 0 ) 1 0 4 论的一些基本概念。然后2
8、2 节说明如何将B a y e s 理论运用在分类中。最后，2 3 节简略介绍一下B a y e s网络的概念。 2 1 基本概念定义1先验概率( 略) ，先验概率可以根据人的经验和历史资料来推断。定义2 后验概率( 略) 。B a y e s 公式：公式( 1 ) ( 略) 。定义5 1 2 S 的g i n i 系数( 略) 。计算公式为公 式( 2 )g i n i ( S ) = 1 一蚤分( 2 )定义4 口2 3分割后的数据集合的g i n i 系数( 略) 。计算公式为公式( 3 ) ：g i n i ，p m i S ) 一百n i ( I S l ) + 等垂“ “| S2
9、)【3 2 2B a y e s 理论在分类中的运用假设向量X 一( x ，X 。，X n ) 是一个未知其类标 签变量C 取值的样本，以下简称这样的样本为未知 样本。X 中的每一个分量x i 对应于数据库中的一个决策属性A ；，i = 1 ，n 。标签变量C 有m 个可能的取值，记为C j ( j 一1 ，m ) 。为了决定X 的类别，我们需要知道条件概率P ( C 。l X ) ，即给定样本x ，断言X 属于C j 为真的概率，j = 1 ，n 。如果在所有P ( c I X ) ( j 一1 ，m ) 中，P ( C k l X ) 值最大，我们就把X归为C k 类。从B a y e s
10、 公式，即公式( 1 ) 中，我们可以看出，给定个样本X ，P ( X ) 是常数。因此只要P ( C k ) P ( X lC k ) 在集合( P ( C j ) P ( XI C j ) I j = 1 ，n ) 中最大，P ( C kl X ) 在集合 P ( C ，I X ) I j 一1 ，n 中就会最大。对于 先验概率P ( C j ) 和条件概率P ( Xl C j ) ( j 一1 ，m ) ，可以由用户根据自己的经验确定，也可以根据训练 样本集合由算法估算出来。根据条件概率的公式，我们有：P ( X l C ，) 一尸( z l ，z 2 ，z 。I C ，) =P ( z
11、 ，h ，1 ，C i )( 4 )若记p a r e n t ( x 。) 为( X 1 ，x 2 ，X ，C ， 中与X ，存 在依赖关系的属性变量的集合( i 一1 ，n ) ，则P ( x ，l z l ，z 2 ，”，z ，一i ，C i ) = P ( z ，I p a r e n t ( x ，) )( 5 )从而，公式( 4 ) 变为：尸( X C j ) 一P ( z l ，z 2 ，z 。f C ，) 一p ( X ，I p 口理押f ( 蕾) )( 6 )2 5B a y e s 网络简介4 3 ( 略)5 E B N C 算法介绍整个算法将分成三步。第一步为数据准备阶段
12、。 这一阶段将为连续的属性找到分割其取值范围的最优二分点，同时，决定处理决策属性的次序。第二步 根据训练样本集合中的信息和专家的背景知识，计算节点之间的依赖系数，进而判断节点之间的联系， 构架B a y e s 网络有向图并计算每一个节点对应的C P T 。简单地说就是建立一个B a y e s 网络分类器。第 三步运用建立好的B a y e s 网络分类器，预测未知样本的类标签属性的取值。3 1 节、3 2 节和3 3 节分别介绍这三步的算法。由于篇幅原因，算法3 、4 、5 和6 的详细说明，参见文 4 3 。 5 1 数据预处理算法首先，我们为样本集合中每一个决策属性，按其取值的升序，建
13、立一个属性歹I j 表视图。该视图中包含三个字段决策属性、标签属性和样本标识。在算法中，我们还维护一个称为直方图的数据结构 3 。从上到下扫描属性列表时，连续属性的直方图中B b e - 。w 表示已处理的样本中该属性和类标签属 性取值联合分布，B 。h 表示的是尚未处理的样本中该属性和类标签属性取值联合分布。B k l o ，初始化为0 ，B 如。初始化为全部样本中该属性和类标签属性取值的联合分布。而对于离散取值的属性，它的直方图就是全部样本中该属性和类标签取值的联合分布。我们首先采用算法1 ，根据g i n i 系数，对连续属性的取值范围进行最优二分。g i n i 讪，系数的具体计 算方
14、法见公式( 2 ) ( 3 ) 。算法1为一个连续取值的属性，找到一个最优二分点。输入：S a m p l e s ，样本集合； S ，样本的个数A ，一个连续取值的属性。 输出：S p l i t ( A ) ，A 的最优二分点； r u i n g ! h i ，用S p l i t ( A ) 划分S a m p l e s 得到的S a m p l e s 的 最小的g i n i I p I i t ( S a m p l e s ) 系数。 方法： 1 ) 初始化直方图； 2 ) C u r s o r = 0 ；将游标移动到属性列表开始 3 ) 根据直方图中的信息计算g i n
15、i p l j 。( S a m p l s ) ； 4 ) m i ng i n i = g i n i I p l i t ( S a m p l e s ) ； 5 ) S p l i t ( A ) 一游标所在处A 的取值； 6 ) W H I L E ( C u r s o r l = s ) 如果游标没有移动到属性列表结束 7 )B E G I N 8 )C u r s o r = C u r s o r + 1 ； 9 )修改直方图中的信息； l O )根据直方图中的信息计算g i n i I p l i t ( S a m p l e s ) ；11 )I Fg i n i ,
16、 p J i ，( S a m p l e s ) 。4 算法的一个实例( 略)5 算法分析与比较5 1 算法复杂度分析E B N C 首先利用g i n i 系数使连续属性离散化。 再利用依赖系数作为测度，根据样本空间中数据信 ：k 衡量各个节点之间的关系，从而构建B a y e s 网 、算法2 的最大时间复杂度为O ( N * S ) ，算法3 的 k 时间复杂度为O ( N * M * K ) ，算法4 的最大时，_ 之杂度为O ( N 2 ) ，从而整个构建算法的最大时间 型杂度为O ( N * M * K + N 2 + N * S ) ，其中N 为属性个数，M 为属性最多的取值个数，K 为节点的父节点最多联合取值状态数，S 是样本数据的个数。 在一般情况下，采用B a y e s 方法学习B a y e s 网 络，假设网络中每一个节点最多只有k ( k 一2 ) 个父节点，
