<jupyter_start><jupyter_text>Part 1: ImplementationImplement Multi-Dimensional Scaling<jupyter_code>from scipy.spatial.distance import pdist
from scipy.spatial.distance import squareform
import numpy as np


def centering(n):
    I = np.identity(n)
    O = np.ones((n, n))
    return I - O/n

def double_centering(D):
    n, n = D.shape
    J = centering(n)
    return (-1/2)*J*D*J

def eig_top(B, n):
    w, v = np.linalg.eig(B)
    i = np.argsort(w)[::-1]
    w, v = w[i].real, v[:,i].real
    return w[:n], v[:,:n]

"""Args:
X: input samples, array (num, dim)
n_components: dimension of output data

Returns:
Y: output samples, array (num, n_components)
"""
def MDS(X, n_components=2):
    D = squareform(pdist(X) ** 2)
    B = double_centering(D)
    w, E = eig_top(B, n_components)
    A = np.diag(np.sqrt(np.abs(w)))
    Y = E.dot(A)
    return Y<jupyter_output><empty_output><jupyter_text>Part 2: Manifold VisualizationVisualize the S-shaped 3-d dataset using the MDS.<jupyter_code>from sklearn import manifold, datasets

SX, St = datasets.make_s_curve(n_samples=1000, random_state=1337)
# SX: input data [n_samples, 3]
# St: univariate position along manifold [n_samples], use for coloring the plots<jupyter_output><empty_output><jupyter_text>The code in the next cell should draw a single plot with the following subplots:1. 3D S-shaped dataset2. 2D Manifold learnt using MDSUse the `St` variable to color the points in your visualizations. Use a color spectrum, and the position along the manifold to assign the color.<jupyter_code>#  Visualization code here
from matplotlib import pyplot as plt
%matplotlib notebook

MX = MDS(SX, 2)

fig = plt.figure(figsize=(6, 10))
axi = fig.add_subplot(211, projection='3d')
colorize = dict(c=St, cmap=plt.cm.get_cmap('rainbow', 4))
axi.scatter3D(SX[:, 0], SX[:, 1], SX[:, 2], **colorize)
axi.title.set_text('3D S-shaped dataset')

axi = fig.add_subplot(212)
axi.scatter([MX[:, 0]], [MX[:, 1]], **colorize)
axi.title.set_text('2D Manifold learnt using MDS')<jupyter_output><empty_output><jupyter_text>Part 2: Clustering and Visualizing high-dimensional dataPerform k-means and spectral clustering on the Swiss roll dataset and visualize using MDS.<jupyter_code># Swiss roll dataset loading here
import numpy


d = []
with open('./swissroll.dat', 'r') as dat_file:
    for line in dat_file:
        line = line.strip().split()
        line = [float(x.strip()) for x in line]
        d.append(line)
swissroll = numpy.array(d)
print (swissroll.shape)<jupyter_output>(1600, 3)<jupyter_text>The code in the next cell should draw a single plot with the following subplots:1. Visualize Swiss roll.2. Unwrap the manifold in 2D and visualize using MDS.<jupyter_code>import numpy    as np
from matplotlib import pyplot as plt
%matplotlib notebook


X  = swissroll
Xc = np.linspace(0, 1, X.shape[0])
MX = MDS(X, 10)

fig = plt.figure(figsize=(6, 10))
axi = fig.add_subplot(211, projection='3d')
colorize = dict(c=Xc, cmap=plt.cm.get_cmap('rainbow', 4))
axi.scatter3D(X[:, 0], X[:, 1], X[:, 2], **colorize)
axi.title.set_text('3D Swiss roll dataset')

axi = fig.add_subplot(212)
axi.scatter(MX[:, 0], MX[:, 1], **colorize)
axi.title.set_text('Unwrap the manifold in 2D using MDS')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13585951940850277, 'fraction_numerical': 0.02279728897104128, 'mean_word_length': 4.75709219858156, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 20, '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': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '610684', 'license': 'MIT', 'n_tokens_mistral': 1269, 'n_tokens_neox': 1209, 'n_words': 344, 'path': 'main.ipynb', 'repo_name': 'python3f/multidimensional_scaling', 'size': '3246'}