CN2 알고리즘은 분류 작업을 위한 기계 학습에서 사용되는 규칙 유도 방법이다. 이 알고리즘은 데이터 세트에서 if-then 규칙 집합을 생성하며, 각 규칙은 속성 값에 대한 조건의 논리곱과 예측 클래스로 구성된다. CN2는 1987년 튜링 연구소에서 피터 클라크와 팀 니블렛이 기계 학습과 인공 지능 분야의 초기 연구를 바탕으로 도입했다. 이 알고리즘은 AQ 계열의 분리 정복 검색 전략과 엔트로피와 같은 의사 결정 트리 유도에 사용되는 정보 이론적 평가 기준을 결합한 것으로 유명하다. 이는 상징적 규칙 학습의 기초적인 접근 방식으로 남아 있으며, 신경망 및 심층 학습 방법의 불투명한 특성과 대조되는 해석 가능한 모델을 제공한다.
이 알고리즘은 훈련 예제의 하위 집합을 포함하는 최상의 규칙을 반복적으로 검색하고, 해당 예제를 제거한 후 나머지 데이터에 대해 이 과정을 반복하여 작동한다. 이 분리 정복 전략은 커버링이라고도 하며, CN2를 분할 정복 접근 방식을 사용하는 의사 결정 트리 알고리즘과 구별한다. CN2는 변형에 따라 정렬된 규칙 목록(결정 목록) 또는 정렬되지 않은 규칙 집합을 생성할 수 있다. 원래 버전은 정렬된 목록을 생성하며, 규칙이 순서대로 적용되고 첫 번째로 일치하는 규칙이 예측을 결정한다. 후속 확장인 CN2-SD(하위 그룹 발견)는 완전한 분류기보다는 흥미로운 하위 그룹을 발견하도록 알고리즘을 조정했다.
검색 및 평가
CN2는 규칙 조건 공간에서 빔 검색을 수행한다. 빈 규칙에서 시작하여 규칙의 품질을 향상시키는 조건을 반복적으로 추가하며, 각 단계에서 고려되는 후보 규칙 수를 제한하기 위해 빔 폭 매개변수를 사용한다. 검색은 규칙의 품질을 측정하는 평가 함수에 의해 안내된다. 원래 CN2는 ID3의 이득 기준과 유사한 엔트로피 기반 정보 이론적 측정을 사용했다. 구체적으로, 알고리즘은 포함된 예제 간의 클래스 분포 엔트로피를 사용하여 규칙을 평가하며, 엔트로피를 줄이는 규칙을 선호한다. 이후 버전에서는 특히 작은 표본을 다룰 때 과적합을 피하기 위해 라플라스 정확도 추정을 도입했다. 라플라스 보정은 각 클래스에 가상 개수를 추가하여 규칙 정확도의 더 견고한 추정을 제공한다.
빔 검색은 본질적으로 탐욕적이며 역추적하지 않지만, 빔 폭은 여러 유망한 경로를 동시에 탐색할 수 있게 한다. 탐욕성과 탐색 간의 이러한 균형은 CN2의 핵심 특성이다. 검색 공간은 데이터에 존재하는 속성-값 쌍에 의해 정의되며, 조건은 일반적으로 명목 속성의 경우 attribute = value, 숫자 속성의 경우 attribute <= value 및 attribute >= value 형태이지만, 원래 알고리즘은 명목 데이터에 초점을 맞췄다.
알고리즘 변형
수년에 걸쳐 여러 CN2 변형이 개발되었다. 가장 중요한 것은 1990년대 후반 나다 라브라치와 동료들이 도입한 CN2-SD로, 목표를 분류에서 하위 그룹 발견으로 전환한다. 하위 그룹 발견에서 목표는 완전한 분류기를 구축하는 것이 아니라 비정상적인 클래스 분포를 가진 흥미로운 인구 하위 그룹을 설명하는 규칙을 찾는 것이다. CN2-SD는 규칙의 일반성과 분포의 비정상성을 균형 있게 맞추는 가중 상대 정확도 측정을 사용하여 규칙을 평가한다. 또 다른 변형인 CN2-R은 무작위화 테스트를 통합하여 규칙의 통계적 유의성을 평가하고 우연히 발생할 수 있는 규칙을 걸러낸다. 이는 더 신뢰할 수 있고 일반화 가능한 규칙 집합을 생성하는 데 도움이 된다.
정렬되지 않은 CN2 변형은 각 규칙이 독립적으로 학습되는 규칙 집합을 생성하며, 예측 시 모든 규칙이 적용되고 그 예측이 결합되며, 종종 투표 또는 가장 높은 특이성을 가진 규칙을 선택하는 방식으로 결합된다. 이 접근 방식은 클래스 영역이 겹치는 데이터 세트에서 더 견고할 수 있다. 정렬된 규칙과 정렬되지 않은 규칙 간의 선택은 응용 분야에 따라 달라진다. 정렬된 목록은 더 간단하고 빠르며, 정렬되지 않은 집합은 희귀 클래스에 대한 더 나은 커버리지를 제공할 수 있다.
응용 및 영향
CN2는 의료 진단, 결함 감지, 생태 모델링 등 다양한 분야에 적용되었다. 해석 가능성은 의료 및 규제 준수와 같이 결정 과정을 이해하는 것이 중요한 분야에서 특히 가치가 있다. 예를 들어, 의료 응용에서 CN2 규칙은 if blood_pressure > 140 and age > 60 then high_risk와 같은 간단한 조건으로 표현될 수 있으며, 임상의가 쉽게 검증할 수 있다. 이 알고리즘은 또한 기계 학습에서 상징적 접근 방식과 하위 상징적 접근 방식을 비교하는 기준으로 사용되었다. 심층 학습과 같은 현대 방법이 복잡한 작업에서 종종 더 높은 정확도를 달성하지만, CN2는 투명한 모델이 필요하거나 데이터가 제한된 문제에서 여전히 관련성이 있다.
이 알고리즘의 영향력은 RIPPER 및 PART와 같은 후속 규칙 학습 시스템으로 확장되었으며, 이들은 유사한 검색 및 평가 전략을 채택했다. CN2의 엔트로피 기반 평가는 의사 결정 트리 유도 및 특성 선택에 사용되는 더 정교한 정보 이론적 측정의 선구자였다. 분리 정복 프레임워크는 PAC 학습 프레임워크 및 규칙 학습의 복잡성과의 연결과 함께 이론적으로 분석되었다.
한계 및 확장
CN2에는 알려진 한계가 있다. 탐욕적 검색이 가짜 패턴에 과적합할 수 있으므로 노이즈가 많은 데이터에 민감하다. 빔 검색은 순수한 언덕 오르기보다 더 철저하지만 제한된 전방 탐색으로 인해 최적의 규칙을 놓칠 수 있다. 이 알고리즘은 속성이 독립적이라고 가정하지만, 실제 데이터에서는 그렇지 않을 수 있다. 확장은 이러한 문제 중 일부를 해결했다. 예를 들어, 전처리 단계 또는 검색 내에서 이산화를 통해 연속 속성을 통합하면 CN2가 숫자 데이터를 처리할 수 있다. CN2-R에서와 같은 통계 테스트의 사용은 과적합을 완화한다. 더 최근 연구는 CN2를 앙상블 방법과 통합하여 여러 규칙 집합을 결합해 견고성을 향상시켰다.
현대 기계 학습의 맥락에서 CN2는 종종 신경망 접근 방식과 대조된다. 신경망은 복잡한 특성 상호 작용을 자동으로 학습할 수 있지만 많은 양의 데이터가 필요하고 해석하기 어렵다. 반면 CN2는 간결하고 인간이 읽을 수 있는 규칙을 생성하지만 고차원 또는 고도로 비선형적인 문제에서는 어려움을 겪을 수 있다. 이러한 균형은 상징적 규칙과 하위 상징적 학습을 결합한 하이브리드 시스템에 대한 연구를 계속 추진하고 있으며, 이는 신경-상징적 AI의 더 넓은 분야에서 관심 주제이다.
구현 및 소프트웨어
CN2는 여러 기계 학습 라이브러리에서 구현된다. 류블랴나 대학에서 개발된 Orange 데이터 마이닝 스위트에는 CN2 학습기가 포함되어 있으며, Weka 툴킷에도 포함되어 있다. 이러한 구현은 실제 데이터 세트에 알고리즘을 적용하기 위한 사용자 친화적인 인터페이스를 제공한다. 알고리즘의 단순성 덕분에 다양한 프로그래밍 언어로 쉽게 구현할 수 있으며, 기계 학습 및 데이터 마이닝 과정에서 교육 예제로 자주 사용된다. 오픈 소스 구현의 가용성은 연구 및 교육에서 계속 사용되는 데 기여했다.
1980년대 후반에 도입되었음에도 불구하고 CN2는 기계 학습 실무자의 도구 상자에서 여전히 관련성 있는 알고리즘으로 남아 있다. 해석 가능성에 대한 초점과 효율적인 검색 전략은 심층 학습의 현재 지배력보다 앞선 다른 상징적 방법과 함께 AI 역사에서 그 위치를 보장한다. 2020년대 현재 CN2는 규칙 학습 및 해석 가능한 AI 연구에서 여전히 인용되며, 새로운 규칙 유도 방법을 평가하는 기준선 역할을 한다.