증분 의사결정 트리

Incremental decision tree

증분 결정 트리 알고리즘은 결정 트리를 출력하는 온라인 기계 학습 알고리즘입니다.C4.5와 같은 많은 의사 결정 트리 방법은 완전한 데이터 집합을 사용하여 트리를 구성합니다.증분 Decision Tree 메서드를 사용하면 과거 인스턴스를 다시 처리할 필요 없이 새로운 개별 데이터 인스턴스만 사용하여 기존 트리를 업데이트할 수 있습니다.이는 트리가 업데이트될 때 전체 데이터 집합을 사용할 수 없거나(즉, 데이터가 저장되지 않음), 원본 데이터 집합이 처리하기에 너무 크거나 시간이 지남에 따라 데이터 특성이 변화하는 상황에서 유용할 수 있습니다.

적용들

  • 온라인 학습
  • 데이터 스트림
  • 컨셉트 드리프트
  • 계층적 모형을 사용하여 잘 모형화할 수 있는 데이터입니다.
  • 사용자가 해석할 수 있는 출력이 필요한 시스템.

방법들

다음은 증분 Decision Tree 메서드의 간단한 목록으로, 그 상위 알고리즘(일반적으로 비증분)별로 정리되어 있습니다.

카트 패밀리

CART(1984)는[1] 분류와 회귀 문제 모두에 대한 비증분적 의사결정 나무 유도자로, 수학과 통계 커뮤니티에서 개발되었다.CART의 뿌리는 AID(1963년)[2]로 거슬러 올라간다.

  • 증분 CART(1989)[3] 크로포드 CART는 데이터를 증분 통합하기 위해 CART를 수정했습니다.

ID3/C4.5 패밀리

ID3(1986)[4] 및 C4.5(1993)[5]는 Quinlan에 의해 개발되었으며 Hunt's Concept Learning System(CLS, 1966)[6]에 뿌리를 두고 있다.ID3 계열의 나무 유도자는 엔지니어링 및 컴퓨터 과학 커뮤니티에서 개발되었습니다.

  • ID3'(1986)[7]는 Schlimer와 Fisher에 의해 제안되었다.이것은 ID3를 증분하는 브루트포스 방식입니다.새로운 데이터 인스턴스를 취득할 때마다 ID3를 사용하여 완전히 새로운 트리가 유도됩니다.
  • ID4(1986)[7]는 데이터를 점진적으로 통합할 수 있다.단, 노드에 대해 새로운 테스트가 선택되면 ID4가 서브트리를 파기하기 때문에 특정 개념은 학습할 수 없었습니다.
  • ID5(1988)[8]는 서브트리를 폐기하지 않았지만 ID3과 같은 트리를 생성하는 것도 보증하지 않았습니다.
  • ID5R(1989)[9]은 증분 트레이닝 순서에 관계없이 데이터 세트의 ID3와 같은 트리를 출력한다.이 작업은 트리의 하위 노드를 반복적으로 업데이트하여 수행되었습니다.숫자 변수, 다중 클래스 분류 작업 또는 결측값을 처리하지 않았습니다.
  • ID6MDL(2007)[10] ID3 또는 ID5R 알고리즘의 확장 버전.
  • ITI(1997)[11]는 의사결정 나무를 점진적으로 유도하는 효율적인 방법이다.데이터의 표시 순서나 트리가 증분 또는 비증분(배치 모드)으로 유도되는지 여부에 관계없이 동일한 트리가 데이터 집합에 대해 생성됩니다.숫자 변수, 다중 클래스 작업 및 결측값을 수용할 수 있습니다.코드는 웹에서 이용할 수 있습니다.[1]

주의: ID6NB(2009)[12]는 증분하지 않습니다.

기타 증분 학습 시스템

의사결정 트리를 구축하지 않았지만 초기 증분 의사결정 트리 학습자, 특히 ID4의 [7]개발에 선행하고 영향을 미치는 여러 증분 개념 학습 시스템이 있었다.그 중 주목할 만한 것은 슐리머와 그레인저의 STAGER(1986)[13]로, 점차적으로 분리 개념을 배웠다.STAGER는 시간이 지남에 따라 변화하는 개념(개념 표류)을 검토하기 위해 개발되었습니다.STAGER에 앞서, Michalski와 Larson(1978)[14][15]은 분리 정상 형식(DNF)에서 개념을 학습하기 위한 감독 시스템인 AQ의 증분 변형을 조사했다.이러한 초기 시스템과 다른 시스템에 대한 경험은 증분 트리 구조의 비감독 학습을 포함하며, 학습 비용과 품질 사이의 고유한 트레이드오프를 반영하는 네 가지 차원에 따라 증분 의사결정 트리 학습자를 구체적으로 평가하기 위한 개념 프레임워크에 기여하였다.:[7] (1) 기술 기반 업데이트 비용 (2) 주어진 특성을 가진 기술 기반에 수렴하는 데 필요한 관찰 수 (3) 시스템이 수행하는 총 노력(처음 2차원의 함수) 및 (4) 최종 기술 기반 품질(종종 일관성)증분 의사결정 나무 학습자가 출현한 역사적 맥락 중 일부는 피셔와 슐리머(1988)[16]에 제시되어 있으며, 이는 증분 학습 시스템을 평가하고 설계하는 데 사용된 네 가지 요소 프레임워크에서도 확장된다.

VFDT 알고리즘

Very Fast Decision Tree 학습자는 수신 데이터 스트림을 서브샘플링하여 대규모 증분 데이터 세트에 대한 교육 시간을 단축합니다.

  • VFDT(2000)[17]
  • CVFDT(2001)[18]는 착신 데이터에 슬라이딩 윈도우를 사용함으로써 개념 드리프트에 적응할 수 있다.창 밖의 오래된 데이터는 잊혀집니다.
  • VFDTc(2006)[19]는 VFDT를 확장하여 연속 데이터, 개념 표류 및 리프 내의 Naigve Bayes 분류기 적용을 지원합니다.
  • VFML(2003)은 툴킷으로 웹에서 이용할 수 있습니다.[2] VFDT와 CVFDT의 크리에이터에 의해 개발되었습니다.

EFDT 알고리즘

초고속 의사결정 트리[20] 학습자는 통계적으로 VFDT보다 강력하므로 더 적은 데이터에서 더 자세한 트리를 학습할 수 있습니다.트리에 새 분기를 삽입할 시기를 결정하는 방법은 VFDT와 다릅니다.VFDT는 최상의 사용 가능한 분기가 다른 어떤 분기보다 낫다고 확신할 때까지 기다립니다.이와는 대조적으로 EFDT는 사용 가능한 최고의 지점이 현재 대안보다 더 낫다고 확신하는 즉시 분할됩니다.처음에, 현재의 대안은 no branch입니다.이를 통해 EFDT는 VFDT보다 훨씬 더 빠르게 분기를 삽입할 수 있습니다. 즉, 증분 학습 중에 EFDT는 VFDT보다 훨씬 빨리 유용한 트리를 배포할 수 있습니다.

그러나 새로운 분기 선택 방법은 차선의 분기를 선택할 가능성을 크게 높입니다.따라서 EFDT는 모든 지점의 성능을 지속적으로 모니터링하며 더 나은 대안이 있다고 확신하는 즉시 지점을 교체할 것입니다.

OLIN 및 IFN

  • OLIN (2002)[21]
  • IOLIN (2008)[22] - 정보 퍼지 네트워크 (IFN)[23] 기반

개나리

「 」를 참조해 주세요.

레퍼런스

  1. ^ Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J.(1984) 분류 및 회귀 나무.벨몬트, 캘리포니아: Wadsworth International Group.
  2. ^ Morgan, J. N, & Sondquist, J. A.(1963) 조사 데이터 분석의 문제점 및 제안.J. Amer.통계.Assoc, 58, 415-434
  3. ^ Crowford, S. L. (1989) CART 알고리즘의 확장.인간-기계 연구에 관한 국제 저널. 31, 197-217.
  4. ^ Quinlan, J. R. (1986) 의사결정 나무의 유도.머신 러닝 1(1), 81-106.
  5. ^ Quinlan, J. R. (1993) C4.5: 기계 학습을 위한 프로그램.샌 마테오, 캘리포니아: 모건 카우프만
  6. ^ Hunt, E. B., Marin, J., & Stone, P. J.(1966) 유도 실험.뉴욕: 학술 출판사.
  7. ^ a b c d Schlimer, J. C., & Fisher, D.(1986) 증분 개념 유도 사례 연구.제5회 인공지능 전국회의 진행상황(496-501페이지)필라델피아, 펜실베이니아: 모건 카우프만
  8. ^ Utgoff, P. (1988) ID5: 증분 ID3.제5회 기계학습 국제회의, 107-120페이지.모건 카우프만 출판사입니다
  9. ^ Utgoff, P. E. (1989) 의사결정 나무의 증분 유도.기계 학습 4, 161-186.
  10. ^ Kroon, M., Korzec, S., Adriani, P. (2007) ID6MDL: 프루닝 후 증분 의사결정 트리.
  11. ^ Utgoff, P.E., Berkman, N.C. 및 Clouse, J.A.(1997) 효율적인 트리 재구성에 기초한 Decision Tree 유도.기계 학습 29, 5-44.
  12. ^ Appavu, S. 및 Rajaram, R. (2009) ID6NB 알고리즘을 사용한 텍스트 분류에 관한 지식 기반 시스템.지식 기반 시스템 22 1~7
  13. ^ Schlimer, J. C., & Granger, R. H. 주니어(1986년).노이즈가 많은 데이터로부터의 증분 학습.기계학습1, 317-354.
  14. ^ 마이클스키, R.S. & 라슨, J. B. (1978)가장 대표적인 훈련 예시와 VL 가설의 증분 생성: ESEL 및 AQ11 프로그램의 기본 방법과 설명(기술의원번호 UIUCDCS-R-78-867).Urbana:일리노이 대학교 컴퓨터 공학부입니다.
  15. ^ 미할스키, R. S.(1973년).가변값 논리 시스템 VL1을 사용하여 분류 규칙을 발견합니다.제3회 인공지능 국제공동회의 진행상황 (p. 162-172).스탠포드, 캘리포니아: 모건 카우프만
  16. ^ Fisher, D. & Schlimer, J. 증분 개념 학습 모델:공동 연구 제안서입니다.Vanderbilt University Technical Report CS-88-05 (영어판), http://www.vuse.vanderbilt.edu/ ~dfisher/tech-timeout/tr-88-05/영어판.http:/영어판.http:/영어판.http:/http:/http:/
  17. ^ 도밍고스, P., Hulten, G. (2000) 고속 데이터 스트림 마이닝프로시저 KDD 2000, ACM 프레스, 뉴욕, 뉴욕, 미국, 71-80페이지.
  18. ^ Hulten, G., Spencer, L., Domainos, P.(2001) 시간 변경 데이터 스트림 마이닝프로시딩 KDD 2001, ACM 프레스, 뉴욕, 97~106페이지.
  19. ^ Gama, J., Fernandes, R., & Rocha, R. (2006) 데이터 스트림 마이닝용 의사결정 트리.인텔리전트 데이터 분석 10 23-45.
  20. ^ Manapragada, C., Web, G.I., Salehi, M. (2018) 초고속 의사결정 트리프로시저 KDD 2018, ACM 프레스, 뉴욕, 뉴욕, 미국, 1953-1962 페이지.
  21. ^ 마지막으로 M. (2002) 비정상 데이터 스트림의 온라인 분류 Intel.데이터 분석. 6(2) 129~147.
  22. ^ Cohen, L., Avrahami, G., Last, M., Kandel, A. (2008) 동적 데이터 스트림 마이닝을 위한 정보 퍼지 알고리즘.소프트 컴퓨팅 적용.8 1283-1294.
  23. ^ Maimon, O., Last, M. (2000) 정보 퍼지 네트워크(IFN) 방법론.Knowledge Discovery 및 데이터 마이닝.보스턴: Kluwer 학술 출판사

외부 링크