[논문]공간 데이터의 분포를 고려한 공간 엔트로피 기반의 의사결정 트리 기법

장윤경; 유병섭; 이동욱; 조숙경; 배해영

doi:10.3745/kipstb.2006.13b.7.643

문제 정의

또한 의사결정 트리의 공간 속성을 엔트로피에 반영하기 위한 객체 간의 거리 계산 방식을 서술한다. 그리고 본 논문에서 분포도가 다른 클래스간의 비교를 위해 사용될 중심극한정리에 대해 알아본다.
기존의 공간 의사결정 트리에 대해 논한다. 또한 의사결정 트리의 공간 속성을 엔트로피에 반영하기 위한 객체 간의 거리 계산 방식을 서술한다. 그리고 본 논문에서 분포도가 다른 클래스간의 비교를 위해 사용될 중심극한정리에 대해 알아본다.
본 논문에서는 공간 데이터의 분포를 고려한 공간 엔트로피 기반의 의사결정 트리 기법을 제안한다. 제안 기법은 데이터의 표준편차와 표준정규분포를 이용하여 클래스의 중점과 공간 데이터 간의 분산 정도를 알아내어 비공간적으로 분류된 객체들이 공간적으로는 어떠한 연관성이 있는지를 나타낸다.
본 논문에서는 표준편차행렬과 표본 정규분포에 기초하여 계산된 엔트로피 기반의 공간 의사결정 트리에 대해서 알아보았다. 제안 기법은 각 클래스의 중심점과의 표준편차행렬을 이용하여 클래스의 분산도를 측정하고 차별도는 각 클래스의 중점을 표본정규분포에 맞게 변형시킨 후 중점 간의 거리 비율로 나타내어진다.
관계에 대한 정보까지 알아내는 것이 중요하다. 본 논문은 (그림 2)와 같이 공간 객체가 분포되어 있을 경우에 대하여 분산도와 차별도를 제시하고 공간 엔트로피와 정보 이득율을 구하는 과정을 설명한다.
유용하다. 본 논문은 기존의 의사결정 트리에서 벗어나 공간 차원의 데이터의 거리를 의사결정 트리 구축에 이용한다는데에 의의가 있다. 그러나 두 객체간의 거리를 계산하는데 있어서 유클리디안 거리 계산 방법을 사용했기 때문에 실생활에 이용할 때에는 공간 객체의 분포와 그 관계를 설명하는데 있어서 한계점이 있었다.
본 장에서는 데이터의 공간 차원에서의 위치와 비공간적 속성들이 서로 얼만큼 영향력이 있는지 알기 위해서 공간 차원에서의 클래스 별 분산도와 차별도를 계산한다. 분산도와 차별도는 다음과 같은 특성이 있다.
본 장에서는 분류를 할 때에 공간 데이터를 고려하는 것이 얼마나 중요한지 알아보고 이러한 공간 속성을 고려하기 위한 기존의 공간 의사결정 트리에 대해 논한다. 또한 의사결정 트리의 공간 속성을 엔트로피에 반영하기 위한 객체 간의 거리 계산 방식을 서술한다.

가설 설정

[규칙 2]: 같은 클래스에 포함되어있는 객체가 가까이 있으면 공간 다양화 계수는 감소한다.
[규칙 E:다른 클래스에 포함되어있는 객체가 가까이 있으면 공간 다양화계수는 증가한다.
[특성 1]: 클래스 내의 객체들 간의 거리가 짧을수록 그 클래스는 분산도가 낮은 클래스이다.
[특성 2]: 한 클래스에 속하는 객체들이 중심점을 기준으로 퍼짐 정도가 작을 때 그 클래스는 분산도가낮은 클래스이다.

제안 방법

이것은 높은 거리 계산 비용을 요구해 전체 의사결정 트리의 구축 비용을 증가시키는 요인이다. 그러나 제안 기법은 한 클래스 안의 두 객체간의 거리가 아닌 중심점으로부터의 클래스 내 객체의 거리 비율을 측정한다. 따라서 n개의 데이터가 같은 클래스에 속한다고 가정하였을 경우 (n-1)번의 거리 계산만이 필요하다.
이때 유클리디안 기법으로 거리를 측정하면 데이터의 분포도를 반영하지 못하는 문제점이 있다. 따라서 본 논문에서는 데이터에 대한 표준편차행렬을 같이 곱해서 같은 거리라도 데이터의 분포도를 반영하여 다른 의미를 갖게 한다. 분포도를 고려하는 두 점 (X₁, Y₁), (X₂, Y₂) 의 거리는 다음과 같이 구한다.
따라서 CASE 3과 4의 경우 그 차이를 분명하게 나타낼 수 없었다. 반면에 제안된 기법은 표준편차행렬 S를 이용하여 객체가 Mi를 중심으로 분산된 정도를 나타낸다. 즉, 중심점과 객체간의 길이가 같다고 하더라고 공간 데이터가 많이 퍼져있는 곳은 엔트로피를 증가시키는 효과가 있고 공간 데이터가 밀집되어 있는 곳은 엔트로피가 감소되는 효과가 있다.
본 논문에서 제안한 차별도는 중점과 표준편차에 따라 각 클래스의 중점끼리의 거리 비율을 표준정규분포를 따르도록 정규화 한 것이다. 따라서 각각 n, k, m의 데이터를 가지고 있는 3개의 클래스에 대한 차별도를 계산하기 위해서 단지 3번의 거리계산이 필요하다.
본 논문에서는 데이터의 분포도를 구려하기 위해 거리를 계산할 때 분산 행렬을 같이 곱한다. (그림 3)의 A, B 경우를 비교해보면 둘 다 같은 중심점을 가지고 있지만 분포도가 다른 경우이다.
실험은 5000개의 클래스 레이블을 가진 데이터 중에서 2000개의 데이터를 훈련 데이터 집합으로 구성하여 의사결정 트리를 구축하고 나머지 30C0개의 데이터를 검정 데이터 집합으로 선택하여 구축된 의사결정 트리가 분류를 올바르게 수행하는지를 검증한다. 본래 구축된 트리는 테스트 데이터를 가지고 클래스 레이블을 예측하기 위해 분류를 수행하지만 본 실험에서는 분류 결과의 정확성 확인을 위해 검증 데이터를 가지고 분류를 수행하였다. 검증 데이터는 분류에 사용될 여러 속성과 함께 최종적으로 분류된 클래스 레이블을 가지고 있기 때문에 구축둰 의사결정 트리가 올바른 분류를 수행하였는지 확인할 수 있다.
나타낸 것이다. 실험은 5000개의 클래스 레이블을 가진 데이터 중에서 2000개의 데이터를 훈련 데이터 집합으로 구성하여 의사결정 트리를 구축하고 나머지 30C0개의 데이터를 검정 데이터 집합으로 선택하여 구축된 의사결정 트리가 분류를 올바르게 수행하는지를 검증한다. 본래 구축된 트리는 테스트 데이터를 가지고 클래스 레이블을 예측하기 위해 분류를 수행하지만 본 실험에서는 분류 결과의 정확성 확인을 위해 검증 데이터를 가지고 분류를 수행하였다.
6GHz의 중앙처리장치, 2GB의 주 기억장치, 120GB 보조 기억장치의 IBM PC 호환 기종에서 MS Window 2000 환경하에 진행되었다. 실험은 ID3 의사결정 트리, 유클리디안 거리 기반 공간 의사결정 트리, 제안된 의사결정 트리에 대해 산사태 발생 여부에 대한 분류를 수행하였다. 실험에 사용된 데이터 집합은 <표 3>과 같이 클래스 레이블을 가진 데이터로써 비공간 속성으로 식물의 종류, 토양의 종류, 비의 양, 지하수 유무, 지질의 종류, 기울기, 지가 등을 가지고 있고 공간 차원에서 (그림2)의 CASE 1, 2, 3, 4와 같은 모양으로 분포되어 있다.
제안 기법에서는 분산도를 구하기 위해 각 클래스의 중심점과 표준편차, 표준편차행렬을 구하고 각 클래스 데이터와 중심점의 거리를 구한다. 거리를 구할 시 표준편차행렬을 같이 곱하여 거리를 계산할 경우 데이터의 분포도를 반영하게 된다.
제안 기법은 각 클래스의 중심점과의 표준편차행렬을 이용하여 클래스의 분산도를 측정하고 차별도는 각 클래스의 중점을 표본정규분포에 맞게 변형시킨 후 중점 간의 거리 비율로 나타내어진다. 이러한 제안 기법은 데이터의 분포도를 반영하기 때문에 비공간적으로 분류된 객체들이 공간 차원에서는 어떠한 연관 관계가 있는지 알 수 있다.
이러한 제안 기법은 데이터의 분포도를 반영하기 때문에 비공간적으로 분류된 객체들이 공간 차원에서는 어떠한 연관 관계가 있는지 알 수 있다. 제안 기법은 기존의 유클리디안 기법 의사결정 트리보다 데이터의 거리와 분포도를 함께 고려하기 때문에 객체들의 공간적 성질을 더욱 잘 반영해줄 수 있는 공간 엔트로피 계산을 수행하고 이로 인해 비공간적으로나 공간적으로 모두 신뢰성 있는 의사결정 트리를 구축하게 된다. 또한 거리를 잴 때 모든 객체간의 거리가 아닌 각 클래스를 대표할 수 있는 중심점으로부터의 거리를 계산하기 때문에 계산 비용을 줄여준다.
하지만 실생활의 공간 객체는 고르게 분포되기 보다는 편중된 분포로 위치하는 경우가 더 많으므로 유클리디안 기반 의사결정 트리는 적합하지 않다. 제안 기법은 데이터의 분포도를 반영하기 때문에 편중된 데이터 집합이나 원 모양 분포의 데이터 집합이 아니더라도 신뢰성 있는 분류를 수행한다. CASE 4는 CASE 3과 비슷한 중점을 가진 클래스의 분포도를 다르게 한 경우이다.
기반의 의사결정 트리 기법을 제안한다. 제안 기법은 데이터의 표준편차와 표준정규분포를 이용하여 클래스의 중점과 공간 데이터 간의 분산 정도를 알아내어 비공간적으로 분류된 객체들이 공간적으로는 어떠한 연관성이 있는지를 나타낸다. 또한 클래스 중심점을 거리 비교대상으로 하고 각 중심점을 표준화하여 이용하기 때문에 높은 신뢰성을 제공하고 계산 비용을 절약한다.
제안기법은 각 클래스 공간 객체들의 중심점과 분산을 고려하여 공간 객체의 분포도가 비공간적 속성과 함께 엔트로피 계산에 참가한다. 제안기법은 ID3, 유클리디안 기반 공간 의사결정 트리브다 작은 엔트로피 값을 가지고 공간, 비공간 속성뿐만 아니라 데이터의 분포도를 고려하여 의사결정 트리를 구축하므로 실생활에 적합한 분류를 수행한다.

대상 데이터

본 논문의 실험은 2.6GHz의 중앙처리장치, 2GB의 주 기억장치, 120GB 보조 기억장치의 IBM PC 호환 기종에서 MS Window 2000 환경하에 진행되었다. 실험은 ID3 의사결정 트리, 유클리디안 거리 기반 공간 의사결정 트리, 제안된 의사결정 트리에 대해 산사태 발생 여부에 대한 분류를 수행하였다.
실험에 사용된 데이터 집합은 과 같이 클래스 레이블을 가진 데이터로써 비공간 속성으로 식물의 종류, 토양의 종류, 비의 양, 지하수 유무, 지질의 종류, 기울기, 지가 등을 가지고 있고 공간 차원에서 (그림2)의 CASE 1, 2, 3, 4와 같은 모양으로 분포되어 있다.
것이다. 실험은 클래스 레이블을 가진 데이터 5000개를 가지고 의사결정 트리를 구축할 때 나타나는 엔트로피를 측정하였다.
또한 거리를 잴 때 모든 객체간의 거리가 아닌 각 클래스를 대표할 수 있는 중심점으로부터의 거리를 계산하기 때문에 계산 비용을 줄여준다. 실험평가 시 5000개의 클래스 레이블을 가진 데이터를 나누어서 2000개는 트리를 구축하는 훈련 데이터로 사용하고 나머지 3000개는 트리를 검증하는 검정 데이터로 사용했다. 실험 결과 제안 기법은 기존의 ID3 의사결정 트리와 공간 엔트로피 의사결정 트리와 비교하여 정확성 측면에 있어서 약 18%의 성능향상을 보였고 트리 구축에 사용되는 데이터 개수를 늘려가며 기존 기법과 비교한 결과 계산 비용면에서 약 11%의 성능 향상을 보였다.

성능/효과

CASE 1의 경우 구축된 의사결정 트리를 가지고 검증 데이터에 대한 분류를 수행하였을 때 의사결정 트리의 분류수행 결과와 검증 데이터의 클래스 레이블의 일치도가 낮았다. 또한 유클리디안 기반 의사결정 트리와 제안된 의사결정 트리의 분류 정확도의 차이가 크지 않았다.
또한 d^ext가 높은 값을 가질수록 한 클래스와 다른 클래스에 포함된 각각의 객체간의 거리비율이 높다는 것을 나타내고 이는 서로 다른 클래스간의 차별성을 높여주므로 엔트로피를 감소시키는 효과가 있다.
또한 유클리디안 기반 의사결정 트리와 제안된 의사결정 트리의 분류 정확도의 차이가 크지 않았다. 이것은 CASE 1의 데이터 집합 속성이 공간 차원과 관련이 적기 때문인데 이러한 경우라면 트리 구축 시간, 엔트르피 계산 비용 등을 고려할 때 ID3 방식으로 구축하는 것이 가장 적합하다.
또한 제안 기법은 기존 기법보다 계산 비용을 절감시키는 효과가 있다. 기존 기법은 같은 클래스에 속하는 한 객체와 나머지 객체 모두의 거리 비율을 합하는 방법을 사용한다.
실험평가 시 5000개의 클래스 레이블을 가진 데이터를 나누어서 2000개는 트리를 구축하는 훈련 데이터로 사용하고 나머지 3000개는 트리를 검증하는 검정 데이터로 사용했다. 실험 결과 제안 기법은 기존의 ID3 의사결정 트리와 공간 엔트로피 의사결정 트리와 비교하여 정확성 측면에 있어서 약 18%의 성능향상을 보였고 트리 구축에 사용되는 데이터 개수를 늘려가며 기존 기법과 비교한 결과 계산 비용면에서 약 11%의 성능 향상을 보였다.
따라서 객체들이 공간적인 분류 특색 없이 흩어져 있는 CASE 1의 경우에는 공간 차원에 대한 계산 비용으로 인하여 엔트로피가 오히려 증가하지만 공간적으로 특성을 가지는CASE 2, 3, 4의 경우 엔트로피를 감소시켜 ID3보다 신뢰성 있는 분류를 수행한다. 제안된 공간 의사결정 트리는 CASE 1의 경우 공간 데이터에 대한 표준화, 중점과 분산의 계산 등으로 인해 ID3, 유클리디안 기반 공간 의사결정 트리보다 계산 비용이 증가한다. 하지만 CASE 2의 경우 표준화된 데이터 제공과 공분산을 반영함으로써 기존 기법보다 엔트로피가 줄이고 신뢰성 있는 의사결정 트리를 구축한다.
유클리디안 기반 의사결정 트리의 경우 전체 데이터가 여러 번씩 엔트로피 계산에 이용되기 때문에 의사결정 트리를 구축하는데 있어서 많은 비용이 요구되었다. 제안된 의사결정 트리는 각 클래스를 대표하는 중심점을 가지고 다른 데이터와 비교하면서 엔트로피를 계산하기 때문에 유클리디안 기반 의사결정 트리보다 훨씬 구축 속도가 빠른 것을 볼 수 있었다.
유클리디안 기법에서는 모든 데이터가 중심점이 되어 다른 데이터와의 거리 계산을 수행하기 때문에 이상치가 전체 엔트로피에 미치는 영향이 크다. 하지만 제안 기법은 모든 데이터를 대표할 수 있는 중심점으로부터 다른 데이터와의 거리 계산을 수행하기 때문에 이상치가 전체 엔트로피에 미치는 영향을 줄임으로써 의사결정 트리의 정확도를 높인다. CASE 3은 한 클래스의 데이터 분포가 타원형으로 되어있는 경우이다.

후속연구

향후 연구로는 공간 프레디킷을 의사결정 트리의 검사 조건으로 포함시키는 것과 공간 차원에서 장애물을 고려하여 엔트로피를 구하는 방법을 고려하고 있다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

공간 데이터의 분포를 고려한 공간 엔트로피 기반의 의사결정 트리 기법
A Spatial Entropy based Decision Tree Method Considering Distribution of Spatial Data 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

성능/효과

후속연구

참고문헌 (15)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

공간 데이터의 분포를 고려한 공간 엔트로피 기반의 의사결정 트리 기법 A Spatial Entropy based Decision Tree Method Considering Distribution of Spatial Data 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

성능/효과

후속연구

참고문헌 (15)

이 논문을 인용한 문헌

저자의 다른 논문 :

유병섭 (8) 이동욱 (20) 조숙경 (5) 배해영 (88)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

공간 데이터의 분포를 고려한 공간 엔트로피 기반의 의사결정 트리 기법
A Spatial Entropy based Decision Tree Method Considering Distribution of Spatial Data 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper