Catalog

1. Introduction to clustering

 2. Mathematical basis

2.1 Spectrum theorem and Rayleigh entropy

 2.2 The basis of probability theory

2.2.1 joint probability

2.2.2 Edge distribution

2.2.3 Conditional probability

2.3 graph theory

2.3.1 Directed graph

2.3.2 Undirected graph

 2.4 Lagrangian optimization

3 K-Means Algorithm

3.1 Algorithm steps

3.2 K-Medoids

3.3 K-Mean The defects of

4 gaussian GMM Model

4.1 summary

5 Spectral Clustering Spectral clustering

5.1 summary

5.2 step

5.3 summary

1. Introduction to clustering

Put similar things together

 2. Mathematical basis

2.1 Spectrum theorem and Rayleigh entropy

Spectrum theorem ： A symmetric matrix is divided into two rotation matrices and a scaling matrix , The scaling matrix is a diagonal matrix .

Rayleigh entropy ： The range of a vector depends on the scaling matrix

 2.2 The basis of probability theory

2.2.1 joint probability

2.2.2 Edge distribution

Remove one of the variables directly , Through joint distribution, separate x,y Distribution

2.2.3 Conditional probability

Appoint y For a certain value x The distribution of

Bayes' formula

2.3 graph theory

2.3.1 Directed graph

It consists of a series of nodes and a series of edges , Nodes represent random variables , Edges represent the connection between random variables .z For age ,x Represents hair color . Variables must be related in order to connect . There's a father son relationship

2.3.2 Undirected graph

No father son relationship , No direction

 2.4 Lagrangian optimization

The maximum value is at the tangent position

3 K-Means Algorithm

3.1 Algorithm steps

 1、 Given manually K Classes   2、 Which class is each point   3、 Update the location of the center point   4、 Iterate until the algorithm converges

Conditions for algorithm convergence ： 1、 The center point no longer moves   2、 The distribution points of all points are no longer changed

 3.2 K-Medoids

K-means For points with noise, the effect is not good .K-Medoids Don't choose the average , Instead, choose a point to minimize the distance sum of all points .

3.3 K-Mean The defects of

• K I don't know
• Sensitive to noise
• No confidence , It is unreasonable for the point at the boundary

4 gaussian GMM Model

4.1 summary

Gaussian model is used to describe each class , Give the probability that each point is of this kind

n Linear combination of Gaussian Models

5 Spectral Clustering Spectral clustering

5.1 summary

The previous points are clustered in Euclidean space , Therefore, the effect of irregular distribution is not good . Spectral clustering is based on the connectivity between points . Use the relationship between points to establish a similarity matrix , Find its eigenvector , Use the eigenvector of each point to K-Means clustering .

Calculate the similarity between points ,

The method of establishing undirected graph matrix ：

1、 There are connections between each node , Similarity is based on distance

2、 Each node only selects a few points close to it to connect    KNN RNN

Get a similar matrix, process it to get a diagonal matrix Degree matrixD,D The value of the diagonal of the matrix is the sum of the row in which it is located , The meaning is the second i Nodes , The sum of the weights of all nodes connected .

5.2 step

• Find the similarity matrix
• Find the minimum eigenvalue of the raoulas matrix as the eigenvector of each row
• Then use eigenvalues to do K-means

After normalized spectral clustering, the two kinds of density are similar , Without thinking, the number is similar

5.3 summary

• High complexity , The amount of computation is n Of 3 Power
• There are no assumptions about the shape of the class , Based on graph theory
• Data of any dimension can be classified
• It can be estimated how many classes , There is no need to manually specify