Wyniki wyszukiwania - BazTech

1

Weighted Laplacians of Grids and Their Application for Inspection of Spectral Graph Clustering Methods

Kłopotek Mieczysław, Wierzchoń Sławomir, Kłopotek Robert

TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk

|

2021

|

Vol. 25, No 3

329--353

EN

This paper investigates the relationship between various types of spectral clustering methods and their kinship to relaxed versions of graph cut methods. This predominantly analytical study exploits the closed (or nearly closed) form of eigenvalues and eigenvectors of unnormalized (combinatorial), normalized, and random walk Laplacians of multidimensional weighted and unweighted grids. We demonstrate that spectral methods can be compared to (normalized) graph cut clustering only if the cut is performed to minimize the sum of the weight square roots (and not the sum of weights) of the removed edges. We demonstrate also that the spectrogram of the regular grid graph can be derived from the composition of spectrograms of path graphs into which such a graph can be decomposed, only for combinatorial Laplacians. It is impossible to do so both for normalized and random-walk Laplacians. We investigate the in-the-limit behavior of combinatorial and normalized Laplacians demonstrating that the eigenvalues of both Laplacians converge to one another with an increase in the number of nodes while their eigenvectors do not. Lastly, we show that the distribution of eigenvalues is not uniform in the limit, violating a fundamental assumption of the compact spectral clustering method.

2

Machine Learning-Based Small Cell Location Selection Process

Wasilewska Małgorzata, Kułacz Łukasz

Journal of Telecommunications and Information Technology

|

2021

|

nr 2

120--126

EN

In this paper, the authors present an algorithm for determining the location of wireless network small cells in a dense urban environment. This algorithm uses machine learning, such as k-means clustering and spectral clustering, as well as a very accurate propagation channel created using the ray tracing method. The authors compared two approaches to the small cell location selection process – one based on the assumption that end terminals may be arbitrarily assigned to stations, and the other assuming that the assignment is based on the received signal power. The mean bitrate values are derived for comparing different scenarios. The results show an improvement compared with the baseline results. This paper concludes that machine learning algorithms may be useful in terms of small cell location selection and also for allocating users to small cell base stations.

3

Constrained spectral clustering via multi-layer graph embeddings on a Grassmann manifold

Trokicić Aleksandar, Todorović Branimir

International Journal of Applied Mathematics and Computer Science

|

2019

|

Vol. 29, no. 1

125--137

EN

We present two algorithms in which constrained spectral clustering is implemented as unconstrained spectral clustering on a multi-layer graph where constraints are represented as graph layers. By using the Nystrom approximation in one of the algorithms, we obtain time and memory complexities which are linear in the number of data points regardless of the number of constraints. Our algorithms achieve superior or comparative accuracy on real world data sets, compared with the existing state-of-the-art solutions. However, the complexity of these algorithms is squared with the number of vertices, while our technique, based on the Nyström approximation method, has linear time complexity. The proposed algorithms efficiently use both soft and hard constraints since the time complexity of the algorithms does not depend on the size of the set of constraints.

4

Clustering based on eigenvectors of the adjacency matrix

Lucińska M., Wierzchoń S. T.

International Journal of Applied Mathematics and Computer Science

|

2018

|

Vol. 28, no. 4

771--786

EN

The paper presents a novel spectral algorithm EVSA (eigenvector structure analysis), which uses eigenvalues and eigenvectors of the adjacency matrix in order to discover clusters. Based on matrix perturbation theory and properties of graph spectra we show that the adjacency matrix can be more suitable for partitioning than other Laplacian matrices. The main problem concerning the use of the adjacency matrix is the selection of the appropriate eigenvectors. We thus propose an approach based on analysis of the adjacency matrix spectrum and eigenvector pairwise correlations. Formulated rules and heuristics allow choosing the right eigenvectors representing clusters, i.e., automatically establishing the number of groups. The algorithm requires only one parameter—the number of nearest neighbors. Unlike many other spectral methods, our solution does not need an additional clustering algorithm for final partitioning. We evaluate the proposed approach using real-world datasets of different sizes. Its performance is competitive to other both standard and new solutions, which require the number of clusters to be given as an input parameter.