<jupyter_start><jupyter_text>Spectral Clustering Applications and its Enhancements ---------------------------------------------------------------------you can Find me on Github:>  [ GitHub](https://github.com/lev1khachatryan) ***Abstract*** - The spectral clustering algorithm is an algorithm forplacing N data points in an I-dimensional space into different clusters.Each cluster is described by its similarity, which means that the pointsin the same cluster are similar and points in different clusters aredissimilar to each other. Recently, spectral clustering has become anincreasingly espouse tool and has been applied in many areas such asstatistics, machine learning, pattern recognition, data mining, andimage processing. This survey paper discusses these methods in detailand later on introduces the relationship between spectral clusteringand k-means clustering and spectral clustering's applications in imagesegmentation, educational data mining, entity resolution and speechseparation. It also mention the improvements in this algorithm usingNystrom methods.         1. INTRODUCTION--------------------------------------------------------------------- Clustering is a task of grouping a set of objects into classeswith similar characteristics. There are many data clusteringalgorithms that do a good job. However, recently spectraltechniques for data clustering have emerged as a powerfultool for clustering data. To solve the clustering problem wecalculate the eigenvectors and eigen values of the graphlaplacian which is a similarity measure between two datapoints. The clustering is obtained from the eigenvectors.Many algorithms have been proposed for spectral clusteringwhich are small disparity of the above technique. In thissurvey report, we will discuss spectral clustering, a morepowerful and specialized clustering algorithm[4] (comparedto K-means)There are several motivations for clustering as following:* A good clustering has predictive power.* Clusters can be useful in communication because theyallow people to put objects with similar features into onecategory and to name them.* Failures of one cluster model may draw special attentionto interesting objects.* Clusters may serve as models of learning processes inneural systems. Spectral clustering[4] glean its name from spectral analysisof a graph, which is how the data are represented. Spectralclustering techniques reduce dimensions using the eigenvalues of the similarity matrix of the data. The similaritymatrix[4] is provided as an input and consists of aquantitative evaluation of the relative similarity of each pairof points in the dataset. The spectral clustering algorithm isan algorithm for grouping N data points in an I-dimensionalspace into several clusters. Each cluster is parameterized byits similarity, which means that the points in the same groupare similar and points in different groups are dissimilar toeach other. We start the algorithm by presenting the datapoints in the form of similarity graph, and then we need to find a partition of the graph so that the points within agroup are similar and the points between different groupsare dissimilar to each other. The partition can be done invarious ways such as minimum cut method, ratio cutmethod, and normalized and MinMaxCut Method[3]. Thisnotebook will discuss the relationship between spectralclustering and k-means clustering and spectral clustering'sapplications in different areas.        2. SPECTRAL CLUSTERING ALGORITHM--------------------------------------------------------------------- Spectral clustering is an appealingly simple: Given somedata, you build an ***affinity (or kernel) matrix***, analyze itsspectrum, and often get a perfect clustering from thedominant eigen vectors for free. This simple algorithm[4]or its slightly more complex variants which yield so goodresults are widely appreciated for applications.***Here are the key steps of spectral clustering algorithm:***  Given a set of points S = {s1, . . . , sn } in a highdimensional space.1. Form a distance matrix D ∈ R2. This distance measure is Euclidean, but other measures also make sense.2. Transform the distance matrix to an affinity matrix by $A_{i,j}$= $exp(− σ_{i,j} )$ if i ≠ j, 0 if i = j. The free parameter σ controls the rate at which affinity drops off with distance.3. Form the diagonal matrix D whose (i,i) element is the sum of A’s ith row, and create the Laplacian matrix L = $D^{−1/2} AD^{−1/2}$4. Obtain the eigenvectors and eigenvalues of L.5. Form a new matrix from the vectors associated with the k largest eigenvalues. Choose k by using eigen gap method.6. Each item now has a vector of k coordinates in the transformed space. Normalize these vectors to unit length.7. Cluster in k-dimensional space. The result will be k wella separated clusters. Spectral clustering is a more advanced algorithm comparedto k-means as it uses several mathematical concepts (i.e.degree matrices weight matrices, similarity matrices,similarity graphs, graph Laplacians, eigenvalues andeigenvectors) in order to divide similar data points in thesame group and dissimilar data points in different groups.This Spectral Clustering works well for many real worlddata sets eventhough, it needs some modification in termsof improving its time complexity, space complexity.         3. SPECTRAL CLUSTERING APPLICATIONS IN RECENT LITERATURE--------------------------------------------------------------------- Spectral Clustering has been extensively used in manyareas, including in the statistics, machine learning, patternrecognition, data mining, and image processing  3.1 Image segmentation --------------------------------------------------------------------- In digital image processing, segmentation is important forimage description and classification. Clusters can be formedfor images build on pixel intensity, color, texture, location,or some combination of these. "Spectral clustering involvesthe eigen decomposition of a pair wise similarity matrix,which is intractable for sufficiently large images. Downsizing the image, however, will cause a loss of finer detailsand can lead to inaccurate segmentation results" (Tung,Wong, and Clausi, 2010). So Tung et al. (2010)[7]proposed a method of spectral clustering to large imagesusing a combination of block wise processing andstochastic ensemble consensus. The idea of this method isto perform an over-segmentation of the image at the pixellevel using spectral clustering, and then merge the segmentsusing a combination of stochastic ensemble consensus and asecond round of spectral clustering at the segment level.And we use stochastic ensemble consensus o integrate bothglobal and local image characteristics in determining thepixel classifications. This step also removes blockwiseprocessing artifacts. (Tung et al., 2010) Tung et al. (2010)[7]also presented the experimental results on a set of naturalscene images (from the Berkeley segmentation database) ofthe normalized cut, the self-tuning spectral clustering.Theyconclude that "the proposed method achieves segmentationresults that are comparable to or better than the other twomethods. In particular, detailed structures are betterpreserved in the segmentation, as reflected in the higherrecall values" (Tung et al., 2010)[7]  3.2 Speech separation--------------------------------------------------------------------- While linkage algorithms and k-means algorithms are verypopular in speech processing and robust to noise, they areonly best suited for rounded linearly separable clusters.However, spectral clustering is able to find extendedclusters and is more robust to noise than the above twoalgorithms. Bach and Jordan applied spectral clustering todata from four different male and female speakers withspeech signals of duration 3 seconds based on a costfunction that characterized how close the eigen structure ofa similarity matrix W is to a partition E. According to <NAME>ordan[2], "minimizing this cost function with respectto the partition E leads to a new clustering algorithm thattakes the form of weighted k-means algorithms. Minimizingthem with respect to W yields a theoretical framework forlearning the similarity matrix". The basic idea of theiralgorithm is to combine the knowledge of physical andpsychophysical properties of speech with learningalgorithms. The physical properties provide parameterizedsimilarity matrices for spectral clustering and thepsychophysical properties help generate segmented trainingdata. There were 15 parameters to estimate using Bach andJordan's [2] spectral learning algorithm. For testing, theyused mixes from speakers which were different from thosein the training set (the four different male and femalespeakers with speech signals of duration 3 seconds). <NAME>'s analyzed that the performance of theseparation is good enough to obtain audible signals ofreasonable quality even though some components of the"black" speaker are missing. As we can seen from theresults, the proposed approach was successful in demixingthe speech signals from two speakers<jupyter_code>%load_ext watermark
import warnings
warnings.filterwarnings("ignore") 
from IPython.core.display import display, HTML

import time

import pandas as pd
import pandas_datareader.data as web
import numpy as np

import matplotlib as mpl
import matplotlib.pyplot as plt
%matplotlib inline
%watermark
from sklearn.datasets import make_moons
random_state = 21
X_mn, y_mn = make_moons(150, noise=.07, random_state=random_state)
cmap = 'viridis'
dot_size=50

fig, ax = plt.subplots(figsize=(9,7))
ax.set_title('Data with ground truth labels ', fontsize=18, fontweight='demi')

ax.scatter(X_mn[:, 0], X_mn[:, 1],c=y_mn,s=dot_size, cmap=cmap)
from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=2, random_state=0).fit(X_mn)
fig, ax = plt.subplots(figsize=(9,7))
ax.set_title('Data after trying to cluster using Kmeans', fontsize=18, fontweight='demi')

ax.scatter(X_mn[:, 0], X_mn[:, 1],c=kmeans.labels_,s=dot_size, cmap=cmap)
from sklearn.neighbors import radius_neighbors_graph
from sklearn.neighbors import kneighbors_graph
A = radius_neighbors_graph(X_mn,0.4,mode='distance', metric='minkowski', p=2, metric_params=None, include_self=False)
# A = kneighbors_graph(X_mn, 2, mode='connectivity', metric='minkowski', p=2, metric_params=None, include_self=False)
A = A.toarray()
A.shape
fig, ax = plt.subplots(figsize=(9,7))
ax.set_title('5 first datapoints', fontsize=18, fontweight='demi')
ax.set_xlim(-1, 2)
ax.set_ylim(-1,1)
ax.scatter(X_mn[:5, 0], X_mn[:5, 1],s=dot_size, cmap=cmap)
for i in range(5):
    ax.annotate(i, (X_mn[i,0],X_mn[i,1]))
from scipy.sparse import csgraph
from sklearn.cluster import KMeans
L = csgraph.laplacian(A, normed=False)
B = np.sum(A,axis=0)
B[:2]
eigval, eigvec = np.linalg.eig(L)
kmeans = KMeans(n_clusters=2, random_state=0).fit(eigvec)
# kmeans
np.where(eigval == np.partition(eigval, 1)[1]) 
eigval[:20]
eigvec[3]
y_spec =eigvec[:,1].copy()
y_spec[y_spec < 0] = 0
y_spec[y_spec > 0] = 1
type(y_spec),y_mn.shape,y_spec.shape
fig, ax = plt.subplots(figsize=(9,7))
ax.set_title('Data after spectral clustering from scratch', fontsize=18, fontweight='demi')
ax.scatter(X_mn[:, 0], X_mn[:, 1],c=y_spec ,s=dot_size, cmap=cmap)
from sklearn.cluster import SpectralClustering

model = SpectralClustering(n_clusters=2, affinity='nearest_neighbors',
                          assign_labels='kmeans')

labelsS = model.fit_predict(X_mn)

fig, ax = plt.subplots(figsize=(9,7))
ax.set_title('Built in sklearn spectral clustering', fontsize=18, fontweight='demi')
plt.scatter(X_mn[:, 0], X_mn[:, 1], c=labelsS, s=dot_size, cmap=cmap)
model<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09315866084425037, 'fraction_numerical': 0.01087421868310643, 'mean_word_length': 4.6072971675468075, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 1, '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': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '634076', 'license': 'MIT', 'n_tokens_mistral': 3106, 'n_tokens_neox': 2848, 'n_words': 1415, 'path': 'Lectures/Levon/SpectralClustering/main.ipynb', 'repo_name': 'lev1khachatryan/ASDS_ML-2', 'size': '11690'}