C5プルーニングアルゴリズムとは？決定木の剪定手法を徹底解説

C5アルゴリズムの概要

C5は、オーストラリアの研究者J. Ross Quinlan（J・ロス・クインラン）氏が長年にわたり開発・改良を続けている決定木アルゴリズムの最新バージョンです。その前身にあたるID3は1986年に発表され、機械学習分野に大きな影響を与えました。その後継アルゴリズムは、現在でも多くの商用データマイニングサービスで採用されています。

CARTとの共通点とプルーニングの仕組み

C5が生成する決定木は、CART（分類回帰木）が生成するものと基本的に同じです。CARTと同様に、C5はまず過学習（オーバーフィッティング）した木を構築し、その後、剪定（プルーニング）を行うことで、より汎化性能の高い柔軟なモデルを作り上げます。

プルーニングの手法は複雑ですが、C5の大きな特徴は、候補となる部分木を選択する際に検証用データセット（バリデーションセット）を使用しない点にあります。

検証データを使わない理由

C5では、木の構築に使用したのと同じデータが、木をどのように剪定すべきかを判断するためにも使われます。これは、このアルゴリズムが学術界をルーツとしていることを反映しています。かつて大学の研究者たちは、訓練データとして使える質の高い実データを大量に入手することが困難でした。そのため、限られた貧弱なデータセットから最後の一滴まで活かそうと、多くの時間と労力を費やしてきました。これは、大量のデータを利用できるビジネスの世界のデータマイナーとは対照的な状況です。

誤り率の推定方法

C5は、各ノードにおける誤り率を求め、実際の誤り率はそれよりもかなり悪い（高い）ものと想定することで、木の剪定を行います。あるノードにN件のレコードが到達し、そのうちE件が誤って分類された場合、そのノードの誤り率はE/Nとなります。

統計的サンプリングとの類推

C5は、統計的サンプリングとの類推を用いて、リーフ（葉）ノードで起こりうる最悪の誤り率を推定します。この類推では、リーフにあるデータを、それぞれ2つの結果のいずれかをとる一連の試行の結果とみなします。

C5は、訓練データで観測された誤りの数をこの範囲の下限とみなし、範囲の上限を代入することで、リーフが未知のデータに対して示す予測誤り率を算出します。ノードが深くなるほど、推定される誤り率は大きくなります。そして、あるノードにおける誤り数の上限推定値が、その子ノードの誤り推定値より小さい場合、子ノードは剪定されます。

モデルの目的と手動プルーニング

モデルの主な目的は、これまで見たことのないデータに対して一貫性のある予測を行うことです。この目的を達成できないルールは、モデルから取り除くべきです。

一部のデータマイニングツールでは、ユーザーが決定木を手動で剪定できる機能を提供しています。これは便利な機能ですが、将来的には、自動的な統計ベースのプルーニングをオプションとしてサポートするデータマイニングソフトウェアが期待されます。そのようなソフトウェアには、「検証データセットの結果の分布が訓練データの分布と異なって見える」といった主観的な判断ではなく、より客観的な基準で分割を棄却できる仕組みが求められます。

まとめ

C5プルーニングアルゴリズムは、検証データに頼らず、構築に使用したデータ自体から統計的な推定に基づいて決定木を剪定する手法です。過学習を防ぎ、未知のデータに対して堅牢な予測を実現するために、誤り率の悲観的推定を活用している点が大きな特徴といえます。