自然言語処理は専門外なんですが、職種的(?にこの分野に精通している人がたくさん社内にいるので僕も少し影響を受け始めています。。
今回は単純ベイズ分類器(Naive Bayes:ナイーブベイズ)による文書分類を基礎の部分だけやってみます。単純(Naive)と呼ばれているのは、文書の出現確率を単語の出現確率の”積”で近似し、語順や単語間の相関関係を考慮しないためにそう呼ばれています。ベイズ理論については書籍がたくさん出ているのでそちらを参考にしてください。ここで説明するにはとても大変なので(というより正しく説明できる自信がない)。この理論の実社会における適用分野としてはスパムフィルタなどが有名です。
ナイーブベイズは他の分類器と比べるとマシンリソースをあまり必要としないので、Flash(ActionScript)でもある程度の文書量までならPlayerがタイムアウトせずに学習/分類が可能です。ちなみにWeb上だとPythonでのサンプルが多く見つかりますが、確かにPythonなら実装が楽そうですね。
ここでは文書はBug-of-words(単語の集合)として扱い、良い文書(good)と悪い文書(bad)という2つのカテゴリーに分類します。また、良い文書が悪い文書に分類されるのを防ぐためにしきい値を設定しています。これは例えば、スパムメールがたまに受信フォルダに入り込むのは我慢できるけど、重要なメールがスパムメールと判定されるのは大変困ってしまいます。なので悪い文書に分類される確率が良い文書に分類される確率よりもしきい値以上高い場合にのみ悪い文書に分類し、しきい値以下の場合はunknownに分類するようにしています。
Naive Bayes Classifier – wonderfl build flash online
補足)
‘HTML5’ と ‘Flash’ という2つの単語を含む文書は悪い文書(bad)である確率が高いが、しきい値(悪い文書である確率が良い文書である確率の3.0倍)以下なため分類は保留。再度学習を重ねてから再試行すると、良い文書である確率が下がってしきい値を超えるため悪い文書に分類される。
* GitHub
naive_bayes at master from wellflat/aslib – GitHub
* 分類テスト
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
package { import flash.display.Sprite; import flash.text.TextField; import flash.text.TextFormat; import flash.utils.Dictionary; [SWF(width="465", height="465", backgroundColor="#000000")] public class Main extends Sprite { private var nb:NaiveBayes; private var tf:TextField; public function Main():void { p("*** Document Classification using Naive Bayes ***\n"); nb = new NaiveBayes(getFeatures); sampleTrain(nb); // train p("P(quick fox|good) = " + nb.getProb("quick fox", "good").toString()); p("P(quick fox|bad) = " + nb.getProb("quick fox", "bad").toString()); p("class 'quick fox': " + nb.classify("quick fox")); p(""); p("P(quick money|good) = " + nb.getProb("quick money", "good").toString()); p("P(quick money|bad) = " + nb.getProb("quick money", "bad").toString()); p("class 'quick money': " + nb.classify("quick money")); p(""); nb.setThreshold("bad", 3.0); // set classification threshold p("P(HTML5 Flash|good) = " + nb.getProb("HTML5 Flash", "good").toString()); p("P(HTML5 Flash|bad) = " + nb.getProb("HTML5 Flash", "bad").toString()); p("class 'HTML5 Flash': " + nb.classify("HTML5 Flash")); p(""); for(var i:int=0; i<10; i++) { // more training sampleTrain(nb); } p("P(HTML5 Flash|good) = " + nb.getProb("HTML5 Flash", "good").toString()); p("P(HTML5 Flash|bad) = " + nb.getProb("HTML5 Flash", "bad").toString()); p("class 'HTML5 Flash': " + nb.classify("HTML5 Flash")); } // sample training set below private function sampleTrain(classifier:Classifier):void { classifier.train("Hello how are you?", "good"); classifier.train("make quick money to live a good life", "bad"); classifier.train("the quick brown fox jumps", "good"); classifier.train("Dive into HTML5", "good"); classifier.train("HTML5 vs. Flash comparison", "bad"); } // make features(bug-of-words) from document private function getFeatures(document:String):Dictionary { var delimiter:RegExp = /\W+/; var words:Array = []; var features:Dictionary = new Dictionary(); for each(var s:String in document.split(delimiter)) { if(s.length > 2) { words.push(s.toLowerCase()); } } for each(var w:String in words) { features[w] = 1; } return features; } private function p(str:String):void { if(!tf) { tf = new TextField(); tf.x = 10; tf.y = 20; tf.width = tf.height = 465; tf.defaultTextFormat = new TextFormat('Courier New', 12, 0x00ff66, true); addChild(tf); } tf.appendText(str + "\n"); } } } |
* Naive Bayesクラス (ベースとしてClassfierクラスを作成)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
// Naive Bayes package { import flash.utils.Dictionary; public class NaiveBayes extends Classifier { private var thresholds:Dictionary; public function NaiveBayes(getFeatures:Function) { super(getFeatures); thresholds = new Dictionary(); } public function getThreshold(category:String):Number { for(var c:String in thresholds) { if(c == category) { return thresholds[category]; } } return 1.0; } public function setThreshold(category:String, threshold:Number):void { thresholds[category] = threshold; } // classify document into category public function classify(document:String):String { var probs:Dictionary = new Dictionary(); var max:Number = 0.0; var best:String = null; getCategories().forEach(function(c:String, index:int, arr:Array):void { probs[c] = getProb(document, c); if(probs[c] > max) { max = probs[c]; best = c; } }); for(var c:String in probs) { var second:Number = probs[c]*getThreshold(best); if(c === best) continue; if(second > probs[best]) return "unknown"; } return best; } // Bayes' theorem // P(category|document) = P(document|category)P(category)/P(document) // public function getProb(document:String, category:String):Number { // P(category) var categoryProb:Number = getCategoryCount(category)/getTotalCount(); // P(document|category) var documentProb:Number = getDocumentProb(document, category); return documentProb*categoryProb; // ignore P(document) } // P(document|category) private function getDocumentProb(document:String, category:String):Number { var features:Dictionary = getFeatures(document); var prob:Number = 1.0; for(var f:String in features) { prob *= getWeightedFeatureProb(f, category); } return prob; } } } // -------------------- // Base Classfier package { import flash.utils.Dictionary; public class Classifier { private var featureCount:Dictionary; private var categoryCount:Dictionary; protected var getFeatures:Function; public function Classifier(getFeatures:Function) { this.featureCount = new Dictionary(); this.categoryCount = new Dictionary(); this.getFeatures = getFeatures; } public function train(document:String, category:String):void { var features:Dictionary = getFeatures(document); for(var f:String in features) { incrFeatureCount(f, category); } incrCategoryCount(category); } protected function getCategoryCount(category:String):Number { if(categoryCount[category]) { return categoryCount[category]; } return 0.0; } protected function getFeatureCount(feature:String, category:String):Number { if(!featureCount[feature][category]) { return 0.0; } return Number(featureCount[feature][category]); } protected function getTotalCount():uint { var cnt:uint = 0; for each(var i:uint in categoryCount) { cnt += i; } return cnt; } protected function getCategories():Array { var categories:Array = []; for(var c:String in categoryCount) { categories.push(c); } return categories; } // P(feature|category) protected function getFeatureProb(feature:String, category:String):Number { if(getCategoryCount(category) == 0) { return 0.0; } return getFeatureCount(feature, category)/getCategoryCount(category); } protected function getWeightedFeatureProb(feature:String, category:String, weight:Number = 1.0, aprob:Number = 0.5):Number { var basicProb:Number = getFeatureProb(feature, category); var totals:Number = 0.0; getCategories().forEach(function(c:String, index:int, arr:Array):void { totals += getFeatureCount(feature, c); }); return ((weight*aprob) + (totals*basicProb))/(weight + totals); } private function incrFeatureCount(feature:String, category:String):void { if(!featureCount[feature]) { featureCount[feature] = new Dictionary(); } if(!featureCount[feature][category]) { featureCount[feature][category] = 0; } featureCount[feature][category]++; } private function incrCategoryCount(category:String):void { if(!categoryCount[category]) { categoryCount[category] = 0; } categoryCount[category]++; } } } |
ナイーブベイズ以外の分類器も後で追加しやすいようにクラスを分けて書いたのですが、AS3のDictionaryクラスが使いづらいので複雑になってしまいました。画像処理だと便利に使えるAS3ですが、描画系以外だとクラスライブラリやデータ構造が貧弱なのでやはり不利です。
このベイズ理論ですが、いきなりこれを勉強しても難しいと思うので、条件付き確率などの確率統計の基礎を固めてから勉強することを強くオススメします。僕は学部時代の教科書をひっぱりだして復習から始めましたがやっぱり難しいです。。この理論は確率的画像処理にも応用されているので、もう少し勉強してからチャレンジしてみたいと思います。
* 参考
入門ベイズ統計―意思決定の理論と発展
集合知プログラミング