植基於分散式粒化運算的決策產生

Distributed Decision Generation Based on Granular Computing

蔡旻嶧(Min-Yi Tsai)

指導教授 ： 王尉任

國立中央大學/資訊電機學院/資訊工程學系/碩士(2012年)

摘要

粒化運算主要關注於在不同的資料顆粒上可以提供給使用者不一樣的觀點，並且能夠從處理這些抽象化資料的過程中取得有意義的知識。在這篇論文中除了提出了一個植基於粒化運算的決策產生演算法(DGAGC)也提出了一個植基於分散式粒化運算的決策產生演算法(MR-DGAGC)，而此MR-DGAGC則是DGAGC的map/reduce版本。DGAGC 改進了一個相似的演算法(PGAGC)並包含了兩個階段，分別是規則產生階段與決策產生階段。在規則產生階段，DGAGC使用了規則合併策略和額外規則產生策略來提高規則的辨識率並提高在高粒度下規則產生的速度。在決策產生階段，DGAGC使用一個新穎的規則選擇策略從規則產生階段所產生的規則中選擇最好的規則當作最終決策。雖然使用了三種策略的DGAGC擁有更好的辨識率，但是它缺少了處理大量資料的能力。為了解決此問題，我們發展了DGAGC的map/reduce的版本(MR-DGAGC)。MR-DGAGC使用了一種香精析取法(本質析取法)的概念將DGAGC套入map/reduce框架中，這種追溯技巧大幅降低DGAGC的計算複雜度。在實驗部分也顯示了這篇論文中所提出的演算法除了比先前的演算法來的好之外也具有擴展性的能力來處理大量資料。

關鍵字

規則顆粒 ； 解空間 ； 顆粒空間 ； 粒化運算 ； 規則選擇

並列摘要

Granular computing aims to provide different views at different granules of data, and to derive knowledge from the process of data abstraction. In this paper, a decision-rule generation algorithm based on granular computing (DGAGC) is proposed and its map/reduce version MR-DGAGC is also introduced. The DGAGC improves a prior similar algorithm, the PGAGC algorithm. The DGAGC consists of two stages, the rule generation stage and the decision making stage. In the rule generation stage, the DGAGC employs a rule combination strategy and an alternative rule generation strategy to increase the recognition of rules and the speed of generating rule in higher granularity. In the decision making stage, the DGAGC provides a novel rule-choosing strategy to use reasonable rules for decision making. By using this rule-choosing strategy, a better decision is made from many reasonable rules which are generated in stage one. Although the DGAGC provides a higher recognition rate, it lacks of the ability of processing large data as the other similar algorithms. To solve the problem, we have developed a map/reduce version of the DGAGC, called the MR-DGAGC, which uses the trace-back concept to massively reduce the time complexity of the DGAGC. The experimental results show that the DGAGC has a higher true positive rate and a lower false positive rate than a prior similar study. The experimental results also show that the MR-DGAGC is scalable.

並列關鍵字

rule granule ； granular computing ； rule-choosing ； granule space ； solution space

參考文獻

[4] Q. Liu, "Granules and Reasoning Based on Granular Computing," Developments in Applied Artificial Intelligence, Lecture Notes in Computer Science, Vol. 2718/2003, pp. 516-526, 2003.

[7] B. Zhang, and L. Zhang, "The Quotient Space Theory of Problem Solving," Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, Lecture Notes in Computer Science, Vol. 2639/2003, pp. 585, 2003.

[9] G. Wang, and F. Liu, "The inconsistency in rough set based rule generation," Rough Sets and Current Trends in Computing, Lecture Notes in Computer Science, vol. 2005/2001, pp. 370–377, 2001.

[10] A. Skowron, and J. Stepanniuk, "Information granules: towards foundations of granular computing," International Journal of Intelligent systems, Vol. 16, pp. 57-85, 2001.

[15] Y.Y. Yao, "On Modeling data mining with granular computing", Proceedings of COMPSAC, pp. 638–643, 2001.