* 이 문서는 일본어 위키백과의 単純ベイズ分類器」를 번역한 것으로써, 오류가 있을 수 있습니다.

 

* 번역한 원본 문서는 한국날짜로 2013년 7월 22일 수집되었습니다.

    単純ベイズ分類器 - Wikipedia.mht

 

*'単純ベイズ分類器(단순베이즈분류기)'는 '나이브 베이즈 분류기'로 번역하였습니다.

 

* 위키백과 연결링크는 페이지가 존재하는 경우 한국어 또는 영어 페이지로 연결했습니다.

 

* 이해를 쉽게 하도록 하기 위하여 '단어를 이용한 신문기사의 종류 분류'를 예로 들자면

 

  본문에 나오는 '클래스(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] 가정이 매우 단순함에도 불구하고 나이브 베이즈 분류기는 복잡한 실제 상황에서 예상보다 훨씬 잘 작동한다. 최근, 베이즈 분류 문제의 주의깊은 분석을 통해 나이브 베이즈 분류기의 효율성에 이론적인 이유가 있다는 것이 밝혀졌다. 나이브 베이지안 분류기의 장점은 분류에 필수적인 파라미터(변수군의 평군과 분산)을 추정하는 데 필요한 훈련 데이터 양이 적다는 점이다. 변수군은 독립적이라고 가정됐기 때문에 각 클래스에 대한 변수의 분산만이 필요하며, 공분산행렬 전체는 불필요하다.

 

 

나이브 베이즈 확률 모델


 

추상적으로 분류기의 확률모델은 다음과 같은 종속 클래스 변수 에 대한 조건부 모델이다. 클래스는 몇가지 특징변수 부터 에 의존한다.

 

   

 

문제는 특징 수 이 큰 경우, 또는 특징이 취할 수 있는 값의 범위가 큰 경우에 확률표를 토대로 한 것과 같은 모델들은 현실적이지 않다는 점이다. 따라서 모델을 좀 더 다루기 쉽게 변형시킨다.

 

베이즈 정리를 써서 다음과 같이 된다.

 

   

 

이 식은 영어로 나타내면 다음과 같다. (Posterior=사후, Prior=사전, Likelihood=공산, Evidence=결과)

 

   

 

실질적으로 분모는 에 의존하지 않는 일정한 를 가지므로 분자만을 고려하면 된다. 분자는 다음과 같이 표현되는 결합확률 모델과 같다.

 

   

 

여기에 조건부 확률의 정의를 반복해서 적용하면 다음과 같이 쓸 수 있다.

 

   

 

여기서 「나이브(단순)」한 조건부 독립성의 가정이 등장한다. 각 특징변수 이 조건부로 또 다른 특징변수 와 독립이다. 즉, 다음이 성립된다.

 

   

 

그러면 동시모델은 다음과 같이 나타낼 수 있다.

 

   

 

즉, 위에서 서술한 독립성의 가정에서 클래스 변수 의 조건분포는 다음과 같이 나타낸다.

 

   

 

여기서 에만 의존하는 계수이며, 특징변수들의 값을 이미 알고 있으면 상수가 된다.

 

이와 같은 모델은 이른바 「클래스 사전 확률」 과 독립확률분포 로 나뉘어 있기 때문에 다루기가 쉽다. 개의 클래스가 있고  모델을 개의 파라미터로 표현할 때 대응하는 나이브 베이즈 모델은 개의 파라미터를 가진다. 2항분류에서는 이며 은 예측에 사용되는 2값의 특징의 개수이다.

 

 

매개 변수 추정


 

모든 모델 파라미터(즉, 클래스 사전확률과 특징확률 분포)는 훈련된 집합에서 상대도수에 따라 추정할 수 있다. 이는 각각 확률 최대우도추정량이다. 이산적이 않은 특징의 경우 사전에 이산화(離散化; discretization)를 할 필요가 있다. 이산화에는 자율기법(즉흥적인 기법; unsupervised)과 교사기법(훈련 데이터에 근거한 기법; supervised)이 있다.

 

어떤 클래스와 특징값의 조합이 훈련에서는 나타나지 않는 경우, 도수에 근거한 확률추정은 0이 된다. 이것을 곱셈에 이용하면 곱에 0이 된다는 문제가 생긴다. 이를 막기 위해 확률 값의 추정을 약간 수정하여 어떤 조합의 확률값도 0이 되지 않도록 하는 방법이 널리 쓰인다. (Pseudo count; 의사 수)

 

 

확률 모델의 분류기 구축


 

지금까지의 설명으로부터 독립특징모델, 즉 나이브 베이지안 확률 모델이 도출되었다. 나이브 베이즈 분류기는 그 모델에 결정규칙을 합친 것이다. 흔히 쓰이는 결정규칙은 가장 그럴듯한 가설을 채용하는 방법으로, 최대사후확률(MAP) 결정규칙이라고 한다. 이러한 분류기를 함수 classify라고 하면 다음과 같이 나타낼 수 있다.

 

   

 


* 이후의 내용은 번역하지 않았습니다.

* 원문에서 이어지는 목차는 '논의', '예: 문서 분류', 'Complement Naive Bayes', '각주', '참고문헌', '관련 항목', '외부 링크', '소프트웨어' 입니다.

저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by Kugi

댓글을 달아 주세요




* 이 문서는 번역에 오류가 있을 수 있습니다. 원본주소는 다음과 같습니다:

http://ebiquity.umbc.edu/blogger/2010/12/07/naive-bayes-classifier-in-50-lines/

 

* 더 나은 번역 의견이 있으시면 댓글로 달아주시기 바랍니다.

 

 

 

나이브 베이즈 분류기 in 50 lines

Krishnamurthy Viswanathan, 12:39am 7 December 2010

 

나이브 베이즈 분류기는 내가 대학원생으로서 얄팍한 경험을 하는 동안 주위에서 본 가장 범용성이 높은 기계 학습 알고리즘 중 하나이다. 그리고 재미삼아 구현을 해 보고 싶었다. 핵심은 구현이 계산의 형태로 축소되고, 테스트 부분을 포함한 전체 파이썬 모듈이 겨우 50여 라인의 코드로 끝났다는 것이다.  나는 실제로 성능을 평가해보지 않았기 때문에 모든 코멘트를 환영한다. 나는 파이썬 아마추어이고 분명 경험 많은 파이썬 해커라면 이 코드의 몇몇 어설픈 부분을 다듬을 수 있을 것이다.

 

원문 보기 (Open)

 

직관과 디자인

여기서 분류기 상관관계의 정의 a는 다음과 같다. (위키피디아 발췌):

 

 

이것은 각각의 가능한 클래스 라벨에 대하여, 각 특징의 조건부 확률을 모두 곱하라는 의미이다. 이 말은 즉 우리가 이 분류기를 구현하기 위해서는 이 개별적인 조건부 확률들을 각각의 라벨, 특징마다 구하고 그것들을 라벨 의 사전확률과 함께 전부 곱해야 한다는 것을 의미한다. 여기서 얻어진 가장 큰 값의 라벨이 분류기로부터 반환되는 라벨이다.

 

이 개별적인 조건부 확률들을 계산하기 위해서 최대우도추정법을 사용한다. 입력/훈련 벡터들의 카운트를 사용해서 매우 짧은 문장으로 이 확률들을 근사한다.

 

즉 훈련 데이터로부터 라벨 가 발생하는 전체 횟수와 특징 와 라벨 가 동시에 발생하는 횟수의 비율을 구한다.

 

원문 보기 (Open)

 

제로 확률 문제

만약 어떤 특징 와 어떤 라벨 가 훈련 데이터집합 내에서 동시에 일어나지 않게 되면 어떨까? 이러한 일이 테스트 데이터 내에서 발생할 때마다

는 0이 될 것이고 따라서 전체 곱도 0이 될 것이다. 이는 최대우도추정과 관련된 문제이다. 이 문제가 특정 훈련 도중에 관찰되지 않았다고 해서 테스트 데이터 내에서 발생하지 않는다는 의미는 아니다. 이 문제를 해결하기 위해서 평활화(smoothing)라고 알려진 방법을 사용한다. 우리는"add one 평활화"이라고 하는 가장 간단한 평활화를 코드에 사용한다

 

. 근본적으로 관측되지 않는 사건의 확률은 1보다 커야 한다. 우리는 각각의 0 카운트에 1을 더함으로써 이를 만족시킨다. 그물 효과에서는 어떤 확률질량을 non-zero 카운트 관측에서부터 zero 카운트 관측까지에 재분배해야만 한다. 따라서 전체 확률질량을 1로 유지하기 위하여 발생가능한 관측들의 개수만큼 각 라벨의 전체 카운트를 증가시켜야만 한다.

 

예를 들어, 두 클래스 이 있을 때, 평활화 된 최대우도추정 확률들은 다음과 같이 쓸 수 있다.

 

 

원문 보기 (Open)

 

코드

간단하게 하기 위해 우리는 Weka의 ARFF 파일 포맷을 입력으로 사용할 것이다. 카운트와 특징 벡터의 디테일을 저장하기 위하여 몇 개의 사전들과 리스트들로 구성된 'Model'이라는 하나의 클래스를 사용한다. 이 구현에서는 오직 이산 값의 특징들만을 다룬다.

 

원문 보기 (Open)

 

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 클래스에는 다음과 같은 멤버 메서드가 있다.

 

원문 보기 (Open)

 

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()

 

위의 메서드는 단순히 특징 이름(클래스 라벨들을 포함), 각각의 발생가능한 값들, 그리고 그 자신의 특징 벡터들을 읽는다. 그리고 위에 정의된 알맞은 데이터 구조를 채운다.

 

원문 보기 (Open)

 

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'이다. 라벨들의 카운트들 또한 관찰의 총 횟수로 이 카운트들을 증가시킴으로써 조정된다.

 

원문 보기 (Open)

 

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. 또한,  이 클래스 라벨을 갖는 사전확률이 이 곱셈의 한 요소로 사용되었다.

 

다음은 테스트 메서드를 포함하는 전체 코드이다.

 

원문 보기 (Open)

 

#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")

 

샘플 ARFF 파일을 다운로드해서 이것을 테스트 해 보라. 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(',')]

 

원문 보기 (Open)

 

저작자 표시 비영리 동일 조건 변경 허락
신고

'기타번역 > 영어[English]' 카테고리의 다른 글

(번역) Naive Bayes classifier in 50 lines [Python]  (0) 2013.07.24
Posted by Kugi

댓글을 달아 주세요




좋은 곡이네요.

Debarge가(家)의 El Debarge가 부른 원곡을 리메이크한 것이라고 합니다.

 

 


이하 가사입니다. 영어 원문은 구글링해서 찾은 것이고 해석은 직접 하였습니다.

 

가사 보기

 

저작자 표시 비영리 동일 조건 변경 허락
신고
Posted by Kugi

댓글을 달아 주세요

  1. 2013.09.14 20:25  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다



티스토리 툴바