iMS_nps: Tackling High-Incompleteness in Educational Data Clustering

TL;DR

The paper presents iMS_nps, an innovative clustering algorithm that combines the Mean Shift procedure with the Nearest Prototype Strategy (NPS). It solves the chronic issue of missing grades in academic credit systems, allowing educators to group students with similar performance levels without knowing the number of groups in advance. It achieves near-perfect cluster validity scores, even when over 50% of the data is missing.

Problem & Motivation: The "Empty Grade" Dilemma

In a modern flexible credit system, students choose different subjects at different times. This flexibility creates a nightmare for data miners: high-dimensional data with massive gaps.

Previous approaches either:

1. Deleted incomplete records: Wasting valuable information and potentially biasing results.
2. Used Pre-processing (Imputation): Filling gaps before clustering, which can introduce noise.
3. Partitioning-based Methods (K-means/FCM): These require the user to guess the number of clusters ($k$) and assume clusters are spherical—both of which are rarely true for complex student behavior data.

The authors' insight was to use a density-based approach. Instead of carving the space into $k$ pieces, why not let the data "flow" toward its natural centers (modes)?

Methodology: The iMS_nps Architecture

The core of the iMS_nps algorithm is its 4-phase iterative process that treats missing value imputation and cluster formation as a joint optimization problem.

1. Initialization and Mode Detection

Unlike standard Mean Shift, iMS_nps initializes missing values with attribute means ($a{m}_d$). It then calculates the Mean Shift vector to move each point toward the densest region in the feature space.

2. The Nearest Prototype Strategy (NPS)

The "secret sauce" is Phase 3. Instead of just moving points, the algorithm identifies the nearest estimation point ($C^{\ast }$) in the complete data subspace and updates the missing dimensions of the current point based on this neighbor. This ensures that points belonging to the same potential student group "pull" each other's missing information toward a consistent mode.

3. Automatic Cluster Discovery

Because it is based on Mean Shift, the algorithm doesn't ask for $k$. The number of clusters is simply the number of converged "stationary points" (modes) found at the end of the process.

Experimental Performance

The researchers tested iMS_nps against a formidable lineup of 15 competitors, including Kernel-based Fuzzy C-Means (KFCM) and SOM-based models.

The Dataset:

• 1,334 students across 43 subjects.
• Missing data rates ranging from 20.14% (Year 4) to a staggering 50.34% (Year 2).

Key Results: The algorithm's performance on the Xie_Beni (XB) and S_Dbw indices—where lower is better—was orders of magnitude better than previous SOTA methods.

The results indicate that while traditional fuzzy clustering struggles with high-level missingness (often leading to numerical instability or poor separation), the density-based approach of iMS_nps remains incredibly stable and precise.

Critical Insight & Conclusion

The success of iMS_nps suggests that density gradients are more robust "anchors" for missing data imputation than the centroids used in partitioning clustering. By allowing the imputation to be guided by the local data density, the algorithm reconstructs the missing student profiles in a way that naturally reinforces cluster separation.

Limitations: The current version relies on a fixed bandwidth ($h$), which the authors found via trial-and-error ($h=0.2$). Future research into adaptive bandwidth selection could make this a truly "set-and-forget" tool for educational administrators looking to support at-risk students in real-time.