콘트라스트 세트 학습

Contrast set learning

대조도 집합 학습은 각 특정 그룹에 대해 식별되는 핵심 예측 변수를 역설계하여 개별 그룹 간의 의미 있는 차이를 식별하려는 연관 규칙 학습의 한 형태입니다.예를 들어, (학위 유형별로 레이블이 지정된) 학생 풀에 대한 속성 집합이 주어지면 대조도 집합 학습자는 학사 학위를 받으려는 학생과 박사 학위를 받으려는 학생 사이의 대조적인 특징을 식별할 수 있습니다.

개요

데이터 마이닝의 일반적인 방법은 객체나 상황의 속성을 분류하고 관찰된 항목이 어떤 범주에 속하는지 추측하는 것입니다.(일반적으로 학습 알고리즘에 트레이닝 세트를 공급함으로써) 새로운 증거를 조사하면 이러한 추측이 개선되고 개선됩니다.대비 세트 학습은 반대 방향으로 작동합니다.분류자는 일련의 이산 카테고리에 새로운 데이터를 배치하기 위해 사용되는 데이터 컬렉션을 읽고 정보를 수집하는 반면 대조 집합 학습은 항목이 속한 카테고리를 취하여 항목을 클래스의 멤버로 식별하는 통계 증거를 역설계하려고 시도합니다.즉, 콘트라스트 세트 학습자는 속성 값을 클래스 [1]분포의 변경 사항과 연관짓는 규칙을 찾습니다.이들은 한 분류와 다른 분류를 대조하는 핵심 예측 변수를 식별하려고 합니다.

예를 들어, 항공 우주 공학자는 새로운 로켓의 시험 발사에 대한 데이터를 기록할 수 있습니다.로켓의 궤적, 작동 온도, 외부 압력 등과 같은 요소를 고려하여 발사 내내 정기적으로 측정이 수행될 것이다.다수의 테스트에 성공한 후 로켓 발사가 실패하면 엔지니어는 콘트라스트 세트 학습을 사용하여 테스트 성공과 실패를 구별할 수 있습니다.대조도 세트 학습자는 적용 시 실패한 각 테스트의 주요 예측 변수와 성공한 테스트(온도가 너무 높았고 풍압이 너무 높았던 경우 등)를 나타내는 일련의 연관 규칙을 생성합니다.

콘트라스트 세트 학습은 [2]연관 규칙 학습의 한 형태입니다.어소시에이션 룰 학습자는, 통상, 트레이닝 세트내에서 공통적으로 발생하는 속성을 링크 하는 룰을 제공합니다(예를 들면, 4년간의 프로그램에 등록해, 풀 코스를 수강하는 사람도 캠퍼스 근처에 사는 경향이 있습니다).대비 세트 학습자는 현재 상황을 설명하는 규칙을 찾는 대신 그룹 간 분포가 유의미하게 다른 규칙을 찾습니다(따라서 이러한 그룹의 예측 [3]변수로 사용할 수 있습니다).예를 들어, 콘트라스트 세트 학습자는 "학사 학위를 가진 사람이나 박사 학위를 가진 사람의 주요 식별자는 무엇이며, 박사 학위와 학사 학위를 가진 사람들은 어떻게 다릅니까?"라고 물을 수 있습니다.

C4.5와 같은 표준 분류기 알고리즘에는 클래스 중요도의 개념이 없습니다(즉, 클래스가 "좋은"지 "나쁜"지 알 수 없습니다).이러한 학습자는 원하는 특정 클래스에 대한 예측을 치우치거나 필터링할 수 없습니다.대조도 집합 학습의 목표는 그룹 간의 의미 있는 차이를 발견하는 것이므로, 학습된 규칙을 특정 분류에 적용할 수 있는 것이 유용하다.MINWAL이나[4] TAR 알고리즘 [5][6][7]패밀리와 같은 여러 대조도 집합 학습자는 학습된 이론을 특정 청중이 관심 있는 결과에 집중시키기 위해 각 클래스에 가중치를 할당합니다.따라서 대조도 집합 학습은 가중치 수업 [8]학습의 한 형태로 간주될 수 있다.

예:슈퍼마켓 구매

표준 분류, 연관 규칙 학습 및 대조 집합 학습 간의 차이는 간단한 슈퍼마켓 비유로 설명할 수 있습니다.다음 작은 데이터 집합에서 각 행은 슈퍼마켓 트랜잭션이며 각 "1"은 해당 항목이 구매되었음을 나타냅니다("0"은 해당 항목이 구매되지 않았음을 나타냅니다).

햄버거. 고구마 푸아그라 양파 샴페인 구입 목적
1 1 0 1 0 쿡아웃
1 1 0 1 0 쿡아웃
0 0 1 0 1 기념일
1 1 0 1 0 쿡아웃
1 1 0 0 1 프랫 파티

이 데이터를 보면

  • 협회 규칙 학습은 양파와 감자를 함께 사는 고객들이 햄버거 고기를 구매할 가능성이 높다는 것을 발견할 수 있다.
  • 분류는 양파, 감자, 햄버거 고기를 구입한 고객이 외식용품을 구매하고 있었다는 것을 발견할 수 있다.
  • 콘트라스트 세트의 학습에서는, 외식 쇼핑과 기념일 저녁 쇼핑의 주된 차이는, 외식 상품을 구입하는 고객이 양파, 감자, 햄버거 고기를 구입하는 것(푸아그라나 샴페인은 구입하지 않는 것)인 것을 알 수 있습니다.

치료 학습

치료 학습은 단일 바람직한 그룹을 취하여 나머지 바람직하지 않은 그룹과 비교하는 가중 대조 집합 학습의 한 형태이다(만족 수준은 가중 클래스로 [5]표현된다).결과적인 "치료"는 적용 시 원하는 결과로 이어지는 일련의 규칙을 제안합니다.

치료 학습은 다음과 같은 제약을 통해 표준 대조도 집합 학습과 다릅니다.

  • 치료 학습은 모든 그룹 간의 차이를 찾는 것이 아니라 초점을 맞출 특정 그룹을 지정하고, 원하는 그룹에 가중치를 적용하고, 나머지 그룹을 하나의 "희망되지 않은" 범주로 묶는다.
  • 치료 학습은 최소한의 이론에 초점을 맞춘다.실제로 치료는 최대 4가지 제약으로 제한된다(즉, 치료 학습자는 로켓이 스케이트보드와 다른 이유를 모두 기술하는 대신 통계적으로 유의한 높은 수준의 로켓을 예측하는 1 - 4가지 주요 차이를 기술한다).

단순성에 초점을 맞추는 것은 치료 학습자에게 중요한 목표입니다.치료 학습은 학급 [8]분포에 가장 큰 영향을 미치는 작은 변화를 추구합니다.

개념적으로 치료 학습자는 모든 속성에 대한 값 범위의 가능한 모든 하위 집합을 탐색합니다.이러한 검색은 실제로 실행할 수 없는 경우가 많기 때문에 치료 학습은 종종 속성 범위를 신속하게 제거하고 무시하는 데 초점을 맞춥니다. 속성 범위를 적용하면 원하는 클래스가 [7]소수인 클래스 분포로 이어집니다.

예: 보스턴 주택 데이터

다음 예는 보스턴 시의 주택 데이터 데이터 집합(500개 이상의 예가 포함된 중요하지 않은 공공 데이터 집합)에 대한 치료 학습자 TAR3의 출력을 보여준다.이 데이터 세트에서는, 각 주택에 대해서 여러가지 요인을 수집해, 각 주택의 품질(낮음, 중저음, 중고음, 고음)에 따라서 분류합니다.원하는 클래스는 "high"로 설정되며 다른 클래스는 모두 바람직하지 않은 것으로 분류됩니다.

치료 학습자의 출력은 다음과 같습니다.

기준선 클래스 분포: 낮음: 29% 메드로우: 29% 메드로우: 21% 높음: 21% 권장 치료법: [PTRATIO=[12.6].16), RM=[6.7..9.78)] 새 클래스 분포: 낮음: 0% 중간값: 0% 중간값: 3% 높음: 97%


적용된 처리(규칙)가 없는 경우 원하는 클래스는 클래스 분포의 21%만 나타냅니다.그러나 6.7~9.78개의 방과 12.6~16개의 이웃 부모-교사 비율이 있는 주택에 대해 데이터 세트를 필터링하면 나머지 예제의 97%가 원하는 계층(고품질 주택)으로 분류된다.

알고리즘

콘트라스트 세트 학습을 실행하는 알고리즘은 여러 가지가 있습니다.다음 서브섹션에서는 두 가지 예를 설명합니다.

스투코

STCCO 콘트라스트 세트[1][3] 학습자는 콘트라스트 세트로부터 학습하는 작업을 트리의 루트 노드가 빈 콘트라스트 세트인 트리 검색 문제로 취급합니다.자녀는 (같은 노드를 두 번 방문하는 것을 피하기 위해) 정규적인 속성 순서를 통해 선택된 추가 항목으로 세트를 특화함으로써 추가됩니다.하위 항목은 주어진 순서에서 모든 기존 용어 뒤에 있는 용어를 추가하여 형성됩니다.형성된 트리는 너비 우선 방식으로 검색됩니다.각 레벨의 노드가 지정되면 데이터 세트가 검사되고 각 그룹에 대한 지원이 계산됩니다.그런 다음 각 노드를 검사하여 노드가 중대하고 큰지, 플루닝할 필요가 있는지, 새로운 자아를 생성해야 하는지 여부를 판단합니다.모든 유의한 콘트라스트 세트를 찾은 후, 포스트 프로세서가 사용자에게 보여줄 서브셋을 선택합니다. 즉, 낮은 순서의 간단한 결과가 먼저 표시되고 그 다음 "놀랍고 현저하게 다른"[3] 상위 순서의 결과가 표시됩니다.

지지 계산은 조영 세트 지원이 모든 그룹에 걸쳐 동일하다는 귀무 가설을 테스트한 결과이다(즉, 조영 세트 지원은 그룹 구성원과 무관하다).각 그룹의 지원 카운트는 분할표에서 분석할 수 있는 빈도 값입니다.여기서 각 행은 대조도 세트의 진실 값을 나타내고 각 열 변수는 그룹 멤버쉽 빈도를 나타냅니다.대조도 집합 빈도와 귀무 가설의 비율 사이에 차이가 있는 경우 알고리즘은 비율 차이가 변수 간의 관계를 나타내는지 또는 랜덤 원인에 기인할 수 있는지 여부를 결정해야 합니다.이는 관측 주파수 카운트와 예상 카운트를 비교하는 카이-제곱 테스트를 통해 확인할 수 있습니다.

노드의 모든 전문화가 중대하고 큰 콘트라스트 세트를 가져올 수 없는 경우 노드는 트리에서 플루닝됩니다.프루닝 결정은 다음 사항을 기반으로 합니다.

  • 최소 편차 크기:임의의 두 그룹의 지원 최대 차이는 사용자가 지정한 임계값보다 커야 합니다.
  • 예상되는 셀 주파수:분할표의 예상 셀 주파수는 콘트라스트 세트가 특수화된 경우에만 감소할 수 있습니다.이러한 빈도가 너무 작으면 카이-제곱 검정의 유효성이 위반됩니다.
  • \ \2} :귀무 가설이 참일 때 계산된 통계량의 분포에는 상한이 유지됩니다.이 컷오프에 대응할 수 없게 되면 노드가 플루닝 됩니다.

TAR3

TAR3[6][9] 가중 대조도 세트 학습자는 규칙 세트의 리프트와 지원이라는 두 가지 기본 개념을 기반으로 합니다.

규칙 집합의 해제란 일부 의사결정이 해당 결정을 내린 후 일련의 예에 대해 내리는 변경이다(즉, 규칙의 부과에 대응하여 세분류 분포가 어떻게 변화하는가).TAR3는 각 클래스에 부가된 가중치의 합계에 각 클래스가 발생하는 빈도를 곱한 가장 큰 변화를 일으키는 최소 규칙 집합을 추구합니다.리프트는 규칙 집합이 적용되는 집합의 점수를 기준선 집합의 점수로 나누어 계산한다(즉, 규칙이 적용되지 않음).TAR3 학습자는 리프트 스코어링 기능을 반대로 함으로써 나머지 클래스에 대해서도 선택하고 대상 클래스를 거부할 수 있습니다.

규칙 집합의 해제에만 의존하는 것은 문제가 있다.데이터 노이즈가 잘못되거나 잘못되면 규칙 집합이 과도하게 적합될 수 있습니다.이러한 오버핏 모델은 리프트 점수가 클 수 있지만 데이터 집합 내에서 현재 상태를 정확하게 반영하지는 않습니다.과적합을 피하기 위해 TAR3는 지원 임계값을 사용하여 이 임계값의 잘못된 쪽에 속하는 모든 규칙을 거부합니다.대상 클래스가 지정되면 지원 임계값은 사용자가 제공한 값(일반적으로 0.2)으로, 규칙 집합이 전체 데이터 집합에서 해당 클래스의 주파수에 적용되었을 때 대상 클래스의 빈도 비율과 비교됩니다.TAR3는 이 임계값보다 낮은 지원을 가진 모든 규칙 세트를 거부합니다.

TAR3는 높은 리프트 값과 높은 지원 값을 모두 요구하므로 이상적인 규칙 세트를 반환할 뿐만 아니라 더 작은 규칙 세트를 선호합니다.채택된 규칙이 적을수록, 그러한 규칙을 뒷받침하는 증거가 더 많이 존재할 것이다.

TAR3 알고리즘은 높은 휴리스틱 값을 가진 속성 값 범위에서 규칙 세트만 구축합니다.알고리즘은 먼저 각 속성의 값 범위의 리프트 점수를 결정함으로써 사용할 범위를 결정합니다.그런 다음 이러한 개별 점수가 정렬되고 누적 확률 분포로 변환됩니다.TAR3은 이 분포에서 값을 랜덤으로 선택합니다. 즉, 낮은 점수 범위를 선택할 가능성은 낮습니다.후보 규칙 집합을 작성하려면 여러 범위를 선택하고 결합합니다.그런 다음 이러한 후보 규칙 집합이 채점되고 정렬됩니다.사용자 정의 라운드 수 이후에도 개선이 나타나지 않으면 알고리즘은 종료되고 최상위 점수 규칙 집합을 반환합니다.

레퍼런스

  1. ^ a b Stephen Bay; Michael Pazzani (2001). "Detecting group differences: Mining contrast sets" (PDF). Data Mining and Knowledge Discovery. 5 (3): 213–246. doi:10.1023/A:1011429418057. S2CID 2941550.
  2. ^ G.I. Webb; S. Butler; D. Newlands (2003). On Detecting Differences Between Groups. KDD'03 Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
  3. ^ a b c Stephen Bay; Michael Pazzani (1999). Detecting change in categorical data: mining contrast sets. KDD '99 Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining.
  4. ^ C.H. Cai; A.W.C. Fu; C.H. Cheng; W.W. Kwong (1998). Mining association rules with weighted items (PDF). Proceedings of International Database Engineering and Applications Symposium (IDEAS 98).
  5. ^ a b Y. Hu (2003). Treatment learning: Implementation and application (Master's thesis). Department of Electrical Engineering, University of British Columbia.
  6. ^ a b K. Gundy-Burlet; J. Schumann; T. Barrett; T. Menzies (2007). Parametric analysis of ANTARES re-entry guidance algorithms using advanced test generation and data analysis. In 9th International Symposium on Artificial Intelligence, Robotics and Automation in Space.
  7. ^ a b Gregory Gay; Tim Menzies; Misty Davies; Karen Gundy-Burlet (2010). "Automatically Finding the Control Variables for Complex System Behavior" (PDF). Automated Software Engineering. 17 (4).
  8. ^ a b T. Menzies; Y. Hu (2003). "Data Mining for Very Busy People" (PDF). IEEE Computer. 36 (11): 22–29. doi:10.1109/mc.2003.1244531.
  9. ^ J. Schumann; K. Gundy-Burlet; C. Pasareanu; T. Menzies; A. Barrett (2009). Software V&V support by parametric analysis of large software simulation systems. Proceedings of the 2009 IEEE Aerospace Conference.