2014년 4월 16일 수요일

프로세스 관점의 데이터마이닝, 수행단계

프로세스 관점의 데이터 마이닝


데이터마이닝의 수행단계
1. 데이터마이닝 프로젝트의 목적 확인
2. 분석에서 사용될 데이터 획득 : 대량의 데이터베이스에서 무작위로 표본 추출, 데이터베이스에서 데이터를 합치기 등
3. 데이터를 탐색, 정제, 전처리 : 데이터의 범위, 그래프 통한 확인, 데이터의 일관성 확인
4. 데이터 축소, supervised 의 경우 데이터를 학습용(training) 데이터, 평가용(test) 데이터, 검증용(validation) 데이터으로 분할 : 불필요 변수 제거, 변수를 변환, 새로운 변수 생성
5. 데이터마이닝 분석유형 선택 : 분류, 예측, 군집 중 어떤 것으로 할 것인가 결정
6. 데이터마이닝 기법 선택 : 회귀분석, 신경망모델, 계층적 군집분석 중 어떤 기법을 쓸 것인지 결정
7. 알고리즘 적용, 데이터마이닝 작업 수행 : 알고리즘 내 변수, 세부 선택 조건 등 다양한 변인들을 적용. 평가용 데이터를 이용하여 피드백
8. 알고리즘 결과 해석 : 검증용 데이터를 이용 최종 선택한 알고리즘을 평가
9. 모형 활용 : 모형을 운영시스템과 통합, 실제 레코드들을 적용하여 운영

("비즈니스 인텔리전스를 위한 데이터 마이닝"에서)

데이터 유형에 따른 데이터마이닝 기법의 분류

데이터 유형에 따른 데이터마이닝 기법의 분류

연속형 반응변수(Continuous Response Variable) 범주형 반응변수(Categorical Response Variable) 반응변수가 없는 경우(unsupervised)
연속형 예측변수(Continuous Predictor) 선형 회귀분석(Linear regression)
신경망 모형(Neural Network Model,NN)
k-최근접이웃기법(k-nearest neighbor,K-NN)
로지스틱 회귀분석(Logistic regression)
판별분석(discriminant analysis)
k-최근접이웃기법(k-nearest neighbor,K-NN)
주성분 분석(Principal Component Analysis,PCA)
군집분석(Cluster Analysis)
범주형 예측변수(Categorical Predictor) 선형 회귀분석(Linear regression)
신경망 모형(Neural Network Model,NN)
회귀나무(Regression Tree)
신경망모형(Neural Network Model,NN)
분류나무(classification tree)
로지스틱 회귀분석(Logistic regression)
단순 베이즈 분류모형(Naive Bayesian Classification)
연관성규칙(Association rules)


("비즈니스 인텔리전스를 위한 데이터 마이닝"에서)

데이터 마이닝 기법이 다양한 이유, 기법 선택시 고려사항

데이터 마이닝에 사용되는 예측 및 분류를 위한 다양한 방법이 존재.
각 기법이 나름대로 장단점을 가지기 때문.
어느 한 기법의 유용성 즉 기법 선택시 고려사항은 다음 것들이 있다.

  • 데이터 집합의 크기
  • 데이터에 존재하는 패턴의 유형
  • 해당 기법이 요구하는 가정을 데이터가 만족시키는지 여부
  • 데이터 잡음의 정도
  • 특수한 분석 목적 등
일반적으로 통용되는 방식은 여러가지 다양한 데이터마이닝 기법들을 적용해보고, 그 목적중에 가장 유용한 기법을 선택하는 것.

("비즈니스 인텔리전스를 위한 데이터 마이닝"에서)

2014년 4월 15일 화요일

Machine Learning : 모델 선택 방법. 3. Bayesian statistics and regularization

이 글에서는 overfitting 에 대응하는 또하나의 툴에 대해 다룬다.
maximum likelihood (ML)을 이용하여 parameter fitting 하는 방법이 있다. 그리고 parameter는 다음에 따라 선택한다.
여기서 theta 는 constant-valued but unknown 으로 frequentist statistics내에서 취해진다. 이 파라메터를 유추하기 위해 maximum likelihood와 같은 통계적 절차(statistics procedure)를 따르는 것이 우리의 할 일이다.
parameter 유추 문제에 접근하는 또다른 방법은, Bayesian view를 갖는 것이다. 그리고 theta를 random variable로 생각하는 것이다. 이 방법에서, 파라메터에 대한 "prior beliefs" (미리 이럴 것이다라고 유추하는 것)을 적용하여, 확률분포 prior distribution p(theta)를 사용한다. training set S

가 주어지고, x의 새로운 값을 예측하려고 하면, 다음과 같은 posterior distribution 를 계산할 수 있다.

       (1)

위 식에서, p(y^(i),x^(i),theta) 는 사용하는 러닝 모델로 부터 나온다. 예를 들어, Bayesian logistic regression을 사용한다면, p(y^(i),x^(i),theta) 는 다음과 같이 될 것이다.


여기서 새로운 테스트 예제 x가 주어지고, 그것을 예측하여야 한다면, theta에 대한 posterior distribution을 사용하여 class label에 대한 posterior distribution를 다음과 같이 계산할 수 있다.
     (2)
위 식에서 p(theta|S) 는 수식(1) 로부터 얻는다. 따라서 x가 주어질때 y 값을 예측하는 경우, 다음과 같은 결과를 얻을 수 있다.
이러한 과정을, "fully Bayesian" prediction 을 수행하는 것으로 생각할 수 있다.  그것은 theta에 대한 posterior p(theta|S) 를 반영하는 평균치를 취하여 계산하는 것을 말한다. 그런데, 일반적으로, 이 posterior distribution 을 계산하는 것은 계산상으로 무척 어렵다. 왜냐하면, 수식(1)의 theta는 보통 매우 높은 차원이고 이것에 대해 적분(integral)을 해야 하기 때문이다. 게다가 이것은 보통 closed-form으로 되지 않을 수 있다.
그래서, 실제적으로는, theta에 대한 posterior distribution을 approximate 한다. 하나의 예로, 수식(2)와 같은 posterior distribution를 single point estimate 로 대치하는 것이다. MAP (maximum a posterior) estimate는 다음과 같다.
   (3)
이것은 theta에 대한 ML(maximum likelihood) estimate를 위한 공식과 같다. 단지 끝에 prior p(theta) 가 있는 것을 제외하고 말이다.
실제적인 응용에서, prior p(theta) 에 대한 일반적인 선택은, 다음을 가정하는 것이다.
이러한 prior 선택을 사용하여, fitted parameters theta_MAP 은 maximum likelihood에 의해 선택된 것보다 더 작은 norm 을 갖는다. 실제로, Bayesian MAP estimate 가 ML estimate보다 overfitting에 대해 덜 취약(susceptible)하게 된다. 예를 들어, Bayesian logistic regression 은, n>>m 인 경우에도 text classification에 효과적인 알고리즘으로 밝혀졌다.

(참조 Andrew Ng 강의노트)


2014년 4월 14일 월요일

Machine Learning : 모델 선택 방법. 2. Feature Selection

모델 선택에 있어 특별하고도 중요한 경우가 feature selection이다. feature의 수가 매우 큰 n 개 즉  n>>m (m=모델의 총개수) 라고 하자. 그런데 그 많은 feature 중에 몇개 만이 learning에 relevant (관련된) 것이라고 추측할 수 있을 것이다. 만약 n 개의 입력 feature들에 대해 (perceptron 같은, 입력에 가중치를 곱해 합한 값이 threshold를 넘으면 활성화되고 아니면 비활성화되는) simple linear classifier 를 사용한다고 가정하면, VC dimension (Vapnik-Chervonenkis dimension, 통계적 분류 알고리즘의 capacity를 측정하는 것으로, "어떤 알고리즘이 shatter할 수 (나눌수) 있는 포인트의 가장 큰 집합의 요소의 수"로서 정의됨) 은 O(n) 이 될 것이고, 이러한 overfitting은 잠재적인 문제를 갖게 될 것이다.
어떤 세팅에서, feature selection 알고리즘을 적용하여 feature의 수를 줄일 수 있다. n 개의 feature가 주어졌을 때, 2^n 개의 가능한 feature subset 이 있을 것이다. 그러면 feature selection은, 2^n 가능 모델들에 대한 model selection 문제로 바뀔수 있다. 큰수의 n에 대해, 모든 2^n 개의 모델을 비교하는 것은 무리가 있다(expensive하다). 그래서, 좋은 feature subset 을 찾는데, 휴리스틱 검색 과정 (heuristic search procedure)를 사용할 수 있다.
다음 과정을 "forward search" 라고 한다.

forward search:
1. feature index subset F를 공집합으로 초기화
2. 반복 {
  (a) i=1, ... , n , 이미 F에 포함된 feature 를 제외하면서 하나씩 넣어서 F_i 라는 subset 만들고, 이 집합의 feature 들을 이용해, 학습, 평가를 수행한다.
  (b) 위 과정에서 가장 좋은 결과를 갖는 F_i 를 선택, F라고 한다.
}
3. 전체 검색 과정을 반복하여 최선의 subset을 찾아낸다.

이 말은 결국, 1단계에서 가장 좋은 feature 1개를 뽑고, 2단계에서는 전단계에서 뽑은 feature에 1개를 더 추가해서 가장 좋은 feature set을 뽑는 과정을 반복하며 feature set을 찾는 알고리즘이다.
예를 들어, feature 가 3개가 있다면,
F_1 = {1}, F_2 = {2} , F_3 = {3} 으로 subset들이 만들어지고, 각각을 적용하여 평가하여 가장 좋은 subset을 찾아낸다. 예를 들어 F_2 였다면, 이를 F 라고 한다.
그다음 루프에서는, F를 포함하여, F_1 = {1,2}, F_3 = {2,3} 식으로 전단계에서 선택한 feature set을 포함하여 나머지 feature를 하나씩 넣어가면서 subset을 만들고 평가를 수행한다. 이러한 과정을 통해 feature selection을 수행한다. 이 과정은 feature의 개수가 미리 지정된 threshold 개수가 되면 중단한다.
이 알고리즘은 wrapper model feature selection 중 하나가된다.

backforward search:
반대로 F={1,...,n} 로 놓고 하나씩 빼가는 과정을 반복하는 것을 backward search라고 한다.

Wrapper feature selection 알고리즘은 종종 잘 동작하기도 하지만, 계산량이 O(n^2) 로 많은 편이다.

Filter feature selection 은 휴리스틱하지만 좀 계산량이 적다. 이 방법의 아이디어는, 각 feature x_i가 클래스 레벨 y 에 얼마나 informative한지 (영향력이 있는지) 측정하는 simple score S(i) 를 계산하는 것이다. 그리고 가장 높은 점수 S(i)를 가진 feature  k개를 선택하는 방법이다.
S(i)의 예로는 x_i와 y 간의 correlation 을 이용하는 것이다. 실제로는 mutual information MI(x_i, y) 를 S(i)로 쓸 수 있다.
확률 p(x_i, y), p(x_i), p(y) 는 training set의 empirical distributions에 따라 평가될 수 있다.
이 score 의 의미는, mutual information은 Kullback-Leibler (KL) divergence로 표현될 수 있음에 주목하면 알 수 있다.

이는 확률분포 p(x_i,y) 와 p(x_i)p(y)가 얼마나 다른가를 나타낸다. 만약 x_i와 y가 서로 독립적인 random variable이라면, p(x_i, y) = p(x_i)p(y) 일 것이고, KL-divergence는 0이 된다. 이런 것을 x_i는 y에 대해 "non-informative하다."라고 한다. 반대의 경우 x_i 는 informative 하고, MI 값은 큰 값이 될 것이다.

그럼 최종적으로 선택할 feature의 개수 k는 어떻게 결정할 것인가? 표준적인 방법 중 하나는, 가능한 k 값에 대해, cross validation을 수행하는 것이다. 예를 들어, naive Bayes 를 text classification에 적용할때, 여기서 설명한 feature subset을 선택하는 방법을 사용하면, classifier accuracy를 향상시키기도 한다.



(참고: 스탠포드 Andrew Ng 강의노트)



2014년 4월 4일 금요일

Machine Learning : 모델 선택 방법. 1. Cross validation

ML를 적용할때 여러가지 알고리즘이 있는데 어떤 것을 선택할 것인가?
예를 들어, polynomial regression model을

로 한다면,  k 는 어떤 값으로 하는 것이 좋을 것인가? bias 와 variance 사이의 tradeoff 가 고려 되면서 말이다.
다른 예로써, locally weighted regression 을 위한 bandwidth parameter t (타오) 나 l_1 regularized SVM 을 위한 파라메터 C 를 자동으로 결정하기를 원한다고 생각해보자.

후보가 되는 모델 셋을 M = {M_1 , ... , M_d}  로 정의하자. 첫번째 예를 적용하면 M_i 는 i-order polynomial regression model 일 것이다.

Cross validation 방법

training set을 S 라고 하자.
* 단순 empirical risk minimization 알고리즘:
1. 모델 M_i 를 S로 학습시켜, hypothesis h_i 를 구한다.
2. training error를 최소로 하는 모델을 선택한다.
그런데 이 알고리즘은 좋지 않다. 왜냐하면, 이 방식을 통해서는 S에 가장 fit 하는 모델이 선택되기 때문에, 항상 high-variance, high-degree polynomial model 이 선정될것이고, 이는 종종 안좋은 선택이 된다.

* hold-out cross validation (simple cross validation) :
1. S를 랜덤하게 S_train 과 S_cv 로 나눈다. S_train은 약 70%로 구성하여, 모델 학습용으로 쓰고 나머지 S_cv 는 평가용으로 쓴다.
2. 각 모델 M_i 을 S_train 으로 학습시켜, hypothesis h_i 를 구한다.
3. S_cv(h_i) 를 적용하였을때 error (generation error)를 최소로 하는 모델을 선택한다.
옵션으로, 모델을 선택후 그 모델에 S_cv도 추가로 학습시킨다.
이 방식의 단점은 빼놓은 30%의 데이터를 학습 ~ 평가에 반영하지 않는 다는 것이다. 그리고 0.7 (70%) 가 보편적이긴 한데, 데이터에 따라 부적절할 수 있다.

* k-fold cross validation :
1. S를 k개의 부분집합으로 나눈다.
2. 각 모델 M_i 에 대해 j 번째 ( j = 1,...,k) 집합 S_j 를 제외시키고 학습시켜 h_ij 를 구하고, S_j를 적용하여 generation error 들을 구한다. 모델 M_i 의 에러는 각 j번째의 에러들의 평균으로 한다.
3. 가장 작은 에러를 갖는 모델을 선택한다. 그리고 전체 데이터 S로 학습시킨다.
이 방식의 문제점은, 전형적인 k값은 10이지만, 항상 적절하지는 않고, k값에 따라 계산량이 많아진다는 것이다.

* leave-one-out cross validation :
앞의 k를 매우 크게 하여 데이터 사이즈인 m과 같게 하는 방법이다. 결국 데이터 1개씩을 빼가면서 모든 테스트를 하는 방법이다.

이러한 cross validation 방법은 모델 선택하는 데도 사용할 수 있지만, 자기 알고리즘을 평가하는데에도 사용할 수 있다.


(참고: 스탠포드 Andrew Ng 강의노트)