<jupyter_start><jupyter_text>Dataset used: [Synthetic 2-d data with N=5000 vectors and k=15 Gaussian clusters with different degree of cluster overlap](http://cs.joensuu.fi/sipu/datasets/)    $2\text{D}$ data was just chosen for better visualization of the results.<jupyter_code># Converting to df just for better visualization:
df = pd.DataFrame(np.loadtxt('data.txt'), columns = ['Feature 1', 'Feature 2'])
display(df)
# Mean Normalization:
X = df.to_numpy()
mu = X.mean(axis=0)
std = X.std(axis=0)
X = (X-mu)/std

x1 = X[:, 0]
x2 = X[:, 1]
plt.scatter(x1, x2, s=0.5)
plt.gca().set_aspect('equal')
plt.title('Clusters')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()<jupyter_output><empty_output><jupyter_text>It's easy to see that $15$ well-separated clusters are present.  K-Means Algorithm:<jupyter_code>def init_centroids(X, K):
    m = X.shape[0]
    centroids = X
    
    # Unvectorized implementation
    #for _ in range(K):
        #c = np.random.randint(m)
        #centroids.append(X[c])
        
    # Vectorized:
    np.random.shuffle(centroids) # Modify a sequence in-place by shuffling its contents
    centroids = centroids[:K]
    return np.asarray(centroids)
# Not needed in the vectorized implementation:
def distance(c_i, x_i):
    return (np.linalg.norm(c_i - x_i))**2
def classify(centroids):
    
    # Vectorized: Takes 8s for execution if printing graphs with axes, and a whopping 0.1s when not!
    distances = (np.square(X - centroids[:, np.newaxis])).sum(axis=2) # numpy broadcasting for the win
    return np.argmin(distances, axis=0)
    
    # Unvectorized: Takes 23s for execution
    #y = []
    #for x_i in X:
    #   d_array = [distance(c_i, x_i) for c_i in centroids]     
    #    y.append(np.argmin(d_array))
    #return np.array(y)
# Define the color-map
cmap = plt.cm.jet
# Extract all colors from the .jet map
cmaplist = [cmap(i) for i in range(cmap.N)]
# Create the new map
cmap = cmap.from_list('Custom cmap', cmaplist, cmap.N)

def show_clusters(C, y, i):
    plt.scatter(x1, x2, c=y, cmap=cmap, s=0.5)
    plt.scatter(C[:, 0], C[:, 1], c = 'red', edgecolors='black', s=100, marker='*')
    plt.gca().set_aspect('equal')
    plt.title('Clustering: Step {}'.format(i))
    plt.axis('off')
    plt.show()
def new_centroids(centroids):
    centroids = np.array([np.mean(X[y == k], axis=0) for k in classes])
    return centroids
K = 15
classes = np.arange(K)
C = init_centroids(X, K)

for i in range(20):
    y = classify(C)
    C = new_centroids(C)
    show_clusters(C, y, i)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14877001171417414, 'fraction_numerical': 0.018352206169465052, 'mean_word_length': 3.779850746268657, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '362178', 'license': 'MIT', 'n_tokens_mistral': 1017, 'n_tokens_neox': 985, 'n_words': 252, 'path': 'K-Means-Clustering/K-Means-Clustering.ipynb', 'repo_name': 'hrshtv/ML-Algorithms', 'size': '2561'}