1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
declare(strict_types=1); |
4
|
|
|
|
5
|
|
|
namespace Phpml\Classification; |
6
|
|
|
|
7
|
|
|
use Phpml\Classification\DecisionTree\DecisionTreeLeaf; |
8
|
|
|
use Phpml\Exception\InvalidArgumentException; |
9
|
|
|
use Phpml\Helper\Predictable; |
10
|
|
|
use Phpml\Helper\Trainable; |
11
|
|
|
use Phpml\Math\Statistic\Mean; |
12
|
|
|
|
13
|
|
|
class DecisionTree implements Classifier |
14
|
|
|
{ |
15
|
|
|
use Trainable; |
16
|
|
|
use Predictable; |
17
|
|
|
|
18
|
|
|
public const CONTINUOUS = 1; |
19
|
|
|
|
20
|
|
|
public const NOMINAL = 2; |
21
|
|
|
|
22
|
|
|
/** |
23
|
|
|
* @var int |
24
|
|
|
*/ |
25
|
|
|
public $actualDepth = 0; |
26
|
|
|
|
27
|
|
|
/** |
28
|
|
|
* @var array |
29
|
|
|
*/ |
30
|
|
|
protected $columnTypes = []; |
31
|
|
|
|
32
|
|
|
/** |
33
|
|
|
* @var DecisionTreeLeaf |
34
|
|
|
*/ |
35
|
|
|
protected $tree; |
36
|
|
|
|
37
|
|
|
/** |
38
|
|
|
* @var int |
39
|
|
|
*/ |
40
|
|
|
protected $maxDepth; |
41
|
|
|
|
42
|
|
|
/** |
43
|
|
|
* @var array |
44
|
|
|
*/ |
45
|
|
|
private $labels = []; |
46
|
|
|
|
47
|
|
|
/** |
48
|
|
|
* @var int |
49
|
|
|
*/ |
50
|
|
|
private $featureCount = 0; |
51
|
|
|
|
52
|
|
|
/** |
53
|
|
|
* @var int |
54
|
|
|
*/ |
55
|
|
|
private $numUsableFeatures = 0; |
56
|
|
|
|
57
|
|
|
/** |
58
|
|
|
* @var array |
59
|
|
|
*/ |
60
|
|
|
private $selectedFeatures = []; |
61
|
|
|
|
62
|
|
|
/** |
63
|
|
|
* @var array|null |
64
|
|
|
*/ |
65
|
|
|
private $featureImportances; |
66
|
|
|
|
67
|
|
|
/** |
68
|
|
|
* @var array |
69
|
|
|
*/ |
70
|
|
|
private $columnNames = []; |
71
|
|
|
|
72
|
|
|
public function __construct(int $maxDepth = 10) |
73
|
|
|
{ |
74
|
|
|
$this->maxDepth = $maxDepth; |
75
|
|
|
} |
76
|
|
|
|
77
|
|
|
public function train(array $samples, array $targets): void |
78
|
|
|
{ |
79
|
|
|
$this->samples = array_merge($this->samples, $samples); |
80
|
|
|
$this->targets = array_merge($this->targets, $targets); |
81
|
|
|
|
82
|
|
|
$this->featureCount = count($this->samples[0]); |
83
|
|
|
$this->columnTypes = self::getColumnTypes($this->samples); |
84
|
|
|
$this->labels = array_keys(array_count_values($this->targets)); |
85
|
|
|
$this->tree = $this->getSplitLeaf(range(0, count($this->samples) - 1)); |
86
|
|
|
|
87
|
|
|
// Each time the tree is trained, feature importances are reset so that |
88
|
|
|
// we will have to compute it again depending on the new data |
89
|
|
|
$this->featureImportances = null; |
90
|
|
|
|
91
|
|
|
// If column names are given or computed before, then there is no |
92
|
|
|
// need to init it and accidentally remove the previous given names |
93
|
|
|
if ($this->columnNames === []) { |
94
|
|
|
$this->columnNames = range(0, $this->featureCount - 1); |
95
|
|
|
} elseif (count($this->columnNames) > $this->featureCount) { |
96
|
|
|
$this->columnNames = array_slice($this->columnNames, 0, $this->featureCount); |
97
|
|
|
} elseif (count($this->columnNames) < $this->featureCount) { |
98
|
|
|
$this->columnNames = array_merge( |
99
|
|
|
$this->columnNames, |
100
|
|
|
range(count($this->columnNames), $this->featureCount - 1) |
101
|
|
|
); |
102
|
|
|
} |
103
|
|
|
} |
104
|
|
|
|
105
|
|
|
public static function getColumnTypes(array $samples): array |
106
|
|
|
{ |
107
|
|
|
$types = []; |
108
|
|
|
$featureCount = count($samples[0]); |
109
|
|
|
for ($i = 0; $i < $featureCount; ++$i) { |
110
|
|
|
$values = array_column($samples, $i); |
111
|
|
|
$isCategorical = self::isCategoricalColumn($values); |
112
|
|
|
$types[] = $isCategorical ? self::NOMINAL : self::CONTINUOUS; |
113
|
|
|
} |
114
|
|
|
|
115
|
|
|
return $types; |
116
|
|
|
} |
117
|
|
|
|
118
|
|
|
/** |
119
|
|
|
* @param mixed $baseValue |
120
|
|
|
*/ |
121
|
|
|
public function getGiniIndex($baseValue, array $colValues, array $targets): float |
122
|
|
|
{ |
123
|
|
|
$countMatrix = []; |
124
|
|
|
foreach ($this->labels as $label) { |
125
|
|
|
$countMatrix[$label] = [0, 0]; |
126
|
|
|
} |
127
|
|
|
|
128
|
|
|
foreach ($colValues as $index => $value) { |
129
|
|
|
$label = $targets[$index]; |
130
|
|
|
$rowIndex = $value === $baseValue ? 0 : 1; |
131
|
|
|
++$countMatrix[$label][$rowIndex]; |
132
|
|
|
} |
133
|
|
|
|
134
|
|
|
$giniParts = [0, 0]; |
135
|
|
|
for ($i = 0; $i <= 1; ++$i) { |
136
|
|
|
$part = 0; |
137
|
|
|
$sum = array_sum(array_column($countMatrix, $i)); |
138
|
|
|
if ($sum > 0) { |
139
|
|
|
foreach ($this->labels as $label) { |
140
|
|
|
$part += ($countMatrix[$label][$i] / (float) $sum) ** 2; |
141
|
|
|
} |
142
|
|
|
} |
143
|
|
|
|
144
|
|
|
$giniParts[$i] = (1 - $part) * $sum; |
145
|
|
|
} |
146
|
|
|
|
147
|
|
|
return array_sum($giniParts) / count($colValues); |
148
|
|
|
} |
149
|
|
|
|
150
|
|
|
/** |
151
|
|
|
* This method is used to set number of columns to be used |
152
|
|
|
* when deciding a split at an internal node of the tree. <br> |
153
|
|
|
* If the value is given 0, then all features are used (default behaviour), |
154
|
|
|
* otherwise the given value will be used as a maximum for number of columns |
155
|
|
|
* randomly selected for each split operation. |
156
|
|
|
* |
157
|
|
|
* @return $this |
158
|
|
|
* |
159
|
|
|
* @throws InvalidArgumentException |
160
|
|
|
*/ |
161
|
|
|
public function setNumFeatures(int $numFeatures) |
162
|
|
|
{ |
163
|
|
|
if ($numFeatures < 0) { |
164
|
|
|
throw new InvalidArgumentException('Selected column count should be greater or equal to zero'); |
165
|
|
|
} |
166
|
|
|
|
167
|
|
|
$this->numUsableFeatures = $numFeatures; |
168
|
|
|
|
169
|
|
|
return $this; |
170
|
|
|
} |
171
|
|
|
|
172
|
|
|
/** |
173
|
|
|
* A string array to represent columns. Useful when HTML output or |
174
|
|
|
* column importances are desired to be inspected. |
175
|
|
|
* |
176
|
|
|
* @return $this |
177
|
|
|
* |
178
|
|
|
* @throws InvalidArgumentException |
179
|
|
|
*/ |
180
|
|
|
public function setColumnNames(array $names) |
181
|
|
|
{ |
182
|
|
|
if ($this->featureCount !== 0 && count($names) !== $this->featureCount) { |
183
|
|
|
throw new InvalidArgumentException(sprintf('Length of the given array should be equal to feature count %s', $this->featureCount)); |
184
|
|
|
} |
185
|
|
|
|
186
|
|
|
$this->columnNames = $names; |
187
|
|
|
|
188
|
|
|
return $this; |
189
|
|
|
} |
190
|
|
|
|
191
|
|
|
public function getHtml(): string |
192
|
|
|
{ |
193
|
|
|
return $this->tree->getHTML($this->columnNames); |
194
|
|
|
} |
195
|
|
|
|
196
|
|
|
/** |
197
|
|
|
* This will return an array including an importance value for |
198
|
|
|
* each column in the given dataset. The importance values are |
199
|
|
|
* normalized and their total makes 1.<br/> |
200
|
|
|
*/ |
201
|
|
|
public function getFeatureImportances(): array |
202
|
|
|
{ |
203
|
|
|
if ($this->featureImportances !== null) { |
204
|
|
|
return $this->featureImportances; |
205
|
|
|
} |
206
|
|
|
|
207
|
|
|
$sampleCount = count($this->samples); |
208
|
|
|
$this->featureImportances = []; |
209
|
|
|
foreach ($this->columnNames as $column => $columnName) { |
210
|
|
|
$nodes = $this->getSplitNodesByColumn($column, $this->tree); |
211
|
|
|
|
212
|
|
|
$importance = 0; |
213
|
|
|
foreach ($nodes as $node) { |
214
|
|
|
$importance += $node->getNodeImpurityDecrease($sampleCount); |
215
|
|
|
} |
216
|
|
|
|
217
|
|
|
$this->featureImportances[$columnName] = $importance; |
218
|
|
|
} |
219
|
|
|
|
220
|
|
|
// Normalize & sort the importances |
221
|
|
|
$total = array_sum($this->featureImportances); |
222
|
|
|
if ($total > 0) { |
223
|
|
|
array_walk($this->featureImportances, function (&$importance) use ($total): void { |
224
|
|
|
$importance /= $total; |
225
|
|
|
}); |
226
|
|
|
arsort($this->featureImportances); |
227
|
|
|
} |
228
|
|
|
|
229
|
|
|
return $this->featureImportances; |
230
|
|
|
} |
231
|
|
|
|
232
|
|
|
protected function getSplitLeaf(array $records, int $depth = 0): DecisionTreeLeaf |
233
|
|
|
{ |
234
|
|
|
$split = $this->getBestSplit($records); |
235
|
|
|
$split->level = $depth; |
236
|
|
|
if ($this->actualDepth < $depth) { |
237
|
|
|
$this->actualDepth = $depth; |
238
|
|
|
} |
239
|
|
|
|
240
|
|
|
// Traverse all records to see if all records belong to the same class, |
241
|
|
|
// otherwise group the records so that we can classify the leaf |
242
|
|
|
// in case maximum depth is reached |
243
|
|
|
$leftRecords = []; |
244
|
|
|
$rightRecords = []; |
245
|
|
|
$remainingTargets = []; |
246
|
|
|
$prevRecord = null; |
247
|
|
|
$allSame = true; |
248
|
|
|
|
249
|
|
|
foreach ($records as $recordNo) { |
250
|
|
|
// Check if the previous record is the same with the current one |
251
|
|
|
$record = $this->samples[$recordNo]; |
252
|
|
|
if ($prevRecord !== null && $prevRecord != $record) { |
253
|
|
|
$allSame = false; |
254
|
|
|
} |
255
|
|
|
|
256
|
|
|
$prevRecord = $record; |
257
|
|
|
|
258
|
|
|
// According to the split criteron, this record will |
259
|
|
|
// belong to either left or the right side in the next split |
260
|
|
|
if ($split->evaluate($record)) { |
261
|
|
|
$leftRecords[] = $recordNo; |
262
|
|
|
} else { |
263
|
|
|
$rightRecords[] = $recordNo; |
264
|
|
|
} |
265
|
|
|
|
266
|
|
|
// Group remaining targets |
267
|
|
|
$target = $this->targets[$recordNo]; |
268
|
|
|
if (!array_key_exists($target, $remainingTargets)) { |
269
|
|
|
$remainingTargets[$target] = 1; |
270
|
|
|
} else { |
271
|
|
|
++$remainingTargets[$target]; |
272
|
|
|
} |
273
|
|
|
} |
274
|
|
|
|
275
|
|
|
if ($allSame || $depth >= $this->maxDepth || count($remainingTargets) === 1) { |
276
|
|
|
$split->isTerminal = true; |
277
|
|
|
arsort($remainingTargets); |
278
|
|
|
$split->classValue = (string) key($remainingTargets); |
279
|
|
|
} else { |
280
|
|
|
if (isset($leftRecords[0])) { |
281
|
|
|
$split->leftLeaf = $this->getSplitLeaf($leftRecords, $depth + 1); |
282
|
|
|
} |
283
|
|
|
|
284
|
|
|
if (isset($rightRecords[0])) { |
285
|
|
|
$split->rightLeaf = $this->getSplitLeaf($rightRecords, $depth + 1); |
286
|
|
|
} |
287
|
|
|
} |
288
|
|
|
|
289
|
|
|
return $split; |
290
|
|
|
} |
291
|
|
|
|
292
|
|
|
protected function getBestSplit(array $records): DecisionTreeLeaf |
293
|
|
|
{ |
294
|
|
|
$targets = array_intersect_key($this->targets, array_flip($records)); |
295
|
|
|
$samples = (array) array_combine( |
296
|
|
|
$records, |
297
|
|
|
$this->preprocess(array_intersect_key($this->samples, array_flip($records))) |
298
|
|
|
); |
299
|
|
|
$bestGiniVal = 1; |
300
|
|
|
$bestSplit = null; |
301
|
|
|
$features = $this->getSelectedFeatures(); |
302
|
|
|
foreach ($features as $i) { |
303
|
|
|
$colValues = []; |
304
|
|
|
foreach ($samples as $index => $row) { |
305
|
|
|
$colValues[$index] = $row[$i]; |
306
|
|
|
} |
307
|
|
|
|
308
|
|
|
$counts = array_count_values($colValues); |
309
|
|
|
arsort($counts); |
310
|
|
|
$baseValue = key($counts); |
311
|
|
|
if ($baseValue === null) { |
312
|
|
|
continue; |
313
|
|
|
} |
314
|
|
|
|
315
|
|
|
$gini = $this->getGiniIndex($baseValue, $colValues, $targets); |
316
|
|
|
if ($bestSplit === null || $bestGiniVal > $gini) { |
317
|
|
|
$split = new DecisionTreeLeaf(); |
318
|
|
|
$split->value = $baseValue; |
319
|
|
|
$split->giniIndex = $gini; |
320
|
|
|
$split->columnIndex = $i; |
321
|
|
|
$split->isContinuous = $this->columnTypes[$i] === self::CONTINUOUS; |
322
|
|
|
$split->records = $records; |
323
|
|
|
|
324
|
|
|
// If a numeric column is to be selected, then |
325
|
|
|
// the original numeric value and the selected operator |
326
|
|
|
// will also be saved into the leaf for future access |
327
|
|
|
if ($this->columnTypes[$i] === self::CONTINUOUS) { |
328
|
|
|
$matches = []; |
329
|
|
|
preg_match("/^([<>=]{1,2})\s*(.*)/", (string) $split->value, $matches); |
330
|
|
|
$split->operator = $matches[1]; |
331
|
|
|
$split->numericValue = (float) $matches[2]; |
332
|
|
|
} |
333
|
|
|
|
334
|
|
|
$bestSplit = $split; |
335
|
|
|
$bestGiniVal = $gini; |
336
|
|
|
} |
337
|
|
|
} |
338
|
|
|
|
339
|
|
|
return $bestSplit; |
|
|
|
|
340
|
|
|
} |
341
|
|
|
|
342
|
|
|
/** |
343
|
|
|
* Returns available features/columns to the tree for the decision making |
344
|
|
|
* process. <br> |
345
|
|
|
* |
346
|
|
|
* If a number is given with setNumFeatures() method, then a random selection |
347
|
|
|
* of features up to this number is returned. <br> |
348
|
|
|
* |
349
|
|
|
* If some features are manually selected by use of setSelectedFeatures(), |
350
|
|
|
* then only these features are returned <br> |
351
|
|
|
* |
352
|
|
|
* If any of above methods were not called beforehand, then all features |
353
|
|
|
* are returned by default. |
354
|
|
|
*/ |
355
|
|
|
protected function getSelectedFeatures(): array |
356
|
|
|
{ |
357
|
|
|
$allFeatures = range(0, $this->featureCount - 1); |
358
|
|
|
if ($this->numUsableFeatures === 0 && count($this->selectedFeatures) === 0) { |
359
|
|
|
return $allFeatures; |
360
|
|
|
} |
361
|
|
|
|
362
|
|
|
if (count($this->selectedFeatures) > 0) { |
363
|
|
|
return $this->selectedFeatures; |
364
|
|
|
} |
365
|
|
|
|
366
|
|
|
$numFeatures = $this->numUsableFeatures; |
367
|
|
|
if ($numFeatures > $this->featureCount) { |
368
|
|
|
$numFeatures = $this->featureCount; |
369
|
|
|
} |
370
|
|
|
|
371
|
|
|
shuffle($allFeatures); |
372
|
|
|
$selectedFeatures = array_slice($allFeatures, 0, $numFeatures); |
373
|
|
|
sort($selectedFeatures); |
374
|
|
|
|
375
|
|
|
return $selectedFeatures; |
376
|
|
|
} |
377
|
|
|
|
378
|
|
|
protected function preprocess(array $samples): array |
379
|
|
|
{ |
380
|
|
|
// Detect and convert continuous data column values into |
381
|
|
|
// discrete values by using the median as a threshold value |
382
|
|
|
$columns = []; |
383
|
|
|
for ($i = 0; $i < $this->featureCount; ++$i) { |
384
|
|
|
$values = array_column($samples, $i); |
385
|
|
|
if ($this->columnTypes[$i] == self::CONTINUOUS) { |
386
|
|
|
$median = Mean::median($values); |
387
|
|
|
foreach ($values as &$value) { |
388
|
|
|
if ($value <= $median) { |
389
|
|
|
$value = "<= ${median}"; |
390
|
|
|
} else { |
391
|
|
|
$value = "> ${median}"; |
392
|
|
|
} |
393
|
|
|
} |
394
|
|
|
} |
395
|
|
|
|
396
|
|
|
$columns[] = $values; |
397
|
|
|
} |
398
|
|
|
|
399
|
|
|
// Below method is a strange yet very simple & efficient method |
400
|
|
|
// to get the transpose of a 2D array |
401
|
|
|
return array_map(null, ...$columns); |
402
|
|
|
} |
403
|
|
|
|
404
|
|
|
protected static function isCategoricalColumn(array $columnValues): bool |
405
|
|
|
{ |
406
|
|
|
$count = count($columnValues); |
407
|
|
|
|
408
|
|
|
// There are two main indicators that *may* show whether a |
409
|
|
|
// column is composed of discrete set of values: |
410
|
|
|
// 1- Column may contain string values and non-float values |
411
|
|
|
// 2- Number of unique values in the column is only a small fraction of |
412
|
|
|
// all values in that column (Lower than or equal to %20 of all values) |
413
|
|
|
$numericValues = array_filter($columnValues, 'is_numeric'); |
414
|
|
|
$floatValues = array_filter($columnValues, 'is_float'); |
415
|
|
|
if (count($floatValues) > 0) { |
416
|
|
|
return false; |
417
|
|
|
} |
418
|
|
|
|
419
|
|
|
if (count($numericValues) !== $count) { |
420
|
|
|
return true; |
421
|
|
|
} |
422
|
|
|
|
423
|
|
|
$distinctValues = array_count_values($columnValues); |
424
|
|
|
|
425
|
|
|
return count($distinctValues) <= $count / 5; |
426
|
|
|
} |
427
|
|
|
|
428
|
|
|
/** |
429
|
|
|
* Used to set predefined features to consider while deciding which column to use for a split |
430
|
|
|
*/ |
431
|
|
|
protected function setSelectedFeatures(array $selectedFeatures): void |
432
|
|
|
{ |
433
|
|
|
$this->selectedFeatures = $selectedFeatures; |
434
|
|
|
} |
435
|
|
|
|
436
|
|
|
/** |
437
|
|
|
* Collects and returns an array of internal nodes that use the given |
438
|
|
|
* column as a split criterion |
439
|
|
|
*/ |
440
|
|
|
protected function getSplitNodesByColumn(int $column, DecisionTreeLeaf $node): array |
441
|
|
|
{ |
442
|
|
|
if ($node->isTerminal) { |
443
|
|
|
return []; |
444
|
|
|
} |
445
|
|
|
|
446
|
|
|
$nodes = []; |
447
|
|
|
if ($node->columnIndex === $column) { |
448
|
|
|
$nodes[] = $node; |
449
|
|
|
} |
450
|
|
|
|
451
|
|
|
$lNodes = []; |
452
|
|
|
$rNodes = []; |
453
|
|
|
if ($node->leftLeaf !== null) { |
454
|
|
|
$lNodes = $this->getSplitNodesByColumn($column, $node->leftLeaf); |
455
|
|
|
} |
456
|
|
|
|
457
|
|
|
if ($node->rightLeaf !== null) { |
458
|
|
|
$rNodes = $this->getSplitNodesByColumn($column, $node->rightLeaf); |
459
|
|
|
} |
460
|
|
|
|
461
|
|
|
return array_merge($nodes, $lNodes, $rNodes); |
462
|
|
|
} |
463
|
|
|
|
464
|
|
|
/** |
465
|
|
|
* @return mixed |
466
|
|
|
*/ |
467
|
|
|
protected function predictSample(array $sample) |
468
|
|
|
{ |
469
|
|
|
$node = $this->tree; |
470
|
|
|
do { |
471
|
|
|
if ($node->isTerminal) { |
472
|
|
|
return $node->classValue; |
473
|
|
|
} |
474
|
|
|
|
475
|
|
|
if ($node->evaluate($sample)) { |
476
|
|
|
$node = $node->leftLeaf; |
477
|
|
|
} else { |
478
|
|
|
$node = $node->rightLeaf; |
479
|
|
|
} |
480
|
|
|
} while ($node); |
481
|
|
|
|
482
|
|
|
return $this->labels[0]; |
483
|
|
|
} |
484
|
|
|
} |
485
|
|
|
|