TL;DR
This paper evaluates several unsupervised vector quantization algorithms for cell network planning in radiocommunication. By applying these algorithms to a real-world environmental dataset and using Mahalanobis distance and Sammon's projection for analysis, the authors provide insights into their strengths and weaknesses for creating homogeneous environmental classes.
What Problem Does This Paper Address?
Planning efficient mobile communication networks (cell nets) is crucial for operators. A key challenge is defining the coverage areas (cells) and optimizing the placement and size of transmitting stations. This process is heavily influenced by how radio waves propagate, which in turn depends on the environment (urban, rural, mountainous, etc.). Since there isn't a universal model for wave propagation across all environments, the authors propose creating homogeneous environmental "classes." These classes would then allow for the application of specific, more accurate predictive models for radio electrical fields within each class. The paper addresses the problem of selecting the most suitable unsupervised learning algorithm for partitioning environmental data into these homogeneous classes.
Methods
The paper evaluates four unsupervised vector quantization algorithms:
- Self-Organization Maps (SOM) by Kohonen: A foundational competitive learning algorithm that preserves topological links from input to output. It updates prototypes in the neighborhood of the winning neuron.
- Desieno's Algorithm: An improvement on SOM that addresses the issue of some prototypes being forgotten due to unequal winning probabilities. It introduces a "conscience factor" to ensure more balanced prototype selection, though it sacrifices topological information preservation.
- Neural Gas by Martinetz: This algorithm aims to preserve topological information by learning the topology rather than fixing it, unlike SOM.
- Growing Neural Gas (GNG) by Fritzke: An extension of Neural Gas that allows the number of classes to evolve and does not fix the topology.
- Buhmann's Algorithm: Based on simulated annealing, this algorithm aims to find an optimal number of classes and avoids local minima. It introduces new prototypes when patterns are assigned poorly or are far from existing prototypes.
To evaluate these algorithms, the authors employ two key analytical tools:
- Mahalanobis' Distance: This distance metric accounts for parameter correlations within the data. It's used in two ways: first, by calculating a global variance-covariance matrix for all data, and second, by calculating it within each identified class. The global approach is found to yield better generalization.
- Sammon's Non-linear Mapping Algorithm: This technique projects high-dimensional data (the 8-dimensional environmental data) into a 2-dimensional space while attempting to preserve inter-point distance ratios. This allows for visual comparison of how prototypes from different algorithms are distributed relative to the data points.
Datasets
The primary dataset used is a national geographic database describing the overground environment in France. From this, the authors extracted a random corpus of 5,000 patterns. Each pattern consists of 8 values: altitude and the percentage of presence in an area of 400 square meters for seven parameters (water, wood, field, rock, and three grades of construction density). These values were normalized using the mean and standard deviation calculated from a larger set of 65,000 patterns.
Key Insights and Ideas
- Algorithm Diversity Reflects Problem Diversity: The paper emphasizes that the wide variety of unsupervised neural networks mirrors the diversity of real-world problems, suggesting that no single algorithm is universally optimal.
- Visualizing High-Dimensional Data is Crucial: Sammon's projection proves invaluable for visually comparing the strategies of different algorithms, revealing how they spread prototypes across the data space.
- Mahalanobis Distance Enhances Class Homogeneity: Using Mahalanobis distance, especially with a global variance-covariance matrix, helps in assigning patterns to classes by accounting for data correlations, leading to potentially more homogeneous classes.
- Different Algorithms Have Distinct Strengths:
- SOM excels at capturing high-density zones but requires careful initialization.
- Desieno's algorithm offers equal prototype probability but loses topological information.
- Neural Gas and GNG provide a compromise, learning topology and spreading prototypes well.
- Buhmann's algorithm is notable for its ability to find an optimal number of classes and its strong performance in minimizing intraclass dispersion, making it a good criterion for class homogeneity.
Key Results
- Visualizations: Figures 1-6 showcase the projected data and prototypes for each algorithm. SOM prototypes cluster in high-density areas. Desieno's algorithm shows a more uniform spread. Neural Gas and GNG also spread prototypes well in high-density zones. Buhmann's algorithm, however, shows prototypes spread across the entire input space.
- Quantitative Evaluation: The paper mentions the number of classes computed for each model: Kohonen (106), Desieno (65), NeuralGas (87), GrowingNeuralGas (92), and Buhmann (31). The significantly lower number of classes for Buhmann's algorithm is attributed to its criterion of minimizing intraclass inertia.
- Qualitative Assessment: The authors conclude that SOM is quantitative, Desieno's is qualitative, and Neural Gas/GNG offer a compromise. Buhmann's algorithm is highlighted for its ability to minimize intraclass dispersion, suggesting it's a strong candidate for creating homogeneous classes.
Limitations and Future Work
- Limitations:
- The paper acknowledges that the "winner-take-all" nature of SOM can lead to forgotten prototypes.
- Desieno's algorithm sacrifices topological information.
- The choice of parameters for each algorithm can significantly influence the results.
- The paper notes that for real-world data, high-density zones might not always appear randomly or distinctly, which can affect the interpretation of visualizations.
- Future Work: The authors suggest that the diversity of unsupervised algorithms and their varied approaches make them suitable for different problems. The paper's analysis provides a framework for selecting the most appropriate algorithm for a given task, implying that further exploration of algorithm-problem pairings is warranted. The paper also hints at the potential of methods that allow for abandoning classes with too small an assignment probability if needed.
Summary updated