An Efficient Grid-based K-prototypes Algorithm for Sustainable Decision Making Using Spatial Objects

• DOI: 10.20944/preprints201806.0440.v1
• Publication Date: 2018-06-29T11:21:23Z
• Authors: Hong-Jun Jang; Byoungwook Kim; Jongwan Kim; Soon-Young Jung
• Keywords: spatial data; grid-based k-prototypes; 0202 electrical engineering, electronic engineering, information engineering; data mining; 02 engineering and technology; sustainability; engineering_other; clustering; 12. Responsible consumption

Data mining plays a critical role in the sustainable decision making. The k-prototypes algorithm is one of the best-known algorithm for clustering both numeric and categorical data. Despite this, however, clustering a large number of spatial object with mixed numeric and categorical attributes is still inefficient due to its high time complexity. In this paper, we propose an efficient grid-based k-prototypes algorithms, GK-prototypes, which achieves high performance for clustering spatial objects. The first proposed algorithm utilizes both maximum and minimum distance between cluster centers and a cell, which can remove unnecessary distance calculation. The second proposed algorithm as extensions of the first proposed algorithm utilizes spatial dependence that spatial data tend to be more similar as objects are closer. Each cell has a bitmap index which stores categorical values of all objects in the same cell for each attribute. This bitmap index can improve the performance in case that a categorical data is skewed. Our evaluation experiments showed that proposed algorithms can achieve better performance than the existing pruning technique in the k-prototypes algorithm.