An Efficient Clustering Algorithm For Very Large Databases

Finding useful patterns in large datasets has attracted considerable interest recently, and one of the most widely studied problems in this area is the identification of clusters, or densely populated regions, in a multi-dimensional dataset. In this paper a new clustering algorithm for very large databases is proposed. The proposed algorithm, at most loads the entire data set into memory, three times. In phase 1, the encompassing space of data set is identified and it is partitioned into several sub-spaces, depending on the amount of available memory. Next, the entire data set, step by step is loaded into memory and each data point is assigned into a sub-space, and the average of data assigned into each sub-space is stored. In the later phase, some of the small sub-clusters corresponding to sub-spaces are hierarchically merged and constitute larger clusters. Our clustering algorithm is independent of the order of training samples appearance and our experimental results with complex data reveal that its performance is better than the well known k means algorithm.

کلیدواژه ها:

Clustering ، Large Database ، Hierarchical ، Space Dividing ، merging