Домашнее задание №8
Deadline: 20.05.2017 23:59:59
ФИВТ, АПТ, Курс по машинному обучению, Весна 2017, Модуль Unspervised Learning,
Alexey Romanenko, alexromsput@gmail.com
Дополнительный материал для выполнения дз:
Оформление дз:
ml.course.mipt@gmail.comML2017_fall <номер_группы> <фамилия>, к примеру -- ML2017_fall 496 ivanov<фамилия>_<группа>_task<номер задания>.ipnb, к примеру -- ML2017_496_task1.ipnbВопросы:
ml.course.mipt@gmail.comML2016_fall Question <Содержание вопроса>Ответе на вопросы своими словами (загугленный материал надо пересказать), ответ обоснуйте (напишите и ОБЪЯСНИТЕ формулки если потребуется), если не выходит, то вернитесь к лекции дополнительным материалам:
Вопрос 1: В чём заключается проблема мультиколлинеарности?
Вопрос 2: Какие проблемы при обучении алгоритмов возникают из-за большой разамерности пространства признаков?
Вопрос 3: В чем суть проклятия размерности?
Вопрос 4: Какая связь между решением задачи PCA и SVD-разложение матрицы регрессии?
Вопрос 5: Почему в tSNE расстояние между парамми объектов измеряется "по-стьюденту" и как это помогает решить проблему "скрученности" (crowding problem)?
Вопрос 6: На какой идее базируются алгоритмы аггломеративной кластеризации? Напишите формулу Ланса-Вильма
Вопрос 7: Какие два шага выделяют в алгоритме кластеризации k-means?
Вопрос 8: В чём отличия (основные упрощения) k-means от EM-алгоритма кластеризации?
Вопрос 9 Какой принцип работы графовых алгоритмов кластеризации?
Вопрос 10 В чем некорректность постановки задачи кластеризации?
PS: Если проверяющий не понял ответ на большинство вопросов, то будет пичалька. Пишите так, чтобы можно было разобраться.
Задача 1 Ответьте на вопросы:
1) Как можно не прибегая к визуализации понять, что кластерная структура у данного облака точек отсутствует?
Можно несколько раз прогнать алгоритм/алгоритмы кластеризации и посмотреть на результаты. Если они получились плохими (например межкластерное расстояние и др.), или сильно меняются в зависимости от запуска, то скорее всего кластерной структуры нет.
2) Какие из алгоритмов кластеризации могут выделять кластеры с ленточной структурой?
3) Какие алгоритмы кластеризации чувствительны к шуму и перемычкам?
4) Каким образом приближают «центр кластера» в нелинейных пространствах?
В качестве центра такого кластера можно брать объект обучающей выборки, сумма расстояний от которого до всех остальных объектов кластера минимальна.
5) Каким образом можно определять число кластеров?
Можно применять алгоритм кластеризации, задавая различное число кластеров. Соответственно полагать число кластеров тому, на котором достигается максимальное качество алгоритма (внутрикластерное расстояние, межкластерное, их отношение и тд.). Либо можно использовать алгоритмы, сами определяющие оптимальное число кластеров (MeanShift).
Задача 2 Даны пять точек на числовой оси $X = (1; 5; 7; 8; 8)$, число кластеров равно 2. Рассчитайте ответ алгоритма K-means (финальные центры кластеров), если начальные центры кластеров c1 = 1, c2 = 10.
Ответ:
Задача 3 Докажите, что the k-means всегда сходится.
Критерием остановки k-means является то, что центры кластеров на очередной итерации не изменились. Так как кол-во возможных разбиений выборки конечно, то такое разбиение достигнется за конечное число итераций, так как на каждой итерации суммарное квадратичное не увеличивается.
Задача 4
Для сжатия размерности пространства алгоритм PCA применяется датасету с количеством признаков $D = 100$. Наблюдается следующий спектр собственных значений матрицы объектов-признаков.
In [12]:
import numpy as np
d = np.linspace(1.6, 0.5, 100) # аппроксимируем эту прямую
dTot = np.sum(d)
n = 100
var_i = np.array([np.sum(d[: i + 1]) / \
dTot * 100.0 for i in range(n)])
m = sum(var_i < 0.95 * 100)
print m
Если хотим терять не более 5% точности, то эффективная размерность $\sim 90$ по первому пункту. Так как 90 не сильно меньше 100, то понижать размерность с помощью PCA нет особого смысла. Либо терять точность.
In [5]:
import numpy as np
import pylab as plt
'''
Performs the Principal Coponent analysis of the Matrix F
Matrix must be n * l dimensions
where n is # features
l is # samples
'''
def PCA(F, varRetained = 0.95, show = False):
# Input
# F - initaial matrix
# Compute Covariance Matrix Sigma
# Input
(n, l) = F.shape
Sigma = 1.0 / l * F.dot(np.transpose(F))
# Compute eigenvectors and eigenvalues of Sigma by SVD
# U, V - matrix, d - array: Sigma = U * np.diag(d) * V
U, d, V = np.linalg.svd(F.T) # посчитать SVD матрицы Sigma
# compute the value m: number of minumum features that retains the given variance varRetaine
d = d**2
dTot = np.sum(d)
var_i = np.array([np.sum(d[: i + 1]) / \
dTot * 100.0 for i in range(n)])
m = sum(var_i < varRetained * 100)
print '%.2f %% variance retained in %d dimensions' % (var_i[m], m) #верните число m и точность, которая достигается при этом числе главных компонент
# plot the variance plot
if show:
plt.plot(var_i)
plt.xlabel('Number of Features')
plt.ylabel(' Percentage Variance retained')
plt.title('PCA $\% \sigma^2 $ vs # features')
plt.show()
# compute the reduced dimensional features by projection
U_reduced = V.T[:, :m] # только m главных компонент
G = F.T.dot(U_reduced) # вычислить матрицу в преобразованном пространстве
return G, U_reduced
In [6]:
# Примените алгоритм к данным MNIST
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_digits
X, y = load_digits(return_X_y=True)
X_train, X_test, Y_train, Y_test = train_test_split(X, y, train_size=0.7)
In [7]:
X_test.shape
Out[7]:
In [8]:
#################################################################
# PCA of training set
print 'Performing PCA - Principal COmponent Analysis'
Z, U_reduced = PCA(X.T, varRetained = 0.95, show = True)
In [9]:
print Z.shape
print U_reduced.shape
In [13]:
np.sum((Z.dot(U_reduced.T) - X)**2) / np.sum((X)**2)
Out[13]:
In [10]:
print Z
print U_reduced
На данных из sklearn.datasets.load_digits примените алгоритмы кластеризации (знания о метках классов при кластеризации использовать нельзя):
In [8]:
from sklearn.decomposition import PCA
from sklearn.cluster import DBSCAN
from sklearn import metrics
import numpy as np
import matplotlib.pyplot as plt
from sklearn.manifold import TSNE
from sklearn.decomposition import PCA
%matplotlib inline
In [9]:
np.random.seed(1)
digits = load_digits()
data = (digits.data)
target = digits.target
In [10]:
tsne = TSNE(n_components=2)
twod_data = tsne.fit_transform(data)
In [11]:
plt.figure(figsize=(10, 16))
colors = plt.cm.Spectral(np.linspace(0, 1, 10))
for i, color in enumerate(colors):
X_i = twod_data[target == i]
plt.scatter(X_i[:, 0], X_i[:, 1], c=color, label=str(i))
plt.legend(loc='best')
plt.title('clusters after t-SNE')
plt.show()
In [12]:
n_samples, n_features = data.shape
n_digits = len(np.unique(digits.target))
labels_true = digits.target
print 'n_digits: {}, n_samples {}, n_features {}'.format(n_digits, n_samples, n_features)
def run_dbscan(eps, min_samples):
db = DBSCAN(eps=eps, min_samples=min_samples).fit(twod_data)
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
labels = db.labels_
n_clusters_ = n_digits
return (db,
metrics.adjusted_rand_score(labels_true, labels),
metrics.adjusted_mutual_info_score(labels_true, labels))
In [13]:
from itertools import product
def get_best_params(eps_, min_samples_):
quality = []
for eps, min_sample in product(eps_, min_samples_):
r = run_dbscan(eps, min_sample)
quality.append(r[1]**2 + r[2]**2)
return list(product(eps_, min_samples_))[np.argmax(quality)]
In [14]:
best_params = get_best_params(np.arange(1, 5, 0.01), np.arange(5, 20))
print best_params
In [15]:
db = run_dbscan(*best_params)[0]
print run_dbscan(*best_params)
In [16]:
len(np.unique(db.labels_))
Out[16]:
In [17]:
colors = plt.cm.Spectral(np.linspace(0, 1, len(np.unique(db.labels_))))
plt.figure(figsize=(10, 16))
for i, label in enumerate(np.unique(db.labels_)):
X_i = twod_data[db.labels_ == label]
plt.scatter(X_i[:, 0], X_i[:, 1], c=colors[i], label=str(label))
plt.legend(loc='best')
plt.show()
In [18]:
cores_n = len(db.core_sample_indices_)
print 'number of core points: {}'.format(cores_n)
plt.figure(figsize=(10, 20))
for i in xrange(100):
plt.subplot(10, 10, i + 1)
plt.imshow(digits.images[db.core_sample_indices_[i]], cmap='binary')
plt.show()
In [19]:
noise = [i for i, x in enumerate(db.labels_) if x == -1]
print 'number of noise points: {}'.format(len(noise))
plt.figure(figsize=(10, 20))
for i, x in enumerate(noise[:100]):
plt.subplot(10, 10, i + 1)
plt.imshow(digits.images[x], cmap='binary')
plt.show()
По полученным результатам и высоким значениям метрик можно сказать, что понижение размерности t-SNE и примененный к этому DBSCAN хорошо работают.
-- KMeans
-- MeanShift
-- AgglomerativeClustering
In [20]:
img = plt.imread('two-birds.jpg')
plt.figure(figsize=(10, 16))
plt.imshow(img)
plt.axis('off')
plt.show()
In [21]:
from skimage.measure import compare_ssim
from sklearn.cluster import KMeans, AgglomerativeClustering, MeanShift
In [22]:
def run(clusterization, img):
img_data = np.copy(img).reshape(-1, 3)
clusters = clusterization.fit_predict(img_data)
for i, x in enumerate(np.unique(clusters)):
current_cluster = img_data[clusters == x]
img_data[clusters == x] = np.mean(current_cluster, axis=0)
new_img = img_data.reshape(img.shape)
plt.figure(figsize=(10, 10))
plt.title('clusters = {}'.format(len(np.unique(clusters))))
plt.imshow(new_img)
plt.show()
return new_img, compare_ssim(img, new_img, multichannel=True)
In [23]:
K = [2, 3, 10, 20]
for k in K:
print '\nSSIM = {:.3f}\n'.format(run(KMeans(n_clusters=k), img)[1])
In [24]:
from sklearn.cluster import estimate_bandwidth
img_data = np.copy(img).reshape(-1, 3)
quants = [0.2, 0.17, 0.055, 0.028] # for needed K
for q in quants:
bandwidth = estimate_bandwidth(img_data,
quantile=q,
n_samples=1000)
ms = MeanShift(bandwidth=bandwidth, bin_seeding=True)
print '\nSSIM = {}\n'.format(run(ms, img)[1])
In [25]:
from sklearn.neighbors import kneighbors_graph
In [26]:
graph = kneighbors_graph(img_data, 30, include_self=False)
for k in K:
print '\nSSIM = {:.3f}\n'.format(run(AgglomerativeClustering(n_clusters=k,
connectivity=graph), img)[1])
Самым лучшим и быстрым способом оказался KMeans
In [ ]: