568 lines
18 KiB
PHP
568 lines
18 KiB
PHP
<?php
|
|
|
|
namespace App\Services;
|
|
|
|
use App\Models\DataTraining;
|
|
use App\Services\PreprocessingService;
|
|
|
|
class C45Service
|
|
{
|
|
// Atribut yang digunakan untuk memprediksi target (jurusan)
|
|
// Ditambahkan 'mapel_favorit' ke dalam atribut prediksi
|
|
private $atribut = ['nilai', 'mapel_favorit', 'minat', 'cita_cita', 'preferensi_studi'];
|
|
|
|
protected $preprocessingService;
|
|
|
|
// Cache data agar tidak berulang kali memproses database
|
|
private $preprocessedData = null;
|
|
|
|
public function __construct(PreprocessingService $preprocessingService)
|
|
{
|
|
$this->preprocessingService = $preprocessingService;
|
|
}
|
|
|
|
public function getTrainingData()
|
|
{
|
|
return DataTraining::all();
|
|
}
|
|
|
|
/**
|
|
* Ambil data training dan terapkan preprocessing serta pembersihan whitespace/string.
|
|
*/
|
|
public function getPreprocessedData()
|
|
{
|
|
if ($this->preprocessedData !== null) {
|
|
return $this->preprocessedData;
|
|
}
|
|
|
|
$rawRecords = DataTraining::all();
|
|
$processed = collect();
|
|
|
|
foreach ($rawRecords as $row) {
|
|
// Terapkan preprocessing
|
|
$data = $this->preprocessingService->preprocess($row);
|
|
|
|
// Terapkan TRIM & Sanitasi String pada setiap kolom agar tidak ada bug matching
|
|
$sanitized = [];
|
|
foreach ($data as $key => $value) {
|
|
$sanitized[$key] = is_string($value) ? trim($value) : $value;
|
|
}
|
|
|
|
$processed->push((object) $sanitized);
|
|
}
|
|
|
|
$this->preprocessedData = $processed;
|
|
return $this->preprocessedData;
|
|
}
|
|
|
|
public function getTotalData()
|
|
{
|
|
return $this->getPreprocessedData()->count();
|
|
}
|
|
|
|
public function getJumlahJurusan()
|
|
{
|
|
return $this->getPreprocessedData()
|
|
->groupBy('jurusan')
|
|
->map(function ($items, $key) {
|
|
return (object) ['jurusan' => $key, 'jumlah' => $items->count()];
|
|
})->values();
|
|
}
|
|
|
|
/**
|
|
* Menghitung Entropy Total Dataset menggunakan log2
|
|
*/
|
|
public function entropyTotal()
|
|
{
|
|
$data = $this->getPreprocessedData();
|
|
$totalData = $data->count();
|
|
if ($totalData == 0) return 0;
|
|
|
|
$kelas = $data->groupBy('jurusan');
|
|
$entropy = 0;
|
|
|
|
foreach ($kelas as $items) {
|
|
$probabilitas = $items->count() / $totalData;
|
|
if ($probabilitas > 0) {
|
|
$entropy -= $probabilitas * log($probabilitas, 2);
|
|
}
|
|
}
|
|
return round($entropy, 6);
|
|
}
|
|
|
|
/**
|
|
* Menghitung Entropy untuk setiap nilai unik pada suatu atribut
|
|
*/
|
|
public function hitungEntropyAtribut($atribut)
|
|
{
|
|
$data = $this->getPreprocessedData();
|
|
|
|
// Pastikan unique value benar-benar bersih
|
|
$nilaiUnik = $data->pluck($atribut)->map(fn($val) => trim($val))->unique()->values();
|
|
$hasil = [];
|
|
|
|
foreach ($nilaiUnik as $nilai) {
|
|
// Filter dengan Strict Trim
|
|
$subset = $data->filter(function ($item) use ($atribut, $nilai) {
|
|
return trim($item->$atribut ?? '') === $nilai;
|
|
});
|
|
|
|
$jumlahSubset = $subset->count();
|
|
if ($jumlahSubset == 0) continue;
|
|
|
|
$kelas = $subset->groupBy('jurusan');
|
|
$entropy = 0;
|
|
|
|
foreach ($kelas as $items) {
|
|
$p = $items->count() / $jumlahSubset;
|
|
if ($p > 0) {
|
|
$entropy -= $p * log($p, 2);
|
|
}
|
|
}
|
|
|
|
$hasil[] = [
|
|
'nilai' => $nilai,
|
|
'jumlah' => $jumlahSubset,
|
|
'entropy' => round($entropy, 6)
|
|
];
|
|
}
|
|
|
|
// Urutkan berdasarkan jumlah terbanyak agar rapi di tampilan
|
|
usort($hasil, fn($a, $b) => $b['jumlah'] <=> $a['jumlah']);
|
|
|
|
return $hasil;
|
|
}
|
|
|
|
public function hitungGain($atribut)
|
|
{
|
|
$totalData = $this->getTotalData();
|
|
if ($totalData == 0) return 0;
|
|
|
|
$entropyTotal = $this->entropyTotal();
|
|
$entropyAtribut = $this->hitungEntropyAtribut($atribut);
|
|
$totalEntropyAtribut = 0;
|
|
|
|
foreach ($entropyAtribut as $item) {
|
|
$totalEntropyAtribut += ($item['jumlah'] / $totalData) * $item['entropy'];
|
|
}
|
|
|
|
return round($entropyTotal - $totalEntropyAtribut, 6);
|
|
}
|
|
|
|
public function hitungSplitInfo($atribut)
|
|
{
|
|
$data = $this->getPreprocessedData();
|
|
$total = $data->count();
|
|
if ($total == 0) return 0;
|
|
|
|
$nilaiUnik = $data->pluck($atribut)->map(fn($val) => trim($val))->unique();
|
|
$split = 0;
|
|
|
|
foreach ($nilaiUnik as $nilai) {
|
|
$jumlah = $data->filter(fn($item) => trim($item->$atribut ?? '') === $nilai)->count();
|
|
$p = $jumlah / $total;
|
|
if ($p > 0) {
|
|
$split -= $p * log($p, 2);
|
|
}
|
|
}
|
|
return round($split, 6);
|
|
}
|
|
|
|
public function hitungGainRatio($atribut)
|
|
{
|
|
$gain = $this->hitungGain($atribut);
|
|
$split = $this->hitungSplitInfo($atribut);
|
|
return $split == 0 ? 0 : round($gain / $split, 6);
|
|
}
|
|
|
|
public function getRootNode()
|
|
{
|
|
$gain = [];
|
|
foreach ($this->atribut as $atribut) {
|
|
$gain[$atribut] = $this->hitungGainRatio($atribut);
|
|
}
|
|
arsort($gain);
|
|
$root = array_key_first($gain);
|
|
|
|
return [
|
|
'root' => $root,
|
|
'gain' => $gain[$root],
|
|
'semua_gain' => $gain
|
|
];
|
|
}
|
|
|
|
public function getSubset($atribut)
|
|
{
|
|
return $this->getPreprocessedData()
|
|
->groupBy(fn($item) => trim($item->$atribut))
|
|
->toArray();
|
|
}
|
|
|
|
// =========================================================================
|
|
// HELPER SUBSET RECURSIVE (PENANGANAN TYPE SAFETY OBJECT/ARRAY)
|
|
// =========================================================================
|
|
|
|
private function getVal($row, $key)
|
|
{
|
|
if (is_object($row)) {
|
|
return trim($row->$key ?? '');
|
|
}
|
|
return trim($row[$key] ?? '');
|
|
}
|
|
|
|
private function entropySubset($data)
|
|
{
|
|
$jumlahData = count($data);
|
|
if ($jumlahData == 0) return 0;
|
|
|
|
$kelas = [];
|
|
foreach ($data as $row) {
|
|
$jurusan = $this->getVal($row, 'jurusan');
|
|
$kelas[$jurusan] = ($kelas[$jurusan] ?? 0) + 1;
|
|
}
|
|
|
|
$entropy = 0;
|
|
foreach ($kelas as $jumlah) {
|
|
$p = $jumlah / $jumlahData;
|
|
if ($p > 0) $entropy -= $p * log($p, 2);
|
|
}
|
|
return round($entropy, 6);
|
|
}
|
|
|
|
private function gainSubset($data, $atribut)
|
|
{
|
|
$entropyAwal = $this->entropySubset($data);
|
|
$jumlahTotal = count($data);
|
|
if ($jumlahTotal == 0) return 0;
|
|
|
|
$kelompok = [];
|
|
foreach ($data as $row) {
|
|
$val = $this->getVal($row, $atribut);
|
|
$kelompok[$val][] = $row;
|
|
}
|
|
|
|
$entropyBaru = 0;
|
|
foreach ($kelompok as $group) {
|
|
$entropyBaru += (count($group) / $jumlahTotal) * $this->entropySubset($group);
|
|
}
|
|
return round($entropyAwal - $entropyBaru, 6);
|
|
}
|
|
|
|
private function splitInfoSubset($data, $atribut)
|
|
{
|
|
$jumlah = count($data);
|
|
if ($jumlah == 0) return 0;
|
|
|
|
$group = [];
|
|
foreach ($data as $row) {
|
|
$val = $this->getVal($row, $atribut);
|
|
$group[$val][] = $row;
|
|
}
|
|
|
|
$split = 0;
|
|
foreach ($group as $g) {
|
|
$p = count($g) / $jumlah;
|
|
if ($p > 0) $split -= $p * log($p, 2);
|
|
}
|
|
return round($split, 6);
|
|
}
|
|
|
|
private function gainRatioSubset($data, $atribut)
|
|
{
|
|
$gain = $this->gainSubset($data, $atribut);
|
|
$split = $this->splitInfoSubset($data, $atribut);
|
|
return $split == 0 ? 0 : round($gain / $split, 6);
|
|
}
|
|
|
|
private function bestAttribute($data, $atributTersisa)
|
|
{
|
|
$hasil = [];
|
|
foreach ($atributTersisa as $atribut) {
|
|
$hasil[$atribut] = $this->gainRatioSubset($data, $atribut);
|
|
}
|
|
arsort($hasil);
|
|
return array_key_first($hasil);
|
|
}
|
|
|
|
private function isPure($data)
|
|
{
|
|
if (count($data) == 0) return false;
|
|
$kelas = [];
|
|
foreach ($data as $row) {
|
|
$kelas[$this->getVal($row, 'jurusan')] = true;
|
|
}
|
|
return count($kelas) == 1;
|
|
}
|
|
|
|
public function majorityClass($data)
|
|
{
|
|
$kelas = [];
|
|
foreach ($data as $row) {
|
|
$j = $this->getVal($row, 'jurusan');
|
|
$kelas[$j] = ($kelas[$j] ?? 0) + 1;
|
|
}
|
|
arsort($kelas);
|
|
return array_key_first($kelas) ?? 'Tidak Diketahui';
|
|
}
|
|
|
|
public function buildTree($data = null, $atribut = null)
|
|
{
|
|
if ($data === null) {
|
|
$data = $this->getPreprocessedData()->toArray();
|
|
}
|
|
if ($atribut === null) {
|
|
$atribut = $this->atribut;
|
|
}
|
|
|
|
// Simpan kelas mayoritas di NODE LOKAL ini untuk penanganan Unseen Value
|
|
$localMajority = $this->majorityClass($data);
|
|
|
|
// 1. Jika data murni (Pure)
|
|
if ($this->isPure($data)) {
|
|
return [
|
|
'type' => 'leaf',
|
|
'label' => $this->getVal($data[0], 'jurusan')
|
|
];
|
|
}
|
|
|
|
// 2. Jika atribut habis, jadikan Leaf dengan kelas mayoritas lokal
|
|
if (count($atribut) == 0) {
|
|
return [
|
|
'type' => 'leaf',
|
|
'label' => $localMajority
|
|
];
|
|
}
|
|
|
|
$best = $this->bestAttribute($data, $atribut);
|
|
|
|
// Simpan 'local_majority' dan 'subset_data' pada struktur Node
|
|
$tree = [
|
|
'type' => 'node',
|
|
'attribute' => $best,
|
|
'local_majority' => $localMajority,
|
|
'children' => []
|
|
];
|
|
|
|
$nilai = [];
|
|
foreach ($data as $row) {
|
|
$v = $this->getVal($row, $best);
|
|
$nilai[$v][] = $row;
|
|
}
|
|
|
|
$atributBaru = array_values(array_diff($atribut, [$best]));
|
|
|
|
foreach ($nilai as $value => $subset) {
|
|
$tree['children'][$value] = $this->buildTree($subset, $atributBaru);
|
|
}
|
|
|
|
return $tree;
|
|
}
|
|
|
|
public function tampilTree($tree, $indent = '')
|
|
{
|
|
if ($tree['type'] == 'leaf') {
|
|
return $indent . "➡ Jurusan = " . $tree['label'] . "\n";
|
|
}
|
|
|
|
$hasil = $indent . "[" . strtoupper($tree['attribute']) . "]\n";
|
|
foreach ($tree['children'] as $value => $child) {
|
|
$hasil .= $indent . "├── " . $value . "\n";
|
|
$hasil .= $this->tampilTree($child, $indent . "│ ");
|
|
}
|
|
return $hasil;
|
|
}
|
|
|
|
public function predictDetail($inputRaw)
|
|
{
|
|
$inputObj = (object) $inputRaw;
|
|
$inputPreprocessed = $this->preprocessingService->preprocess($inputObj);
|
|
|
|
$tree = $this->buildTree();
|
|
$path = [];
|
|
|
|
$resultNode = $this->predictRecursiveWithDetail($tree, $inputPreprocessed, $path);
|
|
|
|
return [
|
|
'rekomendasi_utama' => $resultNode['label'],
|
|
'rule_path' => $resultNode['path'],
|
|
'detail_subset' => $resultNode['subset_info'] ?? null,
|
|
];
|
|
}
|
|
|
|
/**
|
|
* Melakukan rekursi prediksi dengan penanganan Unseen Value yang presisi.
|
|
*/
|
|
private function predictRecursiveWithDetail($tree, $input, &$path)
|
|
{
|
|
if ($tree['type'] == 'leaf') {
|
|
return [
|
|
'label' => $tree['label'],
|
|
'path' => $path
|
|
];
|
|
}
|
|
|
|
$atribut = $tree['attribute'];
|
|
$nilai = isset($input[$atribut]) ? trim($input[$atribut]) : null;
|
|
|
|
// 1. Jika cabang cocok secara presisi, teruskan secara normal
|
|
if ($nilai !== null && isset($tree['children'][$nilai])) {
|
|
$path[] = strtolower($atribut) . ' = ' . $nilai;
|
|
return $this->predictRecursiveWithDetail($tree['children'][$nilai], $input, $path);
|
|
}
|
|
|
|
// 2. PENANGANAN UNSEEN VALUE / CABANG BUNTU:
|
|
// Evaluasi seluruh cabang anak untuk melihat mana yang paling COCOK dengan sisa input user
|
|
$bestChildNode = null;
|
|
$maxMatchScore = -1;
|
|
|
|
foreach ($tree['children'] as $childVal => $childNode) {
|
|
$score = $this->hitungKemiripanInput($childNode, $input);
|
|
if ($score > $maxMatchScore) {
|
|
$maxMatchScore = $score;
|
|
$bestChildNode = $childNode;
|
|
}
|
|
}
|
|
|
|
if ($bestChildNode !== null) {
|
|
$path[] = strtolower($atribut) . " = '{$nilai}' (Unseen -> Dialihkan ke cabang paling relevan)";
|
|
return $this->predictRecursiveWithDetail($bestChildNode, $input, $path);
|
|
}
|
|
|
|
// 3. Fallback terakhir jika buntu total
|
|
$fallbackLabel = $tree['local_majority'] ?? $this->majorityClass($this->getPreprocessedData()->toArray());
|
|
$path[] = strtolower($atribut) . " = '{$nilai}' (Fallback Majority: {$fallbackLabel})";
|
|
|
|
return [
|
|
'label' => $fallbackLabel,
|
|
'path' => $path
|
|
];
|
|
}
|
|
|
|
/**
|
|
* Helper untuk mengukur berapa banyak atribut input user yang cocok pada suatu node cabang
|
|
*/
|
|
private function hitungKemiripanInput($node, $input)
|
|
{
|
|
if ($node['type'] === 'leaf') return 1;
|
|
|
|
$score = 0;
|
|
$attr = $node['attribute'];
|
|
|
|
if (isset($input[$attr]) && isset($node['children'][$input[$attr]])) {
|
|
$score += 2; // Berikan bobot lebih tinggi jika ada kesamaan atribut
|
|
}
|
|
|
|
return $score;
|
|
}
|
|
|
|
/**
|
|
* Mengambil detail perhitungan Gain Ratio untuk SEMUA level/node secara rekursif.
|
|
*/
|
|
public function getDetailSubsets($data = null, $atributTersisa = null, $nodeLevel = 1, $pathName = 'Root Node')
|
|
{
|
|
if ($data === null) {
|
|
$data = $this->getPreprocessedData()->toArray();
|
|
}
|
|
if ($atributTersisa === null) {
|
|
$atributTersisa = $this->atribut;
|
|
}
|
|
|
|
// Jika data murni atau atribut habis, tidak ada pembagian subset lagi
|
|
if ($this->isPure($data) || empty($atributTersisa)) {
|
|
return [];
|
|
}
|
|
|
|
// 1. Cari Best Attribute untuk Node saat ini
|
|
$best = $this->bestAttribute($data, $atributTersisa);
|
|
if (!$best) return [];
|
|
|
|
// 2. Kelompokkan data berdasarkan atribut terbaik yang terpilih
|
|
$subsets = [];
|
|
foreach ($data as $row) {
|
|
$val = $this->getVal($row, $best);
|
|
$subsets[$val][] = $row;
|
|
}
|
|
|
|
$sisaAtributSelanjutnya = array_values(array_diff($atributTersisa, [$best]));
|
|
$nodeDetails = [];
|
|
|
|
// 3. Hitung kalkulasi Gain Ratio untuk subset pada node ini
|
|
$detailBranches = [];
|
|
foreach ($subsets as $nilaiCabang => $items) {
|
|
$isPure = $this->isPure($items);
|
|
$jumlahData = count($items);
|
|
$kalkulasiAtribut = [];
|
|
|
|
if (!$isPure && !empty($sisaAtributSelanjutnya)) {
|
|
foreach ($sisaAtributSelanjutnya as $attr) {
|
|
$gain = $this->gainSubset($items, $attr);
|
|
$split = $this->splitInfoSubset($items, $attr);
|
|
$gainRatio = $split == 0 ? 0 : round($gain / $split, 6);
|
|
|
|
$kalkulasiAtribut[] = [
|
|
'atribut' => $attr,
|
|
'gain' => $gain,
|
|
'split_info' => $split,
|
|
'gain_ratio' => $gainRatio,
|
|
];
|
|
}
|
|
usort($kalkulasiAtribut, fn($a, $b) => $b['gain_ratio'] <=> $a['gain_ratio']);
|
|
}
|
|
|
|
$winnerAtribut = $isPure ? null : ($kalkulasiAtribut[0]['atribut'] ?? null);
|
|
|
|
$detailBranches[$nilaiCabang] = [
|
|
'nilai_cabang' => $nilaiCabang,
|
|
'jumlah_data' => $jumlahData,
|
|
'is_pure' => $isPure,
|
|
'pemenang' => $isPure ? $this->majorityClass($items) : ($winnerAtribut ?? '-'),
|
|
'kalkulasi' => $kalkulasiAtribut,
|
|
'items' => $items
|
|
];
|
|
|
|
// 4. REKURSI: Jika node cabang belum murni, telusuri terus ke Node-3, Node-4, dst.
|
|
if (!$isPure && !empty($sisaAtributSelanjutnya) && $winnerAtribut) {
|
|
$childPath = "{$pathName} ➔ {$best}='{$nilaiCabang}'";
|
|
$childNodes = $this->getDetailSubsets($items, $sisaAtributSelanjutnya, $nodeLevel + 1, $childPath);
|
|
$nodeDetails = array_merge($nodeDetails, $childNodes);
|
|
}
|
|
}
|
|
|
|
// Gabungkan detail node saat ini dengan detail node anak-anaknya
|
|
$currentStructure = [
|
|
'level' => $nodeLevel,
|
|
'path_label' => $pathName,
|
|
'split_by' => $best,
|
|
'branches' => $detailBranches
|
|
];
|
|
|
|
return array_merge([$currentStructure], $nodeDetails);
|
|
}
|
|
|
|
/**
|
|
* Ekstrak pohon keputusan menjadi daftar aturan IF-THEN
|
|
*/
|
|
public function generateRules($tree = null, $currentRule = [])
|
|
{
|
|
if ($tree === null) {
|
|
$tree = $this->buildTree();
|
|
}
|
|
|
|
$rules = [];
|
|
|
|
if ($tree['type'] === 'leaf') {
|
|
$ruleText = "IF " . implode(" AND ", $currentRule) . " THEN Jurusan = " . $tree['label'];
|
|
return [$ruleText];
|
|
}
|
|
|
|
$attr = strtoupper(str_replace('_', ' ', $tree['attribute']));
|
|
|
|
foreach ($tree['children'] as $val => $child) {
|
|
$newRule = $currentRule;
|
|
$newRule[] = "{$attr} = '{$val}'";
|
|
$rules = array_merge($rules, $this->generateRules($child, $newRule));
|
|
}
|
|
|
|
return $rules;
|
|
}
|
|
} |