클러스터 분석

제 cs34 제1단원 구축 주 프로젝트에 대해 저는 표준 도구 패키지를 사용하지 않고 K-Means 분류 알고리즘을 다시 만들기로 결정했습니다.
K-균일치 집합은 무엇입니까?
K균일치 집합은 유행하는 무감독 알고리즘으로 매우 간단하고 사용하기 쉽다.K-means를 사용하는 의미는 매우 간단하다. 비슷한 데이터 포인트를 한데 묶고 잠재적인 모델을 발견한다.K-means의 본질은 데이터에서 고정된 수량(K)의 분류를 집중적으로 찾아 비슷한 데이터 점을 그룹으로 나누는 것이다.
왜 그것이 도움이 됩니까?
K-means 분류 알고리즘은 데이터에 명확하게 표시되지 않은 그룹(클러스터)을 찾는 데 사용됩니다.이것은 어떤 유형의 그룹이 존재하는지에 대한 가설을 확인하거나 복잡한 데이터 집합의 미지의 그룹을 식별하는 데 사용할 수 있다.
K-균일치 분류 예
K-Means 클러스터링 알고리즘은 다음과 같이 사용할 수 있습니다.

행위 분할

증상 집합

재고분류

선별 센서 측정

이상 검출

용어
이 알고리즘과python 코드를 깊이 연구하기 전에 이 알고리즘에 대한 중요한 용어를 토론합시다

K-K-Means 컬렉션 중 K는 컬렉션 수를 나타냅니다.내 알고리즘에 대해 그것은 사용자가 제공한 입력 중의 하나이다

질심-질심은 정점을 주는 기하학적 중심이다.그것은 모든 주어진 산술 평균 위치

유클리드 거리 - 평면 또는 3D 공간에서 두 점 사이의 유클리드 거리는 두 점을 연결하는 선 세그먼트의 길이를 측정합니다.구주정리는 두 점 사이의 거리를 계산하는 데 쓸 수 있다.만약 점(x1, y1)과 (x2, y2)이 2차원 공간에 있다면 그들 사이의 유클리드 거리는√((x2-x1)²+(y2-y1)²)

용량차 - 알고리즘의 수렴 값을 확인합니다.주어진 공차 값보다 오차가 크면 공차 값보다 낮을 때까지 알고리즘을 계속 실행합니다

최대 교체 횟수 - 오차가 주어진 용량보다 낮을 때까지 알고리즘을 실행해야 합니다.

입문
우선, 나는 50개의 점/관찰 값을 포함하는 2차원 데이터 집합을 만들었다.나는 np를 사용하여 랜덤으로 이것들을 만듭니다.임의 ().X와 Y의 각 값은 0에서 10 사이입니다.

import matplotlib.pyplot as plt
import numpy as np
from matplotlib import style

#random numbers multiplied by 10 to give us a more diverse group 
X = np.random.rand(50, 2) * 10

plt.scatter(X[:,0], X[:,1], marker="x", color='b', s=100, linewidths=5)

plt.grid()
plt.show()

이것은 데이터 도표로 무작위로 생성된 데이터를 나타낸다

데이터에서 알 수 있듯이 우리는 그 중의 일부 점을 묶음으로 나눌 수 있다.우리의 예시에서 우리는 7개의 집단을 선택하자.수동으로 클러스터로 표시하면 다음과 같습니다.

현재, 우리는 어떻게 수동으로 이 점들을 묶음으로 나누지 않는 상황에서 이 점을 실현합니까?
시작하기 전에, 나는 3개의 매개 변수를 묘사하고 싶다 (상문 참조)

K-클러스터

공차-오차공차

max_interations = 주어진 용량차보다 오차가 적을 때까지 알고리즘을 실행해야 합니다

    def __init__(self, k=3, tolerance=0.0001, max_iterations=100):
        self.k = k
        self.tolerance = tolerance
        self.max_iterations = max_iterations

우리가 분류를 시작하는 과정은 질심을 정의하는 것부터 시작한다.우리는 7개의 묶음(k=7)을 선택했기 때문에, 이것은 우리가 7개의 질심이 필요하다는 것을 의미한다.질심은 정점을 주는 기하학적 중심이다.우리의 데이터는 무작위이기 때문에, 우리는 7개의 점을 우리의 질심으로 선택할 수 있다.그러나 질심이 어떻게 움직이는지 보여주기 위해 나는 이미 질심을 미리 정의했다. 다음과 같다.

initial_centroids =  {0:[1, 1], 1:[2, 2], 2:[3, 3], 3:[4, 4], 
4:[5, 5], 5:[6 , 6], 6:[8, 8]}

우리가 어떤 질심부터 시작하는지는 결코 중요하지 않다.우리가 어디서 끝내느냐가 중요해.
이 질심을 사용하여 우리의 도표와 데이터가 어떤 것인지 봅시다.나는 모든 질심에 대해 서로 다른 모양을 사용하고 색채 인코딩을 해서 이 질심과 관련된 점들을 보았다.우리는 데이터 점과 질심 초기 집합 사이의 유클리드 거리를 계산해야 한다(위의 정의를 참고하십시오)

for featureset in data:
  distances = [self.calc_euclidean_distance(featureset, 
  self.centroids[centroid]) for centroid in self.centroids]
  cluster_id = distances.index(min(distances))
  self.clusters[cluster_id].append(featureset)

이것이 바로 우리가 얻은 것이다

우리가 제공한 초기 질심에서 알 수 있듯이 질심은 족과 일치하지 않는다.그래서 우리는 질심을 그것들의 묶음에 가까이 옮기기 시작해야 한다.

for cluster_id in self.clusters:
   self.centroids[cluster_id] = np.average(self.clusters[cluster_id], axis=0)

질심 업데이트 효과 한번 볼게요.

보시다시피 우리는 질심에 더 가깝고 그들이 필요로 하는 위치는 아직 멀다.따라서 우리가 원하는 결과를 얻을 때까지 더 많은 교체를 실행합시다.하지만 우리는 언제 좋은 결과가 나올지 알아야 한다.이것은 공차와 최대 교체 횟수를 통해 확정할 수 있다.만약 우리의 오류율이 용차보다 낮지 않다면, 우리는 계속해서, 설정의 최대 교체 횟수에 도달할 때 멈출 것이다.

if np.sum((current_centroid - 
   original_centroid)/original_centroid*100.0) > self.tolerance:
   optimized = Fals

이 예에 대해 나는 대략 7번의 교체를 써서 우리가 원하는 것을 실현했다

위의 그림에서 알 수 있듯이 우리의 성단은 질심과 잘 일치한다.비록 이 집단들은 우리가 수동으로 표시한 집단과 약간 다르지만, 당신은 우리의 기계 학습 알고리즘이 그것들을 분류하는 방면에서 더욱 잘 하는 것을 볼 수 있습니다
현재, 우리는 이미 초기 데이터에 근거하여 질심을 훈련하여, 그것이 어떻게 새로운 데이터 포인트를 예측하는지 보여 준다

Y = np.array([[3,3],
              [2,8],
              [7,2],
              [6,6],
              [9,9],
              [8,4],
              [2,4]])

i = 0
for y in Y:
    cluster_id = model.predict(y)
    c = color_dict[cluster_id]
    plt.scatter(y[0], y[1], marker="*", color=c, s=150, linewidths=5)
    i +=1

plt.grid()
plt.show()

그 결과 우리가 선택한 데이터는 우리가 예상한 방식에 따라 분류되었다.

결론
K 균일치 집합은 수동으로 표시되지 않은 데이터 집합을 만드는 데 매우 간단한 무감독 ML 알고리즘이다.하지만 K-Means 집합에도 문제가 있다.우리가 대량의 새로운 데이터를 사용할 때, 질심은 우리가 원하는 위치가 아닐 수도 있다. 왜냐하면 우리는 비교적 작은 데이터 집합을 사용하여 그것에 대해 훈련을 했기 때문이다.우리가 빅데이터를 가지고 있을 때, 그것에 대해 재분류하는 것은 매우 중요하다
이것은 나의 전체 코드이다

import numpy as np

class K_Means:

    initial_centroids = None

    def __init__(self, k=3, tolerance=0.0001, max_iterations=100):
        self.k = k
        self.tolerance = tolerance
        self.max_iterations = max_iterations

    def set_initial_centroids(self, initial_centroids):
      if len(initial_centroids) == self.k:
       self.initial_centroids = initial_centroids

    def fit(self, data):

        self.centroids_all = []

        if self.initial_centroids is None:
          self.centroids = {}
          for i in range(self.k):
              self.centroids[i] = data[i]
        else:
          self.centroids = self.initial_centroids

        print ("Initial centroids", self.centroids)

        for i in range(self.max_iterations):
            self.clusters = {}

            for i in range(self.k):
                self.clusters[i] = []

            for featureset in data:
                distances = [self.calc_euclidean_distance(featureset, self.centroids[centroid]) for centroid in self.centroids]
                # print("Distances", distances)
                cluster_id = distances.index(min(distances))
                # print("Cluster_id", cluster_id)
                self.clusters[cluster_id].append(featureset)

            prev_centroids = dict(self.centroids)
            self.centroids_all.append(dict(self.centroids))            

            for cluster_id in self.clusters:
                self.centroids[cluster_id] = np.average(self.clusters[cluster_id], axis=0)

            optimized = True

            for i in self.centroids:
                original_centroid = prev_centroids[i]
                current_centroid = self.centroids[i]
                # print("Orginial, Current", original_centroid, current_centroid)
                if np.sum((current_centroid - original_centroid)/original_centroid*100.0) > self.tolerance:
                    optimized = False

            if optimized:
                break

    def calc_euclidean_distance(self, x1, x2):
        return (sum((x1 - x2)**2))**0.5

    def predict(self, data):
        distances = [self.calc_euclidean_distance(data, self.centroids[centroid]) for centroid in self.centroids]
        cluster_id = distances.index(min(distances))
        return cluster_id