Вторая, последняя часть серии, мы рассмотрим алгоритмы неконтролируемого обучения, которые состоят из данных без меток. Давайте сразу перейдем к заданию, поскольку сегодня мы рассмотрим два алгоритма.

Кластеризация K-средних - это один из методов кластерного анализа, который позволяет группировать данные в группы, называемые кластерами. Поскольку метки не предусмотрены для каждых обучающих данных, кластеры определяются по схожести данных друг с другом.

Мы начнем с реализации алгоритмов K-средних. Поскольку K-средства - это итеративный процесс, который назначает обучающие примеры их ближайшим центроидам, а затем пересчитывает центроиды, нам нужны две основные функции, которые именно это делают.

import numpy as np
import matplotlib.pyplot as plt
from scipy.io import loadmat
mat = loadmat("ex7data2.mat")
X = mat["X"]

findClosestCentroids найдите ближайшие центроиды, оценив расстояние между обучающим примером от каждого центроида, и назначьте центроид обучающему примеру с наименьшим расстоянием.

def findClosestCentroids(X, centroids):
    """
    Returns the closest centroids in idx for a dataset X where each row is a single example.
    """
    K = centroids.shape[0]
    idx = np.zeros((X.shape[0],1))
    temp = np.zeros((centroids.shape[0],1))
    
    for i in range(X.shape[0]):
        for j in range(K):
            dist = X[i,:] - centroids[j,:]
            length = np.sum(dist**2)
            temp[j] = length
        idx[i] = np.argmin(temp)+1
    return idx
# Select an initial set of centroids
K = 3
initial_centroids = np.array([[3,3],[6,2],[8,5]])
idx = findClosestCentroids(X, initial_centroids)
print("Closest centroids for the first 3 examples:\n",idx[0:3])

np.argmin найдите индекс с наименьшим расстоянием и назначьте его обучающему примеру. +1 используется здесь для нумерации центроида от 1 вместо 0.

Оператор печати напечатает:

Ближайшие центроиды для первых трех примеров:
[[1.]
[3.]
[2.]]

Чтобы вычислить средние центроиды после присвоения, мы суммируем обучающие примеры, назначенные конкретному центроиду, и делим их на количество примеров в каждом центроиде.

def computeCentroids(X, idx, K):
    """
    returns the new centroids by computing the means of the data points assigned to each centroid.
    """
    m, n = X.shape[0],X.shape[1]
    centroids = np.zeros((K,n))
    count = np.zeros((K,1))
    
    for i in range(m):
        index = int((idx[i]-1)[0])
        centroids[index,:]+=X[i,:]
        count[index]+=1
    
    return centroids/count
centroids = computeCentroids(X, idx, K)
print("Centroids computed after initial finding of closest centroids:\n", centroids)

Оператор печати напечатает:

Центроиды, вычисленные после первоначального нахождения ближайших центроидов:
[[2.42830111 3.15792418]
[5.81350331 2.63365645]
[7.11938687 3.6166844]]

Теперь, чтобы визуализировать весь процесс, я создал подзаговор для каждой итерации алгоритмов, чтобы отслеживать движение центроидов и назначение обучающих примеров.

def plotKmeans(X, centroids, idx, K, num_iters):
    """
    plots the data points with colors assigned to each centroid
    """
    m,n = X.shape[0],X.shape[1]
    
    fig, ax = plt.subplots(nrows=num_iters,ncols=1,figsize=(6,36))
    
    for i in range(num_iters):    
        # Visualisation of data
        color = "rgb"
        for k in range(1,K+1):
            grp = (idx==k).reshape(m,1)
            ax[i].scatter(X[grp[:,0],0],X[grp[:,0],1],c=color[k-1],s=15)
# visualize the new centroids
        ax[i].scatter(centroids[:,0],centroids[:,1],s=120,marker="x",c="black",linewidth=3)
        title = "Iteration Number " + str(i)
        ax[i].set_title(title)
        
        # Compute the centroids mean
        centroids = computeCentroids(X, idx, K)
        
        # assign each training example to the nearest centroid
        idx = findClosestCentroids(X, centroids)
    
    plt.tight_layout()
m,n = X.shape[0],X.shape[1]
plotKmeans(X, initial_centroids,idx, K,10)

Поскольку алгоритмы K-средних не всегда дают оптимальное решение, важна случайная инициализация.

def kMeansInitCentroids(X, K):
    """
    This function initializes K centroids that are to beused in K-Means on the dataset X
    """
    m,n = X.shape[0], X.shape[1]
    centroids = np.zeros((K,n))
    
    for i in range(K):
        centroids[i] = X[np.random.randint(0,m+1),:]
        
    return centroids
centroids = kMeansInitCentroids(X, K)
idx = findClosestCentroids(X, centroids)
plotKmeans(X, centroids,idx, K,10)

Приведенный выше код снова запустит визуализацию, но со случайной инициализацией. Вы можете запустить код несколько раз, чтобы увидеть влияние случайных начальных центроидов.

Теперь, когда мы закончили кодирование алгоритма, мы можем приступить к его реализации с другими наборами данных. В этом упражнении мы будем использовать алгоритм для выбора 16 кластеров для представления изображения (вместо тысяч цветов) для сжатия изображения.

mat2 = loadmat("bird_small.mat")
A = mat2["A"]
# preprocess and reshape the image
X2 = (A/255).reshape(128*128,3)
def runKmeans(X, initial_centroids,num_iters,K):
    
    idx = findClosestCentroids(X, initial_centroids)
    
    for i in range(num_iters):
        
        # Compute the centroids mean
        centroids = computeCentroids(X, idx, K)
# assign each training example to the nearest centroid
        idx = findClosestCentroids(X, initial_centroids)
return centroids, idx

Теперь, чтобы запустить алгоритм k-средних для набора данных

K2 = 16
num_iters = 10
initial_centroids2 = kMeansInitCentroids(X2, K2)
centroids2, idx2 = runKmeans(X2, initial_centroids2, num_iters,K2)
m2,n2 = X.shape[0],X.shape[1]
X2_recovered = X2.copy()
for i in range(1,K2+1):
    X2_recovered[(idx2==i).ravel(),:] = centroids2[i-1]
# Reshape the recovered image into proper dimensions
X2_recovered = X2_recovered.reshape(128,128,3)
# Display the image
import matplotlib.image as mpimg
fig, ax = plt.subplots(1,2)
ax[0].imshow(X2.reshape(128,128,3))
ax[1].imshow(X2_recovered)

Это параллельное сравнение исходного изображения и сжатого изображения, содержащего всего 16 цветов.

В следующей части задания используется набор 2D-данных, чтобы получить интуитивное представление о процессе анализа главных компонентов (PCA), а затем провести PCA для набора данных изображения лица для уменьшения размерности.

Загрузите и визуализируйте набор 2D-данных

mat3 = loadmat("ex7data1.mat")
X3 = mat3["X"]
plt.scatter(X3[:,0],X3[:,1],marker="o",facecolors="none",edgecolors="b")

Чтобы реализовать алгоритм PCA, PCA также состоит из двух вычислительных шагов, на которых мы закодируем один из них для вычисления ковариационной матрицы и будем использовать библиотеку numpy для другого, чтобы получить собственные векторы.

Перед этим необходима нормализация функций, чтобы гарантировать, что данные находятся в одном диапазоне.

def featureNormalize(X):
    """
    Returns a normalized version of X where the mean value of each feature is 0 and the standard deviation is 1.
    """
    mu = np.mean(X,axis=0)
    sigma = np.std(X,axis=0)
    
    X_norm = (X - mu)/sigma
    
    return X_norm, mu , sigma
def pca(X):
    """
    Computes eigenvectors of the covariance matrix of X
    """
    m,n = X.shape[0], X.shape[1]
    
    sigma = 1/m * X.T @ X
    
    U,S,V = svd(sigma)
    
    return U,S,V

np.linalg.svd аналогична функции svd в matlab и возвращает те же матрицы U, S, V. Официальную документацию можно найти здесь.

from numpy.linalg import svd
X_norm,mu,std = featureNormalize(X3)
U,S = pca(X_norm)[:2]
plt.scatter(X3[:,0],X3[:,1],marker="o",facecolors="none",edgecolors="b")
plt.plot([mu[0],(mu+1.5*S[0]*U[:,0].T)[0]],[mu[1],(mu+1.5*S[0]*U[:,0].T)[1]],color="black",linewidth=3)
plt.plot([mu[0],(mu+1.5*S[1]*U[:,1].T)[0]],[mu[1],(mu+1.5*S[1]*U[:,1].T)[1]],color="black",linewidth=3)
plt.xlim(-1,7)
plt.ylim(2,8)

Приведенный выше блок кода реализует PCA в наборе данных и визуализирует собственные векторы в данных. Я обнаружил, что Википедия имеет хороший источник информации по большинству алгоритмов обучения и определенно стоит поискать, если вы хотите глубже изучить алгоритмы.

print("Top eigenvector U(:,1) =:",U[:,0])`

Оператор печати print: Top eigenvector U(:,1) =: [-0.70710678 -0.70710678]

Чтобы уменьшить размер набора данных, мы проецируем данные на найденные главные компоненты (собственные векторы).

def projectData(X, U, K):
    """
    Computes the reduced data representation when projecting only on to the top k eigenvectors
    """
    m = X.shape[0]
    U_reduced = U[:,:K]
    Z = np.zeros((m,K))
    
    for i in range(m):
        for j in range(K):
            Z[i,j] = X[i,:] @ U_reduced[:,j]
    
    return Z
# Project the data onto K=1 dimension
K=1
Z = projectData(X_norm, U, K)
print("Projection of the first example:",Z[0][0])

Оператор печати напечатает: Projection of the first example: 1.4963126084578515

Данные также можно приблизительно восстановить, спроецировав их обратно в исходное размерное пространство.

def recoverData(Z, U, K):
    """
    Recovers an approximation of the original data when using the projected data
    """
    m,n = Z.shape[0],U.shape[0]
    X_rec = np.zeros((m,n))
    U_reduced = U[:,:K]
    
    for i in range(m):
        X_rec[i,:] = Z[i,:] @ U_reduced.T
    
    return X_rec
X_rec  = recoverData(Z, U, K)
print("Approximation of the first example:",X_rec[0,:])

Оператор печати напечатает: Approximation of the first example: [-1.05805279 -1.05805279]

Чтобы визуализировать весь процесс,

plt.scatter(X_norm[:,0],X_norm[:,1],marker="o",label="Original",facecolors="none",edgecolors="b",s=15)
plt.scatter(X_rec[:,0],X_rec[:,1],marker="o",label="Approximation",facecolors="none",edgecolors="r",s=15)
plt.title("The Normalized and Projected Data after PCA")
plt.legend()

Наконец, мы переходим к более сложному набору данных - набору данных изображений лица. Чтобы загрузить и визуализировать данные,

mat4 = loadmat("ex7faces.mat")
X4 = mat4["X"]
fig, ax = plt.subplots(nrows=10,ncols=10,figsize=(8,8))
for i in range(0,100,10):
    for j in range(10):
        ax[int(i/10),j].imshow(X4[i+j,:].reshape(32,32,order="F"),cmap="gray")
        ax[int(i/10),j].axis("off")

Эти изображения содержат 32 x 32 пикселя в оттенках серого, что дает размерность 1024 объекта, и наша задача - уменьшить размер примерно до 100 основных компонентов, которые лучше всего описывают наши данные.

X_norm2 = featureNormalize(X4)[0]
# Run PCA
U2 =pca(X_norm2)[0]
#Visualize the top 36 eigenvectors found
U_reduced = U2[:,:36].T
fig2, ax2 = plt.subplots(6,6,figsize=(8,8))
for i in range(0,36,6):
    for j in range(6):
        ax2[int(i/6),j].imshow(U_reduced[i+j,:].reshape(32,32,order="F"),cmap="gray")
        ax2[int(i/6),j].axis("off")

Выше представлена ​​визуализация 36 основных компонентов, которые описывают самые большие вариации в наборе данных.

Затем мы проецируем данные на первые 100 основных компонентов, эффективно уменьшаем размерность до сотни, восстанавливаем данные и пытаемся понять, что теряется в процессе уменьшения размерности.

K2 = 100
Z2 = projectData(X_norm2, U2, K2)
print("The projected data Z has a size of:",Z2.shape)
# Data reconstruction
X_rec2  = recoverData(Z2, U2, K2)
# Visualize the reconstructed data
fig3, ax3 = plt.subplots(10,10,figsize=(8,8))
for i in range(0,100,10):
    for j in range(10):
        ax3[int(i/10),j].imshow(X_rec2[i+j,:].reshape(32,32,order="F"),cmap="gray")
        ax3[int(i/10),j].axis("off")

Это конец обучения без учителя. С нетерпением ждите последней статьи в этой серии. Записная книжка Jupyter будет загружена на мой GitHub по адресу (https://github.com/Benlau93/Machine-Learning-by-Andrew-Ng-in-Python).

Для другой реализации Python в этой серии:

Спасибо за чтение.