基於密度的超立方體覆蓋之啟發式演算法

Efficient Classification Using Density-Based Hyper-Rectangle Covers

蔣秉芳(Ping-Fang Chiang)

指導教授 ： 王尉任

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

摘要

在資料建模、和機器學習的領域中，我們可以將不同資料對應到歐幾里德超空間後，再建立排他性的超立方體來覆蓋全部資料，然後利用這些超立方體做為資料辨識的規則或知識。然而，以往這方面的研究在建立這樣的排他性超立方體時，經常會花費太多的時間；或是雖然時間很短，卻犧牲太多的準確率。本篇論文嘗試在貪婪演算法高效率的基礎上，以不犧牲太多效率的方式，建構出擁有高度資料辨識率的超立方體覆蓋。針對較大的資料、和較佳的判斷兩方面，本篇論文分別提出兩種不同的啟發式方法，以便滿足大量資料和高精準度的不同需求。另外，論文也提供了將超立方體覆蓋的結果轉為析取範式(DNF)的方法，使得資料在完成建模之後能夠有更佳的可讀性。最後，本篇論文探討了超立方體建模的天生限制，並且嘗試對這個限制提出了將來可能的改善方向。

關鍵字

資料識別 ； 超立方體 ； 資料探勘

並列摘要

In the fields of data modeling and machine learning, using exclusive hyper-rectangles which contain various classes of data in the Euclidean Hyper-Space as rules or knowledge, has been widely studied for data classifications. However, prior hyper-rectangle-based algorithms either take too much time on constructing hyper-rectangles for better classification results, or sacrifice accuracy of classification in return of less execution time. To solve this problem, this paper tries to propose a better hyper-rectangle-covering-based method, which produces good data classification results and yet executes efficiently. Considering both sides of larger data and more accurate result, this paper extends our idea to two novel, alternate heuristic methods, to fulfill different demands on precise classification and massive data usage. In this paper, we also provide a procedure to translate the results of the hyper-rectangle covers into conjunctive normal forms, which are more readable for human beings. We also point out an inherent restriction of the algorithms that use hyper-rectangles for data modeling, and propose a possible research direction to overcome the restriction.

並列關鍵字

Data Classification ； Hyper-Rectangle ； Data Mining

參考文獻

[1] M. Ichino, "A nonparametric multiclass pattern classifier," IEEE Transactions on Systems, Man, and Cybernetics, vol. 9, pp. 345-352, 1979.

[2] M. Kudo and M. Shinbo, "Optimal subclasses with dichotomous variables for feature selection and discrimination," IEEE Transactions on Systems, Man, and Cybernetics, vol. 19, pp. 1194-1199, 1989.

[3] A. Blumer, A. Ehrenfeucht, D. Haussler and M. Warmuth, "Learnability and the vapnik-chervonenkis dimension," Journal of the ACM (JACM), vol. 36, no. 4, pp. 929-965, 1989.

[4] M. Kudo, S. Yanagi and M. Shinbo, "Construction of class regions by a randomized algorithm: A randomized subclass method," Pattern Recognition, vol. 29, pp. 581-588, 1996.

[5] K. Ouchi, A. Nakamura and M. Kudo, "Efficient Construction and Usefulness of Hyper-Rectangle Greedy Covers," in IEEE International Conference on Granular Computing, 2011.