Manhattan, Euclidean And Chebyshev Methods In K-Means Algorithm For Village Status Grouping In Aceh Province

The Ministry of Villages, Development of Disadvantaged Regions and Transmigration (Ministry of Villages PDTT) is a ministry within the Government of Indonesia in charge of developing villages and rural areas, empowering rural communities, accelerating the development of disadvantaged areas, and transmigration. The 2014 Village Potential Data (Podes 2014) is data released by the Central Statistics Agency in collaboration with the Ministry of Villages PDTT in unsupervised form and consists of 6474 villages in the province of Aceh. Podes 2014 data is based on the level of village development (village specific) in Indonesia by using the village as the unit of analysis. Data mining is a method that can be used to group objects in a data into classes that have the same criteria (clustering). One of the algorithms that can be used for the clustering process is the k-means algorithm. Grouping data using k-means is done by calculating the shortest distance from a data point to a centroid point. In this study, a comparison of the distance calculation method on k-means between Manhattan, Euclidean and Chebyshev will be carried out. Tests will be performed using the execution time and the davies boulder index. From the tests that have been carried out, it is found that the number of villages in each cluster is 2,639 developing villages, 1,188 independent villages, 1,182 very underdeveloped villages, 1,266 developed villages and 199 disadvantaged clusters. The Chebyshev distance calculation method has the most efficient accumulation of time compared to Manhattan and Euclidean, while the Euclidean method has the most optimal Davies Index.