본문에 나오는 '클래스(C)'는 분류할 부류를 뜻하므로 c의 종류는 '정치', '사회', '경제', 'IT/과학' 등이고
본문에 나오는 '특징변수(F)'는 분류할 대상을 뜻하므로 문서 내에 포함된 단어의 수가 n개라면 f의 범위는 f1~fn입니다.
* 본문에서 말하는 평활화 기법인 Add-1 smoothing은 Laplace Smoothing 입니다.
나이브 베이즈 분류기
나이브 베이즈 분류기(영어: Naive Bayes classifier)는 단순한 확률적 분류기이다.
개요
나이브 베이즈 분류기의 기반 확률 모델은 강한(간단한)독립가정을 적용한 베이즈 정리에 기반하고 있으며, 좀 더 정확하게 말하자면 「독립특징모델; independent feature model」라고 불러야 할 것이다.
확률모델의 성질로 인해 나이브 베이즈 분류기는 지도학습(supervised learning) 환경에서 효율적으로 훈련할 수 있다. 많은 실제 사례에서 나이브 베이즈 분류기의 파라미터를 추정하기 위해최대우도추정법(最尤法; maximum likelihood estimation)을 사용한다. 즉, 나이브 베이즈 분류기를 사용하기 위해서베이즈확률이나 그 외의 베이즈 기법을 사용할 필요는 없다.
구상[設計; design] 및가정이 매우 단순함에도 불구하고 나이브 베이즈 분류기는 복잡한 실제 상황에서 예상보다 훨씬 잘 작동한다. 최근, 베이즈 분류 문제의 주의깊은 분석을 통해 나이브 베이즈 분류기의 효율성에 이론적인 이유가 있다는 것이 밝혀졌다. 나이브 베이지안 분류기의 장점은 분류에 필수적인 파라미터(변수군의 평군과 분산)을 추정하는 데 필요한 훈련 데이터 양이 적다는 점이다. 변수군은 독립적이라고 가정됐기 때문에 각 클래스에 대한 변수의 분산만이 필요하며, 공분산행렬 전체는 불필요하다.
나이브 베이즈 확률 모델
추상적으로 분류기의 확률모델은 다음과 같은 종속 클래스 변수 에 대한 조건부 모델이다. 클래스는 몇가지 특징변수 부터 에 의존한다.
문제는 특징 수 이 큰 경우, 또는 특징이 취할 수 있는 값의 범위가 큰 경우에 확률표를 토대로 한 것과 같은 모델들은 현실적이지 않다는 점이다. 따라서 모델을 좀 더 다루기 쉽게 변형시킨다.
여기서 「나이브(단순)」한 조건부 독립성의 가정이 등장한다. 각 특징변수 이 조건부로 또 다른 특징변수 와 독립이다. 즉, 다음이 성립된다.
그러면 동시모델은 다음과 같이 나타낼 수 있다.
즉, 위에서 서술한 독립성의 가정에서 클래스 변수 의 조건분포는 다음과 같이 나타낸다.
여기서 는 에만 의존하는 계수이며, 특징변수들의 값을 이미 알고 있으면 상수가 된다.
이와 같은 모델은 이른바 「클래스 사전 확률」 과 독립확률분포 로 나뉘어 있기 때문에 다루기가 쉽다. 개의 클래스가 있고 모델을 개의 파라미터로 표현할 때 대응하는 나이브 베이즈 모델은 개의 파라미터를 가진다. 2항분류에서는 이며 은 예측에 사용되는 2값의 특징의 개수이다.
매개 변수 추정
모든 모델 파라미터(즉, 클래스 사전확률과 특징확률 분포)는 훈련된 집합에서 상대도수에 따라 추정할 수 있다. 이는 각각 확률 최대우도추정량이다. 이산적이 않은 특징의 경우 사전에 이산화(離散化; discretization)를 할 필요가 있다. 이산화에는 자율기법(즉흥적인 기법; unsupervised)과 교사기법(훈련 데이터에 근거한 기법; supervised)이 있다.
어떤클래스와 특징값의 조합이 훈련에서는 나타나지 않는 경우, 도수에 근거한 확률추정은 0이 된다. 이것을 곱셈에 이용하면 곱에 0이 된다는 문제가 생긴다. 이를 막기 위해 확률 값의 추정을 약간 수정하여 어떤 조합의 확률값도 0이 되지 않도록 하는 방법이 널리 쓰인다. (Pseudo count; 의사 수)
확률 모델의 분류기 구축
지금까지의 설명으로부터 독립특징모델, 즉 나이브 베이지안 확률 모델이 도출되었다. 나이브 베이즈 분류기는 그 모델에 결정규칙을 합친 것이다. 흔히 쓰이는 결정규칙은 가장 그럴듯한 가설을 채용하는 방법으로, 최대사후확률(MAP) 결정규칙이라고 한다. 이러한 분류기를 함수 classify라고 하면 다음과 같이 나타낼 수 있다.
* 이후의 내용은 번역하지 않았습니다.
* 원문에서 이어지는 목차는 '논의', '예: 문서 분류', 'Complement Naive Bayes', '각주', '참고문헌', '관련 항목', '외부 링크', '소프트웨어' 입니다.
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(',')]
単純ベイズ分類器 - Wikipedia.mht
의 사전확률과 함께 전부 곱해야 한다는 것을 의미한다. 여기서 얻어진 가장 큰 값의 라벨이 분류기로부터 반환되는 라벨이다.
가 발생하는 전체 횟수와 특징 
와 라벨 
와 어떤 라벨 
가 훈련 데이터집합 내에서 동시에 일어나지 않게 되면 어떨까? 이러한 일이 테스트 데이터 내에서 발생할 때마다 
는 0이 될 것이고 따라서 전체 곱도 0이 될 것이다. 이는 최대우도추정과 관련된 문제이다. 이 문제가 특정 훈련 도중에 관찰되지 않았다고 해서 테스트 데이터 내에서 발생하지 않는다는 의미는 아니다. 이 문제를 해결하기 위해서 평활화(smoothing)라고 알려진 방법을 사용한다. 우리는"add one 평활화"이라고 하는 가장 간단한 평활화를 코드에 사용한다
과 
이 있을 때, 평활화 된 최대우도추정 확률들은 다음과 같이 쓸 수 있다.
가 몇 번 나왔는지를 저장한다.
