正在加载图片...
2.2 Different similarity graphs There are several popular constructions to transform a given set z1,...,n of data points with pairwise similarities sij or pairwise distances dij into a graph.When constructing similarity graphs the goal is to model the local neighborhood relationships between the data points. The s-neighborhood graph:Here we connect all points whose pairwise distances are smaller than s. As the distances between all connected points are roughly of the same scale(at most s),weighting the edges would not incorporate more information about the data to the graph.Hence,the e-neighborhood graph is usually considered as an unweighted graph. k-nearest neighbor graphs:Here the goal is to connect vertex vi with vertex vj if vj is among the k-nearest neighbors of vi.However,this definition leads to a directed graph,as the neighborhood relationship is not symmetric.There are two ways of making this graph undirected.The first way is to simply ignore the directions of the edges,that is we connect vi and vj with an undirected edge if vi is among the k-nearest neighbors of vj or if vi is among the k-nearest neighbors of vi.The resulting graph is what is usually called the k-nearest neighbor graph.The second choice is to connect vertices vi and vj if both vi is among the k-nearest neighbors of v;and v;is among the k-nearest neighbors of vi.The resulting graph is called the mutual k-nearest neighbor graph.In both cases,after connecting the appropriate vertices we weight the edges by the similarity of their endpoints. The fully connected graph:Here we simply connect all points with positive similarity with each other,and we weight all edges by sij.As the graph should represent the local neighborhood re- lationships,this construction is only useful if the similarity function itself models local neighbor- hoods.An example for such a similarity function is the Gaussian similarity function s(i,j)= exp(-i-xil2/(202)),where the parameter o controls the width of the neighborhoods.This pa- rameter plays a similar role as the parameter s in case of the s-neighborhood graph. All graphs mentioned above are regularly used in spectral clustering.To our knowledge,theoretical results on the question how the choice of the similarity graph influences the spectral clustering result do not exist.For a discussion of the behavior of the different graphs we refer to Section 8. 3 Graph Laplacians and their basic properties The main tools for spectral clustering are graph Laplacian matrices.There exists a whole field ded- icated to the study of those matrices,called spectral graph theory (e.g.,see Chung,1997).In this section we want to define different graph Laplacians and point out their most important properties. We will carefully distinguish between different variants of graph Laplacians.Note that in the literature there is no unique convention which matrix exactly is called "graph Laplacian".Usually,every author just calls "his"matrix the graph Laplacian.Hence,a lot of care is needed when reading literature on graph Laplacians. In the following we always assume that G is an undirected,weighted graph with weight matrix W, where wij=wji>0.When using eigenvectors of a matrix,we will not necessarily assume that they are normalized.For example,the constant vector 1 and a multiple al for some a0 will be considered as the same eigenvectors.Eigenvalues will always be ordered increasingly,respecting multiplicities. By "the first k eigenvectors"we refer to the eigenvectors corresponding to the k smallest eigenvalues. 32.2 Different similarity graphs There are several popular constructions to transform a given set x1, . . . , xn of data points with pairwise similarities sij or pairwise distances dij into a graph. When constructing similarity graphs the goal is to model the local neighborhood relationships between the data points. The ε-neighborhood graph: Here we connect all points whose pairwise distances are smaller than ε. As the distances between all connected points are roughly of the same scale (at most ε), weighting the edges would not incorporate more information about the data to the graph. Hence, the ε-neighborhood graph is usually considered as an unweighted graph. k-nearest neighbor graphs: Here the goal is to connect vertex vi with vertex vj if vj is among the k-nearest neighbors of vi . However, this definition leads to a directed graph, as the neighborhood relationship is not symmetric. There are two ways of making this graph undirected. The first way is to simply ignore the directions of the edges, that is we connect vi and vj with an undirected edge if vi is among the k-nearest neighbors of vj or if vj is among the k-nearest neighbors of vi . The resulting graph is what is usually called the k-nearest neighbor graph. The second choice is to connect vertices vi and vj if both vi is among the k-nearest neighbors of vj and vj is among the k-nearest neighbors of vi . The resulting graph is called the mutual k-nearest neighbor graph. In both cases, after connecting the appropriate vertices we weight the edges by the similarity of their endpoints. The fully connected graph: Here we simply connect all points with positive similarity with each other, and we weight all edges by sij . As the graph should represent the local neighborhood re￾lationships, this construction is only useful if the similarity function itself models local neighbor￾hoods. An example for such a similarity function is the Gaussian similarity function s(xi , xj ) = exp(−kxi − xjk 2/(2σ 2 )), where the parameter σ controls the width of the neighborhoods. This pa￾rameter plays a similar role as the parameter ε in case of the ε-neighborhood graph. All graphs mentioned above are regularly used in spectral clustering. To our knowledge, theoretical results on the question how the choice of the similarity graph influences the spectral clustering result do not exist. For a discussion of the behavior of the different graphs we refer to Section 8. 3 Graph Laplacians and their basic properties The main tools for spectral clustering are graph Laplacian matrices. There exists a whole field ded￾icated to the study of those matrices, called spectral graph theory (e.g., see Chung, 1997). In this section we want to define different graph Laplacians and point out their most important properties. We will carefully distinguish between different variants of graph Laplacians. Note that in the literature there is no unique convention which matrix exactly is called “graph Laplacian”. Usually, every author just calls “his” matrix the graph Laplacian. Hence, a lot of care is needed when reading literature on graph Laplacians. In the following we always assume that G is an undirected, weighted graph with weight matrix W, where wij = wji ≥ 0. When using eigenvectors of a matrix, we will not necessarily assume that they are normalized. For example, the constant vector ✶ and a multiple a✶ for some a 6= 0 will be considered as the same eigenvectors. Eigenvalues will always be ordered increasingly, respecting multiplicities. By “the first k eigenvectors” we refer to the eigenvectors corresponding to the k smallest eigenvalues. 3
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有