<commit_before>'''Diffusion mapping by <NAME>, March 2009. Last modified, JWR: 3/23/2009 ported to python'''



import numpy as nu
from scipy.cluster.vq import kmeans2
from scipy.sparse import dok_matrix as spars
from scipy.sparse.linalg import svds

def diffuse(D,eps_val,t=None,neigen=None,threshold = 5E-6):
    ''' diffuse(D,eps_val,t,neigen)
    (ndarray or matrix, float, float, float
    D          --- pairwise distances, n-by-n matrix
    eps_val    --- parameter in weight matrix exp(-D^2/(4*eps_val))
    neigen     --- number of dimensions of final representation
    (default: 95% drop-off in eigenvalue multiplier)
    t          --- optional time parameter in diffusion map 
    (default: model with multiscale geometry)    
    threshold  --- the value in D which should be ignored
    
    Output: 
    X          --- non-trivial diffusion coords. (entered column-wise)  
    eigenvals  --- eigenvalues of Markov matrix
    psi        --- right eigenvectors of Markov matrix
    phi        --- left eigenvectors'''

    assert D.shape[0] == D.shape[1]
    n = D.shape[0]
    K = nu.exp(-D**2/(4.*eps_val)) #or equivalently, K=exp(-(D/sigmaK).^2)
    v = nu.mat(nu.sqrt(nu.sum(K,1)))
    #v = v(:)
    A = K / nu.asarray(v.T * v)   # symmetric graph Laplacian
    
    A[threshold < A] = 0
    #A = sparse(A)  # make matrix sparse to speed up calcs
    #print A.nnz
    if neigen is None:
        # eigendecomposition of symmetric matrix
        U,eigenvals,V = svds(A,51)  
        first_colum = nu.tile(U[:,0],(51,1)).T
    else:
        # eigendecomposition of symmetric matrix
        U,eigenvals,V = svds(A, neigen+1) 
        first_colum = nu.tile(U[:,0],(neigen+1,1)).T
    # right eigenv of Markov matrix
    psi = U / first_colum
    # left eigenv of Markov matrix
    phi = U * first_colum

    eigenvals = eigenvals[::-1]
    # DIFFUSION COORDINATES
    if not t is None: # fixed scale parameter
        lambda_t = eigenvals[1:]**t
        lambda_t = nu.tile(lambda_t,(n,1))
        if neigen is None: # use neigen corresponding to 95% drop-off in lambda_t
            lam = lambda_t[0,:] / lambda_t[0,0]
            neigen = nu.sum(lam < .05) # default number of eigenvalues
            if neigen == 0:
                neigen = 50 # use neigen=50 if 95% dropoff not attained
            print 'Used default value: %f dimensions'%neigen
  
        X = psi[:,:neigen] * lambda_t[:,:neigen]  # diffusion coords X
        #= right eigenvectors rescaled with eigenvalues
    else:  # multiscale geomtry
        lambda_multi = eigenvals[1:] / (1-eigenvals[1:])
        lambda_multi = nu.tile(lambda_multi,(n,1))
        if neigen is None:  # use neigen corresponding to 95% drop-off in lambda_multi
            lam = lambda_multi[0,:] / lambda_multi[0,0]
            neigen = nu.min(lam[lam<.05])
            if neigen == 0:# default number of eigenvalues
                neigen =  50 # use neigen=50 if 95% dropoff not attained
            print 'Used default value: %f dimensions'%neigen
        X = psi[:,1:neigen] * lambda_multi[:,:neigen]  # diffusion coords X
        

    return X,eigenvals, psi, phi

def diffusion_kmeans(X, k, phi0, Niter, epsilon=10**-3):
    '''DIFFUSION_KMEANS diffusion K-means clustering
     diffusion_kmeans(X, k, phi0, Niter, epsilon)
     
     
    Input:
    X(n,d)     --- diffusion coords (right eigenvecs rescaled with
                   eigenvals, skip first trivial one); each row is
                   data pt  
    k          --- number of clusters
    phi0       --- first left eigenvector of P (prop. to stationary distr)
    Niter      --- number of iterations to repeat the clustering with new IC
    epsilon    --- relative distortion (stopping criteria); default: 0.001
     
    Output:
    idx(n,1)   --- labeling of data points; labels between 1 and k
    C(k,d)     --- geometric centroids
    D          --- distortion (sum of squared distances)
    DX(n,k)    --- squared distance from each point to every centroid<commit_msg>fixed bugs and made work<commit_after>'''Diffusion mapping by <NAME>, March 2009. Last modified, JWR: 3/23/2009 ported to python'''



import numpy as nu
from scipy.cluster.vq import kmeans2
#from scipy.sparse.linalg import svds as svd
from scipy.linalg import svd

def diffuse(D,eps_val,neigen=None,t=None,threshold = 5E-6):
    ''' diffuse(D,eps_val,t,neigen)
    (ndarray or matrix, float, float, float
    D          --- pairwise distances, n-by-n matrix
    eps_val    --- parameter in weight matrix exp(-D^2/(4*eps_val))
    neigen     --- number of dimensions of final representation
    (default: 95% drop-off in eigenvalue multiplier)
    t          --- optional time parameter in diffusion map 
    (default: model with multiscale geometry)    
    threshold  --- the value in D which should be ignored
    
    Output: 
    X          --- non-trivial diffusion coords. (entered column-wise)  
    eigenvals  --- eigenvalues of Markov matrix
    psi        --- right eigenvectors of Markov matrix
    phi        --- left eigenvectors'''

    assert D.shape[0] == D.shape[1]
    n = D.shape[0]
    K = nu.exp(-D**2/(4.*eps_val)) #or equivalently, K=exp(-(D/sigmaK).^2)
    v = nu.mat(nu.sqrt(nu.sum(K,1)))
    #v = v(:)
    A = K / nu.asarray(v.T * v)   # symmetric graph Laplacian
    
    #A[threshold < A] = 0
    #A = sparse(A)  # make matrix sparse to speed up calcs
    #print A.nnz
    if neigen is None:
        # eigendecomposition of symmetric matrix
        U,eigenvals,V = svd(A) #,51)
        first_colum = nu.tile(U[:,0],(51,1)).T
        eigenvals = eigenvals[:51]
        # right eigenv of Markov matrix
        psi = U[:,:51] / first_colum
        # left eigenv of Markov matrix
        phi = U[:,:51] * first_colum
        
    else:
        # eigendecomposition of symmetric matrix
        U,eigenvals,V = svd(A) #, neigen+1) 
        first_colum = nu.tile(U[:,0],(neigen+1,1)).T
        eigenvals = eigenvals[:neigen+1]
        # right eigenv of Markov matrix
        psi = U[:,:neigen+1] / first_colum
        # left eigenv of Markov matrix
        phi = U[:,:neigen+1] * first_colum

    #eigenvals.sort()
    # DIFFUSION COORDINATES
    if not t is None: # fixed scale parameter
        lambda_t = eigenvals[1:]**t
        lambda_t = nu.tile(lambda_t,(n,1))
        if neigen is None: # use neigen corresponding to 95% drop-off in lambda_t
            lam = lambda_t[0,:] / lambda_t[0,0]
            neigen = nu.sum(lam < .05) # default number of eigenvalues
            if neigen < 1:
                neigen = 50 # use neigen=50 if 95% dropoff not attained
            print 'Used default value: % dimensions'%neigen
  
        X = psi[:,1:neigen+1] * lambda_t[:,:neigen+1]  # diffusion coords X
        #= right eigenvectors rescaled with eigenvalues
    else:  # multiscale geomtry
        lambda_multi = eigenvals[1:] / (1-eigenvals[1:])
        lambda_multi = nu.tile(lambda_multi,(n,1))
        if neigen is None:  # use neigen corresponding to 95% drop-off in lambda_multi
            lam = lambda_multi[0,:] / lambda_multi[0,0]
            neigen = nu.min(lam[lam<.05])
            if neigen < 1:# default number of eigenvalues
                neigen =  50 # use neigen=50 if 95% dropoff not attained
            print 'Used default value: %i dimensions'%neigen
        X = psi[:,1:neigen+1] * lambda_multi[:,:neigen+1]  # diffusion coords X
        

    return X,eigenvals, psi, phi

def diffusion_kmeans(X, k, phi0, Niter, epsilon=10**-3):
    '''DIFFUSION_KMEANS diffusion K-means clustering
     diffusion_kmeans(X, k, phi0, Niter, epsilon)
     
     
    Input:
    X(n,d)     --- diffusion coords (right eigenvecs rescaled with
                   eigenvals, skip first trivial one); each row is
                   data pt  
    k          --- number of clusters
    phi0       --- first left eigenvector of P (prop. to stationary distr)
    Niter      --- number of iterations to repeat the clustering with new IC
    epsilon    --- relative distortion (stopping criteria); default: 0.001
     
    Output:
    idx(n,1)   --- labeling of data points; labels between 1 and k
    C(k,d)     --- geometric centroids
    D          --- distortion (sum of squared distances)
    DX(n,k)    --- squared distance from each point to every centroid
{'fraction_non_alphanumeric': 0.1108297153883261, 'fraction_numerical': 0.021828268210323205, 'mean_word_length': 2.2508820070560565, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 5, '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}}
{'dir': 'git-commits-cleaned', 'id': '162726', 'n_tokens_mistral': 2833, 'n_tokens_neox': 2624, 'n_words': 818}