Self-organizing topological tree for online vector quantization and data clustering.
The self-organizing Maps (SOM) introduced by Kohonen implement two important operations: vector quantization (VQ) and a topology-preserving mapping. In this paper, an online self-organizing topological tree (SOTT) with faster learning is proposed. A new learning rule delivers the efficiency and topology preservation, which is superior of other structures of SOMs. The computational complexity of the proposed SOTT is O(log N) rather than O(N) as for the basic SOM. The experimental results demonstrate that the reconstruction performance of SOTT is comparable to the full-search SOM and its computation time is much shorter than the full-search SOM and other vector quantizers. In addition, SOTT delivers the hierarchical mapping of codevectors and the progressive transmission and decoding property, which are rarely supported by other vector quantizers at the same time. To circumvent the shortcomings of clustering performance of classical partition clustering algorithms, a hybrid clustering algorithm that fully exploit the online learning and multiresolution characteristics of SOTT is devised. A new linkage metric is proposed which can be updated online to accelerate the time consuming agglomerative hierarchical clustering stage. Besides the enhanced clustering performance, due to the online learning capability, the memory requirement of the proposed SOTT hybrid clustering algorithm is independent of the size of the data set, making it attractive for large database.
Centre for High Performance Embedded Systems, Nanyang Technological University, 639798 Singapore. xupengfei@pmail.ntu.edu.sg
Pengfei
P
Xu
Chip-Hong
CH
Chang
Andrew
A
Paplinski
D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D003205:Computing Methodologies; D003628:Database Management Systems; D016208:Databases, Factual; D007089:Image Enhancement / Q000379:methods; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D009862:Online Systems; D010363:Pattern Recognition, Automated / Q000379:methods*; D012815:Signal Processing, Computer-Assisted; D013382:Subtraction Technique