一种基于粗集理论的动态学习算法

徐嘉彬 高晓红

(楚雄师范学院数学系,云南 楚雄 675000)

一种基于粗集理论的动态学习算法

徐嘉彬 高晓红

(楚雄师范学院数学系,云南 楚雄 675000)

本文对数据库中新增对象重新进行分类,并对此提出了一种基于粗集理论的动态学习算法DLA,并对动态学习算法与传统算法在执行的时间长短上进行比较,得出动态学习算法能在数据库应用中有效地减少更新过程中的计算量,从而达到提高效率的目的。

粗集,动态学习,数据库,新增对象

粗集 (Rough set)理论[1]是由波兰教授 Pawlak于 1982年提出,由于它能有效地分析和处理不精确、不一致、不完整等各种不完备信息,并从中发现隐含的知识,揭示潜在的规律,近年来在机器学习、数据挖掘、人工神经网络等多个领域得到了广泛应用。

而动态学习算法的研究往往是粗集理论中各种研究的重要内容之一,当前在粗集理论的相关算法研究中,基本只适用于静态数据库,但是在现实应用中,数据库往往是不固定的,如数据对象的添加、修改和删除,常常会造成原有规则不适用数据库中的新增对象,而数据库系统往往是很庞大的,如果用以往的粗集理论算法来进行处理,每次更新数据库后都需要用原规则重新扫描一遍,不仅对服务器造成负担,还影响了效率。所以,为解决对大型数据库的修改,对动态学习算法的研究是非常有必要的。当前基于粗集理论的数据库应用中,大多是对静态数据的研究,对动态数据的研究重点是知识约简,而对规则的动态学习算法的研究侧重于针对原有对象的增量性研究上,而从最小规则集的方向研究增量性的还很少见。

为了使基于粗集理论的数据分析能够解决信息系统中的数据动态增长的问题,文献[2]根据决策属性原理把新增对象分为:增强、全新、全矛盾和部分矛盾四种类型,并给出了相关结论,但是在这四种类型中两两之间并不独立,例如增强型和部分矛盾型存在交叉对象。信息系统 (知识表达系统)可以用属性—数值形式的数据表来表示,该表可看作是现实和结果的集合,由此可以将它看作一特殊的数据逻辑结构,即前面提到的决策属性[3],相关决策属性的解释可参考文献 [4]。

1 新增对象的分类

传统算法对新增对象处理的方法是对决策表的知识约简和最小决策算法分别计算一次,显然这种方法不是最佳的,在研究中发现,首先对新增对象进行分类,再分别单独处理每种类型,这样可以有效地减少其计算量。

设 S=(U,P∪Q)是一个决策表,N是由 S产生的 PQ基本决策算法(P,Q)的一个最小决策算法,新增对象 x后得到新决策表 S′=(U′,P∪Q),其中U′=U∪{x}。

针对文献[2]中存在的问题,本文重新从决策属性的角度考虑,对新增对象给出如下新的分类:

类型1 称 x增强于N,对N中任意的规则φ→ψ,若φx/A(φ)→ψ,则至少存在一条这样的规则;

类型 2 称 x是全新的,对N中任意的规则φ→ψ,总有φx/A(φ)≠φ(或不存在 y∈U,使 y=φx|A(φ)→ψx|);

类型 3 称 x是全矛盾的,若存在 y∈U使φx=φy,但ψx≠ψ;

类型 4 称 x是部分矛盾的,若 x与N不是全矛盾且存在φ→ψ∈N使φx/A(φ)=φ但ψx≠ψ。

对于任意规则φ→ψ∈N,若φx/A(φ)|ψx,包含着ψx=ψ,则称对象 x与N不矛盾。

2 基于粗集的动态学习算法

根据上面的分类方法,详细分析不同对象的类型后,提出下面基于 DLA(Dynam ic Learning A lgorithm)算法的基本思路:

(1)新增对象 x;

(2)判断 x是否与 N均衡并计算 Cx,满足转向 (3),不满足转向 (14);

注:N为增添 x前的决策表S的最小决策算法,Cx={φ→ψ∈N|规则φ→ψ和对象 x矛盾}。

(3)N′=N-Cx,Fψ=Φ;注:N′为新增对象 x后新决策表 S′的最小决策算法。

(4)判断 x是否与 N全矛盾,矛盾转向 (5),不矛盾转向 (16);

(5)相比原约简 R,判断 x在U上是否均衡,均衡转向(6),不均衡转向(19);

(8)计算φz/R′→ψz(z∈D)的一个约简φ′→ψ′;注:φz为对象 z的条件部分。

(10)判断 Fψ在论域 U上是否完备,满足转向 (11),不满足转向 (20);

(11)在 D中删除决策为ψz的剩余对象;

(13)判断对象集 D是否为空,为空转向 (21),不为空转向 (8);

(14)判断 x是否增强 N,满足转向 (1),不满足转向 (15);

(15)R′=R,计算φx/R→ψ的一个约简φ→ψ同时把对象集 D置空,转向(13);

(16)令 y∈U与 x矛盾,计算 |ψy|s;

(17)修改 x使得其决策为ψx∨ψy;注:ψx∨ψy表示决策为ψx或ψy。

(19)求 S′的约简 R′,转向 (6);

(21)得到最小决策算法N′。

3 算法验证与分析

由于篇幅有限,对于DLA算法和传统算法的执行时间分析就不给出详细的过程,动态学习算法执行时间是以属性对的比较来作为最小计算单位的(假设数据对象集中有 p个属性 q个对象),传统算法在数据库更新时对所有情况都要重新求一次最小决策算法,执行的时间均为O(2m·q2·p3),而DLA算法在新增对象时增强于原最小决策算法的情况下的执行的时间为O(q·p2),在全新、全矛盾和部分矛盾(不需要再次求知识约简)的情况下执行的时间为O(q2·p2),只有在部分矛盾(需再次求知识约简)时才为O(2m·q2·p3)。

由上述分析可知:当 x增强于N、全新于N、全矛盾于N及部分矛盾于N(不需要再次求知识约简)时,执行的效率均优于传统算法,只有在 x部分矛盾于N(需再次求知识约简)时与传统算法的执行的效率相当,均为指数级算法。总体来看,本文所给出的动态学习算法比传统算法更加高效、可行。

4 结束语

本文给出了一种基于粗集的动态学习算法,并对DLA算法与传统算法在执行时间上的优缺点作了简单的分析,说明动态学习算法能在数据库应用中有效地减少更新过程中的计算量,从而达到提高效率的目的。

另外,本文给出的动态学习算法只适用于在原来模型的基础上增加一个对象的情况,而在日常生活中常常都是向数据库中增添一批对象,这就希望有关人士能在本文提出的算法基础上加以研究推广,以适用于增添一批对象的情况。

[1]Zdzislaw Pawlak.Rough set[J].International Journal of Computer and Infor mation Science,1982.11(5):341—356.

[2]TONG Ling-yun,AN L IP ING.IncrementalLearning of Decision RulesBased on Rough Set Theory[C].Shang hai:Proceedings of the4th W orld Congress on Intelligent Control and Automation,2002:420—425.

[3]Zdzislaw Pawlak.Rough set-theoretical aspects of reasoning about data[M].Boston, KluwerAcadem ic Publishers.1991:24—26.

[4]王国胤,Rough集理论与知识获取 [M].西安:西安交通大学出版社,2001: 23—38.

[5]L IDe-yu,ZHANG Bo.On Knowledge Reduction in Inconsistent Decision Information Systems[J].International Journal of Uncertainty, Fuzziness and Know ledge-B ased System s, 2004,12(5):651—672.

[6]L IANG Ji-ye,XU Zong-ben,M IAO Duo-qian.Reduction of Knowledge in Incomplete Information Systems[M].Beijing: PublishingHouseofElectronicsIndustry, 2000: 528—532.

[7]Munakata,Toshinori.Fundamentals of the New Artificial Intelligence[M].N ew York: Springer-Verlag,1998.

(责任编辑 刘洪基)

A Dynam ic Learn ing Algorithm(DLA)Based on Rough Set Theory

XU Jia-bin;GAO Xiao-hong
(Department of M athematics,Chuxiong N or m al University,Chuxiong675000,China)

In this paper,the author reclassified the new objects in the database,and put forward a dynamic learning algorithm(DLA)based on rough set theory,and compared the dynamic learning algorithm with the traditional algorithm in the implementation of length of time,dynamic learning algorithm derived in the database applications can effectively reduce the computational complexity,so as to enhance the computational efficiency.

rough set;dynamic study;data base;new object

TP18

A

1671-7406(2010)03-0032-03

2010-01-03

徐嘉彬 (1986—),男,云南楚雄人,学士,主要研究方向:粗集理论。