一種基于粗集理論的動態學習算法

徐嘉彬 高曉紅

(楚雄師范學院數學系,云南 楚雄 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—),男,云南楚雄人,學士,主要研究方向:粗集理論。