User:Sungyup Kim/sandbox
데이터 축소를 위한 CNN[edit]
축소된 근접 이웃 (CNN, the Hart algorithm) 은 k-NN 분류를 위해 데이터셋을 축소하려는 목적으로 디자인 된 알고리즘이다.[1] 이 알고리즘은 학습 데이터로부터 프로토타입들의 집합 U 를 선택하고, 이를 통해 1NN이 모든 데이터셋을 분류하는 것만큼 정확하게 U와 1NN이 예시들을 분류할 수 있다.
학습 데이터 X가 주어졌을때, CNN은 반복하여 수행된다.
- X의 모든 요소들을 스캔하여, U로부터 가장 가까운 프로토타입을 가지는 x를 찾는다( U 는 x 와 다른 라벨을 가진다).
- X로부터 x를 삭제하고 그것을 U에 더한다.
- 프로토타입이 더 이상 U에 더해지지 않을 때까지 스캔을 반복한다.
분류하기 위해 X 대신에 U 를 사용한다. 프로토타입이 아닌 예시들은 "흡수된" 점이라고 불린다. 경계 비율을 줄이기 위해서는 학습 예시들을 스캔하는 것이 효율적이다. [2] 학습 예시 x의 경계 비율은 아래와 같다.
- a(x) = ||x'-y|| / ||x-y||
||x-y|| 는 x와 색이 다른 가장 가까운 예시인 y 까지의 거리를 나타내고, ||x'-y|| 는 y 로부터 가장 가까운 예시인 x' 까지의 거리를 나타낸다( x' 는 x 와 같은 라벨을 가진다).
경계 비율은 [0,1] 구간 내에 존재하는데 왜냐하면 ||x'-y|| 는 ||x-y|| 를 절대 초과하지 않기 때문이다. 이 배열(Ordering)은 프로토타입의 집합인 U 로의 포함을 위한 특권을 클래스들의 경계에 준다. x와 다른 라벨을 가지는 점은 x 외부에 있다고 불린다. 경계 비율의 계산은 오른쪽에 도식(illustration)으로 나타내어져 있다. 점 데이터들은 색으로 라벨이 붙여졌는데, 첫 점은 x 이고 라벨은 빨간색이다. 외부의 점들은 파란색, 초록색이다. x 의 외부 점들 중 가장 가까운 점은 x 이다. y 에 가장 가까운 빨간 점은 x' 이다. 경계 비율 a(x)=||x'-y||/||x-y|| 은 시작 점 x 의 특성(attribute)이다.
아래는 연속된 그림속의 CNN을 나타내는 도식이다. 3개의 클래스(빨강, 초록, 파랑)가 있다. 그림 1은 최초에, 각 클래스별로 60개의 점이 존재한다. 그림 2 는 1NN 분류 지도를 보여주는데, 각각의 픽셀은 모든 데이터를 사용하여 1NN에 의해 분류된다. 그림 3은 5NN 분류 맵을 보여준다. 하얀 구역은 분류되지 않은 지역에 대응되며, 5NN 투표(voting)가 같은 경우이다(예를 들어, 5개의 최근접 이웃들 중 2개의 초록, 2개의 빨강과 하나의 파란색 점이 있는 경우). 그림 4는 축소된 데이터셋을 보여준다. X표시는 (3,2)NN 규칙에 의해 선택된 클래스 이상치들을 나타낸다(이 인스턴스들의 모든 3개의 최근접 이웃들은 모두 다른 클래스들에 속한다). 사각형은 프로토타입을 나타내며, 빈 원은 흡수된 점들을 나타낸다. 좌하측 모서리는 클래스 이상치, 프로토타입, 흡수된 점들의 개수를 나타낸다. 이 예시에서는 프로토타입의 수가 클래스에 따라 15%에서 20%까지로 다양하다. 그림 5는 프로토타입에 기초한 1NN 분류 지도와 나타낸 것인데, 초기 데이터터셋에 기초한 1NN 분류 지도와 매우 비슷함을 알 수 있다. 이 그림들은 Mirkes applet. 을 사용하여 만들어졌다.[2]
- k-NN 분류기(classfier)를 위한 CNN 모델
-
Fig. 1. 데이터셋. -
Fig. 2. 1NN 분류 지도. -
Fig. 3. 5NN 분류 지도. -
Fig. 4. CNN을 통해 축소된 데이터셋. -
Fig. 5. CNN을 통해 추출한 프로토타입에 기초한 1NN 분류 지도.
k-NN 회귀[edit]
k-NN 회귀에서는, k-NN 알고리즘은 연속 변수를 예측하기 위해서 사용된다. 하나의 알고리즘은 k 개의 최근접 이웃들의 거리의 역수에 의해 가중된 가중 평균을 사용한다. 이 알고리즘은 다음과 같이 동작한다.
- 질의 예시로부터 라벨이 붙은 예시들까지의 유클리디안 혹은 마하라노비스 거리(Mahalanobis distance) 를 계산한다.
- 거리가 증가하는 순으로 라벨이 붙은 예시들을 정렬한다.
- RMSE 에 기반한 최근접 이웃들의 발견적인(heuristically) 최적 수를 찾는다. 이것은 교차타당화를 통해 이뤄진다.
- k-최근접 다변량 이웃들의 거리의 역수의 가중평균을 계산한다.
결과의 타당성 검증[edit]
A 혼동 행렬 또는 "matching matrix" 는 k-NN 분류의 정확성의 타당성을 검증하기 위한 도구로 자주 사용된다. 우도 비 시험(likelihood-ratio test) 같은 더 강한 통계적 방법이 적용될 수 있다.
- ^ P. E. Hart, The Condensed Nearest Neighbor Rule. IEEE Transactions on Information Theory 18 (1968) 515–516. doi: 10.1109/TIT.1968.1054155
- ^ a b E. M. Mirkes, KNN and Potential Energy: applet. University of Leicester, 2011.