基于粗糙集的增量学习和数据过滤(2002.11.22).pptVIP

《人工智能》第四讲基于粗糙集的增量学习和数据过滤 浙江大学计算机科学与技术学院 2002年11月22日 * * 第一部分 基于粗糙集的增量学习 1.1 为什么需要增量学习算法？ ? 数据库中的数据是动态变化的 ? 数据量（训练样本）的变化引起重复学习 ? 应避免在海量数据的情况下重复学习 ? 只需修改因数据变化而涉及的规则 ? 增量学习算法是数据挖掘算法走向实用化 的关键问题之一 1.2 增量式学习 增量式算法的重要性体现在2个方面： ? 在实际的数据库中，数据量往往是逐渐增 加的，因此，在面临新的数据时，学习方法应能对训练好的系统进行某些改动，以对新数据中蕴涵的知识进行学习。 ? 对一个训练好的系统进行修改的时间代价通常低于重新训练一个系统所需的代价。 增量式算法：就是每当新增数据时，并不需要重建所有的知识库，而是在原有知识库的基础上，仅做由于新增数据所引起的更新，这更加符合人的思维原理。 ? 有了增量式学习算法的支持，知识库就处于动态更新状态，既能具有动态的自适应学习能力，又能有较好的时间特性。 ? 若一个算法是非增量式的，则其时间、空间耗费很大，影响其应用价值。 20世纪80年代中期，一些研究者致力于为决策树（Decision Tree）算法提供增量学习能力。主要成果有： （1）1986年，Schlimmer等提出的ID4算法； （2）1988年，Utgoff提出的ID5算法； （3）1996年，提出TDIDT、MSC算法等； （4) 1997年以后，提出ITI、增量树归纳算法等。 增量式学习问题划分为3类： ? E-IL(Example-Incremental Learning)：学习系统训练好之后，又得到了新的训练例。需要对训练好的系统进行一定的改动，以使其在尽可能保持已有知识的同时，能对新知识进行学习。 ? C-IL(Class-Incremental Learning) ：学习系统训练好之后，输出表示发生了变化，增加了新的输出分类。这时，没有或仅有少量已学习过的训练例可供使用。 典型实例：电子门锁。它对新增的家庭成员，仅需新获得的该新成员的人脸图像，而无需对整个系统进行重新配置和训练，就能将其与陌生人区分开来。 ? A-IL(Attribute-Incremental Learning)：学习系统训练好之后，输入表示发生了变化，增加了新的输出属性。例如，电子门锁与新的人脸特征识别辅助设备的关系。 1.3 基于粗糙集的增量式学习 1994年，N.Shan等人提出一种适用于一致性数据的决策矩阵（Decision Matrix）增量算法。该算法的基本思想如下： ? 对于一个决策系统，根据其决策属性值的数量而决定该决策系统所对应的决策矩阵的个数，即一个决策值对应于一个决策矩阵。 ? 设信息系统I=U,A?{d}，设Xi,Xj?U/IND({d}), 1 ? i,j ? |U/IND({d})|。Xi包含的对象个数为r,Xj包含的对象个数为s，则Xi对于Xj的决策矩阵M(i,j)是一个r*s的矩阵。矩阵中的第i行与第j列的元素表示对象的属性中所有差异属性的析取。 例如：表1.1是医学诊断的一个信息系统I=(U, A) 。其中，U = {e1, e2, ..., e7}, A = {A, T} ? {F}。为方便表达，用1表示“是”，0表示“否”；2表示体温“很高”，1表示体温“高”，0表示体温“正常”，则表1.1的简化形式如表1.2所示。 表1.1 医学诊断信息系统的描述 是 很高 否 e6 否 高 否 e5 否 正常 否 e4 是 很高 是 e3 是 高 是 e2 否 正常 是 e1 流感F 体温T 头痛A 实例 表1.2 简化后的决策系统 1 2 0 e6 0 1 0 e5 0 0 0 e4 1 2 1 e3 1 1 1 e2 0 0 1 e1 F T A U (T, 2) (T, 2) (A, 0) ? (T, 2) e6 (A, 1) ? (T, 2) (A, 1) ? (T, 2) (T, 2) e3 (A, 1) (A, 1) ? (T, 1) (T, 1) e2 e5 e4 e1 表1.3 对应决策为1的决策矩阵 将决策矩阵中的每行的元素进行合取，然后进行简化，得到相应的必然规则： ? (T, 1) ? ((A, 1) ? (T, 1)) ? (A, 1) ? (F, 1) 得 (T, 1) ? (A, 1) ? (F, 1) (1) ? (T, 2)