MLlibのNaiveBayesアルゴリズムのソースコードの学習
18312 ワード
package org.apache.spark.mllib.classification
import breeze.linalg.{DenseMatrix => BDM, DenseVector => BDV, argmax => brzArgmax, sum => brzSum}
import org.apache.spark.{SparkException, Logging}
import org.apache.spark.SparkContext._
import org.apache.spark.mllib.linalg.{DenseVector, SparseVector, Vector}
import org.apache.spark.mllib.regression.LabeledPoint
import org.apache.spark.rdd.RDD
/**
* Model for Naive Bayes Classifiers.
*
* @param labels list of labels
* @param pi log of class priors, whose dimension is C, number of labels
* @param theta log of class conditional probabilities, whose dimension is C-by-D,
* where D is number of features
*/
class NaiveBayesModel private[mllib] (
val labels: Array[Double],
val pi: Array[Double],
val theta: Array[Array[Double]]) extends ClassificationModel with Serializable {
private val brzPi = new BDV[Double](pi)
private val brzTheta = new BDM[Double](theta.length, theta(0).length)
{
// Need to put an extra pair of braces to prevent Scala treating `i` as a member.
var i = 0
while (i < theta.length) {
var j = 0
while (j < theta(i).length) {
brzTheta(i, j) = theta(i)(j)
j += 1
}
i += 1
}
}
override def predict(testData: RDD[Vector]): RDD[Double] = {
val bcModel = testData.context.broadcast(this)
testData.mapPartitions { iter =>
val model = bcModel.value
iter.map(model.predict)
}
}
override def predict(testData: Vector): Double = {
labels(brzArgmax(brzPi + brzTheta * testData.toBreeze))
}
}
/**
* Trains a Naive Bayes model given an RDD of `(label, features)` pairs.
*
* This is the Multinomial NB ([[http://tinyurl.com/lsdw6p]]) which can handle all kinds of
* discrete data. For example, by converting documents into TF-IDF vectors, it can be used for
* document classification. By making every vector a 0-1 vector, it can also be used as
* Bernoulli NB ([[http://tinyurl.com/p7c96j6]]). The input feature values must be nonnegative.
*/
class NaiveBayes private (private var lambda: Double) extends Serializable with Logging {
def this() = this(1.0)
/** Set the smoothing parameter. Default: 1.0. */
def setLambda(lambda: Double): NaiveBayes = {
this.lambda = lambda
this
}
/**
* Run the algorithm with the configured parameters on an input RDD of LabeledPoint entries.
*
* @param data RDD of [[org.apache.spark.mllib.regression.LabeledPoint]].
*/
def run(data: RDD[LabeledPoint]) = {
val requireNonnegativeValues: Vector => Unit = (v: Vector) => {
val values = v match {
case sv: SparseVector =>
sv.values
case dv: DenseVector =>
dv.values
}
if (!values.forall(_ >= 0.0)) {
throw new SparkException(s"Naive Bayes requires nonnegative feature values but found $v.")
}
}
// Aggregates term frequencies per label.
// TODO: Calling combineByKey and collect creates two stages, we can implement something
// TODO: similar to reduceByKeyLocally to save one stage.
val aggregated = data.map(p => (p.label, p.features)).combineByKey[(Long, BDV[Double])](
createCombiner = (v: Vector) => {
requireNonnegativeValues(v)
(1L, v.toBreeze.toDenseVector)
},
mergeValue = (c: (Long, BDV[Double]), v: Vector) => {
requireNonnegativeValues(v)
(c._1 + 1L, c._2 += v.toBreeze)
},
mergeCombiners = (c1: (Long, BDV[Double]), c2: (Long, BDV[Double])) =>
(c1._1 + c2._1, c1._2 += c2._2)
).collect()
val numLabels = aggregated.length
var numDocuments = 0L
aggregated.foreach { case (_, (n, _)) =>
numDocuments += n
}
val numFeatures = aggregated.head match { case (_, (_, v)) => v.size }
val labels = new Array[Double](numLabels)
val pi = new Array[Double](numLabels)
val theta = Array.fill(numLabels)(new Array[Double](numFeatures))
val piLogDenom = math.log(numDocuments + numLabels * lambda)
var i = 0
aggregated.foreach { case (label, (n, sumTermFreqs)) =>
labels(i) = label
val thetaLogDenom = math.log(brzSum(sumTermFreqs) + numFeatures * lambda)
pi(i) = math.log(n + lambda) - piLogDenom
var j = 0
while (j < numFeatures) {
theta(i)(j) = math.log(sumTermFreqs(j) + lambda) - thetaLogDenom
j += 1
}
i += 1
}
new NaiveBayesModel(labels, pi, theta)
}
}
/**
* Top-level methods for calling naive Bayes.
*/
object NaiveBayes {
/**
* Trains a Naive Bayes model given an RDD of `(label, features)` pairs.
*
* This is the Multinomial NB ([[http://tinyurl.com/lsdw6p]]) which can handle all kinds of
* discrete data. For example, by converting documents into TF-IDF vectors, it can be used for
* document classification. By making every vector a 0-1 vector, it can also be used as
* Bernoulli NB ([[http://tinyurl.com/p7c96j6]]).
*
* This version of the method uses a default smoothing parameter of 1.0.
*
* @param input RDD of `(label, array of features)` pairs. Every vector should be a frequency
* vector or a count vector.
*/
def train(input: RDD[LabeledPoint]): NaiveBayesModel = {
new NaiveBayes().run(input)
}
/**
* Trains a Naive Bayes model given an RDD of `(label, features)` pairs.
*
* This is the Multinomial NB ([[http://tinyurl.com/lsdw6p]]) which can handle all kinds of
* discrete data. For example, by converting documents into TF-IDF vectors, it can be used for
* document classification. By making every vector a 0-1 vector, it can also be used as
* Bernoulli NB ([[http://tinyurl.com/p7c96j6]]).
*
* @param input RDD of `(label, array of features)` pairs. Every vector should be a frequency
* vector or a count vector.
* @param lambda The smoothing parameter
*/
def train(input: RDD[LabeledPoint], lambda: Double): NaiveBayesModel = {
new NaiveBayes(lambda).run(input)
}
}package org.apache.spark.mllib.classification
import org.apache.spark.annotation.Experimental
import org.apache.spark.api.java.JavaRDD
import org.apache.spark.mllib.linalg.Vector
import org.apache.spark.rdd.RDD
/**
* :: Experimental ::
* Represents a classification model that predicts to which of a set of categories an example
* belongs. The categories are represented by double values: 0.0, 1.0, 2.0, etc.
*/
@Experimental
trait ClassificationModel extends Serializable {
/**
* Predict values for the given data set using the model trained.
*
* @param testData RDD representing data points to be predicted
* @return an RDD[Double] where each entry contains the corresponding prediction
*/
def predict(testData: RDD[Vector]): RDD[Double]
/**
* Predict values for a single data point using the model trained.
*
* @param testData array representing a single data point
* @return predicted category from the trained model
*/
def predict(testData: Vector): Double
/**
* Predict values for examples stored in a JavaRDD.
* @param testData JavaRDD representing data points to be predicted
* @return a JavaRDD[java.lang.Double] where each entry contains the corresponding prediction
*/
def predict(testData: JavaRDD[Vector]): JavaRDD[java.lang.Double] =
predict(testData.rdd).toJavaRDD().asInstanceOf[JavaRDD[java.lang.Double]]
}素朴贝兹分类阿尔戈里斯姆
分類アルゴリズムとは?簡単に言えば、ある特性を有する物体を既知のカテゴリセットのカテゴリに分類することである.数学的には、次のように定義できます.
既知のコレクション:C={y 1,y 2,.,yn}およびI={x 1,x 2,.,xm,.}マッピング規則y=f(x)を決定し、任意のxi∈Iがあり、yj∈Cが1つしかないようにyj=f(xi)を成立させる.
このうち,Cはカテゴリ集合,Iは分類対象物体,fは分類器であり,分類アルゴリズムの主な任務は分類器fを構築することである.
分類アルゴリズムの構造は、通常、訓練のために既知のカテゴリの集合を必要とし、通常、訓練された分類アルゴリズムが100%の精度を達成することは不可能である.分類器の品質は往々にして訓練データ、検証データ、訓練データサンプルサイズなどの要素と関連している.
例えば、私たちは日常生活の中で見知らぬ人を見て、最初のことはその性別を判断することであり、性別を判断する過程は分類の過程である.これまでの生活経験から、髪の毛の長さ、服装、体型の3つの要素を経て、一人の性別を判断することが多い.ここでの「生活経験」は、日常生活で出会う様々な人を訓練した性別判断に関するモデルである.突然ある日、一人の娘砲があなたの前に出て、長い髪がふわふわしていて、タイトなズボンを着ていましたが、体型がmanで、そこであなたは疑問に思っていました.これまでの経験によると、すでに訓練されたモデルで、この人の性別を判断することはできません.喉頭結節を通じて性別を判断することを学び、モデルの質が向上しました.しかし、性別を判断できない人が永遠に現れることは否めない.だからモデルは永遠に100%の正確さに達することができなくて、訓練データの絶えず増加することに従って無限に100%の正確さに近づくだけです.
ベイズの公式
ベイズの公式、あるいはベイズの定理と呼ばれ、ベイズの分類の基礎である.ベイズ分類は分類アルゴリズムの総称であり、このアルゴリズムの基礎はベイズ式である.現在研究されている4つのベイズ分類アルゴリズムには,Naive Bayes,TAN,BAN,GBNがある.
理工系の学生は大学で確率論を学んだはずだが、その中で最も重要ないくつかの公式には、P(A|B)とP(B|A)のような2つの条件確率の関係を記述するためのベイズ式がある.どのようにして既知のイベントAとBがそれぞれ発生する確率と,イベントBが発生する時のイベントAが発生する確率とで,イベントAが発生する時のイベントBが発生する確率を求めるかがベイズ式の役割である.次のように記述されています.
P(B|A)=P(A|B)×P(B)P(A)
素朴ベイズ分類
シンプルベイズ分類、Naive Bayes、NBアルゴリズムと呼ぶこともできます.その核心思想は非常に簡単である:ある予測項目に対して、それぞれその予測項目が各分類の確率であることを計算し、それから確率が最大の分類をその予測分類として選択する.まるであなたが女性である可能性が40%、男性である可能性が41%だと予測しているように、彼が男性だと判断することができます.
Naive Bayesの数学的定義は次のとおりです.
第4ステップの最大値をどのように取得するか、すなわち、第3ステップの各条件確率をどのように計算するかが最も重要である.以下の方法を使用できます.
Additive smoothing
Additive smoothingは、Laplacian smoothingまたはLidstone smoothingとも呼ばれます.
あるカテゴリの下にある特徴項目の区分が現れない場合、P(ai|yj)=0となり、最終的に乗算された結果が精度を大幅に低下させるため、Additive smoothingを導入してこの問題を解決する.このように0に等しい場合には、そのカウント値を1とすることで、トレーニングサンプルセットの数が十分に大きい場合、結果に影響を及ぼさず、上記周波数が0の気まずい局面を解決することができる.