생각대로 살지 않으면 사는대로 생각한다.

 Baye’s Classification Methods

n  Statistical classifiers(통계적 분류기) : 주어진 데이터가 특정 클래스에 속하는지를 확률을 구해서

   어떤 클래스에 속하는지 예측한다.

n  베이즈 이론에 기본을 두고 있다.

n  나이브 베이지안 분류기 같은 것은 특정 영역에서 의사결정 트리나(Decision Tree) 신경망 분류기(neural network classifier) 보다 성능이 좋다.

n  큰 데이터 베이스에서 높은 정확도 와 속도를 보여준다.

1.      Baye’s Theorem

①     X :  data tuple , n개의  Attribute들로 이루어 져있다.( evidence라고도 한다.)

②     H : Hypothesis(가정) , data tuple X 가 명세화된 클래스 C에 속한다는 가정

③     P(H|X) : X의 Attribute Description이 주어졌을 때, tuple X가 클래스 C 에 속할 확률

n  Posterior probability (사후확률) : X라는 조건에 H의 사후 확률이다. 즉 어떤 일이 발생한 후에 그것(X)이 H라는 클래스에 들어 있을 확률이다.

n  예를 들어서, 고객이 age와 income으로만으로 이루어졌고 각각 35살 4만불의 수입수입이라고 가정해보자, H는 우리의 고객이 컴퓨터를 산다는 가정이다. 그러면 P(H|X)는 이미 고객의 나이와 수입을 아는 X 에 대해서 우리의 컴퓨터를 살 확률이다.

n  다른 예, 유방암 진단을 받은 사람(X)이 정말로 유방암(H) 인지를 확인하는 데에서도 사용이 가능하다. 유방암이 아닌데도 유방암으로 진단이 나올 수가 있기도 하고(11프로정도나 된다), 진단할 때도 신뢰도가 75프로 정도 밖에 수준이 안된다.

④     P(H) : 고객의 정보에 무관하게 모든 X 에 대해서 컴퓨터를 살(H) 확률

n  Prior probability (사전확률) : 사전 확률은 해당 일이 발생하기 전에 예측하는 것을 의미한다.

⑤     P(X|H): H라는 조건에서의 X의 확률

n  사후확률

n  고객이 컴퓨터를 사는 것을 알 때, 35살 4만불수입의 고객 X의 확률이다.

⑥     P(X) : 고객 X가 35살 4만불 수입인 확률

n  Prior probability

⑦     Baye’s Theorem

n  여기서 P(H),P(X|H),P(X)는 주어진 데이터에서 추정한다.

n          

2.      베이즈 이론 예제

n  한 회사의 휴대폰이 불량일 확률은 0.1%, 불량 중에서 배터리 오작동을 일으킬 확률은 40%, 한 대리점에서 배터리 오작동이 10% 이때 이 대리점에서 배터리가 오작동 한 것 중에서 진짜 불량은?

Ø   (H) =0.001 , P(X|H)=0.4 , P(X)=0.1

Ø  P(H|X)=0.001 * 0.4 / 0.1 = 0.004

Ø  즉, 배터리 오작동 중에서 휴대폰 불량일 확률은 0.4%이다

n  40대 여성이 유방암에 걸릴 확률이 1.4% 이고 유방암환자가 진단으로 양성이 나올 확률이 75%이다. 유방암 환자가 아닌 사람이 유방암으로 진단될 확률은 11%일때 유방암 진단을 받은 사람이 진짜 유방암일 확률은?

Ø  P(H) =0.014 , P(X|H)=0.75, P(X)=0.11896

Ø  P(X)는 유방암에 걸렸는데 양성으로 나올확률(0.014*0.75)와 유방암에   걸리지 않았는데 양성으로 나 올 확률(0.986 * 0.11)을 더한 값이 된다.

Ø  P(H|X)= 0.75 * 0.014/ 0.11896 = 약 0.0882

Ø  즉, 유방암 진단을 받았더라도 실제로 유방암일 확률은 8프로이다

3.      Naive Bayesian Classification

①     D는 n-차원 속성 벡터로 이루어진 튜플(tuple)의 데이터 셋이다.

②     m 개의 클래스가 존재한다고 가정할 때, 분류기는 X 가 어느 클래스에 속하는지 예측하게 된다.

n          

n  따라서  왼쪽에 있는 것이 최대화 되는 것을 찾으면 된다.  이것은 maximum posteriori hypothesis 라고 한다.

n  베이즈 정리에 의해서 아래의 식으로 계산이 된다

n          

③     P(X)는 모든 클래스에서 동일한 값을 갖기 때문에 이 분모는 무시하고 분모가 최대가 되는 것을 찾으면 된다. 만약 P(H)(클래스 사전확률)가 알려지지 않았다면 모든 클래스 확률은 동일하다고 가정해서        가 최대화하면 된다.

④     주어진 속성들이 많다면          를 계산하는데 엄청난 비용이 소모가 된다. 이것을 줄이기 위해서 class-conditional independence(클래스 조건 독립)의 개념을 사용한다. 즉 속성간에는 서로 독립적이어서 영향을 주지 않는다고 가정한다

n  여러 개의 속성에 대한      는 아래와 같이 계산이 된다.

n         

n  즉 각각의 속성들이 클래스에 속하는 확률의 곱이다.

n  만약 속성이 범주형 타입(categorical) 이라면 해당 데이터 셋에 존재할 수 있는 확률을 구하면 된다.

n  만약 속성이 연속성 데이터 타입(continuous-value) 이라면 분산과 표준편차를 이용해야한다.

n        의 식으로 구할 수가 있는데, 각각 입력데이터, 현재 클래스에 속한 데이터들에 평균, 현재 클래스에 속한 데이터들의 표준편차 이다. (가우시안(정규) 밀도 함수)

n  이것은 실제로      이렇게 계산이 된다.

n  만약 X=(35살,4만불)이고 나이가 연속성이라고 가정할 때, 평균이 38이고 표준편차가 12라고 하면 해당 확률은 (38-12)~(38+12)에 속하는 것을 구하면 된다.

⑤        

를 만족하는 것을 구해주면 된다. 즉       가 최대가 되는 클래스가 최종적인 예측 클래스가 된다.

4.      나이브 베이즈 분류기 예제

①         

②     위의 D 에서 아래의 조건은 만족하는 X 가 어느 클래스에 속하는지를 구해보자

③         

④          에서 최대가 되는 것을 찾으면 된다.

⑤            는     

⑥        

⑦     따라서

⑧     마지막으로 위의 구한 값에 각각         를 곱하면

⑨        

⑩     즉, X는 컴퓨터를 사는 것으로 분류가 가능하다.

5.      Laplacian correction or Laplace estimator

n        를 계산할 때 각각 속성이 해당 클래스에 속하는 확률을 곱을 구하는 과정에서 하나라도 0이면 전체값이 0으로 되기 때문에 예측을 하는데에 문제가 발생을 한다.

n        

n  이문제를 해결하려면 Laplacian correction을 이용하면 된다. 즉, 우리가 다루는 데이터 셋은 상당히 크므로 그 데이터 셋에 몇 개의 데이터가 추가되도 결과에 크게 영향을 미치지 않으므로 확률이 0이 되지 않게 튜플을 주가해준다.

6.      Laplacian correction 예제

n  위의 예제에서 1000개의 튜플이 있고 income이 low인 사람은 0명, medium은 990명, high는 10명이 있다고 가정하자

n  Laplacian correction을 사용하지 않으면 9,0.990,0.010이 된다.

n  여기에서 Laplacian correction을 적용해서 각각에 하나씩 추가를 하면

n        

이 되며 0값이 없어지게 된다. 

참고문헌:Data Mining Concepts and Techniques, 3rd Edition, Jiawei Han & Micheline Kamber

저작권 문제가 발생시 삭제될 수 있습니다.

 Data Generalization by Attribute-Oriented Induction

1.      Concept description : 데이터 일반화의 한 형태이다.

l  Concept는 일반적으로 데이터 집합(예, 구매자의 숫자나 졸업생의 숫자)을 말하지만,

   Concept Description은 단순한 데이터의 배열이 아니라 data characterization and comparison(데이터 묘사 와 비교)에 대한 서술을 생성한다.

l  Characterization(묘사,정의) : 주어진 데이터 집합의 간결하고 간단명료한 요약을 제공한다.

l  Comparison(a.k.a Discrimination)(비교,차이): 두 개 이상의 데이터 집합에 대한 비교를 서술한다.

l  Concept Description에는 두 가지의 접근 방식이 있다. 하나는 Data Cube(or OLAP)과 Attribute-Oriented Induction이 있다.

l  이제까지 살펴본 OLAP은 Complex data types and aggregation 과 User Control versus automation 때문에 한계가 존재. 즉 복잡한 데이터 형태에 적용하기 힘들며, 사용자가 OLAP에서 잘 알아야 하기 때문에 힘든 점이 있다.

2.      Attributed-Oriented Induction for Data Characterization

①     Data Cube Approach가 제안되기 몇 년 전에 제안되었다.

②     쿼리기반(Query-Oriented), generalization-based, 온라인 데이터 분석기법이다.

③     일반적인 처리 방법

l  관계형 데이터베이스 쿼리를 이용해서 작업과 연관된 데이터를 수집(Initial working relation)

l  Attribute 제거와 Attribute 일반화를 통해서 일반화 한다.

l  일반화된 Tuple에서 동일한 것들을 병합하고 각각 그것들의 개수를 누적해서 집합(aggregation)을 만든다.

④     처리 상세

l  Data Focusing : AOI 전에 관계형 데이터베이스 쿼리를 이용해서 연관된 데이터를 먼저 추출해야 한다. 

                     이 추출된 데이터를 initial working relation이라고 말한다.

l  Attribute removal : Attribute의 distinct value가 많이 존재할 때, 일반화 오퍼레이터가 없거나(case1)(즉 개념계층이 존재하지 않을 때) 상위 레벨 개념이 다른 Attribute의 용어에서 나타난다면(case2) 삭제한다.

l  Attribute generalization : Attribute의 distinct value가 많이 존재하고 일반화 오퍼레이터가 있으면 일반화 시킨다.

⑤     Attribute removal과 Attribute generalization은 모두 distinct value가 큰 데이터 셋에서만 적용이 된다. 여기서 얼마나 큰지를 결정하는 것은 지극히 주관적인데 그것을 제어하는 2가지의 방법이 존재한다.

l  Attribute generalization threshold control

I.       모든 Attribute에 적용되는 하나의 일반화 한계를 설정하거나 각각의 Attribute에 하나의 한계를 설정하는 방법이 있다

II.      만약 유일한 값을 가지는 속성들이 한계점보다 개수가 많다면 앞으로의 속성들은 삭제가 되거나 일반화가 된다.

III.    보통 기본적으로 2 에서 8 의 범위로 설정이 되어 있는데 사용자에 따라서 줄이거나 늘릴 수 있다.

IV.    만약 일반화가 너무 높은 레벨까지 진행이 되었다고 느껴졌다면 한계점을 높임으로써 레벨을 조절(낮추다)할 수가 있다.

V.      즉, Attribute Value에 한계점을 설정한다.

l  Generalized relation threshold control

I.       일반화된 연관에 대한 한계치를 설정한다.

II.      만약 일반화된 연관의 tuple의 개수가 한계점보다 많으면 계속 진행이 되며, 그렇지 않을 경우(적으면) 앞으로의 일반화가 수행이 되지 않는다. 즉 한계점의 개수보다 작아질 때 까지 일반화를 수행한다.

III.    시스템에 보통 10~30으로 설정이 되어있다.

IV.    만약 일반화된 연관이 너무 작다면 한계점을 사용자가 높여서 조절이 가능하다.(drilling down), 반대는 rolling up 이 된다

V.      일반화된 Tuple에 대한 한계점을 설정한다.

⑥     일반화를 처리하면 동일한 Tuple이 생성되는데 이것들을 통합해서 Count Attribute를 생성해서 개수를 설정하고 하나만 남기고 나머지들을 삭제한다.

3.      Basic algorithm for attribute-oriented induction

n  Input

n  Output: P, a prime-generalized-relation

①     W←get_task_relevant_data(DMQuery,DB)

l  DB에서 작업관 연관된 데이터를 추출해서 W(Working Relation)에 넣는다.(Initial Releation)

②     Prepare_for_generalzation(W)

I.       W를 스캔해서 각각의 Attribute의 distinct value들을 수집한다.

II.      각각의 Attribute에 대해서 삭제할 것인지, 아니면 주어진 값 또는 기본 Attribute의 한계점에 기본으로 해서 일반화 시킬 것인지 판단한다.

③     P←generalization(W)

The Prime-generalization-relation P 는 2번의 결과로 생성된 일반화된 relation의 Tuple에서 동일한 것들은 삭제하고 하나만 남기고 개수를 계산해서 하나의 attribute를 생성한다.

이 과정은 아래의 두 가지 중에서 하나를 사용해서 더 효율적으로 만들 수 있다.

l  각각의 일반화된 tuple에 대해서, 정렬된 prime relation P에 바이너리 검색을 통해서 자료를 입력한다. 이때 이미 있으면 count와 다른 누적되는 값을 계산해주고 없으면 새로 넣어준다.(like hashtable)

l  대부분의 경우에 distinct value들이 개수가 적기 때문에 m-차원 배열로 생성한다. 각각의 배열은 count 와 다른 집합 값이 존재한다. 일반화된 tuple을 입력 시에 해당 배열의 집합 값을 증가시킨다.(like array)

4.      AOI Examples

①     name : 많은 distinct values가 존재하지만 일반화하는 연산자(generalization operator)가 존재하지 않기 때문에 삭제한다. Attribute Removal

②     gender : 2가지의 distinct value 만 존재하기 때문에 일반화도 필요가 없고 그대로 유지시킨다.

③     major : 개념계층이 이미 존재한다고 가정하고, 또한 attribute generalization threshold가 5로 설정이 되어있다고 가정했을 때 이 Attribute에는 20개가 넘는 distinct values가 존재하기 때문에 주어진 개념계층으로 일반화가 진행이 된다.

④     birth_place : 개념 계층이 존재할 때, country의  distinct values가 한계점보다 많으면 삭제되어야 한다. 왜냐하면, 일반화 연산자(country)는 있지만 한계점보다 더 작아질 수 없기 때문이다. 즉 이미 유일한 country의 개수가 한계점보다 높기 때문에 더 상위 개념이 없기 때문에 삭제된다. 만약 한계보다 작다면 birth_country로 일반화 된다.

⑤     birth_date : 개념계층이 존재하고 distinct value가 한계보다 작다면 일반화 된다.

⑥     residence : 특성이 number, street, residence city, residence province or state, and residence country 로 구성되어 있다면 너무나 많은 disctinct value가 존재하기 때문에 삭제되어야 한다. Residence_city로 일반화 시키기 위해서 number와 street를 삭제한다.

⑦     phone#: name과 같으므로 삭제한다.

⑧     gpa: 개념계층이 {3.75–4.0, 3.5–3.75, . } 형식의 구간으로 존재한다고 가정하면 {“excellent”, “very good”, .} 형식의 서술형 값으로 교체해서 일반화 시킨다.

⑨     마지막으로 일반화된 tuple이 동일한 것은 count로 개수를 추가해주고 하나만 남겨준다.

5.      Attributed-Oriented Induction for Class Comparison

n  이전까지는 하나의 class에대해서만 Data Generalization을 했는데 두개 이상의 class를 비교하는 것을 Class Comparison(a.k.a. discrimination)이라고 한다. 주의할 점은 비슷한 dimension 과 attributes를 가지고 있어야 한다. 완전히 다른 것은 비교를 할 수가 없다는 것을 주의해야 한다.

n  수행방법은 아래와 같은 절차로 진행된다. (졸업생과 재학생의 일반적인 특성을 비교한다고 가정하면..)

①     Data Collection

l  Query Processing을 이용해서 연관성 있는 데이터를 수집한다.

l  DMQL은 Relational Database에 맞는 SQL 구문으로 변환이 된다.

l  연관데이터는 target class와 하나 또는 여러 개 집합의 contrasting class로 각각 나뉜다.

②     Dimension relevance analysis

l  많은 차원(dimensions,colums)들이 존재하면 아주 높은 연관성 있는 데이터를 위해서 Correlation 또는 Entropy-based measures 로 연관성 높은 것만 선택을 해준다.

l  name,gender, birth place, residence, and phone# 같이 연관성 적은 것들 것은 삭제가 된다.

③     Synchronous generalization

l  먼저 target class에 대해서 사용자 또는 전문가에 의해서 설정된 Threshold에 의해서 일반화를 한다.(Prime target class relation)

l  Constrasting class에 대해서는 prime target class relation과 같은 레벨로 일반화를 진행한다.

④     Presentation of the derived comparison

l  테이블,그래프,rules 등의 방법으로 visualization을 한다.

l  보통 presentation에는 비교하는 단위인 count%(percentage count)가 포함이 된다.

n  

참고문헌:Data Mining Concepts and Techniques, 3rd Edition, Jiawei Han & Micheline Kamber

저작권 문제가 발생시 삭제될 수 있습니다.

Data Transformation and Data Discretization

1.     데이터 선처리 기법으로 데이터 변환과 데이터 이산화 방법이 있다. 데이터를 변환하거나 통합함으로써 

      데이터 마이닝 프로세스를 더 효율적이고 패턴을 찾는데 더 쉽게 이해할 수 있게 한다. 

      그 방법으로는 6가지정도의 방법(methods)이 있다.

①     Smmoothing: 노이즈 데이터의 제거,방법으로는 Binning,regression,clustering 이 있다.

②     Atrribute/Feature construction : 새로운 Attribute의 추가(마이닝 프로세스를 위해서)

③     Aggregation(종합):데이터를 요약(summary)한다.

④     Normalization(정규화):Attributes를 특정 범위 안에 들어가게 처리한다. (ex. 0 to 1)

⑤     Discretization(이산화):숫자 데이터들은 단위명이나 개념적인 이름으로 대체한다.

     (ex. age attribute 를 0-10,11-20 의 라벨로 바꾸거나 youth , adult 등으로 변경한다.)

⑥     Concept hierarchy generation for nominal data(명목데이터의 개념 계층 생성) : 명목형 데이터들을 

     개념적으로 계층을 만든다 (e.g., street를 city 나 country의 상위 개념으로 변경한다.)

2.      Normalization

: 정규화는 3가지의 종류가 존재한다.

①     Min-Max normalization : 표본 데이터에서 최대값과 최소값을 확인 후에 이를 바탕으로 정의한 임의의 범위에 들게 처리한다. 돈처럼 단위가 큰 것을 [0,1]의 범위로 표준화를 해서 비교하기 쉽게 처리할 수 도 있다. 여기에서 주의점은 범위 밖의 새로운 데이터가 Input으로 들어왔을 때는 “out-of-bound” 가 발생한다.

②     Z-score normalization(zero-mean normalization) : 평균과 표준편차를 기반으로 정규화 한다. 

     이것은 실제의 최대값과 최소값을 모를 때 유용하게 사용된다.

-식의 변형(variation) : 표준편차를 사용하는 대신에 절대평균편차를 사용하면 아웃라이어에 대해서 좀더 강력하게 된다. 제곱근을 사용하는 대신에 차이에 절대값으로 계산되기 때문에 아웃라이어 들이 다소 줄어든다.

③     Normalization by decimal scaling: 소수점을 변경함으로 써 정규화 한다. 

     정규화된 값의 절대값은 1보다 작아야한다.

3.      이산화(Discretization)

Ø  이산화의 전략에는 2가지의 타입이 있다. 분류 정보(class information)을 사용 여부 와 진행 방향에 따라서

   분류가 된다.

①     분류 정보 사용 여부

n  Supervised : 이미 분류 정보가 있는 것을 기반으로 데이터를 분류한다.

n  Unsupervised : 분류 정보가 없어서 사용자의 정의에 따라서 분류한다.

②     진행 방향

n  Top-down(Splitting) : 하나 또는 몇 개의 지점에서 Split Point(분할점)을 찾아서 세분화 한다.

n  Bottom-up(Merging) :  모든 연속된 값들을 잠재적인 분할점이라고 생각하고 그것들에서 이웃하는 값들은 구간으로 묶어서 병합하면서 구간을 축소해나간다.

Ø  Methods

①     Binning : Top-down & unsupervised

n  파티션 분할 방법

A.     Equal-Width: 간격을 동일하게 한다. (Range)

B.      Equal-Depth: 개수가 동일하게 분할한다.(Frequency)

n  Smoothing 기법들

A.     Smoothing by bin mean:통의 평균값으로 모두 변경

B.      Smoothing by bin median:통의 중간값으로 모두 변경

C.      Smoothing by bin boundary:통의 범주에 가까운 값으로 변경

②     Histogram Analysis: Top-down & unsupervised

n  파티션 분할 방법은 Equal-width 와 equal-depth 로 한다.

n  막대형 그래프(bar chart)

③     Cluster : Top-down or Bottom-up & unsupervised

n  Numeric Attribute에 적용이 되며 가장 인기 있는 방법이다.

n  데이터 포인트에 대한 근접성 과 분포를 고려하기 때문에 양질의 이산화 결과를 얻을 수 있다.

n  몇 개의 시작 지점으로부터 구별점을 찾아서 하향식으로 세분화 할 수 도 있고, 전체에서 유사한 데이터들을 병합해 나가면서 상향식으로 결합 할 수 도 있다.

④     Decision Tree(의사결정트리) : Top-down & supervised

n  다른 Methods과 다르게 class information을 사용한다.

n  예를 들어서, 병원에서 병에 대한 환자들의 증상이 이미 분류가 되어있다. 따라서 의사는 환자의 증상들을 확인해가면서 어떤 병인지를 진단하는데 사용할 수 있다.

n  Entropy(불확실성) : 의사결정 트리에서 분할점이 되는 지점은 엔트로피가 가장적은 지점이 된다. 즉, 다른것과의 구분이 모호하지 않고(모호하면 엔트로피가 높음) 낮아야 진단을 할 수 있다.

⑤     Correlation Analyses : Bottom-up & unsupervised

n  인접한 구간을 합쳐서 큰 구간을 생성해서 미리 정의된 정지 조건까지 계속 합처나간다.

n  ChiMerge 기법이 있다.

4.      명목형 데이터에 대한 개념 계층 생성

①     Specification of a partial ordering of attributes explicitly at the schema level by users or experts

n  미리 스키마 단계에서 부분적으로 Attributes들의 순서를 설정한다.

②     Specification of a portion of a hierarchy by explicit data grouping

n  큰 데이터 베이스에서는 전체 값에 대한 개념계층을 생성할 수 가 없기 때문에, 중간 레벨의 작은 부분에 대한 명시적인 그룹을 명세화 한다. 예를 들어서, 국가(country)나 주(province)에 대해서 동부, 서부로 구분해서 동부에 해당하는 주를 포함하게 한다.

③     Specification of a set of attributes, but not of their partial ordering

n  사용자가 Attributes의 집합은 명세했지만 순서(ordering)을 설정하지 않았을 때 시스템에서 자동적으로 의미상의 개념 계층을 생성할 수 있다.

n  예를 들어서, street,city,province_or_state,country들의 Attribute들이 있을때 distinct한 value가 street가 가장 많게 되고 country가 가장 적게 된다. 따라서 이 개수에 기반해서 순서를 설정한다.

n  주의: 이런 체험적인 방법은 항상 정상적으로 동작하는 것은 아니다. 만약 time dimension에 20개의 year와 12개의 month와 7개의 day of week가 있을때는 올바른 계층이 생성이 되지 않는다.

④     Specification of only a partial set of attributes

n  사용자가 아주 작은 부분만 정의 했을 경우를 대비해서, DB 스키마 단계에서 시스템 관리자가 미리 연관된 의미상으로 밀접한 Attributes를 함께 고정시켜놓는다. 그래서 하나의 Attribute를 가지고 명세하려고 하면 자동적으로 연관된(semantically tightly linked) Attributes이 추가 된다.

    그러나 필요하면 사용자가 이 기능을 Override할 수 가 있다.

참고문헌:Data Mining Concepts and Techniques, 3rd Edition, Jiawei Han & Micheline Kamber

저작권 문제가 발생시 삭제될 수 있습니다.