<jupyter_start><jupyter_text>K-meansThe key idea: __Step 1: random selection of centroids____Step 2: calculate distance to each point and assign each point to cluster____Step 3: calculate average of the assigned points and____Step 4: move centroids to the new position____Step 5: Steps 2-4 until cluster assignment is not changed__<jupyter_code>def dist(a, b):
    return np.linalg.norm(a - b)
def dist_2d(a,b):
    squared_distance = 0
    for i in range(len(a)):
        squared_distance += (a[i] - b[i])**2
    dist = sqrt(squared_distances)
    return dist<jupyter_output><empty_output><jupyter_text>Make some fake data<jupyter_code>fake_centers = 4

x, y = make_blobs(n_samples=5000, centers=fake_centers, n_features=2, random_state=195)

x2 = deepcopy(x)
y2 = deepcopy(y)
# plot regression dataset
%matplotlib inline
pyplot.scatter(x[:, 0], x[:, 1])
pyplot.show()<jupyter_output><empty_output><jupyter_text>Let's say that we want to cluster our data into 3 groups<jupyter_code>number_of_clusters = fake_centers
def generate_random_clusters(n_features, k):
    c_position = []
    for i in range(n_features):
        c_position.append(np.random.randint(0.8 * np.min(x[:, i]), 0.8 * np.max(x[:, i]), size=k)) 
                                           # 0.8 to stay in the range (it really doesn't matter as this
                                           #                           is random initialization)
    return c_position
n_features = 2
c_positions = generate_random_clusters(n_features, number_of_clusters) 
c_positions = np.array(c_positions).T
print(c_positions)
print(x)
pyplot.scatter(x[:, 0], x[:, 1])
pyplot.scatter(c_positions[:, 0], c_positions[:, 1], marker='*', s=300, c='orange')
pyplot.show()<jupyter_output><empty_output><jupyter_text>Error function is defined as distance between new centroids and old centroids<jupyter_code>def error(c, c_old):
    return dist(c, c_old)<jupyter_output><empty_output><jupyter_text>So now we are ready to start K-means we need to loop until error is zero then we can break<jupyter_code>def kmeans(x, c_positions, number_of_clusters):
    clusters = np.zeros(len(x))
    old_clusters = np.zeros(c_positions.shape)
    error = 1
    while error != 0:
        for i in range(len(x)):
            distances = [dist(x[i], c) for c in c_positions]
            cluster = np.argmin(distances)
            clusters[i] = cluster        
        
        old_clusters = deepcopy(c_positions)
    
        for j in range(0, number_of_clusters):
            points = [x[n] for n in range(len(x)) if clusters[n] == j]
            c_positions[j] = np.mean(points, axis=0)        
        
        error = dist(c_positions, old_clusters)
        
    return c_positions, clusters
new_clusters, p = kmeans(x, c_positions, number_of_clusters)
print(new_clusters)
pyplot.scatter(x[:, 0], x[:, 1])
pyplot.scatter(new_clusters[:, 0], new_clusters[:, 1], marker='*', s=300, c='r')
pyplot.show()
def plot_in_col(x, number_of_clusters, p, new_clusters):
    for i in range(number_of_clusters):
        col_points = np.array([x[n] for n in range(len(x)) if p[n] == i])
        pyplot.scatter(col_points[:, 0], col_points[:, 1], s=10)
    pyplot.scatter(new_clusters[:, 0], new_clusters[:, 1], marker='*', s=300, c='r')
    pyplot.show()
plot_in_col(x, number_of_clusters, p, new_clusters)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1230631704410012, 'fraction_numerical': 0.01728247914183552, 'mean_word_length': 3.6689847009735743, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '309216', 'license': 'MIT', 'n_tokens_mistral': 1220, 'n_tokens_neox': 1171, 'n_words': 294, 'path': 'k-means-from-scratch.ipynb', 'repo_name': 'tpalczew/kmeans-from-scratch', 'size': '3356'}