ジニ不純度計算の高速化『集合知プログラミング』

プログラムの時間計算量とか空間計算量とかまともにやってこなかったせいで、ふわふわした知識しか持ち合わせていないのですが、
『集合知プログラミング』を読んでいたら、明らかに無駄な計算をしている部分を発見したので、修正してみました。

7.4.1 ジニ不純度(p.160~)

ジニ不純度とは、決定木を作る際の分岐条件の決定に使われる指標で、ある確率分布に基づいた変数をランダムに当てはめた場合の誤差率の期待値と定義されています。なんのこっちゃ分からないですね、はい。Google先生に聞いてください。

・元のプログラム(O(n^2))

def giniimpurity(rows):
  total=len(rows)
  counts=uniquecounts(rows)
  imp=0
  for k1 in counts:
    p1=float(counts[k1])/total
    for k2 in counts:
      if k1==k2: continue
      p2=float(counts[k2])/total
      imp+=p1*p2
  return imp

・修正後(O(n))

def giniimpurity(rows):
  total=len(rows)
  counts=uniquecounts(rows)
  imp=1
  for k1 in counts:
    p1=float(counts[k1])/total
    imp-=p1*p1
  return imp

当てはまらない確率を1つ1つ確率を足し合わせていくのか、1から当てはまる確率を引くのかという違いですが、計算量のオーダーが明らかに変わります。この本で紹介されている程度のデータ数だと違いはほとんどないですが、データ量が膨大になってくるとアルゴリズムは結構大事になると思うので、適当にしないでもらいたいですね。

英語版だと以下のリンクからデータがダウンロード出来るみたいです。
http://forum.myquant.cn/uploads/default/original/1X/2065c4d1964e26331996cfa23d12acd185e3d7b6.pdf

日本語版はこちら