<jupyter_start><jupyter_text>Diffusion Distance A distance function between any two points based on the random walk on the graph [1].Diffusion map Low dimensional description of the data by the first few eigenvectors [1].<jupyter_code>n = 3
X, y = make_blobs(n_samples=n, cluster_std=.1, centers=[[1,1]])
X<jupyter_output><empty_output><jupyter_text>Define a pairwise similarity matrix between points...<jupyter_code>L = k(X, .9)<jupyter_output><empty_output><jupyter_text>and a diagonal normalization matrix $D_{i,i} = \sum_j L_{i,j}$<jupyter_code>D = diag(L)<jupyter_output><empty_output><jupyter_text>Matrix M $M = D^{-1}L$<jupyter_code>M = inv(D).dot(L)<jupyter_output><empty_output><jupyter_text>The matrix M is adjoint to a symmetric matrix $M_s = D^{1/2}MD^{-1/2}$M and Ms share the same eigenvalues. Since Ms is symmetric, it is diagonalizable and has a set of _n_ real eigenvalues {$\lambda_{j=0}^{n-1}$} whose corresponding eigenvectors form an orthonormal basis of $\mathbf{R}^n$. The left and right eigenvectors of M, denoted $\phi_j$ and $\psi_j$ are related to those of Ms.$$ \phi_j = \mathbf{v}_j D^{1/2}, \psi_j = \mathbf{v}_j D^{-1/2} $$<jupyter_code>Ms = diag(D, .5).dot(M).dot(diag(D,-.5))<jupyter_output><empty_output><jupyter_text>---Now we utilize the fact that by constrution M is a stochastic matrix<jupyter_code>p0 = np.eye(n)<jupyter_output><empty_output><jupyter_text>*The stationary probability distribution $\Phi_0$ *<jupyter_code>e = p0
for i in range(1000):
    e = e.dot(M)
print e
p1 = p0.dot(M)
p1
w, v = eig(M)
w = w.real
print w
print v
# sorting the eigenvalues and vectors
temp = {_:(w[_], v[:,_]) for _ in range(len(w))}
w = []
v = []
for _ in sorted(temp.items(), key=lambda x:x[1], reverse=True):
    w.append(_[1][0])
    v.append(_[1][1])
w = np.array(w)
v = np.array(v).T
print w
print v
psi = v / v[:,0]
print psi<jupyter_output>[[ 1.          1.13561702  0.8453218 ]
 [ 1.         -1.29828484  0.5694839 ]
 [ 1.          0.15757678 -1.40039963]]<jupyter_text>Diffusion Map$$ \Psi_t(x) = (\lambda_1^t\psi(x), \lambda_2^t\psi(x), ..., \lambda_k^t\psi(x)) $$<jupyter_code>diffmap = (w.reshape(-1,1) * psi.T).T[:,1:]
diffmap<jupyter_output><empty_output><jupyter_text>Diffusion DistanceDefined by Euclidean distance in the diffusion map$$ D_t^2(x_0, x_1) = ||\Psi_t(x_0) - \Psi_t(x_1)||^2 $$<jupyter_code>dt0 = pairwise_distances(diffmap)**2
dt0<jupyter_output><empty_output><jupyter_text>Diffusion Distance [2]Defined by probability distribution on time _t_.$$D_t^2(x_0, x_1) = ||p(t, y|x_0) - p(t, y|x_1)||_w^2 \\= \sum_y (p(t, y|x_0) - p(t, y|x_1))^2 w(y)$$<jupyter_code>dt = []
for i in range(n):
    _ = []
    for j in range(n):
        _.append(sum((p1[i]-p1[j])**2 / v[:,0]**2))
    dt.append(_)
dt = np.array(dt)
dt
(dt0 - dt)
print M
M.sum(axis=1)
w, v = eig(M)
w = w.real
print w
print v
p0*w[0]*v[:,0]**2 + p0*w[1]*v[:,1]**2 + p0*w[2]*v[:,2]**2<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.18237704918032788, 'fraction_numerical': 0.045765027322404374, 'mean_word_length': 4.989775051124744, 'pattern_counts': {'":': 0, '<': 40, '<?xml version=': 0, '>': 40, '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': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '494506', 'license': 'MIT', 'n_tokens_mistral': 1306, 'n_tokens_neox': 1239, 'n_words': 281, 'path': 'subjects/diffusion maps/Diffusion Maps 02.ipynb', 'repo_name': 'NekuSakuraba/my_capstone_research', 'size': '2928'}