A Study of Out of School Children Problem in Rajasthan using K-means clustering with Genetic Algorithm

Astha Pareek, Amita Sharma, Manish GuptaInternational Journal of Computer Applications 2016 · DOI

Abstract

Clustering technique has been broadly used in numerous disciplines, such as science, statistic, software engineering and other social sciences in order to identify natural groups in large amounts of data. K-means is one of the most generally used partitioning clustering algorithms that tries to locate a user specific number of clusters (k), which are represented by their centroids, by minimizing the square error function. There are two straightforward approaches to cluster center initialization i.e. either to choose the initial values arbitrarily or else to choose the first k samples of the data points. Both approaches cause the algorithm to converge to sub optimal solutions. In contrast Genetic algorithm is one of the most frequently used transformative calculations which perform worldwide research to discover the result to a clustering issue. The algorithm normally begins with an arrangement of haphazardly developed individuals called the populace and design consecutive, new eras of the populace by genetic operations for example population selection, fitness function, crossover and mutation. This paper compares K-means and genetic algorithm based data clustering. A new algorithm is proposed known as genetic algorithm K-means (GAKM). Comparison was done of the basis of external, internal and time complexity.

Introduction

Clustering is a fundamental tool in data mining, but the standard K-means algorithm is highly sensitive to its starting point. Because K-means begins by randomly picking initial cluster centers (centroids), it often falls into "local minima," producing sub-optimal groupings that do not accurately represent the underlying data. This computational challenge is particularly relevant when addressing social issues like the "Out of School Children" problem in Rajasthan, India. Despite policies like Sarva Shiksha Abhiyan, Rajasthan faces unique challenges in student retention. To design effective interventions, policymakers require stable, accurate insights from complex demographic data.

This study utilizes the Child Tracking Survey (CTS) data from 2010, provided by the Rajasthan Elementary Education Council. The dataset contains approximately 1.2 million records of children aged 6–14 across 33 districts. Features include district codes, gender, disability status, enrollment status, and specific reasons for dropout.

Methodology

The authors propose a hybrid algorithm called Genetic Algorithm K-means (GAKM). This approach leverages the global search capabilities of Genetic Algorithms (GA) to identify optimal initial centroids before applying K-means for local refinement.

The GAKM pipeline consists of:

  1. Initialization: Random generation of a population of potential cluster centers (chromosomes).
  2. Fitness Evaluation: Candidates are evaluated based on their coverage of the problem space.
  3. Genetic Operators: The algorithm employs Ranking Selection, Crossover (25% probability), and Mutation (25% probability) to evolve the population.
  4. K-means Refinement: The "fittest" initial seeds are used as the starting point for the standard K-means algorithm.

Performance was evaluated using internal indices (Average Silhouette Width), external indices (Purity and Entropy), and total execution time.

Results and Analysis

Experimental results across various districts and cluster counts ($K=5, 9, 12$) demonstrate the superiority of the GAKM approach.

Cluster Quality and Stability

The study confirms that initialization is critical. By utilizing a Genetic Algorithm for seed selection, the final model becomes significantly more reliable. As shown in Figure 1, GAKM consistently achieves higher Average Silhouette Widths compared to basic K-means, indicating more distinct and meaningful clusters.

Figure 1: Comparison of Average Silhouette Width for K=5 across five districts, showing GAKM's superior cluster separation.

Furthermore, the relationship between Entropy and Purity highlights GAKM's effectiveness. As cluster quality improves, Entropy (disorder) decreases while Purity increases. GAKM consistently outperformed K-means in these external metrics, as illustrated by the lower entropy values in Figure 2.

Figure 2: Comparison of Entropy for K=5 across five districts, demonstrating lower disorder in GAKM clusters.

Efficiency and Social Insights

Counter-intuitively, the added complexity of the Genetic Algorithm can reduce total processing time. Because GAKM starts with superior seeds, the K-means phase converges in fewer iterations. For instance, in District 3 ($K=5$), GAKM finished in 69 seconds compared to 156 seconds for basic K-means.

Qualitatively, the clustering identified key drivers of school dropouts: agricultural work, grazing cattle, poor economic conditions, and early marriage. By identifying specific "significant reasons" per district, the model enables localized educational policies rather than blanket approaches.

Conclusion

The GAKM hybrid algorithm effectively addresses the initialization sensitivity of K-means, providing more accurate and efficient clustering for large-scale social datasets. The findings suggest that targeted interventions addressing child labor in agriculture, poverty, and early marriage are essential for achieving zero-dropout rates in Rajasthan. Future research may explore other optimization techniques, such as Particle Swarm Optimization (PSO), to further refine seed selection.

Summary updated

Abstract

Clustering technique has been broadly used in numerous disciplines, such as science, statistic, software engineering and other social sciences in order to identify natural groups in large amounts of data. K-means is one of the most generally used partitioning clustering algorithms that tries to locate a user specific number of clusters (k), which are represented by their centroids, by minimizing the square error function. There are two straightforward approaches to cluster center initialization i.e. either to choose the initial values arbitrarily or else to choose the first k samples of the data points. Both approaches cause the algorithm to converge to sub optimal solutions. In contrast Genetic algorithm is one of the most frequently used transformative calculations which perform worldwide research to discover the result to a clustering issue. The algorithm normally begins with an arrangement of haphazardly developed individuals called the populace and design consecutive, new eras of the populace by genetic operations for example population selection, fitness function, crossover and mutation. This paper compares K-means and genetic algorithm based data clustering. A new algorithm is proposed known as genetic algorithm K-means (GAKM).Comparison was done of the basis of external, internal and time complexity.
BibTeX
@article{pareek2016study,
  author = {Astha Pareek and Amita Sharma and Manish Gupta},
  title = {{A Study of Out of School Children Problem in Rajasthan using K-means clustering with Genetic Algorithm}},
  journal = {International Journal of Computer Applications},
  year = {2016},
  doi = {10.5120/ijca2016910403},
}
Figure