Python의 K- 평균 함수

Question

방법론을 이해하기 위해 Python에서 k- 평균 함수를 작성했습니다. 나는 k 값이 더 큰 더 복잡한 데이터 세트에서 이것을 사용하려고하지만 매우 느리게 실행됩니다. 누구든지 이것을 개선 할 수있는 방법에 대한 권장 사항이 있습니까? 예제 데이터 세트를로드하고 알고리즘을 적용하는 것과 함께 아래 코드를 제공했습니다.

def Euc(x,y):
    return math.sqrt(sum([(a - b) ** 2 for a,b in zip(x,y)]))

def K_means(TE,k):
    Iteration = 0
    R = []
    O_a = []
    Epoch = 0
    Tol = 1
    Old_Tol = 2
    Tol_r = []
    start_time = time.time()
    mean_cl = [[random.uniform(TE.iloc[i].min(),TE.iloc[i].max()) for i in range(len(TE.columns))] for c in range(0,k)]
    for n in range(len(TE)):
        D = [Euc(TE.iloc[n].tolist(),mean_cl[c]) for c in range(0,k)]  
        O_a.append(D.index(min(D)))
    while(abs(Old_Tol - Tol) > 0.005):
        Old_Tol = Tol
        Epoch = Epoch + 1
        mean_cl = [TE.iloc[[j for j, x in enumerate(O_a) if x == i]].mean() for i in range(0,k)]
        N_a = []
        for n in range(len(TE)):
            Iteration = Iteration + 1
            D = [Euc(TE.iloc[n].tolist(),mean_cl[c]) for c in range(0,k)] 
            N_a.append(D.index(min(D)))
       Tol = np.mean([x != y for x,y in zip(O_a,N_a)])
        Tol_r.append(Tol)
        O_a = N_a
    R.append(time.time() - start_time)
    R.append(Tol_r)
    R.append(N_a)
    R.append(Iteration)
    return R

def load_Pima():
    url = "http://www.stats.ox.ac.uk/pub/PRNN/pima.tr"
    Pima_training = pd.read_csv(url,sep = '\s+')
    url = "http://www.stats.ox.ac.uk/pub/PRNN/pima.te"
    Pima_testing = pd.read_csv(url,sep = '\s+')
    Pima_training = Pima_training.iloc[1:]
    Pima_testing = Pima_testing.iloc[1:]
    Pima_training.loc[:,"type"] = Pima_training.loc[:,"type"].apply(lambda x : 0 if x == 'Yes' else 1)
    Pima_testing.loc[:,"type"] = Pima_testing.loc[:,"type"].apply(lambda x : 0 if x == 'Yes' else 1)
    Features = Pima_training.loc[:,Pima_training.columns != "type"]
    Means = Features.mean()
    SDs = Features.std()
    for name in Features.columns:
        Pima_training[name] = (Pima_training[name]-Means[name])/SDs[name]
        Pima_testing[name] = (Pima_testing[name]-Means[name])/SDs[name]
    return Pima_training, Pima_testing

Pima_training, Pima_testing = load_Pima()

class_var = "type"
random.seed(2031)
k = 2
TE = Pima_testing
TE = TE.loc[:,TE.columns != class_var]
km = K_means(TE,k)

이 함수는 알고리즘의 런타임, 각 세대의 허용 오차 (클러스터 할당 변경 률의 %), 최종 클러스터 할당 및 총 반복 횟수를 반환합니다. 이미 4 개의 for 루프를 제거하여 속도가 상당히 빨라졌습니다. 하지만 파이썬 프로그래밍의 부족이 이것을 더 효율적으로 만드는 데 방해가 될까 두렵습니다. 도움을 주시면 감사하겠습니다!

Answer 1

여러 지점에서이를 벡터화하여 행 단위가 아닌 전체 데이터 프레임에 산술을 적용 할 수 있습니다.

def min_euclidean(df, options):
    """ Returns the index of the series in iterable options for which df - row has minimum
    Euclidean distance """
    return pd.DataFrame(((df - series) ** 2).sum(axis=1, skipna=False) for series in options).idxmin()

def k_means(TE, k):
    iteration = 0
    epoch = 0
    tol = 1
    old_tol = 2
    tols = []
    start_time = time.time()
    mean_cl = [random.uniform(TE.min(), TE.max()) for _ in range(k)]
    o_a = min_euclidean(TE, mean_cl)
    while abs(old_tol - tol) > 0.005:
        old_tol = tol
        epoch += 1
        mean_cl = [TE[o_a == i].mean() for i in range(k)]
        n_a = min_euclidean(TE, mean_cl)
        iteration += len(TE)
        tol = (o_a != n_a).mean()
        tols.append(tol)
        o_a = n_a
    return time.time() - start_time, tols, n_a, iteration

참고 :

• 가능한 한 목록 대신 Pandas 시리즈 또는 데이터 프레임을 사용합니다.
• mean_cl목록 목록 대신 Pandas 시리즈 목록으로 계산 합니다. 이렇게하면의 열 또는 행 인덱스를 반복하는 것을 방지 할 수 TE있습니다. mean_cl데이터 프레임 으로 저장 하여 이를 더 최적화하는 방법이있을 수 있지만 그렇게 작업하는 명백한 방법을 볼 수 없습니다.
• 유클리드 거리에 대한 제곱근을 취할 필요가 없습니다. 최소 거리와 관련된 인덱스는 제곱 값과 동일하게 작동합니다.
• o_a그리고 n_a또한 시리즈로 저장됩니다. 그런 다음 (o_a!= n_a).mean()그들 사이의 불균형을 계산할 수 있습니다.
• 여기서 가장 큰 최적화는 아마도 min_euclidean전체 데이터 프레임에 대한 제곱 차이를 반복하는 대신 최적화 된 방식으로 계산 하는 함수일 것입니다.

이것은 벡터화에 대한 유용한 설명 이 될 수 있습니다. Pandas 시리즈 및 데이터 프레임을 최적으로 작업하려면 일반 Python과는 약간 다른 사고 방식이 필요합니다.

편집 : 여기 팬더 대신 numpy를 사용하는 버전이 있습니다. 이것은 모든 작업을 완전히 벡터화하고 훨씬 더 빠릅니다. 이 StackOverflow 답변 의 최적화를 사용합니다 .

def k_means(TE, k):
    epoch = 0
    tol = 1
    old_tol = 2
    tols = []
    start_time = time.time()
    te = np.array(TE)
    rows, columns = te.shape
    te3 = te[:, np.newaxis]  # 3d version of te for calculating euclidean more easily
    k_range = np.arange(k)[:, np.newaxis]
    mean_cl = np.random.uniform(te.min(axis=0), te.max(axis=0), size=(k, columns))
    o_a = np.nanargmin(((te3 - mean_cl) ** 2).sum(axis=2), axis=1)
    while abs(old_tol - tol) > 0.005:
        old_tol = tol
        epoch += 1
        m = o_a == k_range     # masks for each value in range 0 to k-1
        mean_cl = m.dot(te) / m.sum(1, keepdims=True)
        n_a = np.nanargmin(((te3 - mean_cl) ** 2).sum(axis=2), axis=1)
        tol = (o_a != n_a).mean()
        tols.append(tol)
        o_a = n_a
    return time.time() - start_time, tols, n_a, epoch * rows