﻿ 多值决策表的最小决策树生成 Minimal Decision Tree Generation for Multi-Label Decision Tables

Computer Science and Application
Vol.06 No.10(2016), Article ID:18830,12 pages
10.12677/CSA.2016.610076

Minimal Decision Tree Generation for Multi-Label Decision Tables

Ying Qiao, Meiling Xu, Farong Zhong, Jing Zeng, Yuchang Mo

Zhejiang Normal University, Jinhua Zhejiang

Received: Oct. 5th, 2016; accepted: Oct. 23rd, 2016; published: Oct. 28th, 2016

ABSTRACT

Decision tree is a widely used classification in data mining. It can discover the essential knowledge from the common decision tables (each row has a decision). However, it is difficult to do data mining from the multi-label decision tables (each row has a set of decisions). In a multi-label decision tables, each row contains several decisions, and several decision attributes are represented using a set. By testing the existing heuristic algorithms, such as greedy algorithms, their performance is not stable, i.e., the size of the decision tree might become very large. In this paper, we propose a dynamic programming algorithm to minimize the size of the decision trees for a multi- label decision table. In our algorithm, the multi-label decision table is divided into several subtables, and the decision tree is constructed by using all subtables of the multi-label decision table, then useful information can be discovered from the multi-label decision tables.

Keywords:Multi-Label Decision Tables, Decision Trees, Dynamic Programming Algorithm

1. 引言

2. 概念

Table 1. A multi-label decision table T

Table 2. A degenerate table T′ of the multi-label decision table T

am)表示。这样的非空子表(包括表T)称为T的可分离子表。如表1的多值决策表T的子表T(f1, 0)由第1行和第4行组成(见表3)；类似地，子表T(f1, 0)(f2, 0)由第4行组成(见表4)。

3. 决策树最小化算法

3.1. 决策树

1) 如果T(v)是退化的，那么v被标记为T(v)的常用决策。

2) 如果T(v)是非退化的，那么v用fi∈E(T(v))表示，假设E(T(v), fi) = {a1, …, ak}，则来自节点v的k条输出边为a1, …, ak

N(Γ)表示决策树Γ的节点数，Nt(Γ)和Nn(Γ)分别表示决策树Γ的叶子节点数和非叶子节点数。

Table 3. A subtable T(f1, 0) of the multi-label decision table T

Table 4. A subtable T(f1, 0)(f2, 0) of the multi-label decision table T

Figure 1. A decision tree for the multi-label decision table

3.2. 动态规划算法

4. 实例分析

4.1. 实例介绍

4.2. 最小决策树构造

Step1：假定S(T) = {T0}，且对T0未做过任何的处理，令Ts = T0可写出表Ts的子表Ts(f1, 0)，Ts(f1, 1)，Ts(f2, 0)，Ts(f2, 1)，Ts(f3, 0)，Ts(f3, 1)。见表7~12。

Step2：在S(T)集合中选择一个未处理过的子表，令Ts = Ts(f1, 0)，这时Ts的子表为Ts(f1, 0)(f2, 0)，Ts(f1, 0)(f2, 1)，Ts(f1, 0)(f3, 0)，Ts(f1, 0)(f3, 1)。列举如下(见表13~16)。

Step3：选择S(T)集合中的任意一个表，当选择T表时，由于T表为非退化表，所以根据算法2得出以下结果(图2)，其中Γf1、Γf2、Γf3分别表示Ts(f1, 0)和Ts(f1, 1)，Ts(f2, 0)和Ts(f2, 1)，Ts(f3, 0)和Ts(f3, 1)所对应的决策树子树。

Step4：当选择T的子表Ts(f1, 0)时，得到的结果是Γf2和Γf3，但Γf2和Γf3分别表示Ts(f1, 0)(f2, 0)和Ts(f1, 0)(f2, 1)，Ts(f1, 0)(f3, 0)和Ts(f1, 0)(f3, 1)所对应的决策树子树。

Step5：当选择Ts(f1, 0)的子表Ts(f1, 0)(f2, 0)时，得到的决策树为Γf1,f2,f3；当选择Ts(f1, 0)的子表Ts(f1, 0)(f3, 0)和Ts(f1, 0)(f3, 1)，得到决策树Γf1,f3。由于Γf1,f3的规模比Γf1,f2,f3小，因此选择决策树Γf1,f3 (图4)。

Table 5. A student’s rank table

Table 6. A multi-label decision table T0

Table 7. A subtable Ts(f1, 0) of the multi-label decision table T0

Table 8. A subtable Ts(f1, 1) of the multi-label decision table T0

Table 9. A subtable Ts(f2, 0) of the multi-label decision table T0

Table 10. A subtable Ts(f2, 1) of the multi-label decision table T0

Table 11. A subtable Ts(f3, 0) of the multi-label decision table T0

Table 12. A subtable Ts(f3, 1) of the multi-label decision table T0

Table 13. A subtable Ts(f1, 0)(f2, 0) of the multi-label decision table T0

Table 14. A subtable Ts(f1, 0)(f2, 1) of the multi-label decision table T0

Table 15. A subtable Ts(f1, 0)(f3, 0) of the multi-label decision table T0

Table 16. A subtable Ts(f1, 0)(f3, 1) of the multi-label decision table T0

(1) (2) (3)

Figure 2. Some subtrees of the decision tree, (1) Γf1, (2) Γf2, (3) Γf3

(1) (2)

Figure 3. Some subtrees of the decision tree, (1) Γf1,f2, (2) Γf1,f3

(1) (2)

Figure 4. Some subtrees of the decision tree, (1) Γf1,f2,f3, (2) Γf1,f3

(1) (2) (3)

Figure 5. Some subtrees of the decision tree, (1) Γf2,f1,f3, (2) Γf2,f3,f1, (3) Γf3,f2,f1

Figure 6. The result of classification by dynamic programming algorithm

4.3. 性能比较

Step1：选择的子表T0为表T，即T0 = T，树G中只有一个根节点v，所以用T0标记节点v。通过使用表6中的数据计算不纯度函数I(T0, f1)、I(T0, f2)、I(T0, f3)的值分别为3，3，7，由于I(T0, f1) = I(T0, f2)相等，所以取fi中i值小的I(T0, f1)，用f1代替T0标记节点v，对于每个δ，δ∈E(T′, f2) = {0, 1}，在树G中加入节点v0，v1，分别与连接节点v相连并将边标记为0，1，分别用子表T(f1, 0)，T(f1, 1)标记节点v0，v1，结果如图7所示。

Step2：在子表T(f1, 0) ,T(f1, 1)中任选选择一个如T(f1, 0)即T0= T(f1, 0)。使用表7~11中的数据计算不纯度函数I(T0, f2)、I(T0, f3)的值分别为5和0，所以选择f3，用f3代替T0标记节点v0，分别用子表T(f1, 0) (f3, 0)、T(f1, 1) (f3, 1)标记节点v0，v1，结果如图8所示。

5. 总结

Figure 7. Decision tree for the first step

Figure 8. Decision tree for the second step

Figure 9. Decision tree by greedy algorithm

Figure 10. The result of classification by greedy algorithm

Minimal Decision Tree Generation for Multi-Label Decision Tables[J]. 计算机科学与应用, 2016, 06(10): 617-628. http://dx.doi.org/10.12677/CSA.2016.610076

1. 1. Boutell, M.R., Luo, J., Shen, X. and Brown, C.M. (2004) Learning Multi-Label Scene Classification. Pattern Recognition, 37, 1757-1771. http://dx.doi.org/10.1016/j.patcog.2004.03.009

2. 2. Wieczorkowska, A., Synak, P., Lewis, R.A. and Ras, Z.W. (2005) Extracting Emotions from Music Data. ISMIS, Volume 3488 of the series Lecture Notes in Computer Science, 456-465.

3. 3. Blockeel, H., Schietgat, L., Struyf, J., Dzeroski, S. and Clare, A. (2006) Decision Trees for Hierarchical Multilabel Classification: A Case Study in Functional Genomics. In: Fürnkranz, J., Scheffer, T. and Spiliopoulou, M., Eds., Proceedings PKDD, ser. LNCS, Springer, Berlin, Vol. 4213, 18-29.

4. 4. Zhou, Z.-H., Jiang, K. and Li, M. (2005) Multi-Instance Learning Basedweb Mining. Applied Intelligence, 22, 135-147. http://dx.doi.org/10.1007/s10489-005-5602-z

5. 5. Moshkov, M. and Zielosko, B. (2011) Combinatorial Machine Learning -A Rough Set Approach. ser. Studies in Computational Intelligence, Springer, Vol. 360. http://dx.doi.org/10.1007/978-3-642-20995-6

6. 6. Comité, F.D., Gilleron, R. and Tommasi, M. (2003) Learning Multi-Label Alternating Decision Trees from Texts and Data. Proceedings of 3rd International Conference, MLDM 2003, Leipzig, 5-7 July 2003, 35-49. http://dx.doi.org/10.1007/3-540-45065-3

7. 7. Loza Mencía, E. and Fürnkranz, J. (2008) Pairwise Learning of Multilabel Clas-sifications with Perceptrons. IEEE International Joint Conference on Neural Networks, 1-8 June 2008, 2899-2906. http://dx.doi.org/10.1109/IJCNN.2008.4634206

8. 8. Tsoumakas, G., Katakis, I. and Vlahavas, I.P. (2010) Mining Multi-Label Data. In: Maimon, O. and Rokach, L., Eds., Data Mining and KnowledgeDiscovery Handbook, Tel Aviv University, 667-685.

9. 9. Zhou, Z.-H., Zhang, M.-L., Huang, S.-J. and Li, Y.-F. (2012) Multi-Instance Multi-Label Learning. Artificial Intelli-gence, 176, 2291-2320. http://dx.doi.org/10.1016/j.artint.2011.10.002

10. 10. Azad, M., Chikalov, I., Moshkov, M. and Zielosko, B. (2012) Greedy Algorithm for Construction of Decision Trees for Tables with Many-Valued Decisions. Proceedings of the 21st International Workshop on Concurrency, Specification and Programming, Berlin, 26-28 September 2012, ser. CEUR Workshop Proceedings, L. Popova-Zeugmann, Ed.CEUR-WS.org, 2012, Vol. 928.

11. 11. Azad, M., Chikalov, I. and Moshkov, M. (2013) Three Approaches to Deal within Consistent Decision Tables— Comparison of Decision Tree Complexity. RSFDGrC, Halifax, 11-14 Oc-tober 2013, 46-54. http://dx.doi.org/10.1007/978-3-642-41218-9

12. 12. Tsoumakas, G. and Katakis, I. (2007) Multi-Label Classification: An Over-view. IJDWM, 3, 1-13. http://dx.doi.org/10.4018/jdwm.2007070101

13. 13. Zhu, X. and Goldberg, A.B. (2009) Introduction to Semi-Supervised Learning, ser. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, San Rafael, Califor-nia.

14. 14. Cour, T., Sapp, B., Jordan, C. and Taskar, B. (2009) Learning from Ambiguously Labeled Images. CVPR, Miami, Florida, 20-25 July 2009, 919-926.

15. 15. Hüllermeier, E. and Beringer, J. (2006) Learning from Ambiguously Labeled Examples. Intelligent Data Analysis, 10, 419-439.

16. 16. Jin, R. and Ghahramani, Z. (2002) Learning with Multiple Labels. NIPS, Vancouver, British Co-lumbia, 9-14 December 2002, 897-904.

17. 17. Moshkov, M. and Chikalov, I. (2000) On Algorithm for Constructing of Decision Trees with Minimal Depth. Fundamenta Informaticae, 41, 295-299.