<jupyter_start><jupyter_text>This notebook implements K means clustering algorithm and principal components analysis (PCA), using numpy.  Imports and Data generation.<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from sklearn import datasets
from sklearn.datasets import make_classification
seed = 42
def generate_data(size):
  '''
  generate_data(size)
  This function generates synthetic data.
  size: number of examples in the dataset.
  return the dataset as a NumPy array.
  '''
  X, Y = datasets.make_classification(400, 3, 3, 0, n_classes=4, random_state=seed, n_clusters_per_class=1, class_sep=3)
  # plt.scatter(X[:, 0], X[:, 1])
  return X
# Generate data 
data = pd.DataFrame(generate_data(1000))<jupyter_output><empty_output><jupyter_text>K Means<jupyter_code># print first five rows in the data
data.head()
# repeat
# 1. Initilize centroids
# 2. compute distances
# 3. Assign to each cluster its data point
# 4. update the centrioid
# 1. Initilize centroids
def initlialize_centroids(data, k):
  '''
  initlialize_centroids(data, k)
  This function initializes random centroids by choosing them randomly from the data.
  data: dataset as a pandas DataFrame.
  k: number of centroids.
  return the centroids as DataFrame.
  '''
  # np.random.seed(seed)
  # data size
  n = data.shape[0]
  # Pick random indices
  inds = np.random.choice(n, size=k, replace=False)
  # pick the centriods
  centriods = data.iloc[inds, :]
  return centriods
# pick three random centriods
k = 4
centriods = initlialize_centroids(data, k)
centriods
# plt.scatter(centriods.to_numpy()[:, 0], centriods.to_numpy()[:, 1])
# 2. compute distances
from collections import defaultdict

def compute_distnce(data, centroids):
  '''
  compute_distnce(data, centriods)
  This function computes the distance between each point and the centroids.
  data: dataset as a pandas DataFrame.
  centroids: cluster centroids.
  it returns a data frame that contains the point distance from each cluster at each point.
  '''
  K = centroids.shape[0]
  dis_df = pd.DataFrame(columns= [f"c{i}" for i in range(1, K+1)])
  for k in range(K):
    dis_df[f"c{k+1}"] = ((data - centroids.iloc[k, :])**2).sum(axis=1)
  return dis_df
dis_df = compute_distnce(data, centriods)
dis_df
def assign_clusters(data, dis_df, centroids):
  '''
  assign_clusters(data, dis_df, centroids)
  This function assigns a point to each cluster based on the smallest distance to the cluster centroid.
  data: dataset as a pandas DataFrame.
  dis_df: data frame that contains the point distance from each cluster at each point.
  centroids: cluster centroids.
  returns a dictionary that contains the points in each cluster.
  '''
  K = centriods.shape[0]
  columns= [f"c{i}" for i in range(1, K+1)]
  d = {i: v for i, v in zip(range(K), columns)}
  argmin = dis_df.to_numpy().argmin(axis=1)
  clusters = {k:[] for k in columns}
  for i, dis in enumerate(dis_df.to_numpy()):
    min_ind = dis.argmin()
    # print(min_ind)
    point = data.iloc[i]
    cluster = d[min_ind]
    clusters[cluster].append(point.to_numpy())
  # print(clusters)
  return clusters
clu = assign_clusters(data, dis_df, centriods)
# 4. update the centrioid
def update_cnetriod(clusters, k, n):
  '''
  update_cnetriod(clusters, k, n).
  This function updates the values of the centroids after assigning each point to its corresponding cluster
  clusters: a dictionary that contains the points in each cluster.
  k: number of centroids.
  n: the shape of the data return the updated centroids as DataFrame.
  '''
  d = {}
  for i, cluster in enumerate(clusters):
    d[f"c{i+1}"] = np.mean(clusters[cluster], axis=0)
    # print(clusters[cluster])
    # print(d[f"c{i+1}"], len(clusters[cluster]))
  df = pd.DataFrame(d, columns=None).T
  df.columns = [i for i in range(n)]
  df.index = [i for i in range(k)]
  # print(df)
  return df
def K_means(data, iterations=1000, k=3, show_progress=False):
  '''
  K_means(data, iterations=1000, k=3, show_progress=False)
  This function implements K-means clustring algoithm.
  data: dataset as a pandas DataFrame.
  iterations: number of training iterations.
  k: number of clusters/centriods.
  show_progress: print the values of centriods after each iteration.
  '''
  centriods = initlialize_centroids(data, k)
  # print(centriods)
  n = data.shape[1]
  for i in range(iterations):
    dis_df = compute_distnce(data.copy(), centriods)
    # print(dis_df)
    # print(f"dis: {dis_df}")
    clusters = assign_clusters(data, dis_df, centriods)
    centriods = update_cnetriod(clusters, k, n)
    if show_progress:
      print(f"Iteration: {i+1}")
      print(centriods.to_numpy())
  return centriods, clusters
# run K-means algorithm 
final_centriods, _ = K_means(data, 10, 4, False)
# plot the results for the first two dimensions
plt.scatter(data.iloc[:, 0], data.iloc[:, 1])
plt.scatter(final_centriods.iloc[:, 0], final_centriods.iloc[:, 1])
# plot the results for the second two dimensions
plt.scatter(data.iloc[:, 1], data.iloc[:, 2])
plt.scatter(final_centriods.iloc[:, 1], final_centriods.iloc[:, 2])<jupyter_output><empty_output><jupyter_text>PCA<jupyter_code># PCA
# 1. Standarize your data
# 2. Compute the covariance matrix
# 3. Perform eigen decemposition to extract the k principle components 
data = data.copy()
# 1. Standarize your data
def standardize_data(data):
  return (data - data.mean()) / data.std()
# 2. Compute the covariance matrix
def cov_matrix(data):
  return data.to_numpy().T @ data.to_numpy()
# 3. Perform eigen decemposition to extract the k principle components 
def eig_decomp(m):
  e, v = np.linalg.eig(m)
  return e, v
def PCA(data, rank):
  '''
  PCA(data, rank)
  This function implements PCA using Eigendecomposition.
  return the prjection matrix and the eigenvalues
  '''
  # data_stand = standardize_data(data)
  cov = cov_matrix(data)
  e, v = eig_decomp(cov)
  P = v[:, :rank]
  return P, e
def PCA_SVD(data, rank):
  '''
  PCA(data, rank)
  This function implements PCA using Singular Value Decomposition (SVD).
  return the prjection matrix.
  '''
  U, D, V = np.linalg.svd(data)
  P = V[:,:rank]
  return P
P = PCA_SVD(data, 2)
# Using the first two principal components, we will plot the projected data and the centriods from the previous section
data_proj = data.to_numpy() @ P
centriods_proj = final_centriods.to_numpy() @ P
plt.scatter(data_proj[:, 0], data_proj[:, 1])
plt.scatter(centriods_proj[:, 0], centriods_proj[:, 1])
P = PCA(data, 2)
print(P[0])
data.shape
plt.scatter(data_proj[:, 0], data_proj[:, 1])
plt.scatter(centriods_proj[:, 0], centriods_proj[:, 1])
P, _ = PCA(data, 4)
# Now we will take the first three principal components, and plot the projected data and the centriods from the previous section
data_proj_3d = data.to_numpy() @ P
centriods_proj_3d = final_centriods.to_numpy() @ P
centriods_proj_3d
fig = plt.figure(figsize = (8, 7))
ax = plt.axes(projection ="3d")
ax.scatter3D(data_proj_3d[:, 0], data_proj_3d[:, 1], data_proj_3d[:, 2])
ax.scatter3D(centriods_proj_3d[:, 0], centriods_proj_3d[:, 1], centriods_proj_3d[:, 2])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1177874491085217, 'fraction_numerical': 0.014319809069212411, 'mean_word_length': 4.60062893081761, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, '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': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '13037', 'license': 'MIT', 'n_tokens_mistral': 2656, 'n_tokens_neox': 2535, 'n_words': 762, 'path': 'Faisal_Mohamed_K_means_and_PCA.ipynb', 'repo_name': 'FaisalAhmed0/machine_learning_from_scratch', 'size': '7123'}