Krishnamurthy Viswanathan, 12:39am 7 December 2010
나이브 베이즈 분류기는 내가 대학원생으로서 얄팍한 경험을 하는 동안 주위에서 본 가장 범용성이 높은 기계 학습 알고리즘 중 하나이다. 그리고 재미삼아 구현을 해 보고 싶었다. 핵심은 구현이 계산의 형태로 축소되고, 테스트 부분을 포함한 전체 파이썬 모듈이 겨우 50여 라인의 코드로 끝났다는 것이다. 나는 실제로 성능을 평가해보지 않았기 때문에 모든 코멘트를 환영한다. 나는 파이썬 아마추어이고 분명 경험 많은 파이썬 해커라면 이 코드의 몇몇 어설픈 부분을 다듬을 수 있을 것이다.
TheNaive Bayes classifieris one of the most versatile machine learning algorithms that I have seen around during my meager experience as a graduate student, and I wanted to do a toy implementation for fun. At its core, the implementation is reduced to a form of counting, and the entire Python module, including a test harness took only 50 lines of code. I haven’t really evaluated the performance, so I welcome any comments. I am a Python amateur, and am sure that experienced Python hackers can trim a few rough edges off this code.
직관과 디자인
여기서 분류기 상관관계의 정의 a는 다음과 같다. (위키피디아 발췌):
이것은 각각의 가능한 클래스 라벨에 대하여, 각 특징의 조건부 확률을 모두 곱하라는 의미이다. 이 말은 즉 우리가 이 분류기를 구현하기 위해서는 이 개별적인 조건부 확률들을 각각의 라벨, 특징마다 구하고 그것들을 라벨 의 사전확률과 함께 전부 곱해야 한다는 것을 의미한다. 여기서 얻어진 가장 큰 값의 라벨이 분류기로부터 반환되는 라벨이다.
이 개별적인 조건부 확률들을 계산하기 위해서 최대우도추정법을 사용한다. 입력/훈련 벡터들의 카운트를 사용해서 매우 짧은 문장으로 이 확률들을 근사한다.
즉 훈련 데이터로부터 라벨 가 발생하는 전체 횟수와 특징 와 라벨 가 동시에 발생하는 횟수의 비율을 구한다.
Here is definition a of the classifier functionality (from wikipedia):
Now this means, that for each possible class label, multiply together the conditional probability of each feature, given the class label. This means, for us to implement the classifier, all we need to do, is compute these individual conditional probabilities for each label, for each feature, p(Fi | Cj), and multiply them together with the prior probability for that label p(Cj). The label for which we get the largest product, is the label returned by the classifier.
In order to compute these individual conditional probabilities, we use theMaximum Likelihood Estimationmethod. In a very short sentence, we approximate these probabilities using the counts from the input/training vectors.
Hence we have: p(Fi | Cj) = count( Fi ^ Cj) / count(Cj)
That is, we count from the training corpus, the ratio of the number of occurrences of the feature Fi and the label Cj together to the total number of occurrences of the label Cj.
제로 확률 문제
만약 어떤 특징 와 어떤 라벨 가 훈련 데이터집합 내에서 동시에 일어나지 않게 되면 어떨까? 이러한 일이 테스트 데이터 내에서 발생할 때마다
는 0이 될 것이고 따라서 전체 곱도 0이 될 것이다. 이는 최대우도추정과 관련된 문제이다. 이 문제가 특정 훈련 도중에 관찰되지 않았다고 해서 테스트 데이터 내에서 발생하지 않는다는 의미는 아니다. 이 문제를 해결하기 위해서 평활화(smoothing)라고 알려진 방법을 사용한다. 우리는"add one 평활화"이라고 하는 가장 간단한 평활화를 코드에 사용한다
. 근본적으로 관측되지 않는 사건의 확률은 1보다 커야 한다. 우리는 각각의 0 카운트에 1을 더함으로써 이를 만족시킨다. 그물 효과에서는 어떤 확률질량을 non-zero 카운트 관측에서부터 zero 카운트 관측까지에 재분배해야만 한다. 따라서 전체 확률질량을 1로 유지하기 위하여 발생가능한 관측들의 개수만큼 각 라벨의 전체 카운트를 증가시켜야만 한다.
예를 들어, 두 클래스 과 이 있을 때, 평활화 된 최대우도추정 확률들은 다음과 같이 쓸 수 있다.
What if we have never seen a particular feature Fa and a particular label Cb together in the training dataset? Whenever they occur in the test data, p(Fa | Cb) will be zero. Hence the overall product will also be zero. This is a problem with maximum likelihood estimates. Just because a particular observation was not made during training does not mean that it will never occur in the test data. In order to remedy this issue, we use what is known as smoothing. The simplest kind of smoothing that we use in this code, is called “add one smoothing”. Essentially, the probability for an unseen event should be greater than one. We achieve this by adding one to each zero count. The net effect should be that we redistribute some of the probability mass from the non-zero count observations to the zero-count observations. Hence, we also need to increase the total count for each label by the number of possible observations, in order to maintain the total probability mass at 1.
For example, if we have two classes C = 0 and C = 1, then after smoothing, the smoothed MLE probabilities can be written as:
p-smoothed(Fi | Cj) = [count(Fi ^ Cj) + 1]/[count(Cj) + N] where N is the total number of observations across all features in the training corpus.
코드
간단하게 하기 위해 우리는 Weka의 ARFF 파일 포맷을 입력으로 사용할 것이다. 카운트와 특징 벡터의 디테일을 저장하기 위하여 몇 개의 사전들과 리스트들로 구성된 'Model'이라는 하나의 클래스를 사용한다. 이 구현에서는 오직 이산 값의 특징들만을 다룬다.
For simplicity, we will use Weka’sARFFfile format as input. We have a single class called Model which has a few dictionaries and lists to store the counts and feature vector details. In this implementation, we only deal with discrete valued features.
from __future__ import division
import collections
import math
class Model:
def __init__(self, arffFile):
self.trainingFile = arffFile
self.features = {} #all feature names and their possible values (including the class label)
self.featureNameList = [] #this is to maintain the order of features as in the arff
self.featureCounts = collections.defaultdict(lambda: 1)
#contains tuples of the form (label, feature_name, feature_value)
self.featureVectors = [] #contains all the values and the label as the last entry
self.labelCounts = collections.defaultdict(lambda: 0) #these will be smoothed later
'features' 사전은 모든 발생가능한 특징들의 값을 저장한다. 'featureNameList'는 단순히 ARFF 파일에서 나타나는 같은 순서로 된 특징들의 이름들을 포함하는 리스트이다. 이는 특징들의 사전이 원래부터 순서를 갖지 않기 때문이며, 우리는 명시적으로 특징 순서를 유지할 필요가 있다. 'featureCounts'는 각 라벨 값과 특징 값이 동시에 발생한 실제 카운트를 포함한다. 이 사전의 키는 다음과 같은 형태의 튜플이다: (class_label, feature_name, feature_value). 따라서 'yes'라는 라벨의 특징 F1의 값이 1인 경우가 15번 관찰됬다면 사전 안에 다음과 같은 엔트리가 존재하는 것이다: {('yes', 'F1', '15)}. 이 사전 내의 카운트의 디폴트 값이 어떻게 '0'이 아닌 '1'이 됐는지에 주목하라. 이는 카운트가 평활화되었기 때문이다. 'featureVectors' 리스트는 사실 ARFF 파일의 모든 인풋 특징 벡터들을 포함한다. 이 벡터의 마지막 특징은 Weka ARFF 파일의 관례로써, 클래스 라벨 자기자신이다. 마지막으로 'labelCounts'는 클래스 라벨들 스스로의 카운트들, 즉 훈련하는 동안 라벨 가 몇 번 나왔는지를 저장한다.
또한 Model 클래스에는 다음과 같은 멤버 메서드가 있다.
The dictionary ‘features’ saves all possible values for a feature. ‘featureNameList‘ is simply a list that contains the names of the features in the same order that it appears in the ARFF file. This is because our features dictionary does not have any intrinsic order, and we need to maintain feature order explicitly. ‘featureCounts‘ contains the actual counts for co-occurrence of each feature value with each label value. The keys for this dictionary are tuples of the form (class_label, feature_name, feature_value). Hence, if we have observed the feature F1 with the value ‘x’ for the label ‘yes’, fifteen times, then we will have the entry {(‘yes’, ‘F1′, 15)} in the dictionary.Notehow the default values for counts in this dictionary is ’1′ instead of ’0′. This is because we are smoothing the counts. The ‘featureVectors‘ list actually contains all the input feature vectors from the ARFF file. The last feature in this vector is the class label itself, as is the convention with weka ARFF files. Finally, ‘labelCounts‘ stores the counts of the class labels themselves, i.e. now many times did we see the label Ci during training.
We also have the following member functions in the Model class:
def GetValues(self):
file = open(self.trainingFile, 'r')
for line in file:
if line[0] != '@': #start of actual data
self.featureVectors.append(line.strip().lower().split(','))
else: #feature definitions
if line.strip().lower().find('@data') == -1 and (not line.lower().startswith('@relation')):
self.featureNameList.append(line.strip().split()[1])
self.features[self.featureNameList[len(self.featureNameList) - 1]] =
line[line.find('{')+1: line.find('}')].strip().split(',')
file.close()
위의 메서드는 단순히 특징 이름(클래스 라벨들을 포함), 각각의 발생가능한 값들, 그리고 그 자신의 특징 벡터들을 읽는다. 그리고 위에 정의된 알맞은 데이터 구조를 채운다.
The above method simply reads the feature names (including class labels), their possible values, and the feature vectors themselves; and populate the appropriate data structures defined above.
def TrainClassifier(self):
for fv in self.featureVectors:
self.labelCounts[fv[len(fv)-1]] += 1 #udpate count of the label
for counter in range(0, len(fv)-1):
self.featureCounts[(fv[len(fv)-1], self.featureNameList[counter], fv[counter])] += 1
for label in self.labelCounts:
#increase label counts (smoothing). remember that the last feature is actually the label
for feature in self.featureNameList[:len(self.featureNameList)-1]:
self.labelCounts[label] += len(self.features[feature])
TrainClassifier 메서드는 단순히 각 특징 값과 클래스 라벨이 동시에 발생하는 횟수를 세고, 그것들을 3-튜플 형태로 저장한다. 이 카운트들은 add-one 평활화를 통해 자동적으로 평활화된다. 이 사전의 디폴트 카운트값은 '1'이다. 라벨들의 카운트들 또한 관찰의 총 횟수로 이 카운트들을 증가시킴으로써 조정된다.
The TrainClassifier method simply counts the number of co-occurrences of each feature value with each class label, and stores them in the form of 3-tuples. These counts are automatically smoothed by using add-one smoothing as the default value of count for this dictionary is ’1′. The counts of the labels is also adjusted by incrementing these counts by the total number of observations.
def Classify(self, featureVector): #featureVector is a simple list like the ones that we use to train
probabilityPerLabel = {} #store the final probability for each class label
for label in self.labelCounts:
logProb = 0
for featureValue in featureVector:
logProb += math.log(self.featureCounts[(label,
self.featureNameList[featureVector.index(featureValue)],
featureValue)]/self.labelCounts[label])
probabilityPerLabel[label] =
(self.labelCounts[label]/sum(self.labelCounts.values())) * math.exp(logProb)
print probabilityPerLabel
return max(probabilityPerLabel, key = lambda classLabel: probabilityPerLabel[classLabel])
마지막으로, 단일 특징 벡터(하나의 리스트)를 인수로 받아서 각 라벨마다 개별적인 (최대우도추정에 의해 평활화된) 조건부 확률들의 결과를 계산하는 Classify 메서드가 있다. 각 라벨들에 마지막으로 계산된 확률은 사전 'probabilitPerLabel'에 저장된다. 마지막줄에서 가장 높은 확률을 가진 probabilityPerLabel가 반환된다. Note that the multiplication is actually done as addition in the log domain as the numbers involved are extremely small. 또한, 이 클래스 라벨을 갖는 사전확률이 이 곱셈의 한 요소로 사용되었다.
다음은 테스트 메서드를 포함하는 전체 코드이다.
Finally, we have the Classify method, that accepts as argument, a single feature vector (as a list), and computes the product of individual conditional probabilities (smoothed MLE) for each label. The final computed probabilities for each label are stored in the ‘probabilityPerLabel‘ dictionary. In the last line, we return the entry fromprobabilityPerLabelwhich has the highest probability. Note that the multiplication is actually done as addition in the log domain as the numbers involved are extremely small. Also, one of the factors used in this multiplication, is the prior probability of having this class label.
Here is the complete code, including a test method:
#Author: Krishnamurthy Koduvayur Viswanathan
from __future__ import division
import collections
import math
class Model:
def __init__(self, arffFile):
self.trainingFile = arffFile
self.features = {} #all feature names and their possible values (including the class label)
self.featureNameList = [] #this is to maintain the order of features as in the arff
self.featureCounts = collections.defaultdict(lambda: 1)
#contains tuples of the form (label, feature_name, feature_value)
self.featureVectors = [] #contains all the values and the label as the last entry
self.labelCounts = collections.defaultdict(lambda: 0) #these will be smoothed later
def TrainClassifier(self):
for fv in self.featureVectors:
self.labelCounts[fv[len(fv)-1]] += 1 #udpate count of the label
for counter in range(0, len(fv)-1):
self.featureCounts[(fv[len(fv)-1], self.featureNameList[counter], fv[counter])] += 1
for label in self.labelCounts:
#increase label counts (smoothing). remember that the last feature is actually the label
for feature in self.featureNameList[:len(self.featureNameList)-1]:
self.labelCounts[label] += len(self.features[feature])
def Classify(self, featureVector): #featureVector is a simple list like the ones that we use to train
probabilityPerLabel = {}
for label in self.labelCounts:
logProb = 0
for featureValue in featureVector:
logProb += math.log(self.featureCounts[(label,
self.featureNameList[featureVector.index(featureValue)],
featureValue)]/self.labelCounts[label])
probabilityPerLabel[label] =
(self.labelCounts[label]/sum(self.labelCounts.values())) * math.exp(logProb)
print probabilityPerLabel
return max(probabilityPerLabel, key = lambda classLabel: probabilityPerLabel[classLabel])
def GetValues(self):
file = open(self.trainingFile, 'r')
for line in file:
if line[0] != '@': #start of actual data
self.featureVectors.append(line.strip().lower().split(','))
else: #feature definitions
if line.strip().lower().find('@data') == -1 and (not line.lower().startswith('@relation')):
self.featureNameList.append(line.strip().split()[1])
self.features[self.featureNameList[len(self.featureNameList) - 1]] =
line[line.find('{')+1: line.find('}')].strip().split(',')
file.close()
def TestClassifier(self, arffFile):
file = open(arffFile, 'r')
for line in file:
if line[0] != '@':
vector = line.strip().lower().split(',')
print "classifier: " + self.Classify(vector) + " given " + vector[len(vector) - 1]
if __name__ == "__main__":
model = Model("/home/tennis.arff")
model.GetValues()
model.TrainClassifier()
model.TestClassifier("/home/tennis.arff")
Update: 나는 GetValues() 함수의 끝에서 첫(번째) 줄에서 버그를 찾았다. 이 줄은 ARFF 파일에서 발생가능한 값을 가져오고 self.featureNameList에 저장한다. 이 메서드는 공백이 제대로 처리되지 않았다. 이 라인을 다음과 같이 고쳤다:
self.features[self.featureNameList[len(self.featureNameList) - 1]] = [featureName.strip() for featureName in line[line.find('{')+1: line.find('}')].strip().split(',')]
Update: I found a bug in the last but one(th) line of the GetValues() function. This line gets the possible attribute values from the arff file and stores them in self.featureNameList. This method did not deal with whitespaces correctly. Update this line to:
self.features[self.featureNameList[len(self.featureNameList) - 1]] = [featureName.strip() for featureName in line[line.find('{')+1: line.find('}')].strip().split(',')]
의 사전확률과 함께 전부 곱해야 한다는 것을 의미한다. 여기서 얻어진 가장 큰 값의 라벨이 분류기로부터 반환되는 라벨이다.
가 발생하는 전체 횟수와 특징 
와 라벨 
와 어떤 라벨 
가 훈련 데이터집합 내에서 동시에 일어나지 않게 되면 어떨까? 이러한 일이 테스트 데이터 내에서 발생할 때마다 
는 0이 될 것이고 따라서 전체 곱도 0이 될 것이다. 이는 최대우도추정과 관련된 문제이다. 이 문제가 특정 훈련 도중에 관찰되지 않았다고 해서 테스트 데이터 내에서 발생하지 않는다는 의미는 아니다. 이 문제를 해결하기 위해서 평활화(smoothing)라고 알려진 방법을 사용한다. 우리는"add one 평활화"이라고 하는 가장 간단한 평활화를 코드에 사용한다
과 
이 있을 때, 평활화 된 최대우도추정 확률들은 다음과 같이 쓸 수 있다.
가 몇 번 나왔는지를 저장한다.
tennis.arff
