Machine learning methods based on probabilistic decision tree under the multi-valued preference environment

Figures & data

Table 1. A single-valued preference sample.

No.	Attributes				Class P/N
	Outlook	Temperature	Humidity	Windy
$D11$	rain	mild	normal	false	$P$
$D12$	rain	cool	normal	true	$N$
$D13$	overcast	hot	high	false	$P$

Source: The Authors.

Table 2. A multi-valued preference sample.

No.	Attributes				Class P/N
	Outlook	Temperature	Humidity	Windy
$D21$	rain	mild	normal	false	$(p_{21},1-p_{21})$
$D22$	rain, overcast	cool, hot	normal, high	true	$(p_{22},1-p_{22})$
$D23$	overcast, sunny, rain	hot, mild, cool	high	false, true	$(p_{23},1-p_{23})$

Source: The Authors.

Table 3. A probabilistic multi-valued preference sample.

No.	Attributes				Class P/N
	Outlook	Temperature	Humidity	Windy
$D31$	rain $o_{13}$	mild $t_{12}$	normal $h_{12}$	false $w_{12}$	$(p_{31},1-p_{31})$
$D32$	overcast, rain $o_{22},o_{23}$	hot, cool $t_{21},t_{23}$	high, normal $h_{21},h_{22}$	true $w_{21}$	$(p_{32},1-p_{32})$
$D33$	sunny, overcast, rain $o_{31},o_{32},o_{33}$	hot, mild, cool $t_{31},t_{32},t_{33}$	high $h_{31}$	true, false $w_{31},w_{32}$	$(p_{33},1-p_{33})$

Source: The Authors.

Table 4. The main notations in the multi-valued preference environment.

Notations	Introduction	Notations	Introduction
$S^{\prime }$	The training data set after quantity matching	$1/L_i$	The multiple of preferences $a_{iw}$ that should be reduced after quantity matching
$\left|S^{\prime }\right|$	The sample number of $S^{\prime }$	$1/L_{ik}$	The multiple of preferences $a_{\mathit{iwk}}$ that should be reduced after quantity matching
$A$	The attribute of $S^{\prime }$	$1/R_i^c$	The multiple of preferences $a_{iu}^c$ that should be reduced after quantity matching
$\left|C_k\right|$	The sample number of the class $C_k$	$1/R_{ik}^c$	The multiple of preferences $a_{\mathit{iuk}}^c$ that should be reduced after quantity matching
$\left|a_{iw}\right|$	The weight about the $w$ th preference of the root node attribute in the $i$ th sample	$P_{iw}^Z(b)$	The preferences $a_{iw}$ of the root node attribute is under branch $Z,$ where there are $b$ samples with classification result $P$
$\left|a_{\mathit{iwk}}\right|$	The weight about the $w$ th preference in the root node attribute belongs to the class $k$ in the $i$ th sample	$P_{\mathit{icu}}^Z(b)$	The preference $a_{iu}$ of the $c$ th sub node is under branch $Z,$ where there are $b$ samples with classification result $P$
$\left|a_{iu}^c\right|$	The weight about the $u$ th preference of the sub node attribute $c$ in the $i$ th sample	$N_{iw}^Z(g)$	The preference $a_{iw}$ of the root node attribute is under branch $Z,$ where there are $g$ samples with classification result $N$
$\left|a_{\mathit{iuk}}^c\right|$	The weight about the $u$ th preference of the sub node attribute $c$ belongs to class $k$ in the $i$ th sample	$N_{\mathit{icu}}^Z(g)$	The preference $a_{iu}$ of the $c$ th sub node is under branch $Z,$ where there are $g$ samples with classification result $N$

Source: The Authors.

Table

Input: The multi-valued training data set $S.$ Step 1: Preprocess the multi-valued training data set $S$ to match its weight and quantity, and obtain a new data set $S^{\prime }.$ Step 2: Take each attribute $A$ in the new training data set $S^{\prime }$ as a node. Step 3: Transform the preference in an attribute and divide the corresponding data into the different sub nodes. Step 4: Use the bifurcation criterion to calculate the optimal preference for partitioning. Step 5: Convert all the attributes according to the second step, select the best attribute and preference, and derive the final sub node. Step 6: Perform Steps 3-5 again for all the nodes until each node becomes a final node, and then we can obtain a DT. Step 7: Compare the DT with the original data and obtain classification results under the same bifurcation, and then calculate the probability of each classification and obtain a probabilistic DT.

Output: A probabilistic DT.

Figure 1. The DT generated based on the information gain and the data set ${\mathit{S}}^{\prime }.$

Source: The Authors.

Table 5. A multi-valued training set containing 10 samples.

No.	Attributes				Class
	Outlook	Temperature	Humidity	Windy
$S1$	sunny	hot	normal	false	P
$S2$	rain	mild	high	true	N
$S3$	rain, sunny	cool, mild	normal	true	P
$S4$	overcast, rain	hot, cool	high, normal	false, true	P
$S5$	overcast	mild, hot	high, normal	false	P
$S6$	sunny, rain	hot, cool	high	true, false	N
$S7$	overcast, rain, sunny	cool, mild	normal	true	P
$S8$	rain, overcast	cool, mild, hot	normal, high	false	P
$S9$	sunny, rain	hot, cool, mild	normal	false, true	N
$S10$	rain, sunny, overcast	mild, cool, hot	normal, high	true, false	P

Source: The Authors.

Table 6. A new training sample set after quantity expanding.

No.	Attributes				Class
	Outlook	Temperature	Humidity	Windy
$S^{\prime }1$	sunny; sunny; sunny; sunny; sunny; sunny	hot; hot; hot; hot; hot; hot	normal; normal	false; false	P
$S^{\prime }2$	rain; rain; rain; rain; rain; rain	mild; mild; mild; mild; mild; mild	high; high	true; true	N
$S^{\prime }3$	rain, sunny; rain, sunny; rain, sunny	cool, mild; cool, mild; cool, mild	normal; normal	true; true	P
$S^{\prime }4$	overcast, rain; overcast, rain; overcast, rain	hot, cool; hot, cool; hot, cool	high, normal	false, true	P
$S^{\prime }5$	overcast; overcast; overcast; overcast; overcast; overcast	mild, hot; mild, hot; mild, hot	high, normal	false; false	P
$S^{\prime }6$	sunny, rain; sunny, rain; sunny, rain	hot, cool; hot, cool; hot, cool	high; high	true, false	N
$S^{\prime }7$	overcast, rain, sunny; overcast, rain, sunny	cool, mild; cool, mild; cool, mild	normal; normal;	true; true	P
$S^{\prime }8$	rain, overcast; rain, overcast; rain, overcast	cool, mild, hot; cool, mild, hot	normal, high	false; false	P
$S^{\prime }9$	sunny, overcast, rain; sunny, overcast, rain	hot, cool, mild; hot, cool, mild	normal; normal	false, true	N
$S^{\prime }10$	rain, sunny, overcast; rain, sunny, overcast	mild, cool, hot; mild, cool, hot	normal, high	true, false	P

Source: The Authors.

Table 7. The bifurcation criterion value in the multi-valued preference environment.

Preference = “sunny”		Preference = “rain”
M (S′1, A2) =0.0222		M (S′2, A2) =0.1393
M (S′1, A3) =0.1776		M (S′2, A3) =0.1463
M (S′1, A4) =0.0143		M (S′2, A4) =0.0243
Select the attribute “A3”		Select the attribute “A3”
Pre = "sunny, high"	Pre = "sunny, normal"	Pre = "rain, high"	Pre = "rain, normal"
M (S′11, A2) = 0.1843	M (S′12, A2) = 0.0177	M (S′21, A2) = 0.1335	M (S′22, A2) = 0.0196
M (S′11, A4) = 0	M (S′12, A4) = 0.0008	M (S′21, A4) = 0.1860	M (S′22, A4) = 0.0218
Select the attribute “A2”, and the last attribute is “A4”		Select the attribute “A4”, and the last attribute is “A2”
Pre = “sunny, high, hot”	Pre = “sunny, normal, hot”	Pre = “rain, high, true”	Pre = “rain, normal, true”
“sunny, high, hot, true”	“sunny, normal, hot, true”	“rain, high, true, hot”	“rain, normal, true, hot”
“sunny, high, hot, false”	“sunny, normal, hot, false”	“rain, high, true, mild”	“rain, normal, true, mild”
Pre = “sunny, high, mild”	Pre= “sunny, normal, mild”	“rain, high, true, cool”	“rain, normal, true, cool”
“sunny, high, mild, true”	“sunny, normal, mild, true”	Pre = “rain, high, false”	Pre = “rain, normal, false”
“sunny, high, mild, false”	“sunny, normal, mild, false”	“rain, high, false, hot”	“rain, normal, false, hot”
Pre = “sunny, high, cool”	Pre = “sunny, normal, cool”	“rain, high, false, mild”	“rain, normal, false, mild”
“sunny, high, cool, true”	“sunny, normal, cool, true”	“rain, high, false, cool”	“rain, normal, false, cool”
“sunny, high, cool, false”	“sunny, normal, cool, false”

Source: The Authors.

Table 8. Some main notations in the probabilistic multi-valued preference environment.

Notations	Introduction	Notations	Introduction
$T^{\prime }$	The new training data set after quantity matching	$\left|q_{iu}^c\right|$	The weight about the $u$ th preference of the sub node attribute $c$ in the $i$ th sample
$\left|T^{\prime }\right|$	The sample number of $T^{\prime }$	$\left|q_{\mathit{iuk}}^c\right|$	The weight about the $u$ th preference of the sub node attribute $c$ belongs to class $k$ in the $i$ th sample
$Q$	An attribute of $T^{\prime }$	$P_{iw}^Z{(b)}^{\prime }$	The preferences $q_{iw}$ of the root node attribute is under branch $Z,$ where there are $b$ samples with classification result $P$
$\left|C_k\right|$	The sample number of the class $C_k$	$P_{\mathit{icu}}^Z{(b)}^{\prime }$	The preference $q_{iu}$ of the $c$ th sub node is under branch $Z,$ where there are $b$ samples with classification result $P$
$\left|q_{iw}\right|$	The weight about the $w$ th preference of the root node attribute in the $i$ th sample	$N_{iw}^Z{(g)}^{\prime }$	The preference $q_{iw}$ of the root node attribute is under branch $Z,$ where there are $g$ samples with classification result $N$
$\left|q_{\mathit{iwk}}\right|$	The weight about the $w$ th preference in the root node attribute belongs to the class $k$ in the $i$ th sample	$N_{\mathit{icu}}^Z{(g)}^{\prime }$	The preference $q_{iu}$ of the $c$ th sub node is under branch $Z,$ where there are $g$ samples with classification result $N$

Source: The Authors.

Table

Input: The training data set $T.$ Step 1: Treat each attribute $Q$ in the new training data set $T$′ as a node. Step 2: Traverse each preference $q$ of the current attribute and divide the data into different sub nodes by preference. Step 3: Use bifurcation criterion to determine the optimal preference for partitioning. Step 4: Consider the probability of each preference in the calculation process. Step 5: Traverse all the attributes by the second step, select the best attribute and the best preference of the attribute, and get the final sub node. Step 6: Continue to perform Steps 2-5 for all sub nodes, until each final sub node becomes a stop node, and obtain a DT. Step 7: Calculate the probability of the classification result under each branch in the DT.

Output: A probabilistic DT.

Table 9. The probabilistic multi-valued training set containing 60 samples.

NO.	Attributes				Class	NO.	Attributes				Class
	Outlook	Temperature	Humidity	Windy			Outlook	Temperature	Humidity	Windy
$T1$	sunny	hot	normal	false	P	$T31$	sunny, rain	hot, cool	normal	true	N
	1.0	1.0	1.0	1.0			0.33, 0.67	0.02, 0.98	1.0	1.0
$T2$	rain	mild	high	true	N	$T32$	overcast, rain	mild, cool	high, normal	true, false	P
	1.0	1.0	1.0	1.0			0.46, 0.54	0.19, 0.81	0.45, 0.55	0.2, 0.8
$T3$	sunny, rain	mild, cool	normal	true, false	P	$T33$	sunny	hot, cool	normal	true	P
	0.13, 0.87	0.28, 0.72	1.0	0.31, 0.69			1.0	0.17, 0.83	1.0	1.0
$T4$	overcast, rain	hot, cool	high, normal	true, false	P	$T34$	sunny, overcast, rain	mild	high	false	P
	0.75, 0.25	0.81, 0.19	0.88, 0.12	0.8, 0.2			0.2, 0.43, 0.37	1.0	1.0	1.0
$T5$	overcast	hot, mild	high, normal	false	P	$T35$	overcast	hot, cool	high	true, false	P
	1.0	0.43, 0.57	0.49, 0.51	1.0			1.0	0.03, 0.97	1.0	0.24, 0.76
$T6$	sunny, rain	hot, cool	high	true	N	$T36$	sunny, overcast, rain	hot, mild	normal	true	P
	0.9, 0.1	0.74, 0.26	1.0	1.0			0.19, 0.31, 0.5	0.06, 0.94	1.0	1.0
$T7$	sunny, overcast, rain	mild, cool	normal	true	P	$T37$	rain	cool	normal	false	N
	0.1, 0.78, 0.12	0.05, 0.95	1.0	1.0			1.0	1.0	1.0	1.0
$T8$	overcast, rain	hot, cool	high, normal	false	P	$T38$	sunny, rain	mild, cool	high	true, false	P
	0.31, 0.69	0.49, 0.51	0.17, 0.83	1.0			0.43, 0.57	0.49, 0.51	1.0	0.32, 0.68
$T9$	sunny, rain	mild	normal	true	N	$T39$	overcast	hot, mild	high, normal	false	P
	0.4, 0.6	1.0	1.0	1.0			1.0	0.59, 0.41	0.06, 0.94	1.0
$T10$	overcast, rain	hot, cool	high, normal	false	P	$T40$	rain	cool	normal	true	N
	0.55, 0.45	0.8, 0.2	0.21, 0.79	1.0			1.0	1.0	1.0	1.0
$T11$	sunny, rain	hot, mild	normal	true, false	N	$T41$	sunny, overcast, rain	mild, cool	high	true, false	P
	0.39, 0.61	0.73, 0.27	1.0	0.14, 0.86			0.14, 0.41, 0.45	0.07, 0.93	1.0	0.06, 0.94
$T12$	sunny, overcast, rain	mild, cool	high, normal	true	P	$T42$	overcast	hot mild	high, normal	false	P
	0.2, 0.23, 0.57	0.38, 0.62	0.05, 0.95	1.0			1.0	0.21, 0.79	0.09, 0.91	1.0
$T13$	overcast, rain	hot, cool	high	true, false	P	$T43$	sunny, overcast, rain	hot, cool	normal	true, false	P
	0.06, 0.94	0.26, 0.74	1.0	0.06, 0.94			0.28, 0.25, 0.47	0.03, 0.97	1.0	0.39, 0.61
$T14$	sunny, rain	mild	high, normal	false	P	$T44$	sunny	hot, mild	high	false	P
	0.27, 0.73	1.0	0.1, 0.9	1.0			1.0	0.16, 0.84	1.0	1.0
$T15$	overcast	hot, mild, cool	normal	true, false	P	$T45$	sunny, overcast, rain	cool	normal	true	P
	1.0	0.26, 0.14, 0.6	1.0	0.33, 0.67			0.25, 0.16, 0.59	1.0	1.0	1.0
$T16$	sunny, overcast, rain	hot, cool	high, normal	false	P	$T46$	rain	hot, cool	high, normal	true, false	N
	0.46, 0.19, 0.35	0.13, 0.87	0.33, 0.67	1.0			1.0	0.41, 0.59	0.08, 0.92	0.13, 0.87
$T17$	sunny, overcast	hot, mild, cool	high	true, false	P	$T47$	sunny, overcast	hot, mild	high, normal	true, false	P
	0.77, 0.23	0.1, 0.26, 0.64	1.0	0.02, 0.98			0.49, 0.51	0.06, 0.94	0.07, 0.93	0.4, 0.6
$T18$	rain	mild	high, normal	true, false	N	$T48$	overcast, rain	mild	high	true	P
	1.0	1.0	0.08, 0.92	0.29, 0.71			0.42, 0.58	1.0	1.0	1.0
$T19$	sunny, rain	hot, mild, cool	normal	true	N	$T49$	sunny, overcast	hot, cool	normal	true, false	P
	0.43, 0.57	0.09, 0.33, 0.58	1.0	1.0			0.3, 0.7	0.42, 0.58	1.0	0.15, 0.85
$T20$	sunny, overcast	hot	high, normal	true, false	P	$T50$	sunny, rain	mild	high, normal	false	N
	0.78, 0.22	1.0	0.18, 0.82	0.01, 0.99			0.24, 0.76	1.0	0.35, 0.65	1.0
$T21$	sunny, overcast, rain	mild, cool,	high	false	P	$T51$	sunny, rain	cool, hot	high, normal	true	P 50.05% N 49.95%
	0.16, 0.23, 0.61	0.08, 0.92,	1.0	1.0			0.19, 0.81	0.29, 0.71	0.06, 0.94	1.0
$T22$	overcast	hot	normal	true, false	P	$T52$	overcast, sunny, rain	hot, mild	normal	true, false	P 48.62% N 51.38%
	1.0	1.0	1.0	0.28, 0.72			0.18, 0.77,0.05	0.27, 0.73	1.0	0.91, 0.09
$T23$	sunny, rain	hot, mild, cool	high, normal	true, false	N	$T53$	overcast, rain	cool	high, normal	false	P 91.68% N 8.32%
	0.49, 0.51	0.05, 0.19, 0.76	0.07, 0.93	0.39, 0.61			0.54, 0.46	1.0	0.72, 0.28	1.0
$T24$	overcast, rain	mild	normal	false	P	$T54$	sunny, overcast	mild, cool, hot	normal	true	P 96.8% N 3.2%
	0.43 0.57	1.0	1.0	1.0			0.09, 0.91	0.10, 0.17, 0.73	1.0	1.0
$T25$	rain	hot, mild, cool	normal	true	N	$T55$	rain, sunny, overcast	hot, cool	high	true, false	P 74.91% N 25.09%
	1.0	0.08, 0.05, 0.87	1.0	1.0			0.39, 0.48, 0.13	0.39, 0.61	1.0	0.95, 0.05
$T26$	sunny, overcast, rain	hot, cool	high, normal	true, false	P	$T56$	sunny	hot, mild, cool	normal, high	false	P 85% N 15%
	0.46, 0.4, 0.14	0.1, 0.9	0.16, 0.84	0.34, 0.66			1.0	0.23, 0.42, 0.35	0.83, 0.17	1.0
$T27$	sunny	hot, mild, cool	high	true, false	P	$T57$	overcast, sunny, rain	mild	normal	true, false	P 68.41% N 31.59%
	1.0	0.02, 0.19, 0.79	1.0	0.17, 0.83			0.03, 0.71, 0.26	1.0	1.0	0.40, 0.60
$T28$	overcast	cool	normal	false	P	$T58$	rain, overcast	mild, hot	high	true	P 72.13% N 27.87%
	1.0	1.0	1.0	1.0			0.86, 0.14	0.73, 0.27	1.0	1.0
$T29$	sunny, overcast, rain	hot, mild,	high	true, false	P	$T59$	sunny, rain	hot, cool	high, normal	false	P 72.18% N 27.82%
	0.12, 0.29, 0.59	0.7, 0.3,	1.0	0.02, 0.98			0.36, 0.64	0.88, 0.12	0.52, 0.48	1.0
$T30$	overcast, rain	mild, cool	high, normal	false	P	$T60$	rain	cool, mild	normal, high	true, false	P 68.11% N 31.89%
	0.21, 0.79	0.67, 0.33	0.44, 0.56	1.0			1.0	0.69,0.31	0.71,0.29	0.30,0.70

Source: The Authors.

Table 10. The bifurcation criterion value about sub nodes in the probabilistic multi-valued environment.

Preference = “sunny”		Preference = “rain”
M (T′1, A2) =0.0439		M (T′3, A2) =0.0010
M (T′1, A3) =0.0461		M (T′3, A3) =0.0300
M (T′1, A4) =0.1767		M (T′3, A4) =0.0590
Select the attribute “A4”		Select the attribute “A4”
Pre = “sunny, true”	Pre = “sunny, false”	Pre = “rain, true”	Pre= “rain, false”
M (T′11, A2) = 0.0825	M (T′12, A2) = 0.0177	M (T′31, A2) = 0.0036	M (T′32, A2) = 0.0016
M (T′11, A3) = 0.0971	M (T′12, A4) = 0.0008	M (T′31, A3) = 0.1470	M (T′32, A3) = 0.0192
Select the attribute “A3”, and the last attribute is “A2”		Select the attribute “A3”, and the last attribute is “A2”
Pre = “sunny, true, high”	Pre= “sunny, true, normal”	Pre = “rain, true, high”	Pre = “rain, false, high”
“sunny, true, high, hot”	“sunny, true, normal, hot”	“rain, true, high, hot”	“rain, false, high, hot”
“sunny, true, high, mild”	“sunny, true, normal, mild”	“rain, true, high, hot”	“rain, false, high, mild”
“sunny, true, high, cool”	“sunny, true, normal, cool”	“rain, true, high, hot”	“rain, false, high, cool”
Pre = “sunny, false, high”		Pre = “rain, true, normal”	Pre = “rain, false, normal”
		“rain, true, normal, hot”	“rain, false, normal, hot”
		“rain, true, normal, mild”	“rain, false, normal, mild”
		“rain, true, normal, cool”	“rain, false, normal, cool”

Source: The Authors.

Figure 2. The DT based on the information gain and the data set ${\mathit{T}}^{\prime }.$

Source: The Authors.