以增量式約略集何為基礎的規則歸納法

An Incremental Rough Set Based Rule Induction

范有寧(Fan, Yu-Neng)

指導教授 ： 黃俊哲

國立暨南國際大學/管理學院/資訊管理學系/碩士(2007年)

摘要

增量式演算法是藉由保留某些上一次探勘後的相關資訊，當資料新增時，不需要重新執行現有的資料探勘方法即能夠維持規則的正確性與有效性。文獻中顯示，有相當多數的增量式演算法應用於約略集合領域，但傳統的增量式約略集合歸納法往往難以找出可靠的規則，且難以處理新增資料於大型資料庫的情況。因此本文提出一增量式的規則歸納法並以Bill Tseng教授所提的Rule-Extraction Algorithm (REA)方法為基礎，以處理前述所提到之問題。透過本論文所提之演算法，當有新資料增加時，不需重新對原始資料進行規則歸納。只需將原始的規則做部分的修改即可使資料庫中的規則維持其正確性，因此也節省了許多重新計算的時間。且此種演算法特別適用於大型的資料庫中。

關鍵字

約略集合 ； 增量式演算法 ； 屬性約簡 ； 規則歸納法

並列摘要

The incremental technique is a way to solve the issue of new added-in data without re-implementing the DM algorithm in a dynamic database. There are numerous studies of incremental rough set based approach. However, these approaches are applied to traditional rough set based rule induction, which often generate too many rules without focus and can not guarantee that the classification of a decision table is credible. Moreover, these previous literature of incremental approaches are not capable to deal with the problems of large database. In this paper, an incremental rule-extraction algorithm based on the REA of Professor Tseng is proposed to solve the aforementioned problem. Using this algorithm, when a new object is added up to information system, it is unnecessary to re-compute rule sets from the very beginning. The proposed approach updates rule sets by partly modifying original rule sets, hence a lot of time are saved, and it is especially useful when extracting rules from large databases.

並列關鍵字

Rough Set Theory ； Incremental Algorithm ； Attribute Reduction ； Rule Induction

參考文獻

References

Asharaf, S., Narasimha Murty, M., and Shevade, S.K., 2006, “Rough set based incremental clustering of interval data”, Pattern Recognition Letters, Vol. 27 (6), pp. 515-519.

Bazan, Jan, Peters, James F., Skowron, Andrzej Hung Son, Nguyen, and Szczuka, Marcin , 2003, “Rough set approach to pattern extraction from classifiers”, Electronic Notes in Theoretical Computer Science, Vol, 82(4), pp. 1-10.

Bian, Xuehai, 1998, “Certain rule leaming of the inconsistent data,” Journal of East China Shipbuilding Institute, Vol.12, No. 1, pp. 25-30. (In Chinese)

Blaszczynski, Jerzy Slowinski, and Roman, 2003, “Incremental induction of decision rules from dominance-based rough approximations,” Electronic Notes in Theoretical Computer Science, Vol. 82(4), pp. 1-12.