Comparison of Clustering Algorithms

There are a lot of clustering algorithms. Nevertheless, there are questions: how to decide which algorithm should be used, how fast are they and what kind of data they can process properly. In this technical note I would like to compare several classical and bio-inspired clustering algorithms (that are based on oscillatory networks).

For comparison clustering algorithms python implementation of them is used (library pyclustering – branch 0.6.dev0). The library provides opportunity to use CCORE library (C/C++ part of the library), but currently amount of python implemented clustering algorithms is greater than amount of C/C++ implemented algorithms. Nevertheless, functionality and cluster analysis abilities can be compared using only python implementation.

Following algorithms are considered in this technical note: Agglomerative, BIRCH, CLARANS, CURE, DBSCAN, HSyncNet, K-Means, K-Medians, K-Medoids (PAM), OPTICS, ROCK, SyncNet, SYNC-SOM, X-Means. Almost of them are classical algorithms, except bio-inspired class: HSyncNet, SyncNet, SYNC-SOM. Let’s divide them into following categories:

  • Hierarchical algorithms: Agglomerative, BIRCH, CURE, HSyncNet.
  • Density based algorithms: DBSCAN, OPTICS, ROCK, SyncNet, SYNC-SOM.
  • Partitioning based algorithms: K-Means, K-Medians, K-Medoids (PAM), X-Means.

Almost all these algorithms require input data in RAM except BIRCH and SYNC-SOM, and thus there is limitation to use them for processing large databases. BIRCH encodes input data space (reduces it) by CF-Tree and SYNC-SOM encodes input data by SOM layer (self-organized feature map). FCPS data set collection for clustering testing is used. This data collection consists of 2D and 3D data sets with various complexity. Examples of data and proper clustering results (DBSCAN with correct parameters) are presented on figure 1.

dbscan_results
Figure 1. Clustering results of FCPS data by DBSCAN algorithm.

Another one example of clustering where some clusters are allocated incorrectly (K-Medians) presented on figure 2.

k-medians_results
Figure 2. Clustering results of FCPS data by K-Mediands algorithm.

Time processing and correctness (proper allocation is marked by green color, improper allocation – red color) of clusters allocation for FCPS are presented in table 1.

Table_Clustreing_Comparison
Table 1. Time processing and correctness of clustering algorithms.

Some words about bio-inspired algorithms: SyncNet, HSyncNet, SYNC-SOM are able to allocate clusters but allocation depends on output of these oscillatory networks. Approach is pretty simple: each oscillator of a first layer (SyncNet and HSyncNet have only one layer) corresponds to only one object from input data space (SYNC-SOM’s neurons of the first layer compete with each other to capture objects). After simulation (processing input data space) oscillatory network has one or several ensembles of synchronous oscillators where each ensembles corresponds to only one cluster. But ensembles might have the same phases because considered algorithms have got de-synchronization mechanism – ensembles just do not interact with each other. It means that sometimes clustering result might be incorrect and simulation should be repeated. This problem can be resolved by using high level of local synchronization but it leads to increasing of simulation time.

Andrei

Advertisements

Wi-Fi connection after update in Ubuntu

It is just a note that has helped me to resolve problem with Wi-Fi broken connection after system upgrade in Ubuntu 14.04 on a laptop DELL Inspiron 3537.

What: after system update Wi-Fi connecction does not work despite hardware Wi-Fi module is switched on (Wi-Fi connection LED is ON on the laptop) – transmission power is OFF.

$ iwconfig
eth0      no wireless extensions.

lo        no wireless extensions.

wlan0     IEEE 802.11bgn  ESSID:"FlatNetwork_2.4GHz"
          Mode:Managed  Frequency:2.462 GHz  Access Point: 10:FE:ED:FF:D2:AD
          Tx-Power=off
          ... ... ...

Transmission power is off (Tx-Power=off) as you can see it from the example above.

Solution: solution is pretty simple in my case, I have not dug why it may happen after system update, but it is enough (at least for me and for the considered problem) to down wlan0 network interface, then up it and reboot the system:

$ sudo ifdown -a
$ sudo ifup -a
$ sudo reboot 0

Andrei

Screen brightness in Ubuntu

It is just a note that has helped me to resolve problem with brightness in Ubuntu 14.04 on laptop DELL Inspiron 3537.

What: screen brightness is not changed via system setting Brightness & Lock or using  Fn + F4 and Fn + F5.

Solution:

  1. Check module that provides interface to control brightness:
    $ ls /sys/class/backlight
  2. Create configuration file for graphic card where brightness option will be specified.
    $ sudo touch /usr/share/X11/xorg.conf.d/20-intel.conf
    $ sudo nano /usr/share/X11/xorg.conf.d/20-intel.conf
    
  3. Create configuration to control brightness:
    Section "Device"
    	Identifier	"card0"
    	Driver		"intel"
    	Option		"Backlight"	"intel_backlight"
    	BusID		"PCI:0:2:0"
    EndSection
    
  4. Reboot laptop and check that screen brightness can be changed.

Andrei