機器學(xué)習(xí)(周志華) 西瓜書 第九章課后習(xí)題9.10—— Python實現(xiàn)?

• 實驗題目

試設(shè)計一個能自動確定聚類數(shù)的改進 k 均值算法，編程實現(xiàn)并在西瓜數(shù)據(jù)集 4.0 上運行。

• 實驗原理

K均值算法原理

K均值算法

自動確定k值的度量指標(biāo)，最小化E：

? ? ? ?E值越小則簇內(nèi)樣本相似度越高，簇間樣本相似度越低，且k值保證是較小的值，即簇類盡可能保證是大型簇類（這里考慮樣本只有兩種類別，所以k值應(yīng)趨近于2）；

• 實驗過程

數(shù)據(jù)集獲取

將西瓜數(shù)據(jù)集4.0保存為data_4.txt

            
              編號,密度,含糖率
1,0.697,0.460
2,0.774,0.376
3, 0.634,0.264
4,0.608,0.318
5,0.556,0.215
6,0.403,0.237
7,0.481,0.149
8,0.437,0.211
9,0.666,0.091
10,0.243,0.267
11,0.245,0.057
12,0.343,0.099
13,0.639,0.161
14,0.657,0.198
15,0.360,0.370
16,0.593,0.042
17,0.719,0.103
18,0.359,0.188
19,0.339,0.241
20,0.282,0.257
21,0.748,0.232
22,0.714,0.346
23,0.483,0.312
24,0.478,0.437
25,0.525,0.369
26,0.751,0.489
27,0.532,0.472
28,0.473,0.376
29,0.725,0.445
30,0.446,0.459
            
          

算法實現(xiàn)

讀取數(shù)據(jù)

計算兩樣本向量的的歐式距離

為給定的簇類計算均值向量

靜態(tài)K均值算法，獲得劃分為k簇類集

對劃分后的結(jié)果進行誤差計算，基于自動確定k值的度量指標(biāo)

動態(tài)K均值算法，返回最佳的k值

main函數(shù)，調(diào)用上述函數(shù)，輸出自動確定k值后的劃分結(jié)果

• 實驗結(jié)果

• 程序清單：

            
              import random as rd
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

def loadData(filename):
    dataSet = pd.read_csv(filename)
    dataSet.drop(columns=['編號'], inplace=True)
    return dataSet

#計算每個向量和均值向量之間的距離
def calc_distance(x, mu):
	distance = 0
	for xi, yi in zip(x, mu):
		distance += (xi-yi)**2

	return distance**(.5)

#根據(jù)目前的簇類計算出均值向量
def calc_mu(dataSet, indexs):
	Ci = dataSet.loc[indexs]
	return np.array(Ci.mean())

def k_means(dataSet, k, iterate=100):
	Mu_indexs = rd.sample(range(dataSet.shape[0]), k)
	Mu = [np.array(dataSet.loc[index]) for index in Mu_indexs]
	now, flag = 0, True

	while flag and now < iterate:
		C = [[] for _ in range(k)]
		for index, row in dataSet.iterrows():
			distances = []
			for mu in Mu:
				# x = np.array(dataSet.loc[index])
				distance = calc_distance(row, mu)
				distances.append(distance)

			label = np.argmin(distances)
			C[label].append(index)

		flag = False
		for i in range(len(Mu)):
			new_mu = calc_mu(dataSet, C[i])
			if (new_mu!=Mu[i]).any():
				flag = True
			Mu[i] = new_mu

		now += 1

	return C, Mu

def calc_E(dataSet, C, Mu, k):
	E_inside, E_outside, size= 0, 0, dataSet.shape[0]
	#簇內(nèi)
	for Ci, mu in zip(C, Mu):
		for index in Ci:
			distance = calc_distance(dataSet.loc[index], mu)
			E_inside += distance**2
	# 正則化保持權(quán)重
	E_inside /= size

	# 簇間
	for a in range(k):
		for b in range(k):
			if a == b:
				continue
			distance = calc_distance(Mu[a], Mu[b])
			E_outside += distance**2

	E_outside /= k
	return E_inside - E_outside + 2*k/size

def Dynamic_K_means(dataSet):
	size, before_E = len(dataSet), 9999
	for k in range(2, size):
		Es = []
		# 計算多次k均值，取平方誤差平均值
		for time in range(10):
			C, Mu = k_means(dataSet, k)
			E = calc_E(dataSet, C, Mu, k)
			Es.append(E)
		Best_E = sum(Es)/len(Es)

		if before_E <= Best_E:
			return k-1
		else:
			before_E = Best_E

	return 1

if __name__=='__main__':
    filename = 'data_4.txt'
    dataSet = loadData(filename)
    k = Dynamic_K_means(dataSet)

    Best_E = 9999
    # 多次計算，取最好結(jié)果
    for _ in range(10):
    	C, Mu= k_means(dataSet, k)
    	E = calc_E(dataSet, C, Mu, k)
    	if E < Best_E:
    		Best_E = E
    		Best_C = C

    print('k =', k)
    for Ci in Best_C:
    	print(Ci)

            
          

?