Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 数据开采与知识发现综述（三）
发信站: 哈工大紫丁香 (2001年06月14日16:00:46 星期四), 站内信件

三、数据开采的各种方法和技术
    下面介绍10种数据开采和知识发现的方法和技术,它们分别从不
同的角度进行数据开采和知识发现。
    1.决策树方法
    利用信息论中的互信息(信息增益)寻找数据库中具有最大信息量
的字段,建立决策树的一个结点,再根据字段的不同取值建立树的分支
;在每个分支子集中重复建树的下层结点和分支的过程,即可建立决策
树。国际上最有影响和最早的决策树方法是Quiulan研制的ID3方法,
它对越大的数据库效果越好。在ID3方法的基础上,后人又发展了各种
决策树方法。
    我们研制的IBLE方法是,利用信息论中的信道容量,寻找数据库中
信息量从大到小的多个字段的取值,建立决策规则树的一个结点,再根
据所有字段取值的权值之和与两个阈值比较, 建立左、中、右三个分
支;在各分支子集中重复建树的结点和分支的过程,即可建立决策规则
树。IBLE方法与ID3方法相比,在识别率上提高了10个百分点。
    2.神经网络方法
    它模拟人脑神经元结构,以MP模型和Hebb学习规则为基础,建立了
三大类多种神经网络模型。
    (1)前馈式网络 它以感知机、反向传播模型、函数型网络为代表
,可用于预测、模式识别等方面。
    (2)反馈式网络 它以Hopfield的离散模型和连续模型为代表,分
别用于联想记忆和优化计算。
    (3)自组织网络 它以ART模型、Koholon模型为代表,用于聚类。
    神经网络的知识体现在网络连接的权值上,是一个分布式矩阵结
构;神经网络的学习体现在神经网络权值的逐步计算上(包括反复迭代
或累加计算)。
    3.覆盖正例排斥反例方法
    它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。比较
典型的有Michalski的AQ11方法、洪家荣改进的AQ15方法,以及洪家荣
的AE5方法。
    AQ系列的核心算法是,在正例集中任选一个种子,到反例集中逐个
比较,对字段取值构成的选择子相容则舍去,相斥则保留。按此思想循
环所有正例种子,将得到正例集的规则(选择子的合取式)。AE系列方
法是用扩张矩阵来完成的。
    4.粗集(Rough Set)方法
    在数据库中,将行元素看成对象,列元素看成属性(分为条件属性
和决策属性)。等价关系R定义为不同对象在某个(或几个)属性上取值
相同,这些满足等价关系的对象组成的集合称为该等价关系R的等价类
。条件属性上的等价类E与决策属性上的等价类Y之间有三种情况:①
下近似:Y包含E;②上近似:Y和E的交非空;③无关:Y和E的交为空。对
下近似建立确定性规则,对上近似建立不确定性规则(含可信度),对无
关情况不存在规则。
    5.概念树方法
    对数据库中记录的属性字段按归类方式进行抽象,建立起来的层
次结构称为概念树。如"城市"概念树的最下层是具体市名或县名(如
长沙、南京等),它的直接上层是省名(如湖南、江苏等),省名的直接
上层是国家行政区(如华南、华东等),再上层是国名(如中国、日本等
) 。利用概念树提升的方法可以大大浓缩数据库中的记录。对多个属
性字段的概念树进行提升,将得到高度概括的知识基表,然后再将它转
换成规则。
    6.遗传算法
    这是模拟生物进化过程的算法,由三个基本算子组成:
    (1)繁殖(选择) 是从一个旧种群(父代)选出生命力强的个体,产
生新种群(后代)的过程。
    (2)交叉(重组) 选择两个不同个体(染色体)的部分(基因)进行交
换,形成新个体。
    (3)变异(突变) 对某些个体的某些基因进行变异(1变0、0变1)。
    这种遗传算法可起到产生优良后代的作用。这些后代需满足适应
值,经过若干代的遗传,将得到满足要求的后代(问题的解)。遗传算法
已在优化计算和分类机器学习方面发挥了显著作用。
    7.公式发现
    在工程和科学数据库(由试验数据组成)中,对若干数据项(变量)
进行一定的数学运算,求得相应的数学公式。比较典型的BACON发现系
统完成了对物理学中大量定律的重新发现。其基本思想是,对数据项
进行初等数学运算(加、减、乘、除等),形成组合数据项,若它的值为
常数项,就得到了组合数据项等于常数的公式。
    我们研制了FDD发现系统。其基本思想是,对两个数据项交替取初
等函数后,与另一数据项的线性组合若为直线时,就找到了数据项(变
量)的初等函数的线性组合公式。该系统发现的公式比BACON系统发现
的公式更宽。
    8.统计分析方法
    在数据库字段项之间存在两种关系:①函数关系(能用函数公式表
示的确定性关系);②相关关系(不能用函数公式表示、但仍是相关确
定关系)。对它们的分析采用如下方法:回归分析、相关分析、主成分
分析。
    9.模糊论方法
    利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模
式识别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高,
精确化能力就越低,即模糊性越强。这是Zadeh 总结出的互克性原理
。
    10.可视化技术
    可视化数据分析技术拓宽了传统的图表功能,使用户对数据的剖
析更清楚。例如,把数据库中的多维数据变成多种图形,这对揭示数据
的状况、内在本质及规律性起了很大作用。

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]