In the extension matrix approach of inductive learning, the minimum formula (MFL) ofa positive example (e^+) against a set of negative examples (NE) and tbe optimal covering(MCV) of a set of positive examples (PE) aga...In the extension matrix approach of inductive learning, the minimum formula (MFL) ofa positive example (e^+) against a set of negative examples (NE) and tbe optimal covering(MCV) of a set of positive examples (PE) against NE are two striking optimization prob-lems. They have been proved to be NP-hard in Ref. [1]. This paper presents four algorithms,named MFL, HFL, MCV and HCV respectively. Algorithms MFL and MCV are complete forsolving the problems MFL and MCV but they opelate in exponential time on the number ofattributes in an example space and polynomial time on the number of examples. AlgorithmsHFL and HCV are two heuristic algorithms homologous to Algorithms MFL and MCV buttheir time complexities are polynomial.展开更多
This paper presents a new inductive learning algorithm, HGR (Version 2.0), based on the newly-developed extension matrix theory. The basic idea is to partition the positive examples of a specific class in a given exam...This paper presents a new inductive learning algorithm, HGR (Version 2.0), based on the newly-developed extension matrix theory. The basic idea is to partition the positive examples of a specific class in a given example set into consistent groups, and each group corresponds to a consistent rule which covers all the examples in this group and none of the negative examples. Then a performance comparison of the HGR algorithm with other inductive algorithms, such as C4.5, OC1, HCV and SVM, is given in the paper. The authors not only selected 15 databases from the famous UCI machine learning repository, but also considered a real world problem. Experimental results show that their method achieves higher accuracy and fewer rules as compared with other algorithms.展开更多
基金Project supported by the National Natural Science Foundation of China.
文摘In the extension matrix approach of inductive learning, the minimum formula (MFL) ofa positive example (e^+) against a set of negative examples (NE) and tbe optimal covering(MCV) of a set of positive examples (PE) against NE are two striking optimization prob-lems. They have been proved to be NP-hard in Ref. [1]. This paper presents four algorithms,named MFL, HFL, MCV and HCV respectively. Algorithms MFL and MCV are complete forsolving the problems MFL and MCV but they opelate in exponential time on the number ofattributes in an example space and polynomial time on the number of examples. AlgorithmsHFL and HCV are two heuristic algorithms homologous to Algorithms MFL and MCV buttheir time complexities are polynomial.
文摘This paper presents a new inductive learning algorithm, HGR (Version 2.0), based on the newly-developed extension matrix theory. The basic idea is to partition the positive examples of a specific class in a given example set into consistent groups, and each group corresponds to a consistent rule which covers all the examples in this group and none of the negative examples. Then a performance comparison of the HGR algorithm with other inductive algorithms, such as C4.5, OC1, HCV and SVM, is given in the paper. The authors not only selected 15 databases from the famous UCI machine learning repository, but also considered a real world problem. Experimental results show that their method achieves higher accuracy and fewer rules as compared with other algorithms.
