기술나눔

군집분석방법(3)

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina


5. 클러스터링의 품질 평가

군집 분석은 데이터 집합을 하위 집합으로 분해하는 것으로, 각 하위 집합을 클러스터라고 하며, 모든 하위 집합의 집합을 개체 집합의 클러스터라고 합니다. 좋은 클러스터링 알고리즘은 고품질 클러스터와 고품질 클러스터를 생성해야 합니다. 즉, 클러스터 내의 전반적인 유사성은 가장 높고 클러스터 간의 전반적인 유사성은 가장 낮습니다.많은 클러스터링 알고리즘에는 다음이 포함되어 있습니다. kk케이-평균화 알고리즘, DBSCAN 알고리즘 등은 모두 사용자가 클러스터에 포함된 클러스터 수를 미리 지정해야 합니다. kk케이, 따라서 k의 간단한 추정 방법은 아래에서 논의됩니다.

(1) 클러스터 수 추정

다음과 같은 많은 클러스터링 알고리즘 kk케이-평균화 알고리즘, DIANA 알고리즘 등도 미리 클러스터 수를 지정해야 함 kk케이,그리고 kk케이의 값은 클러스터링 품질에 큰 영향을 미칩니다. 그러나 클러스터 수는 미리 결정되어야 합니다. kk케이 쉬운 일이 아닙니다. 먼저 두 가지 극단적인 경우를 고려해 볼 수 있습니다.
(1) 전체 데이터 세트를 넣습니다. 봄 여름 시즌에스클러스터로 간주됩니다. 케이 = 1 케이 = 1케이=1, 이는 간단하고 편리해 보이지만 이 클러스터 분석의 결과는 가치가 없습니다.
(2) 데이터 세트 넣기 봄 여름 시즌에스의 각 객체는 클러스터로 처리됩니다. k = ∣ S ∣ = nk=|S|=n케이=에스=N , 따라서 가장 세밀한 클러스터링을 생성합니다. 따라서 각 군집에는 군집 내 차이가 없으며 군집 내 유사도는 가장 높은 수준에 도달합니다.하지만 이런 종류의 클러스터링은 다음 용도로 사용할 수 없습니다. 봄 여름 시즌에스에 대한 정보를 제공하십시오 봄 여름 시즌에스일반적인 설명.
클러스터의 수를 알 수 있다. kk케이최소한 만족해야 한다 2 ≤ k ≤ n − 1 2≤k≤n-12케이N1, 그러나 클러스터 수 kk케이정확히 어떤 가치가 가장 적절한지는 여전히 모호합니다.
일반적으로 고려하면, kk케이의 값은 데이터 세트 분포의 모양과 규모, 사용자가 요구하는 클러스터링 분해능에 따라 추정할 수 있으며, 학자들은 엘보우법, 교차 검증법, 정보 이론 등 다양한 추정 방법을 사용하고 있습니다. 기반 방법 등
간단하고 일반적으로 사용되는 kk케이가치 실증적 추정 방법은N객체의 데이터 세트, 클러스터링된 클러스터 수 kk케이선택하다 명 2N2 2N 적절합니다.현재 평균 기대치 하에서 각 클러스터는 대략적으로 2n제곱{2n}2N 사물.이를 바탕으로 일부 사람들은 추가 제한, 즉 클러스터 수를 제안했습니다. k &lt; nk케이<N
예를 들어 숫자 = 8 숫자 = 8N=8, 클러스터 수 케이 = 2 케이 = 2케이=2 이고, 평균적으로 클러스터당 4개의 포인트가 있으며, 추가 경험식에 따르면 k &lt; 2.83 k&lt; 2.83 이다케이<2.83 .클러스터 수에 대한 이 두 가지 정보를 사용하여 kk케이실험식은 예 10-5에서 한쪽으로 설명되는 것 같습니다. 케이 = 2 케이 = 2케이=2 가장 적절한 클러스터 수입니다.

(2) 외부 품질 평가

클러스터 수를 잘 추정한 경우 kk케이, 하나 이상의 클러스터링 방법을 사용할 수 있습니다. 예를 들면 다음과 같습니다. kk케이 -평균 알고리즘, 응집 계층적 알고리즘 또는 DBSCAN 알고리즘은 알려진 데이터 세트에 대한 클러스터 분석을 수행하고 다양한 클러스터링 결과를 얻습니다. 이제 문제는 어떤 방법이 더 나은 클러스터링 결과를 내는지, 즉 서로 다른 방법으로 생성된 클러스터링 결과를 어떻게 비교하느냐 하는 것입니다. 이것이 클러스터링의 품질 평가입니다.
현재 클러스터링의 품질 평가를 위해 선택할 수 있는 방법은 많지만 일반적으로 외부(외부) 품질 평가와 내부(내재) 품질 평가의 두 가지 범주로 나눌 수 있습니다.
외부 품질 평가는 일반적으로 전문가가 구성한 데이터 세트에 이상적인 클러스터가 이미 존재한다고 가정하고 이를 특정 알고리즘의 클러스터링 결과와 일반적으로 사용되는 벤치마크 방법으로 비교합니다. 클래스 정밀도에 대한 두 가지 일반적인 방법입니다.

1. 클러스터링 엔트로피 방법

가상 데이터 세트 S = { X 1 , X 2 , … , X n } S = { X_1, X_2, … , X_n }에스={엑스1,엑스2,,엑스N},그리고 T = { T 1 , T 2 , … , T m } T = { T_1 , T_2 ,… , T_m }={1,2,,} 전문가들이 제시한 이상적인 표준 클러스터링이며, C = { C 1 , C 2 , … , C k } C = { C_1 , C_2 , … , C_k }={1,2,,케이} 에 대한 알고리즘에 의해 결정됩니다. 봄 여름 시즌에스의 클러스터, 그 다음 클러스터의 경우 씨아이씨아이기준 클러스터링과 비교 티티클러스터링 엔트로피는 다음과 같이 정의됩니다.
E ( C i ∣ T ) = − ∑ j = 1 m ∣ C i ∩ T j ∣ ∣ C i ∣ log ⁡ 2 ∣ C i ∩ T j ∣ ∣ C i ∣ (10-20) E(C_i|T)=-sum_{j=1}^mfrac{|C_icap T_j|}{|C_i|}log_2frac{|C_icap T_j|}{|C_i|}태그{10-20}이자형()=제이=1제이봐라g2제이(10-20) 그리고 참조벤치마크 정보 티티전체 클러스터링 엔트로피는 모든 클러스터로 정의됩니다. 씨아이씨아이벤치마크 정보 티티클러스터링 엔트로피의 가중 평균은 다음과 같습니다.
E(C) = 1 ∑ i = 1 k ∣ C i ∣ ∑ i = 1 k ∣ C i ∣ × E(C i ∣ T ) (10-21) E(C)=frac{1}{mathop{sum}limits_{i=1}^k|C_i|}sum_{i=1}^k|C_i|times E(C_i|T)tag{10-21}이자형()==1케이1=1케이×이자형()(10-21) 클러스터링 엔트로피 방법은 다음과 같이 믿습니다. 이(씨) 이(씨)이자형() 값이 작을수록 참조기준선 대비 티티클러스터링 품질이 높아집니다.
식 (10-21)의 오른쪽에 첫 번째 항의 분모가 있다는 점은 주목할 가치가 있습니다. ∑ i = 1 k ∣ C i ∣케이=1|| =1케이 각 클러스터의 요소 수의 합이며 사용할 수 없습니다.N 교체.왜냐면, 그럴 때만 참조파티셔닝 클러스터인 경우 분모는 다음과 같습니다.N, DBSCAN 클러스터링과 같은 일반적인 클러스터링 방법의 분모는 다음보다 작을 수 있습니다.N

2. 클러스터링 정확도

군집화 정확도(정밀도) 평가의 기본 아이디어는 군집 내 가장 많은 수의 범주를 군집의 범주 레이블로 사용하는 것, 즉 군집에 대한 것입니다. 씨아이씨아이,존재하는 경우 티 제이 티_제이제이만들다 ∣ C i ∩ T j ∣ = 최대 ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } |C_icap T_j|=최대{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}제이=최대{1,2,,}, 그것은 것으로 간주됩니다 씨아이씨아이카테고리는 티 제이 티_제이제이 .따라서 클러스터는 씨아이씨아이벤치마크 정보 티티정확도는 다음과 같이 정의됩니다.
J(C_i∣T) = 최대⁡ { ∣C_i∩T1∣, ∣C_i∩T2∣, ⋯, ∣C_i∩Tm∣} ∣C_i∣(10-22) J(C_i|T)=frac{max{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}}{|C_i|}태그{10-22}제이()=최대{1,2,,}(10-22) 그리고 참조벤치마크 정보 티티전체 정확도는 모든 클러스터에 대해 정의됩니다. 씨아이씨아이벤치마크 정보 티티클러스터링 정확도의 가중 평균, 즉
J(C) = 1 ∑ i = 1 k ∣ C i ∣ ∑ i = 1 k ∣ C i ∣ × J(C i ∣ T ) (10-23) J(C)=frac{1}{mathop{sum}limits_{i=1}^k|C_i|}sum_{i=1}^k|C_i|times J(C_i|T)tag{10-23}제이()==1케이1=1케이×제이()(10-23) 클러스터링 정확도 방법은 다음과 같이 믿습니다. 제이(씨)제이(씨)제이() 값이 클수록 클러스터링 참조기준선 대비 티티클러스터링 품질이 높아집니다.
게다가 일반적으로 1 − J(C) 1-J(C)1제이() ~라고 불리는 참조벤치마크 정보 티티 전체 오류율.따라서 클러스터링 정확도는 제이(씨)제이(씨)제이() 크거나 전반적인 오류율 1 − J(C) 1-J(C)1제이() 작다는 것은 클러스터링 알고리즘이 서로 다른 범주의 개체를 서로 다른 클러스터로 더 잘 클러스터링할 수 있음을 보여줍니다. 즉, 클러스터링 정확도가 높습니다.

(3) 내부품질평가

내부 품질 평가에 대해 알려진 외부 벤치마크는 없으며 데이터 세트만 사용됩니다. 봄 여름 시즌에스클러스터링 참조클러스터의 본질적인 특성과 크기를 평가하려면 참조 품질. 즉, 클러스터링 효과는 일반적으로 클러스터 내 평균 유사도, 클러스터 간 평균 유사도 또는 전체 유사도를 계산하여 평가합니다.
내부 품질 평가는 클러스터링 알고리즘과 관련이 있으며 클러스터링 효과의 품질을 평가하거나 최적의 클러스터링 수를 판단하는 데 주로 사용됩니다. 따라서 클러스터링 효율성은 일반적으로 클러스터 내 거리와 클러스터 간 거리의 비율로 측정됩니다. 이 유형의 일반적으로 사용되는 표시기에는 CH 표시기, Dunn 표시기, I 표시기, Xie-eni 표시기 등이 포함됩니다.

1. 채널 표시기

CH 지수는 Calinski-Harabasz 지수의 약어입니다. 먼저 각 군집 지점과 군집 중심 사이의 거리의 제곱합을 계산하여 클래스 내 친밀도를 측정한 다음 거리의 제곱합을 계산합니다. 각 클러스터 중심점과 측정할 데이터 세트의 중심점 사이의 데이터 세트의 분리, 분리와 근접성의 비율이 CH 지수입니다.
설정 X‾ i 오버라인{X}_i엑스클러스터를 나타냅니다 참조중심점(평균), X‾ 오버라인{X}엑스데이터 세트를 나타냅니다. 봄 여름 시즌에스의 중심점 d ( X‾i , X‾ ) d(윗줄{X}_i,윗줄{X})(엑스,엑스) ~을 위한 X‾ i 오버라인{X}_i엑스도착하다 X‾ 오버라인{X}엑스의 특정 거리 함수를 사용한 후 클러스터링 참조중간 클러스터의 컴팩트함은 다음과 같이 정의됩니다.
트레이스(A) = ∑ i = 1 k ∑ X j ∈ C id( X j , X‾ i ) 2 (10-24) 텍스트{트레이스}(A) = sum_{i=1}^ksum_{X_jin C_i}d(X_j,overline{X}_i)^2태그{10-24}추적하다()==1케이엑스제이(엑스제이,엑스)2(10-24) 따라서 Trace(A)는 클러스터입니다. 참조 클러스터 중심 사이의 거리 제곱의 합입니다.그리고 클러스터링 참조분리 정도는 다음과 같이 정의됩니다.
추적(B) = ∑ i = 1 k ∣ C i ∣ d ( X‾ i , X‾ ) 2 (10-25) 텍스트{추적}(B)=sum_{i=1}^k|C_i|d(윗줄{X}_i,윗줄{X})^2태그{10-25}추적하다()==1케이(엑스,엑스)2(10-25) 즉, Trace(B)는 클러스터링을 하고 있습니다. 참조각 클러스터 중심점 봄 여름 시즌에스의 중심점으로부터의 거리 제곱의 가중합입니다.
이것으로부터 만약에 N = ∑ i = 1 k ∣ C i ∣N=케이=1|| N==1케이 그런 다음 CH 표시기는 다음과 같이 정의될 수 있습니다.
V CH(k) = 트레이스(B)/(k-1) 트레이스(A)/(N-k) (10-26) V_{text{CH}}(k)=frac{text{트레이스}(B)/(k-1)}{text{트레이스}(A)/(Nk)}태그{10-26}V(케이)=추적하다()/(N케이)추적하다()/(케이1)(10-26) 식 (10-26)은 일반적으로 다음 두 가지 상황에서 사용됩니다.
(1) 두 알고리즘으로 얻은 클러스터링이 더 나은지 평가합니다.
데이터 세트를 분석하기 위해 두 가지 알고리즘이 사용된다고 가정합니다. 봄 여름 시즌에스클러스터 분석이 수행되었으며 두 개의 서로 다른 클러스터(둘 다 다음을 포함함) kk케이클러스터), 더 큰 CH 값에 해당하는 클러스터링이 더 좋습니다. 왜냐하면 CH 값이 클수록 클러스터의 각 클러스터가 자체에 더 가깝고 클러스터가 더 분산되어 있음을 의미하기 때문입니다.
(2) 동일한 알고리즘으로 얻은 클러스터 수가 다른 두 클러스터 중 어느 것이 더 나은지 평가합니다.
알고리즘에 데이터 세트가 있다고 가정합니다. 봄 여름 시즌에스클러스터 분석을 수행하여 클러스터 수를 다음과 같이 얻었습니다. 케이 1 케이_1케이1그리고 비 2 비_22 두 클러스터 중 CH 값이 클수록 클러스터링 결과가 더 좋으며 이는 이 클러스터에 해당하는 클러스터 수가 더 적합하다는 의미이기도 합니다.따라서 식 (10-26)을 반복적으로 적용하면 데이터 세트를 얻을 수도 있습니다. 봄 여름 시즌에스클러스터링을 위한 최적의 클러스터 수입니다.

2. 던 지표

Dunn 지표는 클러스터를 사용합니다. 씨아이씨아이클러스터 포함 씨제이 씨제이제이사이의 최소 거리 ds ( C i , C j ) d_s(C_i, C_j)에스(,제이) 모든 클러스터 중에서 가장 큰 클러스터 직경을 사용하면서 클러스터 간 분리를 계산합니다. 최대 ⁡ { Φ ( C 1 ), Φ ( C 2 ), . . . , Φ ( C k ) } 최대 { varPhi(C_1), varPhi(C_2),..., varPhi(C_k)}최대{Φ(1),Φ(2),...,Φ(케이)} 클러스터 내의 견고성을 특성화하기 위해 Dunn 지수는 전자와 후자 사이의 비율의 최소값입니다.
VD(k) = min⁡ i ≠ jds(Ci, Cj)max⁡ { Φ(C1), Φ(C2), . . . , Φ ( C k ) } (10-27) V_D(k)=min_{i≠j}frac{d_s(C_i,C_j)}{max{varPhi(C_1), varPhi(C_2),...,varPhi (C_k)}}태그{10-27}V(케이)==제이최대{Φ(1),Φ(2),...,Φ(케이)}에스(,제이)(10-27) Dunn 값이 클수록 클러스터 간의 거리가 멀고 해당 클러스터링이 더 좋아집니다.CH 평가 지수와 유사하게 Dunn 지수는 서로 다른 알고리즘으로 얻은 클러스터의 품질을 평가하는 데 사용할 수 있으며, 동일한 알고리즘으로 클러스터 수가 다른 클러스터를 얻은 것이 더 나은지 평가하는 데에도 사용할 수 있습니다. 찾는 데 사용할 수 있습니다. 봄 여름 시즌에스최적의 클러스터 수.

6. 이상치 채굴

이상값은 대부분의 데이터에서 크게 벗어나는 데이터 세트의 특수 데이터입니다. 앞서 소개한 분류, 클러스터링 등 데이터 마이닝 알고리즘의 초점은 대부분의 데이터에 적용되는 규칙적인 패턴을 찾는 것입니다. 따라서 많은 데이터 마이닝 알고리즘은 마이닝을 구현할 때 이상값의 영향을 줄이거나 제거하려고 시도합니다. 또는 노이즈로 무시되지만 많은 실제 응용에서 사람들은 이상점의 편차가 무작위 요인에 의해 발생하는 것이 아니라 완전히 다른 메커니즘에 의해 발생할 수 있다고 의심하며 특별한 분석 및 활용을 위해 이를 파헤쳐야 합니다. 예를 들어 보안 관리, 위험 제어 등의 응용 분야에서는 일반 데이터 패턴보다 이상값을 식별하는 패턴이 더 중요합니다.

(1) 관련사항 개요

Outlier라는 단어는 일반적으로 Outlier로 번역되지만 이상치로도 번역됩니다. 그러나 격리된 지점, 비정상적인 지점, 새로운 지점, 편차 지점, 예외 지점, 노이즈, 비정상적인 데이터 등과 같은 다양한 응용 상황에는 많은 별칭이 있습니다. 이상치 마이닝은 중국 문헌에서 이상치 데이터 마이닝, 이상치 데이터 탐지, 이상치 데이터 마이닝, 예외 데이터 마이닝, 희귀 사건 마이닝과 같은 유사한 용어를 사용합니다.

1. 이상값 생성

(1) 데이터는 사기, 침입, 질병 발생, 특이한 실험 결과 등으로 인한 이상 현상에서 비롯됩니다. 예를 들어, 어떤 사람의 평균 전화 요금은 약 200위안이지만 어떤 달에는 갑자기 수천 위안으로 증가합니다. 어떤 사람의 신용 카드는 일반적으로 한 달에 약 5,000위안을 소비하지만 어떤 달에는 소비량이 30,000위안을 초과합니다. 이러한 이상값은 일반적으로 데이터 마이닝에서 상대적으로 흥미롭고 적용의 핵심 포인트 중 하나입니다.
(2) 기후변화, 고객의 새로운 구매 패턴, 유전적 변이 등 데이터 유통의 자연적 특성을 반영하여 데이터 변수의 고유한 변화로 인해 발생합니다. 또한 흥미로운 초점 영역 중 하나입니다.
(3) 데이터 측정 및 수집 오류는 주로 사람의 실수, 측정 장비의 고장 또는 소음의 존재로 인해 발생합니다. 예를 들어, 특정 과목에서 학생의 성적이 -100인 것은 프로그램에서 설정한 기본값 때문일 수 있습니다. 회사의 최고 관리자의 급여가 일반 직원의 급여보다 훨씬 높기 때문에 이상치처럼 보일 수 있습니다. 합리적인 데이터.

2. 이상치 채굴 문제

일반적으로 이상치 마이닝 문제는 세 가지 하위 문제로 분해하여 설명할 수 있습니다.
(1) 이상치 정의
아웃라이어는 실무적인 문제와 밀접한 관련이 있기 때문에 어떤 데이터가 아웃라이어인지 비정상 데이터인지 명확하게 정의하는 것이 아웃라이어 마이닝의 전제이자 일차적인 작업입니다. 일반적으로 아웃라이어에 대한 정확한 분석을 제공하기 위해서는 도메인 전문가의 경험과 지식을 결합하는 것이 필요합니다. . 적절한 설명이나 정의를 제공하십시오.
(2) 채굴 이상값
이상점을 명확하게 정의한 후, 정의된 이상점을 효과적으로 식별하거나 마이닝하기 위해 어떤 알고리즘을 사용할 것인지가 이상점 마이닝의 핵심 작업입니다. 이상치 마이닝 알고리즘은 일반적으로 사용자의 관심을 끌기 위해 데이터에 반영될 수 있는 패턴 관점에서 의심스러운 이상치 데이터를 사용자에게 제공합니다.
(3) 이상치 이해
마이닝 결과의 합리적인 설명, 이해 및 실제 적용에 대한 안내는 아웃라이어 마이닝의 목표입니다. 이상값이 생성되는 메커니즘이 불확실하므로, 이상값 마이닝 알고리즘으로 검출한 '이상값'이 실제로 실제 이상 행위에 해당하는지 여부는 이상값 마이닝 알고리즘으로는 설명할 수 없고, 이상값 마이닝 알고리즘으로만 설명할 수 있습니다. . 업계 또는 도메인 전문가가 지침을 이해하고 설명합니다.

3. 이상치의 상대성

이상값은 대부분의 데이터에서 분명히 벗어나는 데이터 세트의 특수 데이터이지만 "분명히"와 "대부분"은 상대적입니다. 즉, 이상값은 다르지만 상대적입니다. 따라서 이상값을 정의하고 마이닝할 때 고려해야 할 몇 가지 문제가 있습니다.
(1) 글로벌 또는 로컬 이상치
데이터 개체는 로컬 이웃에 비해 이상값일 수 있지만 전체 데이터 세트에 대해서는 그렇지 않을 수 있습니다. 예를 들어, 키가 1.9미터인 학생은 우리 학교 수학 전공 1급에서는 특이점이지만 야오밍과 같은 프로 선수를 포함해 전국의 사람들 사이에서는 그렇지 않습니다.
(2) 이상치의 수
이상점의 개수는 알 수 없으나 정상점의 개수는 이상점의 개수를 훨씬 초과해야 한다. 즉, 대규모 데이터 세트에서 이상점의 개수가 차지하는 비중이 낮아야 한다는 것이 일반적으로 믿어진다. 이상점의 비율은 5% 미만이거나 1% 미만이어야 합니다.
(3) 점의 이상치 요인
개체가 이상값인지 여부를 보고하기 위해 "예" 또는 "아니요"를 사용할 수 없습니다. 대신 개체의 편차 정도, 즉 이상값 요인(Outlier Factor) 또는 이상값 점수(Outlier Score)를 사용해야 합니다. 데이터의 그룹 이탈 정도를 특성화한 후, 특정 임계값 이상의 이상 요인을 포함하는 개체를 필터링하고 이를 의사 결정자 또는 도메인 전문가에게 제공하여 이해 및 설명을 제공하고 실무에 적용합니다.

(2) 거리 기반 방법

1. 기본 개념

정의 10-11 양의 정수가 있습니다. kk케이, 물체 더블 엑스엑스~의 kk케이- 가장 가까운 이웃 거리는 다음 조건을 만족하는 양의 정수입니다. dk(X) d_k(X)케이(엑스)
(1) 제외 더블 엑스엑스또한, 최소한 kk케이사물와이풀다 d(X, Y) ≤ dk(X) d(X, Y)≤d_k(X)(엑스,와이)케이(엑스)
(2) 제외 더블 엑스엑스또한, 최대 케이 − 1 케이-1케이1 사물와이풀다 d(X, Y) &lt; dk(X)d(X,Y)(엑스,와이)<케이(엑스)
~에 d(X, Y) d(X, Y)의 값은 다음과 같다.(엑스,와이) 객체이다 더블 엑스엑스그리고와이그들 사이에 어떤 거리 기능이 있습니다.

물체의 kk케이- 최근접 이웃 거리가 클수록 객체가 대부분의 데이터에서 멀리 떨어져 있을 가능성이 높으므로 객체가 더블 엑스엑스~의 kk케이-가장 가까운 이웃 거리 dk(X) d_k(X)케이(엑스) 이상값 요인으로 사용됩니다.

정의 10-12 만들다 D(X, k) = { Y ∣ d(X, Y) ≤ dk(X) ∧ Y ≠ X } D(X, k)={Y|d(X, Y)≤d_k(X)쐐기 Y≠X}(엑스,케이)={와이(엑스,와이)케이(엑스)와이=엑스}, 그런 다음 호출됩니다. D(X, k)는 X, k의 합이다.(엑스,케이) 더블 엑스엑스~의 kk케이-가장 가까운 이웃(도메인).

정의 10-12에서 볼 수 있듯이 D(X, k)는 X, k의 합이다.(엑스,케이) 더블 엑스엑스중심, 거리로 더블 엑스엑스초과하지 않음 dk(X) d_k(X)케이(엑스) 물체와이 으로 구성된 컬렉션입니다. 특별한 주의를 기울일 가치가 있습니다. 더블 엑스엑스그것에 속하지 않는다 kk케이-가장 가까운 이웃, 즉 X ∉ D ( X , k ) X not in D(X, k)엑스/(엑스,케이) . 특히, 더블 엑스엑스~의 kk케이-가장 가까운 이웃 D(X, k)는 X, k의 합이다.(엑스,케이) 포함된 객체의 수가 훨씬 초과할 수 있습니다. kk케이,지금 바로 ∣ D ( X , k ) ∣ ≥ k |D(X, k)|≥k(엑스,케이)케이

정의 10-13 양의 정수가 있습니다. kk케이, 물체 더블 엑스엑스~의 kk케이- 가장 가까운 이웃 이상값 요인은 다음과 같이 정의됩니다.
OF 1 ( X , k ) = ∑ Y ∈ D ( X , k ) d ( X , Y ) ∣ D ( X , k ) ∣ (10-28) 텍스트{OF}_1(X, k)=frac{mathop{sum}limits_{Yin D(X, k)}d(X, Y)}{|D(X, k)|}태그{10-28}1(엑스,케이)=(엑스,케이)와이(엑스,케이)(엑스,와이)(10-28)

2. 알고리즘 설명

주어진 데이터 세트와 가장 가까운 이웃 거리의 수에 대해 kk케이, 위의 공식을 사용하여 계산할 수 있습니다. kk케이-최근접 이상값 요인을 큰 것부터 작은 것 순으로 출력합니다. 그 중 이상값 요인이 큰 여러 개체는 일반적으로 그 중에서 이상값일 가능성이 가장 높습니다. , 어느 점이 실제로 이상치인지.

알고리즘 10-8 거리 기반 이상치 탐지 알고리즘
입력: 데이터 세트 봄 여름 시즌에스, 가장 가까운 이웃 거리의 수 kk케이
출력: 의심되는 이상점 및 해당 이상치 요인의 내림차순 목록
(1)반복
(2) 테이크 봄 여름 시즌에스처리되지 않은 개체 더블 엑스엑스
(3) 알았어 더블 엑스엑스~의 kk케이-가장 가까운 이웃 D(X, k)는 X, k의 합이다.(엑스,케이)
(4) 계산 더블 엑스엑스~의 kk케이-최근접 이웃 이상치 요인 OF 1 ( X , k ) 텍스트{OF}_1(X,k)1(엑스,케이)
(5)까지 봄 여름 시즌에스의 모든 포인트가 처리되었습니다.
(6) 예 OF 1 ( X , k ) 텍스트{OF}_1(X,k)1(엑스,케이)내림차순으로 정렬하여 출력 ( X , OF 1 ( X , k ) ) (X, 텍스트 {OF}_1 (X, k))(엑스,1(엑스,케이))

3. 계산 예

예제 10-12 11개의 포인트로 구성된 2차원 데이터 세트 봄 여름 시즌에스이는 표 10-10에 주어진다. 케이 = 2 케이 = 2케이=2, 유클리드 거리 제곱 계산을 사용합니다. X 7 , X 10 , X 11 X_7, X_{10},X_{11}엑스7,엑스10,엑스11 다른 모든 점에 대한 이상치 요인입니다.

여기에 이미지 설명을 삽입하세요.
풀다: 알고리즘의 원리를 직관적으로 이해하기 위해, 봄 여름 시즌에스의 데이터 객체는 아래 그림(10-27)의 평면에 표시됩니다.

여기에 이미지 설명을 삽입하세요.
다음은 지정된 지점과 다른 지점의 이상값 요인을 각각 계산합니다.

(1) 계산 대상 엑스 7 엑스_7엑스7이상치 요인
그림에서 알 수 있듯이 거리가 X 7 = ( 6 , 8 ) X_7=(6,8)엑스7=(6,8) 가장 가까운 지점은 X 10 = ( 5 , 7 ) X_{10}=(5,7)엑스10=(5,7),그리고 d(X7, X10) = 1.41 d(X_7, X_{10}) = 1.41(엑스7,엑스10)=1.41, 다른 가장 가까운 지점은 X 11 = ( 5 , 2 ) X_{11}=(5,2)엑스11=(5,2) X 9 = ( 3 , 2 ) X_9 = ( 3, 2 )엑스9=(3,2) X 8 = ( 2 , 4 ) X_8=(2,4)엑스8=(2,4)
계획된 d(X7, X11) = 6.08 d(X_7, X_{11})=6.08(엑스7,엑스11)=6.08 d(X7, X9) = 6.71 d(X_7, X_9)=6.71(엑스7,엑스9)=6.71 d(X7, X8) = 5.66 d(X_7, X_8)=5.66(엑스7,엑스8)=5.66
왜냐하면 케이 = 2 케이 = 2케이=2,그래서 d2(X7) = 5.66 d_2(X7)=5.662(엑스7)=5.66, 정의 10-11에 따르면 우리는 D(X7,2) = {X10, X8} D(X7,2) = {X10, X8}(엑스7,2)={엑스10,엑스8}
식(10-28)에 따르면, 엑스 7 엑스_7엑스7이상치 요인
OF 1 ( X 7 , 2 ) = ∑ Y ∈ N ( X 7 , 2 ) d ( X 7 , Y ) ∣ N ( X 7 , k ) ∣ = d ( X 7 , X 10 ) + d ( X 7 , X 8 ) 2 = 1.41 + 5.66 2 = 3.541(엑스7,2)=와이N(엑스7,2)(엑스7,와이)|N(엑스7,케이)|=(엑스7,엑스10)+(엑스7,엑스8)2=1.41+5.662=3.54 1(엑스7,2)=N(엑스7,케이)와이N(엑스7,2)(엑스7,와이)=2(엑스7,엑스10)+(엑스7,엑스8)=21.41+5.66=3.54(2) 계산 대상 엑스 10 엑스_{10}엑스10이상치 요인 OF 1 ( X 10 , 2 ) = 2.83 텍스트 {OF}_1(X_{10},2)=2.83}1(엑스10,2)=2.83

(3) 계산 대상 엑스 11 엑스_{11}엑스11이상치 요인 OF 1 ( X 11 , 2 ) = 2.5 텍스트 {OF}_1(X_{11},2) = 2.51(엑스11,2)=2.5

(4) 계산 대상 엑스 5 엑스_{5}엑스5이상치 요인 OF 1 ( X 5 , 2 ) = 1 텍스트 {OF}_1(X_{5},2) = 11(엑스5,2)=1

마찬가지로 나머지 개체의 이상값 요인도 계산할 수 있습니다. 다음 표(10-11)를 참조하세요.

여기에 이미지 설명을 삽입하세요.
4. 이상치 요인 임계값

~에 따르면 kk케이 -최근접 이웃 이론에서는 이상값 요인이 클수록 이상값일 가능성이 높아집니다. 따라서 이상값과 정상점을 구별하기 위한 임계값을 지정해야 합니다. 가장 간단한 방법은 이상점의 수를 지정하는 것이지만 이 방법은 너무 단순하여 일부 실제 이상점을 놓치거나 가능한 이상점에 너무 많은 정상점을 부여하여 도메인 전문가나 의사결정자가 어려움을 겪는 경우가 있습니다. 특이치를 이해하고 해석하는 데 있습니다.
(1) 이상치 요인 분할 임계값 방법은 먼저 이상치 요인을 내림차순으로 정렬하고, 동시에 이상치 요인에 따라 데이터 개체의 번호를 오름차순으로 다시 매깁니다.
(2) 이상치 요인에 기초 OF 1 ( X , k ) 텍스트{OF}_1(X,k)1(엑스,케이) 는 세로좌표이고, 이상치 요인 일련번호는 가로좌표, 즉 (일련번호, 1개의 텍스트{OF}_11값)을 평면에 표시하고 연결하여 증가하지 않는 폴리라인을 형성하며, 폴리라인이 급격하게 감소하고 완만하게 감소하면서 교차하는 지점이 이상값 인수가 더 적은 개체에 해당하는 것으로 나타났습니다. 이 임계값보다 크거나 같은 것은 정상 개체이고, 나머지는 가능한 이상값입니다.

예제 10-13 예제 10-12의 데이터 세트 봄 여름 시즌에스 , 이상치 요인은 표 10-11에 내림차순 및 일련번호로 요약되어 있습니다. 이상점 요인 분할 임계값 방법을 기반으로 이상점의 임계값을 찾아보세요.

풀다: 먼저 (일련번호, 1개의 텍스트{OF}_11 값)을 평면의 점으로 표시하고 폴리라인으로 연결합니다. 아래 그림 10-28과 같습니다.

여기에 이미지 설명을 삽입하세요.
그런 다음 그림 10-28을 보면 네 번째 점(4, 1.27)의 왼쪽에 있는 폴리라인이 매우 급격하게 떨어지는 반면 오른쪽에 있는 폴리라인은 매우 완만하게 떨어지는 것을 볼 수 있습니다. 따라서 이상치 인자 1.27이 선택됩니다. 한계점.왜냐하면 X 7 、 X 10 X_7、X_{10}엑스7엑스10 그리고 엑스 11 엑스_{11}엑스11 이상점 요인은 각각 3.54, 2.83, 2.5로 모두 1.27보다 큽니다. 따라서 이 세 점은 이상점일 가능성이 가장 높으며 나머지 점은 일반 점입니다.
그림 10-27을 다시 보면, X 7 、 X 10 X_7、X_{10}엑스7엑스10 그리고 엑스 11 엑스_{11}엑스11 실제로 왼쪽에 있는 밀집된 대다수의 개체에서 멀리 떨어져 있으므로 이를 데이터 세트로 취급합니다. 봄 여름 시즌에스이상치가 합리적입니다.

5. 알고리즘 평가

거리 기반 이상치 검출 방법의 가장 큰 장점은 원리가 간단하고 사용이 용이하다는 점이다. 단점은 주로 다음과 같은 측면에서 나타난다.
(1) 매개변수 kk케이테스트 결과가 매개변수에 미치는 영향을 결정하는 간단하고 효과적인 방법이 선택에 부족합니다. kk케이민감도에 대해 보편적으로 인정되는 분석 결과는 없습니다.
(2) 시간 복잡도는 O ( ∣ S ∣ 2 ) O(|S|^2)영형(에스2), 대규모 데이터 세트에 대한 확장성이 부족합니다.
(3) 글로벌 이상치 요인 임계값을 사용하기 때문에 밀도가 다른 지역의 데이터 세트에서 이상치를 마이닝하기가 어렵습니다.

(3) 상대밀도에 기초한 방법

거리 방법은 전역 이상값 확인 방법이지만 서로 다른 밀도 영역의 데이터 세트를 처리할 수 없습니다. 즉, 로컬 밀도 영역의 이상값을 감지할 수 없습니다. 실제 응용에서는 모든 데이터가 단일 밀도로 분포되지 않습니다. 데이터 세트에 여러 밀도 분포가 포함되어 있거나 서로 다른 밀도 하위 집합이 혼합되어 있는 경우 거리와 같은 전역 이상값 감지 방법은 일반적으로 잘 작동하지 않습니다. 왜냐하면 객체가 이상값인지 여부는 주변 데이터와의 관계에만 의존하는 것이 아니기 때문입니다. 주변의 밀도와 관련이 있습니다.

1. 상대밀도의 개념

밀도 근방의 관점에서 보면, 이상치는 저밀도 지역에 있는 객체이기 때문에 국지적 근방 밀도와 객체의 상대밀도 개념을 도입할 필요가 있다.

정의 10-14 (1) 물체 더블 엑스엑스~의 kk케이- 가장 가까운 이웃 지역 밀도(density)는 다음과 같이 정의됩니다.
dsty(X, k) = ∣ D(X, k) ∣ ∑ Y ∈ D(X, k) d(X, Y) (10-29) 텍스트{dsty}(X, k)=frac{|D(X, k)|}{mathop{sum}limits_{Yin D(X, k)}d(X, Y)}태그{10-29}디스티(엑스,케이)=와이(엑스,케이)(엑스,와이)(엑스,케이)(10-29) (2) 물체 더블 엑스엑스~의 kk케이-최근접 이웃 지역 상대 밀도(Relative Density)
rdsty(X, k) = ∑ Y ∈ D(X, k) dsty(X, k) / ∣ D(X, k) ∣ dsty(X, k) (10-30) text{rdsty}(X, k)=frac{mathop{sum}limits_{Yin D(X, k)}text{dsty}(X, k)/|D(X, k)|}{text{dsty}(X, k)}tag{10-30}rdsty(엑스,케이)=디스티(엑스,케이)와이(엑스,케이)디스티(엑스,케이)/∣(엑스,케이)(10-30) ~에 D(X, k)는 X, k의 합이다.(엑스,케이) 그것은 개체입니다 더블 엑스엑스~의 kk케이- 가장 가까운 이웃(정의 10-12에 제시됨), X와 k의 관계는 다음과 같다.(엑스,케이) 컬렉션의 개체 수입니다.

2. 알고리즘 설명

~에 의해 rdsty ( X , k ) 텍스트 {rdsty}(X, k)rdsty(엑스,케이) 이상치로서 OF 2 ( X , k ) 텍스트 {OF}_2(X, k)2(엑스,케이), 계산은 두 단계로 나뉩니다.
(1) 이웃 수에 따라 kk케이, 각 객체를 계산 더블 엑스엑스~의 kk케이-가장 가까운 이웃 지역 밀도 dsty ( X , k ) 텍스트{dsty}(X,k)디스티(엑스,케이)
(2) 계산 더블 엑스엑스가장 가까운 이웃의 평균 밀도 kk케이-가장 가까운 이웃 지역 상대 밀도 rdsty ( X , k ) 텍스트 {rdsty}(X, k)rdsty(엑스,케이)
데이터 세트는 여러 개의 자연 클러스터로 구성됩니다. 클러스터 내 핵심 지점에 가까운 개체의 상대 밀도는 1에 가까운 반면 클러스터 가장자리 또는 클러스터 외부에 있는 개체의 상대 밀도는 상대적으로 큽니다. 따라서 상대 밀도 값이 클수록 이상치일 가능성이 높아집니다.

알고리즘 10-9 상대밀도 기반 이상치 탐지 알고리즘
입력: 데이터 세트 봄 여름 시즌에스, 가장 가까운 이웃의 수 kk케이
출력: 의심되는 이상점 및 해당 이상치 요인의 내림차순 목록
(1)반복
(2) 테이크 봄 여름 시즌에스처리되지 않은 개체 더블 엑스엑스
(3) 알았어 더블 엑스엑스~의 kk케이-가장 가까운 이웃 D(X, k)는 X, k의 합이다.(엑스,케이)
(4) 활용 D(X, k)는 X, k의 합이다.(엑스,케이)계산하다 더블 엑스엑스밀도 dsty ( X , k ) 텍스트{dsty}(X,k)디스티(엑스,케이)
(5)까지 봄 여름 시즌에스의 모든 포인트가 처리되었습니다.
(6)반복
(7) 테이크 봄 여름 시즌에스첫 번째 개체 더블 엑스엑스
(8) 알았어 더블 엑스엑스상대밀도 rdsty ( X , k ) 텍스트 {rdsty}(X, k)rdsty(엑스,케이)에 할당하고 OF 2 ( X , k ) 텍스트 {OF}_2(X, k)2(엑스,케이)
(9)까지 봄 여름 시즌에스의 모든 개체가 처리되었습니다.
(10) 오른쪽 OF 2 ( X , k ) 텍스트 {OF}_2(X, k)2(엑스,케이)내림차순으로 정렬하여 출력 ( X , OF 2 ( X , k ) ) (X, 텍스트 {OF}_2(X, k))(엑스,2(엑스,케이))

예 10-14 예제 10-12에 주어진 2차원 데이터 세트의 경우 봄 여름 시즌에스 (자세한 내용은 표 10-10 참조) 케이 = 2 케이 = 2케이=2, 유클리드 거리를 계산해 보세요. X 7 , X 10 , X 11 X_7, X_{10},X_{11}엑스7,엑스10,엑스11 동일한 객체의 상대 밀도를 기반으로 하는 이상값 요인입니다.

여기에 이미지 설명을 삽입하세요.
풀다:왜냐하면 케이 = 2 케이 = 2케이=2, 따라서 모든 객체의 2-최근접 이웃 로컬 밀도가 필요합니다.

(1) 표 10-11에서 각 데이터 객체의 2-최근접 이웃을 찾습니다. X_i의 값은 X_i의 값과 같습니다.(엑스,2)
예제 10-12의 동일한 계산 방법에 따르면 다음을 얻을 수 있습니다.
D(X1, 2) = {X2, X3, X5},D(X2, 2) = {X1, X6},D(X3, 2) = {X1, X4},D(X4, 2) = {X3, X5},D(X5, 2) = {X1, X4, X6, X9},D(X6, 2) = {X2, X5, X8},D(X7, 2) = {X10, X8},D(X8, 2) = {X2, X6},D(X9, 2) = {X5, X4 , X 6 },D(X 10, 2) = {X 7, X 8 },D(X 11, 2) = {X 9, X 5 }(엑스1,2)={엑스2,엑스3,엑스5}(엑스2,2)={엑스1,엑스6}              (엑스3,2)={엑스1,엑스4}(엑스4,2)={엑스3,엑스5}       (엑스5,2)={엑스1,엑스4,엑스6,엑스9}(엑스6,2)={엑스2,엑스5,엑스8}(엑스7,2)={엑스10,엑스8}     (엑스8,2)={엑스2,엑스6}               (엑스9,2)={엑스5,엑스4,엑스6}(엑스10,2)={엑스7,엑스8}     (엑스11,2)={엑스9,엑스5} (엑스1,2)={엑스2,엑스3,엑스5}(엑스2,2)={엑스1,엑스6}              (엑스3,2)={엑스1,엑스4}(엑스4,2)={엑스3,엑스5}       (엑스5,2)={엑스1,엑스4,엑스6,엑스9}(엑스6,2)={엑스2,엑스5,엑스8}(엑스7,2)={엑스10,엑스8}     (엑스8,2)={엑스2,엑스6}               (엑스9,2)={엑스5,엑스4,엑스6}(엑스10,2)={엑스7,엑스8}     (엑스11,2)={엑스9,엑스5}

(2) 각 데이터 객체의 국소 밀도를 계산합니다. dsty ( X i , 2 ) 텍스트{dsty}(X_i,2)디스티(엑스,2)

① 계산하다 엑스 1 엑스_1엑스1밀도
왜냐하면 D(X1, 2) = {X2, X3, X5} D(X_1, 2) = {X_2, X_3, X_5}(엑스1,2)={엑스2,엑스3,엑스5}, 그래서 계산 후에 우리는 d(X1, X2) = 1 d(X_1, X_2)=1(엑스1,엑스2)=1 d(X1, X3) = 1 d(X_1, X_3)=1(엑스1,엑스3)=1 d(X1, X5) = 1 d(X_1, X_5)=1(엑스1,엑스5)=1
공식 (10-29)에 따르면 다음을 얻습니다.
dsty(X1, 2) = ∣D(X1, 2) ∣∑Y∈N(X1, 2)d(X1, Y) = ∣N(X1, 2) ∣d(X1, X2) + d(X1, X3) + d(X1, X5) = 31 + 1 + 1 = 1디스티(엑스1,2)=|(엑스1,2)|와이N(엑스1,2)(엑스1,와이)=|N(엑스1,2)|(엑스1,엑스2)+(엑스1,엑스3)+(엑스1,엑스5)=31+1+1=1 디스티(엑스1,2)=와이N(엑스1,2)(엑스1,와이)(엑스1,2)=(엑스1,엑스2)+(엑스1,엑스3)+(엑스1,엑스5)N(엑스1,2)=1+1+13=1

② 계산 엑스 2 엑스_2엑스2밀도
왜냐하면 D(X2, 2) = {X1, X6} D(X_2, 2) = {X_1,X_6}(엑스2,2)={엑스1,엑스6}, 그래서 계산된 d(X2, X1) = 1 d(X_2, X_1) = 1(엑스2,엑스1)=1 d(X2, X6) = 1 d(X_2, X_6) = 1(엑스2,엑스6)=1
공식 (10-29)에 따르면 다음을 얻습니다.
dsty(X2, 2) = ∣D(X2, 2) ∣∑Y∈N(X2, 2)d(X2, Y) = 21+1 = 1디스티(엑스2,2)=|(엑스2,2)|와이N(엑스2,2)(엑스2,와이)=21+1=1 디스티(엑스2,2)=와이N(엑스2,2)(엑스2,와이)(엑스2,2)=1+12=1

다른 데이터 개체의 로컬 밀도도 비슷하게 계산할 수 있습니다(아래 표 10-12 참조).

여기에 이미지 설명을 삽입하세요.
(3) 각 객체의 계산 X 나는 X_i엑스상대밀도 rdsty ( X i , 2 ) 텍스트 {rdsty}(X_i, 2)rdsty(엑스,2), 이를 이상값 요인으로 간주합니다. 2개의 텍스트{OF}_22
① 계산하다 엑스 1 엑스_1엑스1상대밀도
상대밀도 공식(10-30)에 따라 표 10-12의 각 물체의 밀도값을 이용하면 다음과 같다.
rdsty ( X 1 , 2 ) = ∑ Y ∈ N ( X 1 , 2 ) dsty ( Y , 2 ) / ∣ N ( X 1 , 2 ) ∣ dsty ( X 1 , 2 ) = ( 1 + 1 + 1 ) / 3 1 = 1 = OF 2 ( X 1 , 2 )rdsty(엑스1,2)=와이N(엑스1,2)디스티(와이,2)/|N(엑스1,2)|디스티(엑스1,2)=(1+1+1)/31=1=2(엑스1,2) rdsty(엑스1,2)=디스티(엑스1,2)와이N(엑스1,2)디스티(와이,2)/∣N(엑스1,2)=1(1+1+1)/3=1=2(엑스1,2)

② 비슷한 계산을 얻을 수 있다 X 2 、 X 3 、 … 、 X 11 X_2、X_3、…、X_{11}엑스2엑스3엑스11 상대 밀도 값.
예를 들어 엑스 5 엑스_5엑스5상대 밀도:
rdsty(X5,2) = ∑ Y ∈ N(X5,2) dsty(Y,2) / ∣ N(X5,2) ∣ dsty(X5,2) = (1 + 1 + 1 + 0.79) / 4 1 = 0.95 = OF 2(X5,2)rdsty(엑스5,2)=와이N(엑스5,2)디스티(와이,2)/|N(엑스5,2)|디스티(엑스5,2)=(1+1+1+0.79)/41=0.95=2(엑스5,2) rdsty(엑스5,2)=디스티(엑스5,2)와이N(엑스5,2)디스티(와이,2)/∣N(엑스5,2)=1(1+1+1+0.79)/4=0.95=2(엑스5,2) 결과는 하기 표 10-13에 요약되어 있다.

여기에 이미지 설명을 삽입하세요.
예 10-15 표 10-14에 표시된 데이터 세트가 주어지면 유클리드 거리를 사용하여 k = 2, 3, 5 k=2,3,5케이=2,3,5, 각 포인트의 값을 계산합니다. kk케이-가장 가까운 이웃 지역 밀도, kk케이-가장 가까운 이웃 지역 상대 밀도(이상값 요인) 2개의 텍스트{OF}_22) 그리고 이를 바탕으로 kk케이-가장 가까운 이웃 거리에 대한 이상값 요인 1개의 텍스트{OF}_11

여기에 이미지 설명을 삽입하세요.
풀다: (1) 이해를 돕기 위해 다음과 같이 할 수 있다. 봄 여름 시즌에스점의 상대적인 위치는 2차원 평면에 표시됩니다(그림 10-30).

여기에 이미지 설명을 삽입하세요.
(2) 거리 및 상대 밀도 기반 알고리즘 10-8 및 10-9를 각각 활용합니다.각 개체를 개별적으로 계산 kk케이-가장 가까운 이웃 지역 밀도 dsty 텍스트{dsty}디스티 kk케이-가장 가까운 이웃 지역 상대 밀도(이상값 요인) 2개의 텍스트{OF}_22) 그리고 이를 바탕으로 kk케이-가장 가까운 이웃 거리에 대한 이상값 요인 1개의 텍스트{OF}_11, 결과는 표 10-15에 요약되어 있다.

여기에 이미지 설명을 삽입하세요.
(3) 단순분석
① 그림 10-30에서 볼 수 있듯이, 엑스 15 엑스_{15}엑스15그리고 엑스 16 엑스_{16}엑스16 봄 여름 시즌에스두 가지 명백한 이상값이 있으며 거리와 상대 밀도를 기반으로 하는 방법을 사용하면 이를 더 잘 찾아낼 수 있습니다.
② 이 예에서 두 알고리즘은 kk케이예상만큼 민감하지 않으며 이상값일 수도 있습니다. 엑스 15 엑스_{15}엑스15그리고 엑스 16 엑스_{16}엑스16다른 물체와의 분리가 매우 분명합니다.
③표 10-15에서 알 수 있듯이 kk케이2, 3, 5개를 가져가세요. 엑스 1 엑스_1엑스1지역의 dsty 텍스트{dsty}디스티 값이 훨씬 낮습니다. 엑스 7 엑스_7엑스7지역의 dsty 텍스트{dsty}디스티 이는 그림 10-30에 표시된 면적 밀도와 일치합니다.그러나 두 지역의 상대밀도 값은 2개의 텍스트{OF}_22 그러나 눈에 띄는 차이는 거의 없습니다. 이는 상대 밀도의 특성에 따라 결정됩니다. 즉, 균일하게 분포된 데이터 포인트의 경우 포인트 사이의 거리에 관계없이 핵심 포인트의 상대 밀도는 1입니다.

7. 기타 클러스터링 방법

1. 클러스터링 알고리즘 개선

  (1) kk케이-모드( kk케이-modes) 알고리즘은 kk케이 -평균 알고리즘은 수치 속성의 제한에만 적합하며 이산 데이터의 신속한 클러스터링을 달성하기 위해 제안되었습니다.왜냐하면 kk케이- 모듈러 알고리즘은 단순한 0-1 매칭 방법을 사용하여 동일한 이산 속성 하에서 두 속성 값 사이의 거리를 계산하는데, 이는 순서 속성 값 간의 차이를 약화시킵니다. 즉, 두 속성 값 간의 차이를 완전히 반영할 수 없습니다. ​​동일한 서수 속성 아래에는 여전히 개선과 개선의 여지가 있습니다.
  (2) kk케이-프로토타입( kk케이-Prototype) 알고리즘과 결합 kk케이-평균화 알고리즘 kk케이 - 모듈식 알고리즘의 장점은 이산 속성과 수치 속성(혼합 속성이라고 함)을 모두 사용하여 데이터 세트를 클러스터링할 수 있다는 것입니다.개별 속성이 필요합니다. kk케이-모듈형 알고리즘 계산 ​​객체 더블 엑스엑스그리고와이사이의 거리 d_1(X,Y)는 벡터 X의 벡터이다.1(엑스,와이), 숫자 속성의 경우 다음을 사용합니다. kk케이-평균화 알고리즘의 방법으로 물체 사이의 거리를 계산합니다. d2(X,Y) d_2(X,Y) 는 X의 벡터이다.2(엑스,와이), 마지막으로 가중치 부여 방법을 사용합니다. α d 1 ( X , Y ) + ( 1 − α ) d 2 ( X , Y ) 알파 d_1(X, Y) + (1-알파)d_2(X, Y)α1(엑스,와이)+(1α)2(엑스,와이) 데이터 세트 개체로 더블 엑스엑스그리고와이사이의 거리 d(X, Y) d(X, Y)의 값은 다음과 같다.(엑스,와이),안에 α ∈ [ 0 , 1 ] 알파인[0,1]α[0,1] 는 중량 계수이며 일반적으로 다음과 같습니다. α = 0.5 알파 = 0.5α=0.5
(3) BIRCH 알고리즘(Balanced Iterative Reducing and Clustering Using Hierarchies)은 포괄적인 계층적 클러스터링 방법입니다.클러스터링 기능(CF) 및 클러스터링 기능 트리(CF 트리, B-트리와 유사)를 사용하여 클러스터의 클러스터를 요약합니다. 씨아이씨아이,안에 CF i = ( ni , LS i , SS i ) 텍스트{CF}_i = ( ni , 텍스트{LS}_i , 텍스트{SS}_i)CF=(,엘에스,봄 여름 시즌) 세쌍둥이다, 니 니_이N클러스터의 객체 수입니다. LS i 텍스트{LS}_i엘에스 니 니_이N객체 구성 요소의 선형 합, SS i 텍스트{SS}_i봄 여름 시즌 니 니_이N물체의 구성 요소의 제곱의 합입니다.
(4) CURE(Clustering Using Representatives) 알고리즘은 kk케이 -평균화 알고리즘이 또 다른 개선되었습니다. 많은 클러스터링 알고리즘은 구형 클러스터를 클러스터링하는 데만 적합한 반면 일부 클러스터링 알고리즘은 고립된 지점에 더 민감합니다. 위의 두 가지 문제를 해결하기 위해 CURE 알고리즘이 변경되었습니다. kk케이-평균화 알고리즘은 클러스터 중심 합을 사용합니다. kk케이- 중심점 알고리즘은 기존 방식인 하나의 특정 개체를 사용하여 클러스터를 표현하지만, 클러스터 내 여러 개의 대표 개체를 사용하여 클러스터를 표현하므로 비구형 클러스터의 클러스터링에 적응하고 영향을 줄일 수 있습니다. 클러스터링 시 노이즈.
(5) ROCK(RObust Clustering using linkK) 알고리즘은 바이너리 또는 범주형 속성 데이터 세트에 대해 제안된 클러스터링 알고리즘이다.
(6) DBSCAN 알고리즘의 밀도를 줄이기 위해 OPTICS(Ordering Points To 식별 the Clustering Structure) 알고리즘이 사용됩니다. ( ε , 최소점수 ) (바렙실론,텍스트{최소점수})(ε,최소 포인트) 매개변수 감도. 결과 클러스터를 명시적으로 생성하지는 않지만 클러스터 분석을 위해 증가된 클러스터 순위를 생성합니다(예: 도달 가능한 거리를 세로 축으로 하고 샘플 포인트 출력 순서를 가로 축으로 하는 좌표 차트). 이 순위는 각 샘플 포인트의 밀도 기반 클러스터링 구조를 나타냅니다.밀도 매개변수를 기반으로 이 정렬을 통해 얻을 수 있습니다. ( ε , 최소점수 ) (바렙실론,텍스트{최소점수})(ε,최소 포인트) DBSCAN 알고리즘의 클러스터링 결과.

2. 기타 새로운 클러스터링 방법

몇 가지 새로운 이론이나 기술을 사용하여 새로운 클러스터링 방법을 설계합니다.

(1) 그리드 기반 클러스터링 방법
그리드 기반 방식은 객체 공간을 제한된 수의 셀로 수량화하여 그리드 구조를 형성하고 각 차원의 분할 지점의 위치 정보를 배열에 저장하여 전체 공간을 관통하며 모든 클러스터링을 수행합니다. 작업은 이 그리드 구조(즉, 양자화 공간)에서 수행됩니다. 이 방법의 가장 큰 장점은 처리 속도가 매우 빠르다는 것입니다. 처리 속도는 데이터 개체 수와 무관하며 정량화 공간의 각 차원의 셀 수에만 관련됩니다. 그러나 효율성 향상은 다음과 같습니다. 클러스터링 결과가 희생됩니다. 그리드 클러스터링 알고리즘에는 수량화 규모의 문제가 있기 때문에 일반적으로 작은 단위부터 클러스터를 찾기 시작한 다음 점차적으로 단위의 크기를 늘리고 만족스러운 클러스터를 찾을 때까지 이 과정을 반복합니다.

(2) 모델 기반 클러스터링 방법
모델 기반 방법은 각 클러스터에 대한 모델을 가정하고 주어진 모델에 가장 적합한 데이터를 찾습니다. 모델 기반 방법은 클러스터를 찾기 위해 샘플의 공간 분포를 반영하는 밀도 함수를 설정하여 주어진 데이터와 특정 데이터 모델 간의 적응성을 최적화하려고 시도합니다.

(3) 퍼지 집합 기반의 클러스터링 방법
실제로는 대부분의 객체가 속하는 클러스터에 엄격한 속성 값이 없으며 속성 값과 형식에 중개 또는 불확실성이 있어 소프트 파티셔닝에 적합합니다. 퍼지 군집화 분석은 표본 귀인의 사이성을 기술할 수 있다는 장점이 있고, 현실 세계를 객관적으로 반영할 수 있다는 점에서 오늘날 군집분석 연구의 핫스팟 중 하나가 되었습니다.
퍼지 클러스터링 알고리즘은 퍼지 수학적 이론과 불확실한 클러스터링 방법을 기반으로 한 비지도 학습 방법입니다. 퍼지 클러스터링은 일단 제안되어 학계에서 큰 관심을 받았습니다. 퍼지 클러스터링은 대규모 클러스터링 "패밀리"이며 퍼지 클러스터링에 대한 연구도 매우 활발합니다.

(4) 대략적인 집합을 기반으로 한 클러스터링 방법
대략적인 클러스터링은 대략적인 집합 이론을 기반으로 하는 불확실한 클러스터링 방법입니다. 대략적인 집합과 클러스터링 알고리즘 간의 결합 관점에서 대략적인 클러스터링 방법은 강한 결합 대략적인 클러스터링과 약한 결합 대략적인 클러스터링의 두 가지 범주로 나눌 수 있습니다.
물론 클러스터 분석의 새로운 연구 방향은 이것보다 훨씬 더 넓습니다. 예를 들어 데이터 흐름 마이닝 및 클러스터링 알고리즘, 불확실한 데이터 및 해당 클러스터링 알고리즘, 양자 컴퓨팅 및 양자 유전자 클러스터링 알고리즘은 모두 최근 몇 년 동안 등장한 클러스터링 기술입니다. . 최첨단 연구 주제.

3. 기타 이상치 채굴 방법

앞서 소개한 아웃라이어 마이닝 방법은 실제 응용 분야에서 더 성숙한 아웃라이어 마이닝 방법 중 두 가지에 불과합니다. 이들은 마이닝 방법에 사용되는 기술 유형 또는 두 가지 사전 지식을 사용하여 결정할 수 있습니다. 각도: 정도.

(1) 사용된 기술의 종류
주로 통계적 방법, 거리 기반 방법, 밀도 기반 방법, 클러스터링 기반 방법, 편차 기반 방법, 깊이 기반 방법, 웨이블릿 변환 기반 방법, 그래프 기반 방법, 패턴 기반 방법 및 신경망이 있습니다. 방법 등

(2) 사전 지식의 활용
정규 또는 이상치 클래스 정보의 가용성에 따라 세 가지 일반적인 접근 방식이 있습니다.
① 비지도 이상치 탐지 방법, 즉 데이터 세트에 카테고리 라벨과 같은 사전 지식이 없습니다.
② 지도된 이상치 검출 방법, 즉 이상치와 정상점을 포함하는 훈련 세트의 존재를 통해 이상치의 특성을 추출하는 방법;
③ 준지도(Semi-supervised) 이상치 검출 방법은 훈련 데이터에 레이블이 있는 정규 데이터가 포함되어 있지만 이상치 데이터 객체에 대한 정보는 없습니다.