C4.5——情報ゲイン率


情報利得率の計算方法について説明します.ID 3アルゴリズムを熟知した後、情報利得を計算する方法が分かった.計算式は以下の通り(Wikipediaから):または、より直感的に理解しやすい別の式で計算する.
訓練データセットDの属性セットAをクラスタグに従って区分する情報エントロピー:を得る.
属性セットAの各属性ごとに分割する、情報エントロピーのセット:を得る.
計算情報ゲイン次に、情報利得を計算する.すなわち、前者が後者を差分し、属性集合Aの情報利得のセットを得る.これにより、情報利得が計算される.
計算情報ゲイン率次に、情報利得率を計算する式を以下に示す(Wikipediaから).ここで、IGは情報利得を表し、前述の手順に従って計算される.IVは我々が現在計算する必要があるものであり、それは分裂情報を考慮するためのメトリックであり、分裂情報は属性分裂データの広さと均一性を測定するためのプログラムであり、計算式は以下のように示されている(Wikipediaから):簡略化して、以下の式を見てより直感的である:ここで、Vは属性集合Aの属性のすべての値を表す.
C 4について、典型的には複数回引用するトレーニングデータセットDを例に挙げて説明する.5アルゴリズムは、情報利得をどのように計算し、決定ノードを選択するか.
上のトレーニングセットには4つの属性があり、すなわち属性集合A={OUTLOOK,TEMPERATURE,HUMIDITY,WINDY}である.クラスラベルは2つあり,クラスラベル集合C={Yes,No}は,それぞれアウトドアに適していることとアウトドアに適していないことを示しているが,実は2つの分類問題である.データセットDは14個のトレーニングサンプルを含み、そのうちカテゴリ「Yes」に属するものは9個、カテゴリ「No」に属するものは5個であり、その情報エントロピーを計算する.1 Info(D) = -9/14 * log2(9/14) - 5/14 * log2(5/14) = 0.940
次に、プロパティセットの各プロパティについて、次のように情報エントロピーを計算します.1 Info(OUTLOOK) = 5/14 * [- 2/5 * log2(2/5) – 3/5 * log2(3/5)] + 4/14 * [ - 4/4 * log2(4/4) - 0/4 * log2(0/4)] + 5/14 * [ - 3/5 * log2(3/5) – 2/5 * log2(2/5)] = 0.694 2 Info(TEMPERATURE) = 4/14 * [- 2/4 * log2(2/4) – 2/4 * log2(2/4)] + 6/14 * [ - 4/6 * log2(4/6) - 2/6 * log2(2/6)] + 4/14 * [ - 3/4 * log2(3/4) – 1/4 * log2(1/4)] = 0.911 3 Info(HUMIDITY) = 7/14 * [- 3/7 * log2(3/7) – 4/7 * log2(4/7)] + 7/14 * [ - 6/7 * log2(6/7) - 1/7 * log2(1/7)] = 0.789 4 Info(WINDY) = 6/14 * [- 3/6 * log2(3/6) – 3/6 * log2(3/6)] + 8/14 * [ - 6/8 * log2(6/8) - 2/8 * log2(2/8)] = 0.892
上記のデータによれば、第1のルートノードを選択することに依存する情報利得値を計算することができ、以下のように計算することができる.1 Gain(OUTLOOK) = Info(D) - Info(OUTLOOK) = 0.940 - 0.694 = 0.246 2 Gain(TEMPERATURE) = Info(D) - Info(TEMPERATURE) = 0.940 - 0.911 = 0.029 3 Gain(HUMIDITY) = Info(D) - Info(HUMIDITY) = 0.940 - 0.789 = 0.151 4 Gain(WINDY) = Info(D) - Info(WINDY) = 0.940 - 0.892 = 0.048
次に,分裂情報メトリックH(V)を計算した.
OUTLOOK属性属性OUTPLOOKは3つの値をとり、そのうちSunnyは5つのサンプル、Rainyは5つのサンプル、Overcastは4つのサンプルがある場合1 H(OUTLOOK) = - 5/14 * log2(5/14) - 5/14 * log2(5/14) - 4/14 * log2(4/14) = 1.577406282852345
TEMPERATURE属性属性TEMPERATUREは3つの取値があり、そのうちHotは4つのサンプル、Mildは6つのサンプル、Coolは4つのサンプルがある場合1 H(TEMPERATURE) = - 4/14 * log2(4/14) - 6/14 * log2(6/14) - 4/14 * log2(4/14) = 1.5566567074628228
HUMIDITY属性属性HUMIDITYには2つの値があり、Normalには7つのサンプルがあり、Highには7つのサンプルがある場合1 H(HUMIDITY) = - 7/14 * log2(7/14) - 7/14 * log2(7/14) = 1.0
WINDY属性属性WINDYは2つの取値があり、そのうちTrueは6つのサンプル、Falseは8つのサンプルがあり、1 H(WINDY) = - 6/14 * log2(6/14) - 8/14 * log2(8/14) = 0.9852281360342516
上記の計算結果から、以下に示すように、情報利得率を計算することができます.1 IGR(OUTLOOK) = Info(OUTLOOK) / H(OUTLOOK) = 0.246/1.577406282852345 = 0.15595221261270145 2 IGR(TEMPERATURE) = Info(TEMPERATURE) / H(TEMPERATURE) = 0.029 / 1.5566567074628228 = 0.018629669509642094 3 IGR(HUMIDITY) = Info(HUMIDITY) / H(HUMIDITY) = 0.151/1.0 = 0.151 4 IGR(WINDY) = Info(WINDY) / H(WINDY) = 0.048/0.9852281360342516 = 0.048719680492692784
計算した情報利得率に基づいて,決定ツリーノードとして属性セットの属性を選択し,そのノードを分裂させる.
C4.5アルゴリズムの利点は,生成された分類規則が理解しやすく,精度が高いことである.C4.5アルゴリズムの欠点は、ツリーを構築する過程で、データセットを複数回順次スキャンし、ソートする必要があるため、アルゴリズムの非効率を招くことである.
リファレンスリンク
http://blog.sina.com.cn/s/blog_68ffc7a40100urn3.html
http://en.wikipedia.org/wiki/Information_gain_ratio
http://blog.sina.com.cn/s/blog_54c5622701016h4j.html
http://en.wikipedia.org/wiki/Information_gain_ratio
http://baike.baidu.com/view/8775136.htm
http://www.cnblogs.com/zhangchaoyang/articles/2842490.html
http://www.codecogs.com/latex/eqneditor.php
http://shiyanjun.cn/archives/428.html