Classification Functions for Machine Learning and Data Mining
Tsutomu Sasao
Springer Nature,
July 2023.

Amazon.com

Contents

1 Introduction	1
1.1 Aim of this Book . . . . . . . . . . . . . . . . . . . . . . . .	 1
1.2 Organization of the Book . . . . . . . . . . . . . . . . . . . .	 1

2 Definitions and Basic Properties	5
2.1 Two-Class Function . . . . . . . . . . . . . . . . . . . . . . .	 5
2.2 Classification Function . . . . . . . . . . . . . . . . . . . . .	 8
2.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	10

3 Minimization of Variables: Exact Method	13
3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . .	13
3.2 Exact Algorithm . . . . . . . . . . . . . . . . . . . . . . . . .	14
3.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	15
3.4 Exercises	. . . . . . . . . . . . . . . . . . . . . . . . . . . .	16

4 Minimization of Variables: Heuristic Method	19
4.1 Impurity Measure . . . . . . . . . . . . . . . . . . . . . . . .	19
4.2 Heuristic Algorithm . . . . . . . . . . . . . . . . . . . . . . .	22
4.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	27
4.4 Exercises	. . . . . . . . . . . . . . . . . . . . . . . . . . . .	28

5 Two-Class Functions	29
5.1 Statistical Analysis	. . . . . . . . . . . . . . . . . . . . 29
5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . .	34
5.2.1 Random 6-variable functions with k0 = k1 = 4 . . . .	34
5.2.2 Number functions that require no variables, for n =
	16,20,24,28 and k0 = k1 = 64. . . . . . . . . . . . .	34
5.2.3 Random 24-variable Functions with k0 = k1	. . . . .	36
5.2.4 Random 24-variable Functions with
5.2.5 Random 60-Variable Function . . . . . . . . . . . . .	36
5.2.6 Non-Random Functions	. . . . . . . . . . . . . . . .	37
5.2.7 MNIST Handwritten Character Recognition Circuit . .	38
5.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	41
5.4 Exercises	. . . . . . . . . . . . . . . . . . . . . . . . . . . .	41

6 Linear Decomposition	43
6.1 Algorithm for Linear Decomposition . . . . . . . . . . . . . .	43
6.2 Number of Variables to Represent Non-Linear Function . . . .	48
6.3 Examples of Reductions	. . . . . . . . . . . . . . . . . . . .	49
6.4 Experimental Results for Larger Problems . . . . . . . . . . .	52
6.4.1 Benchmark Functions and Computer Environment	. .	52
6.4.2 Reduction of Primitive Variables . . . . . . . . . . . .	52
6.4.3 Reduction of Compound Variables . . . . . . . . . . .	53
6.4.4 MNIST Character Recognition Circuit (45-unit real-
	ization) . . . . . . . . . . . . . . . . . . . . . . . . .	54
6.4.5 Fashion MNIST (45-unit realization)	. . . . . . . . .	54
6.4.6 Single-Unit Realization of MNIST . . . . . . . . . . .	55
6.4.7 MNIST Two-Class Problem	. . . . . . . . . . . . . .	56
6.4.8 Spam E-Mail Filter (two-class function) . . . . . . . .	57
6.5 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	57
6.6 Exercises	. . . . . . . . . . . . . . . . . . . . . . . . . . . .	58

7 Data Mining and Machine Learning	61
7.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . .	61
7.2 Comparison with a Tree-based Classifier . . . . . . . . . . . .	65
7.3 Performance Measures	. . . . . . . . . . . . . . . . . . . . 68
7.4 Evaluation Methods . . . . . . . . . . . . . . . . . . . . . . .	69
7.5 Accuracy for MNIST . . . . . . . . . . . . . . . . . . . . . .	69
7.6 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	71
7.7 Exercises	. . . . . . . . . . . . . . . . . . . . . . . . . . . .	71

8	Functions with Multi-Valued Inputs 75
8.1	SOP with Multi-valued Inputs	. . . . . . . . . . . . . . . . 75
8.2	Minimization of Multi-valued Variables	. . . . . . . . . . . . 78
8.3	SOP Minimization and Generalization Ability . . . . . . . . .   79
8.4	Experiments with UCI Data Sets . . . . . . . . . . . . . . . .  82
8.4.1	Breast Cancer . . . . . . . . . . . . . . . . . . . . . .       82
8.4.2	Chess3196	. . . . . . . . . . . . . . . . . . . . . . .   82
8.4.3	Connect-4 . . . . . . . . . . . . . . . . . . . . . . . .       82
8.4.4	Dermatology . . . . . . . . . . . . . . . . . . . . . .         83
8.4.5	Letter Recognition . . . . . . . . . . . . . . . . . . .        83
8.4.6	Monks	. . . . . . . . . . . . . . . . . . . . . . . . .       83
8.4.7	Mushroom	. . . . . . . . . . . . . . . . . . . . . . .   83
8.4.8	Promoter	. . . . . . . . . . . . . . . . . . . . . . . . 84
8.4.9	Splice . . . . . . . . . . . . . . . . . . . . . . . . . .      84
8.4.10 Teaching Assistant Evaluation . . . . . . . . . . . . .          84
8.4.11 Tic-Tac-Toe . . . . . . . . . . . . . . . . . . . . . . .        84
8.4.12 Vote . . . . . . . . . . . . . . . . . . . . . . . . . . .       85
8.4.13 Zoo . . . . . . . . . . . . . . . . . . . . . . . . . . .        85
8.5	Experiments with Imbalanced Data Set . . . . . . . . . . . . .  86
8.5.1 Hepatitis	. . . . . . . . . . . . . . . . . . . . . . . .         86
8.5.2 Thoracic	. . . . . . . . . . . . . . . . . . . . . . . .         87
8.6	Observations	. . . . . . . . . . . . . . . . . . . . . . . . 88
8.6.1 Analysis of Table 8.4.1 . . . . . . . . . . . . . . . . .         88
8.6.2 Analysis of Table 8.4.2 . . . . . . . . . . . . . . . . .         88
8.7 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   88
8.8 Exercises	. . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

9 Easily Reconstructable Functions	91
9.1 Reconstruction of Functions by SOP minimization	. . . . . .     91
9.2 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . .   95
9.2.1 SOP Minimizer for Machine Learning . . . . . . . . . 95
9.2.2 Achilles Heel Functions	. . . . . . . . . . . . . . . . 96
9.2.3 Other Monotone Increasing Functions . . . . . . . . . 96
9.2.4 Functions Generated by Random SOPs	. . . . . . . . 98
9.3 Evaluation of Methods	. . . . . . . . . . . . . . . . . . .   98
9.4 Comparison with Other Classifiers	100
9.4.1 Performance of the Proposed Method	100
9.4.2 Performance of Other Methods	100
9.5 Extension to Multi-Valued Input Functions	102
9.6 Remarks	103
9.7 Exercises	104

10 Functions with Continuous Variables	107
10.1 Generation of Rules from Examples	107
10.2 Algorithms and Examples	109
10.2.1 Discretization	109
10.2.2 Domain Reduction	111
10.2.3 Multi-Valued Input SOP Minimization	111
10.3 Experimental Results	114
10.4 Remarks	118
10.5 Exercises	118

11 References	121
11.1 Reduction of Variables	121
11.2 Analysis	122
11.3 Architecture	122
11.4 Applications	122
11.5 Survey	122
11.6 Miscellaneous	123

12 Conclusions	127
12.1 Summary of the Book	127
12.2 Remaining Problems	128
Appendix: Solutions to the Exercises	129


Back