CN2アルゴリズム

CN2誘導アルゴリズムは、ルール誘導のための学習アルゴリズムです。^[1]トレーニングデータが不完全な場合でも機能するように設計されています。これは、AQアルゴリズムとID3アルゴリズムのアイデアに基づいています。その結果、AQによって作成されたようなルールセットが作成されますが、ID3のようなノイズの多いデータも処理できます。

分類ルールのリストを生成するには、アルゴリズムに、すでに分類されている例のセット (TrainingSet) を与える必要があります。分類に使用するために、単独または組み合わせで任意の例のセットに適用できる条件のセット (SimpleConditionSet) が事前定義されています。

ルーチン CN2(トレーニングセット)
   ClassificationRuleListを空にする
   繰り返す
      BestConditionExpressionをFind_BestConditionExpression(TrainingSet)とする
      BestConditionExpressionがnilでない場合
         それから
            TrainingSubsetをBestConditionExpressionでカバーされる例とする
            TrainingSetからTrainingSubset内の例を削除します
            MostCommonClassをTrainingSubset内の最も一般的な例のクラスとする
            ClassificationRuleListにルールを追加する
               'if ' が BestConditionExpression ' の場合、クラスは ' MostCommonClass ' になります
   TrainingSetが空になるか、BestConditionExpressionがnilになるまで
ClassificationRuleListを返す

ルーチン Find_BestConditionExpression(TrainingSet)
   ConditionalExpressionSetを空にする
   BestConditionExpressionをnilにする
   繰り返す
      TrialConditionalExpressionSetを条件式の集合とする。
         {x と y。x は ConditionalExpressionSet に属し、y は SimpleConditionSet に属します}。
      TrialConditionalExpressionSet内のConditionalExpressionSetに含まれるすべての式を削除します（つまり、
          非特化のもの）または null（例：big = y および big = n）
      TrialConditionalExpressionSet内のすべての式Fについて
         もし
            Fは統計的に有意である
               そしてFはBestConditionExpressionよりも優れている
               TrainingSetでテストされたときにユーザー定義の基準によって
            それから
               BestConditionExpressionの現在の値をFに置き換える
      TrialConditionalExpressionSet内の式の数 > ユーザー定義の最大値
         TrialConditionalExpressionSetから最悪の式を削除する
      ConditionalExpressionSetをTrialConditionalExpressionSetとする
   ConditionalExpressionSetが空になるまで
BestConditionExpressionを返す

• CN2 アルゴリズムの説明