The use of data topology in unsupervised clustering of high-dimensional data with self -organizing maps

[摘要] High-dimensional data is increasingly becoming common because of its rich information content that can provide comprehensive characterization of objects (patterns) in real world situations. Unsupervised clustering aims to utilize this rich information content for detailed discovery of distinct patterns. However, conventional clustering methods may be inadequate for capturing intricate structure in high-dimensional and large data, such as hyperspectral images or genetic microarray data. These data usually have many meaningful clusters, including interesting rare ones, whose discovery may be of great importance. Yet, faithful delineation of clusters may be impossible and rare clusters may be undiscovered due to limitations of clustering methods. A powerful method in high-dimensional data analysis is the Self-Organizing Map (SOM) [1]. An SOM is a neural learning algorithm that quantizes data spaces and spatially orders the quantization prototypes on a rigid lattice. The information learned by the SOM can be exploited to extract detailed cluster structure either by explanatory visualization or by clustering the SOM prototypes. Available SOM visualization or clustering schemes that are successful for relatively simple data often miss the finer structure in high-dimensional and large data. Our goal is to provide advanced visualization and clustering schemes for SOMs for detailed cluster extraction. The main contribution is the exploitation of the data topology inherent in the SOM's knowledge but largely underutilized in existing approaches. We achieve this by proposing a ;;connectivity matrix” CONN , which is a weighted Delaunay triangulation. CONN and its specific rendering on the SOM (CONNvis) help detailed delineation of clusters which can be obscure in existing schemes. The capability of CONNvis in cluster extraction inspires a new index for the evaluation of cluster validity. The proposed index, Conn_Index , is shown to be effective in various applications of synthetic and real data sets. Based on our experiences, we expect CONN and Conn_Index to help produce an automated clustering of the SOM which may be as detailed as can be achieved with the interactive methods including our CONNvis clustering. This will be a significant achievement for structure discovery given that automated schemes in previous works produce results inferior to results from semi-manual procedures.

[发布机构] Rice University

[效力级别] engineering