پیاده سازی الگوریتم K-means++‎‏ در پایتون — راهنمای گام به گام

1import numpy as np
2import matplotlib.pyplot as plt
3
4def CreateDataset(Cs:np.ndarray, nD:int, S:float):
5    nC = Cs.shape[0]
6    N = nD * nC
7    X = np.zeros((N, 2))
8    for i in range(nC):
9        for j in range(nD):
10            X[nC*j + i, 0] = Cs[i, 0] + np.random.randn() / S
11            X[nC*j + i, 1] = Cs[i, 1] + np.random.randn() / S
12    return X
13
14def GetClusters(Centers:np.ndarray, X:np.ndarray):
15    nClusters = Centers.shape[0]
16    Clusters = []
17    for i in range(nClusters):
18        Clusters.append([])
19    for xj in X:
20        d = np.zeros(nClusters)
21        for i in range(nClusters):
22            d[i] = np.linalg.norm(xj - Centers[i])
23        a = np.argmin(d)
24        Clusters[a].append(xj)
25    for i in range(nClusters):
26        Clusters[i] = np.array(Clusters[i])
27    return Clusters
28
29def UpdateCenters(Centers:np.ndarray, Clusters:list):
30    nClusters = Centers.shape[0]
31    for i in range(nClusters):
32        if np.size(Clusters[i]) != 0:
33            Centers[i] = np.mean(Clusters[i], axis = 0)
34    return Centers

1np.random.seed(0)
2plt.style.use('ggplot')
3
4Cs = np.array([[-0.5, +1.0], [+1.6, -0.1],
5               [-0.9, -1.7], [-2.9, +2.3],
6               [+0.7, +2.2], [-2.2, +0.3]])
7nD = 200
8S = 2.5
9
10X = CreateDataset(Cs, nD, S)
11
12plt.scatter(X[:, 0], X[:, 1], c='k', s=9, label='Data')
13plt.scatter(Cs[:,0], Cs[:, 1], c='r', s=100, marker = '*', label='Center')
14plt.title('Scatter Plot of Data')
15plt.xlabel('X1')
16plt.ylabel('X2')
17plt.legend()
18plt.show()

1def Cost(Centers:np.ndarray, X:np.ndarray):
2    WCSS = 0
3    for i in Centers:
4        d = []
5        for j in X:
6            d.append(np.linalg.norm(i - j, ord=2)**2)
7        WCSS += min(d)
8    return WCSS

1nRun = 100
2nClusters = 5
3nIter = 10
4
5Costs = np.zeros(nRun)
6
7for i in range(nRun):
8    Centers = np.random.uniform(-2, +2, (nClusters, 2))
9    Clusters = GetClusters(Centers, X)
10    for _ in range (nIter):
11        Centers = UpdateCenters(Centers, Clusters)
12        Clusters = GetClusters(Centers, X)
13    Costs[i] = Cost(Centers, X)

1plt.hist(Costs, bins=11, color='crimson', alpha=0.5)
2plt.title('K-Means Algorithm Final Cost Function Value With Different Initilizations')
3plt.xlabel('Cost')
4plt.ylabel('Frequency')
5plt.show()

1def KMeansPP(nClusters:int, X:np.ndarray):

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))
4    Centers[0] = X[np.random.randint(nD)]

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))
4    Centers[0] = X[np.random.randint(nD)]
5    for i in range(nClusters - 1):

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))
4    Centers[0] = X[np.random.randint(nD)]
5    for i in range(nClusters - 1):
6        D = np.zeros(nD)

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))
4    Centers[0] = X[np.random.randint(nD)]
5    for i in range(nClusters - 1):
6        D = np.zeros(nD)
7        for j in range(nD):

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))
4    Centers[0] = X[np.random.randint(nD)]
5    for i in range(nClusters - 1):
6        D = np.zeros(nD)
7        for j in range(nD):
8            d = []

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))
4    Centers[0] = X[np.random.randint(nD)]
5    for i in range(nClusters - 1):
6        D = np.zeros(nD)
7        for j in range(nD):
8            d = []
9            for k in range(i+1):
10                d.append(np.linalg.norm(X[j] - Centers[k], ord=2))

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))
4    Centers[0] = X[np.random.randint(nD)]
5    for i in range(nClusters - 1):
6        D = np.zeros(nD)
7        for j in range(nD):
8            d = []
9            for k in range(i+1):
10                d.append(np.linalg.norm(X[j] - Centers[k], ord=2))
11            D[j] = min(d)

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))
4    Centers[0] = X[np.random.randint(nD)]
5    for i in range(nClusters - 1):
6        D = np.zeros(nD)
7        for j in range(nD):
8            d = []
9            for k in range(i+1):
10                d.append(np.linalg.norm(X[j] - Centers[k], ord=2))
11            D[j] = min(d)
12        D2 = np.power(D, 2)

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))
4    Centers[0] = X[np.random.randint(nD)]
5    for i in range(nClusters - 1):
6        D = np.zeros(nD)
7        for j in range(nD):
8            d = []
9            for k in range(i+1):
10                d.append(np.linalg.norm(X[j] - Centers[k], ord=2))
11            D[j] = min(d)
12        D2 = np.power(D, 2)
13        SD2 = np.sum(D2)
14        P = D2 / SD2

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))
4    Centers[0] = X[np.random.randint(nD)]
5    for i in range(nClusters - 1):
6        D = np.zeros(nD)
7        for j in range(nD):
8            d = []
9            for k in range(i+1):
10                d.append(np.linalg.norm(X[j] - Centers[k], ord=2))
11            D[j] = min(d)
12        D2 = np.power(D, 2)
13        SD2 = np.sum(D2)
14        P = D2 / SD2
15        Index = np.random.choice(nD, size=1, p=P)[0]
16        Centers[i+1] = X[Index]

1def KMeansPP(nClusters:int, X:np.ndarray):
2    nD = X.shape[0]
3    Centers = np.zeros((nClusters, 2))
4    Centers[0] = X[np.random.randint(nD)]
5    for i in range(nClusters - 1):
6        D = np.zeros(nD)
7        for j in range(nD):
8            d = []
9            for k in range(i+1):
10                d.append(np.linalg.norm(X[j] - Centers[k], ord=2))
11            D[j] = min(d)
12        D2 = np.power(D, 2)
13        SD2 = np.sum(D2)
14        P = D2 / SD2
15        Index = np.random.choice(nD, size=1, p=P)[0]
16        Centers[i+1] = X[Index]
17    return Centers

1nRun = 100
2nClusters = 5
3nIter = 10
4
5Costs = np.zeros(nRun)
6
7for i in range(nRun):
8    Centers = KMeansPP(nClusters, X)
9    Clusters = GetClusters(Centers, X)
10    for _ in range (nIter):
11        Centers = UpdateCenters(Centers, Clusters)
12        Clusters = GetClusters(Centers, X)
13    Costs[i] = Cost(Centers, X)