python kmeans

파이썬-kmeans

k-평균 클러스터링의 Python 구현. k-평균은 유사한 데이터 포인트를 사용자가 지정한 수의 그룹으로 그룹화하는 비지도 학습 기술입니다. 아래 예는 k-means++ 중심 초기화 알고리즘을 사용하여 붓꽃 ​​데이터 세트에 대한 클러스터의 진행을 보여줍니다.

설명

k-평균은 N개의 d차원 실수 벡터 집합에서 사용자가 지정한 k(<N) 개수의 클러스터를 식별하려고 시도합니다. 알고리즘은 클러스터 중심에서 클러스터 구성원까지의 거리 제곱합을 최소화하려고 시도하여 진행됩니다. 표준 알고리즘은 세 단계로 진행됩니다.

1. k개의 무작위 중심(클러스터 중심)을 초기화합니다.
2. 거리 측정법(일반적으로 유클리드 거리)에 따라 가장 가까운 클러스터에 데이터 포인트를 할당합니다.
3. 중심을 클러스터 구성원의 평균으로 업데이트합니다.
4. 2단계의 할당이 변경되지 않을 때까지 2단계와 3단계를 반복합니다.

알고리즘의 출력은 각 데이터 포인트에 대한 클러스터 할당과 "왜곡"의 최종 수준입니다. 알고리즘은 입증 가능한 최적의 솔루션을 생성하지 않으며 초기 클러스터 중심으로 인해 알고리즘이 분명히 차선책인 로컬 최적 솔루션에 정체될 수 있습니다(결과 섹션의 기본 2D 예 참조).

많은 연구가 다음에 중점을 두었습니다.

• 초기 클러스터 센터를 선택합니다. K-Means++는 잘 알려진 방법이며 이 구현에 포함되어 있으며 알고리즘은 다음 하위 섹션에 설명되어 있습니다.
• 거리 계산, 즉 유클리드 이외의 측정값을 사용하는 경우 여기를 참조하세요.

K-평균++

위의 1단계에서처럼 임의의 중심을 초기화하는 대신 k-평균++는 잘못된 초기 구성을 피하기 위해 초기 중심을 확률적으로 분산시킵니다. 알고리즘은 다음과 같습니다.

1. 첫 번째 중심을 무작위로 선택합니다.
2. 각 데이터 포인트 x에 대해 x에서 이미 선택된 가장 가까운 중심까지의 거리 d(x)를 계산합니다.
3. d(x)2에 비례하는 가중 확률을 사용하여 다음 중심이 될 데이터 포인트를 선택합니다.

이 기술은 다른 초기 중심 근처에 있지 않은 데이터 포인트에 유리하며 유전 알고리즘에서 자주 사용되는 룰렛 휠(또는 적합도 비례) 선택을 연상시키는 선택 정책을 사용합니다.

자원

기본 알고리즘

• K-평균은 데이터 마이닝을 위한 상위 10가지 알고리즘에 설명되어 있습니다.

• K-Means는 여기에서 발췌한 정보 이론, 추론 및 학습 알고리즘에 설명되어 있습니다.

• CMU의 Andrew Moore 교수는 여기에 좋은 메모를 했습니다.

• 범죄 데이터를 활용한 Edureka 예시

클러스터 초기화

• K-Means++ 및 전체 논문은 여기에 있습니다.

• K-Means 클러스터링 알고리즘의 효율적인 초기화 방법에 대한 비교 연구

SciPy를 사용하지 않는 이유는 무엇입니까?

SciPy에는 k-평균 구현이 있습니다. 이 작업의 목적은 학습 목적으로 순수한 Python 구현을 구축하고 다른 사람들이 k-평균 알고리즘을 배울 수 있도록 돕는 것입니다. 최소한의 Python 경험만 있는 관심 있는 독자는 SciPy와 같은 라이브러리의 복잡성을 추가하지 않고도 이 코드를 읽고 실행할 수 있습니다. 생산용으로는 절대 사용되지 않습니다 :)

코드 실행

종속성

• 파이썬 3.6.3
• matplotlib 2.1.1 - 설치 지침은 여기를 참조하세요.

실행

Python 인터프리터를 사용하여 코드를 실행합니다.

python kmeans.py ./resources/<config.cfg>

여기서 config.cfg는 일반 텍스트 구성 파일입니다. 구성 파일의 형식은 다음 필드가 포함된 Python dict입니다.

 {
   'data_file' : '\resources\iris.csv',
   'data_project_columns' : ['sepal_length','sepal_width','petal_length','petal_width','class'],
   'k' : 3,
   'cluster_atts' : ['sepal_length','sepal_width','petal_length','petal_width'],
   'init_cluster_func' : 'kmeans_plus_plus',
   'plot_config' :
    {'output_file_prefix' : 'iris',
     'plots_configs': [
        {'plot_atts' : ['sepal_length','sepal_width']},
        {'plot_atts' : ['sepal_length','petal_length']},
        {'plot_atts' : ['sepal_length','petal_width']},
        {'plot_atts' : ['sepal_width','petal_length']},
        {'plot_atts' : ['sepal_width','petal_width']},
        {'plot_atts' : ['sepal_width','petal_width']}
     ]
   }
}

다음을 지정해야 합니다.

• csv 데이터 파일;
• 파일에서 투영할 필드의 하위 집합입니다.
• 형성할 클러스터 수, k;
• 클러스터링 프로세스에 사용되는 속성의 하위 집합입니다.
• 선택적으로 초기 클러스터 func(기본값='rand_init_centroids')를 지정하고, 관심 있는 작성자는 자신의 코드를 코드에 추가하고 여기에서 지정했습니다.
• 다음을 포함하는 플롯 구성
  • 작업 디렉터리에서 프로세스 중에 생성된 png 파일의 접두어를 지정하지 않으면 이미지가 생성되지 않습니다.
  • 개별 플롯 구성은 플롯당 2차원으로 제한됩니다.

결과

붓꽃 데이터 세트

Lichman, M.(2013)의 Iris 데이터 세트(iris.config). UCI 머신러닝 저장소 . 캘리포니아주 어바인: 캘리포니아 대학교 정보 및 컴퓨터 과학 대학은 기계 학습 커뮤니티에서 매우 잘 알려진 데이터 세트입니다. 무작위 초기 클러스터의 결과는 다음과 같습니다.

기본 합성 2D 데이터

이 데이터는 디버깅 목적으로 생성되었으며(basic2d.config 참조) 초기 무작위 클러스터를 잘못 선택했을 때의 영향을 보여줍니다. 아래 결과는 알고리즘이 명확한 클러스터 할당에 도달하지 못하게 하는 초기 중심 구성을 보여줍니다. 이 경우 빨간색 중심이 배치된다는 것은 파란색 중심이 왼쪽 아래 및 오른쪽 아래 사분면의 모든 데이터 포인트를 캡처한다는 의미입니다.

범죄

범죄 데이터 세트(crime.config)는 여기 Edureka에서 가져온 것입니다.