Proses penjanaan pepohon keputusan adalah berkaitan dengan algoritma id3

Algoritma ID3 ialah algoritma klasik untuk menjana pepohon keputusan, yang dicadangkan oleh Ross Quinlan pada tahun 1986. Ia memilih ciri terbaik sebagai pemisahan nod dengan mengira keuntungan maklumat bagi setiap ciri. Algoritma ID3 digunakan secara meluas dalam bidang pembelajaran mesin dan perlombongan data, terutamanya memainkan peranan penting dalam tugas klasifikasi. Penggunaannya boleh meningkatkan ketepatan model dan kebolehtafsiran sambil juga dapat mengendalikan set data yang kompleks dengan pelbagai ciri dan kategori.

Pohon keputusan ialah struktur pokok yang digunakan untuk pengelasan atau regresi. Ia terdiri daripada nod dan tepi Nod mewakili ciri atau atribut, dan tepi mewakili nilai atau keputusan yang mungkin. Nod akar mewakili ciri yang paling penting, dan nod daun mewakili hasil pengelasan akhir. Pohon keputusan menentukan hasil pengelasan dengan menilai secara beransur-ansur nilai ciri, dan setiap penghakiman diteruskan di sepanjang dahan pokok itu. Struktur ini mudah dan intuitif, mudah difahami dan dijelaskan. Kunci kepada algoritma pepohon keputusan ialah memilih ciri dan titik keputusan terbaik untuk memaksimumkan ketepatan pengelasan.

Idea asas algoritma ID3 adalah untuk membahagikan set data kepada subset yang lebih kecil pada setiap nod dengan memilih ciri terbaik. Kemudian, proses yang sama digunakan secara rekursif untuk setiap subset sehingga syarat penamatan dicapai. Dalam masalah klasifikasi, syarat penamatan biasanya semua kejadian tergolong dalam kelas yang sama atau tiada lagi ciri untuk dipecahkan. Dalam masalah regresi, keadaan penamatan biasanya mencapai ralat atau had kedalaman tertentu. Kaedah pembahagian rekursif atas ke bawah ini membolehkan algoritma ID3 menggunakan sepenuhnya maklumat ciri semasa membina pepohon keputusan, dengan itu mencapai tugas pengelasan dan regresi yang cekap.

Proses menjana pepohon keputusan oleh algoritma ID3

1. Pilih ciri terbaik

Kira perolehan maklumat setiap ciri, dan pilih ciri dengan perolehan maklumat tertinggi sebagai nod berpecah. Keuntungan maklumat merujuk kepada sejauh mana ketulenan keputusan pengelasan dipertingkatkan selepas memisahkan set data mengikut ciri tertentu, iaitu perubahan dalam entropi.

Formula pengiraan perolehan maklumat adalah seperti berikut:

IG(D,F)=H(D)-sum_{vin Values(F)}frac{|D_v|}{|D|}H( D_v)

Antaranya, IG(D,F) mewakili perolehan maklumat ciri F dalam set data D; H(D) mewakili entropi set data D_v mewakili subset dengan nilai v pada ciri F; Nilai (F) mewakili set nilai ciri F.

2 Bahagikan set data kepada subset

Gunakan ciri terbaik yang dipilih sebagai nod belah dan bahagikan set data D kepada beberapa subset D_1, D_2,...,D_k, setiap subset sepadan dengan salah satu daripada. ciri-ciri F Ambil nilai.

3. Hasilkan subpokok secara rekursif

Untuk setiap subset D_i, jana subpokok secara rekursif. Jika semua kejadian dalam subset D_i tergolong dalam kategori yang sama, atau tiada lagi ciri untuk pemisahan, nod daun dijana dengan kategori ini sebagai hasil pengelasan.

4. Bina pepohon keputusan

Sambungkan nod belah dan subpohon untuk membentuk pepohon keputusan.

Kod pelaksanaan Python algoritma ID3

import math

class DecisionTree:
    def __init__(self):
        self.tree = {}

    def fit(self, X, y):
        self.tree = self._build_tree(X, y)

    def predict(self, X):
        y_pred = []
        for i in range(len(X)):
            node = self.tree
            while isinstance(node, dict):
                feature = list(node.keys())[0]
                value = X[i][feature]
                node = node[feature][value]
            y_pred.append(node)
        return y_pred

    def _entropy(self, y):
        n = len(y)
        counts = {}
        for value in y:
            counts[value] = counts.get(value, 0) + 1
        entropy = 0
        for count in counts.values():
            p = count / n
            entropy -= p * math.log2(p)
        return entropy

    def _information_gain(self, X, y, feature):
        n = len(y)
        values = set([x[feature] for x in X])
        entropy = 0
        for value in values:
            subset_x = [x forx in X if x[feature] == value]
            subset_y = [y[i] for i in range(len(y)) if X[i][feature] == value]
            entropy += len(subset_y) / n * self._entropy(subset_y)
        information_gain = self._entropy(y) - entropy
        return information_gain

    def _majority_vote(self, y):
        counts = {}
        for value in y:
            counts[value] = counts.get(value, 0) + 1
        majority = max(counts, key=counts.get)
        return majority

    def _build_tree(self, X, y):
        if len(set(y)) == 1:
            return y[0]
        if len(X[0]) == 0:
            return self._majority_vote(y)
        best_feature = max(range(len(X[0])), key=lambda i: self._information_gain(X, y, i))
        tree = {best_feature: {}}
        values = set([x[best_feature] for x in X])
        for value in values:
            subset_x = [x for x in X if x[best_feature] == value]
            subset_y = [y[i] for i in range(len(y)) if X[i][best_feature] == value]
            subtree = self._build_tree(subset_x, subset_y)
            tree[best_feature][value] = subtree
        return tree

Dalam kod di atas, kaedah muat digunakan untuk melatih pepohon keputusan, dan kaedah ramalan digunakan untuk meramalkan kategori kejadian baharu. Kaedah _entropy mengira entropi, kaedah _information_gain mengira keuntungan maklumat, kaedah _majority_vote digunakan untuk membuat keputusan pengundian dalam nod daun, dan kaedah _build_tree secara rekursif menjana subpokok. Pokok keputusan akhir yang dibina disimpan dalam diri.pokok.

Perlu diingatkan bahawa pelaksanaan kod di atas tidak termasuk teknik pengoptimuman seperti pemangkasan. Dalam aplikasi praktikal, untuk mengelakkan overfitting, biasanya perlu menggunakan teknik seperti pemangkasan untuk mengoptimumkan proses penjanaan pokok keputusan.

Secara keseluruhan, algoritma ID3 ialah algoritma penjanaan pepohon keputusan yang mudah dan berkesan, yang memilih ciri terbaik dengan mengira keuntungan maklumat bagi setiap ciri dan menjana pepohon keputusan secara rekursif. Ia berfungsi dengan baik apabila berurusan dengan set data kecil dan set data dengan ciri diskret, dan mudah difahami dan dilaksanakan. Walau bagaimanapun, ia tidak dapat mengendalikan ciri berterusan dan nilai yang hilang, dan mudah diganggu oleh data yang bising. Oleh itu, dalam aplikasi praktikal, adalah perlu untuk memilih algoritma yang sesuai dan teknik pengoptimuman berdasarkan ciri-ciri set data.

Atas ialah kandungan terperinci Proses penjanaan pepohon keputusan adalah berkaitan dengan algoritma id3. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!