Coverage Models in 2-Dimensions

Home

Overview

This work was inspired by various immunological inspired coverage models, specifically models I was reading about in regard to using negative selection for novelty and anomaly detection. The outcome is the software and applet provided on this page that contains a number of Learning Vector Quantisation (LVQ) and Self-Organising Map (SOM) exemplar placement algorithms and volume filling approaches. I'm not sure where I want to take this work - it was simply the outcome of me trying out some ideas. If you are interested in extending this work or have some interesting configurations, please contact me.

Software

The software provides a number of two-dimensional test problems that contain convex regions. The intent of the algorithms is to cover the convex regions of the domains given a set number of point samples from within the convex region - essentially learn the regions from a set number of samples. The algorithms are all SOM and LVQ based for placing and moving exemplars around the domain based on sampling. There are two main types of structures on which the algorithms can operate - conventional SOM structures; a 2D lattice each point with a coordinate on the lattice, and one-dimensional lattice where connectivity (neighbourhoods) are defined by edges and not node coordinates as in conventional SOM. This second approach was implemented to support SOM-like learning on random graphs, small world graphs, and regular graphs. These structures and algorithms were then extended in simple ways to support volume filling using squares and arbitrary adaptive polygons (the vertices of which are called satellites).

Try the latest version of the applet here.

Algorithms

• Self-Organizing Map - requires a 2D lattice (placement algorithm)
• Connectivity-Based SOM - works with any structure (just placement) - does not use a neighbourhood function, instead it uses the number of hops through the graph structure
• Satellite-based Volume SOM - the same as the connectivitySOM, although each exemplar as n (>=3) satellites that define a polygon of the exemplars coverage volume. The placement of the satellites in relation to exemplar is adapted over time.
• Square-based Volume SOM - the same as the connectivitySOM, although each exemplar has a square that is defines the volume coverage of the exemplar. The size of the square is adaptive over time.

Structures

• 2D lattice - a conventional SOM lattice where each exemplar has a coordinate on a two-dimensional lattice as well as an exemplar coordinate that is the substrate for adaptation.
• 1D lattice - a set of nodes. Each node is connected to 0 or n of its neighbours (0 permits LVQ like behaviour). Once connected, the edges of the graph can be rewired with a probability p (1 permits random graphs), Additional short cut links can then be added with probability p. This structure supports small-world graphs, random graphs, regular graphs, unconnected vertices and all manner of in-between configurations.
• Square Volume Map - A 1D lattice structure where each node has an associated square with a defined initial radius. The square radius will remain fixed unless adapted using an appropriate algorithm (square-based volume som)
• Satellite Map - A 1D lattice structure where each node has a polygon defined by n (>=3) satellites. The satellites will remain at the exemplars origin unless adapted by an appropriate algorithm (satellite-based volume som)

Scenarios

This section provides example run scenarios with configuration parameters for repeatability. The scenarios provide interesting examples of what the various algorithms are capable of producing.

	Canonical Self-Organizing Map (SOM) Algorithm: SOM, 0.3, 11, 50,000, Bubble Structure: 2DLattice, 9, 11
	1-D Lattice SOM Algorithm: Connectivity-SOM, 0.3, 10, 25,000 Structure: 1DLattice, 100, 3, 0, 0
	Canonical Learning Vector Quantization (LVQ) Algorithm: Connectivity-SOM, 0.3, 1, 25,000 Structure: 1DLattice, 100, 0, 0, 0
	LVQ with Static Radius Square Volumes Algorithm: ConnectivitySOM, 0.3, 1, 25,000 Structure: SquareVolumeMap, 100, 0, 0, 0, 22
	LVQ with adaptive Satellite Volumes Algorithm: SatelliteVolumeSOM, 0.3, 1, 50,000, 1 Structure: SatelliteMap, 100, 0, 0, 0, 4
	SOM with Adaptive Radius Square Volumes Algorithm: SquareVolumeSOM, 0.3, 7, 25,000, 0.3, 0.1 Structure: SquareVolumeMap, 100, 2, 0, 0, 20

Download

The software requires Java 1.5 (5.0) to run as well as a few Jakarta Commons libraries (math and lang) which are provided in the offline download.

• Version 1.0, March 23rd 2006, download (initial public version)
• Version 1.1, Soon...

To-Do

The following are features I would like to add to this software over time, as well as user-requested features that I'd like to include (time permitting):

• Support dynamic problems - specifically convex regions that move through the problem space
• Support problem configuration  - user selected differing sample distributions (uniform, Gaussian)

Home