Making kernel-based vector quantization robust and effective for incomplete educational data clustering

Educational data mining is nowadays well known worldwide for discovering knowledge hidden in educational data to support educational decision making. As one of the widely used mining tasks, educational data clustering has been considered with many different student-related aspects in [4, 5, 11‐13, 15, 18, 20‐22, 26] for many various purposes. For example, discovering the groups of similar students is based on study performance in [11], learning behavior in [15], skill in [18], preference in [26], etc. A variety of data have been collected and processed for clustering the students. For example, Bogarín et al. [4] used data of the undergraduate students in an online course using Moodle and Zakrzewska [26] got data about the undergraduate and graduate students participating in the experiments in online collaboration also on Moodle, Refs. [5, 11, 20] clustered the data of undergraduate students and courses in a few years, Jayabal and Ramanathan [12] analyzed the 10\(\mathrm{th}\) grade data, Kerr and Chung [13] extracted the student performance features from log data in educational video games and simulations, Li and Yoo [15] used the data recorded from each student’s actual lab experience, and so on. Among these related works, only Inyang and Joshua [11] has presented the handling of incomplete data by deleting the missing results in the courses while the others had no mention of incomplete data issues. If the number of missing values is small, ignoring them might have no impact on the performance of the clustering task. Otherwise, the effectiveness of the clustering task might be influenced by data insufficiency. In addition, incomplete data are ubiquitous in the data gathered in an academic credit system, especially in the case we would like to provide any appropriate support to the students as soon as possible in the second, third, or fourth year of their study period. So, our work in this paper is dedicated to a clustering task on incomplete educational data.

Despite such a lack of incomplete data handling for an educational data clustering task, we are aware of many existing works on incomplete data clustering in general such as [1, 2, 7‐9, 23, 25, 27]. Among these works, Refs. [1, 2, 9, 23, 27] updated incomplete data while doing data clustering, Wang [25] translated incomplete data into so-called fuzzy observations before generating clusters, and Refs. [7, 8] estimated incomplete data after attaining clusters. Thus, it can be seen that Wang [25] handled incomplete data in the preprocessing phase of the clustering task, Refs. [1, 2, 9, 23, 27] tackled incomplete data in the clustering phase of the clustering task, and Refs. [7, 8] performed post-processing incomplete data after the clustering task was done. Furthermore, some existing works such as Refs. [9, 27] have constrained the resulting shapes of the clusters. Fuzzy c-means, mean-shift clustering, and the self-organizing map (SOM) learning algorithm are some examples which have been enhanced for incomplete data clustering. Nonetheless, it is hard for us to foresee which incomplete data handling techniques are certainly appropriate for a particular application domain and also work well with any existing learning algorithms. Therefore, a study of handling incomplete data in a clustering task is needed to attain an effective cluster model in general and in the education domain.

Based on the motivations stated previously, we concentrate on a solution to the incomplete educational data clustering task in an academic credit system. In particular, we define a kernel-based vector quantization approach to effectively clustering incomplete educational data where incompleteness can be present in any data record at any dimension. Indeed, this work is an extended version of the work previously proposed in [24] where we focused on an effective algorithmic framework for incomplete educational data clustering and illustrated the applicability of the framework with the two proposed algorithms: K_nps and S_nps. K_nps followed the partitioning approach while S_nps did the neural network-based approach. Both of them utilized the nearest prototype strategy for incomplete data updates while do clustering within our proposed algorithmic framework. Like K_nps and S_nps, this work is also based on the proposed framework in [24]; however, defines a new approach using kernel-based vector quantization proposed in [10] and the nearest prototype strategy to handle the ubiquity of incomplete data. The resulting algorithm, named VQ_fk_nps, is our novel incomplete educational data clustering approach as compared to the algorithms K_nps and S_nps which have been achieved in [24]. As compared to K_nps and S_nps, VQ_fk_nps is capable of forming the groups of the similar students which are the clusters with non-spherical shapes in the data space corresponding to the spherical clusters in the feature space. Via the experimental results on real educational data sets with internal clustering validation measures, VQ_fk_nps is confirmed to outperform several existing approaches and thus, be effective for incomplete educational data clustering. Besides, the incomplete data sets that become completed after the data clustering task can be utilized in other mining tasks such as classification and association analysis.

For further evaluation from the empirical perspectives, we present several experimental results in this section. The experiments were performed on educational data including study results of the undergraduate students enrolled in 2005–2008 following the program in Computer Science in the academic credit system at Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology, Vietnam, [3]. Three data sets were prepared corresponding to 3 years of study from year 2 to year 4: data set “Year 2” for second-year students, “Year 3” for third-year students, and “Year 4” for fourth-year students. Each data set includes the study results of 1334 students (i.e., \(n=1334\)). Each vector of a data set representing a student has 43 dimensions (i.e., \(p=43\)) corresponding to 43 subjects. Missing grades appear corresponding to incomplete subjects as detailed in Table 1 where the percentage of missingness in data set “Year 2” is the highest and the one in “Year 4” is the lowest.

As for the algorithms, we used the following algorithms for comparison with our proposed algorithm, VQ_fk_nps:

As an extended version of the work in [24], we re-used the choices of the parameter values for NPSFCM and OCSFCM where the number c (or k) of clusters is 5 and the weighting exponent m is 1.25. As for other parameter values of an initial learning rate lr \(_{0}\) and the bandwidth \(\sigma \), we used a trial-and-error scheme which is quite tedious and thus, they will be automatically determined in our future work. The value of lr \(_{0}\) is 0.9 and the value of \(\sigma \) for “Year 2” data set is 1.15, \(\sigma \) for “Year 3” data set is 2.11, and \(\sigma \) for “Year 4” data set is 2.02. In addition, the stopping criterion is set for all the experiments based on the stability of the resulting clusters or the distance matrix in kernel-based vector quantization which is exactly the same as one in [9], which is 10\(^{-5}\). In order to avoid randomness in initialization, each experimental result for comparison in Table 2 is an averaged value calculated from 30 runs of each algorithm. Their corresponding standard deviations are given in Table 3. Besides, several results for K_an, ImpSOM, NPSFCM, and OCSFCM in Table 2 are inherited from the corresponding results of our previous work in [24].

Regarding examining how well VQ_fk_nps clusters incomplete educational data, we also used two internal clustering validation measures well-known in unsupervised learning: Xie_Beni and S_Dbw. Examined in [19], Xie_Beni is popularly used for fuzzy cluster validity with the inter-cluster separation defined as the minimum square distance between cluster centers and the intra-cluster compactness defined as the mean square distance between each object and its cluster center. The smaller Xie_Beni, the better the resultant clusters are. As analyzed in [16], S_Dbw is a measure that can examine the separation and compactness of the resulting clusters with respect to monotonicity, noise, density, subclusters, and skewed distributions in data. The smaller S_Dbw, the better the clusters are. More details about Xie_Beni and S_Dbw can be found in [16]. In addition, One-Way ANOVA was conducted with equal variances assumed for post hoc multiple comparisons with Bonferroni at the 0.05 level of significance. Levene Statistic is also included for a test of homogeneity of variances. In Table 2, a star (\(^{*})\) is used to denote the mean difference significant at the 0.05 level in comparison with the averaged results of VQ_fk_nps.

Presented in Table 2, the values of Xie_Beni and S_Dbw from our algorithm, VQ_fk_nps, are always the smallest ones with a very much difference from the results of the other algorithms. In particular, the difference between the fuzzy approaches and ours can be explained in such a way that our educational data sets have many distinct groups of similar students and thus, a choice of the nearest prototype strategy is appropriate. This result is also consistent with such a fact that we have got a small value (1.25) for the weighting exponent m in [24]. Considering the variance at each individual measure, we observe a quite large range for Xie_Beni and a small one for S_Dbw from different approaches and algorithms except for VQ_fk_nps. Xie_Beni shows the clearer distinction between the algorithms while S_Dbw shows that distinction a little. Almost the differences between VQ_fk_nps and the other approaches are significant through a statistical test at the 0.05 level. Therefore, it can be concluded that VQ_fk_nps is suitable for educational data sets as compared to the others which have been examined. Besides, Table 3 gives us the standard deviations corresponding to the averaged results of 30 runs from each algorithm in Table 2. Via the values of those standard deviations, there is no much variance in the results from many various executions of VQ_fk_nps as compared to other variants of VQ_fk_nps, leading to the fact that VQ_fk_nps is more stable than its variants. Nevertheless, the most stable algorithms with almost no variance are S_an and VQ_an. Such a stability of S_an and VQ_an stems from the nature of the self-organizing learning process. As our algorithm performs the clustering of data vectors in the feature space and tackles the incomplete data handling in the data space, its stability might be influenced although we considered this feature by reducing the randomness in initialization.

Generally speaking, VQ_fk_nps can perform the data clustering task effectively on incomplete educational data and produce the non-spherical clusters with higher compactness and better separation in the data space through the internal clustering validation measures such as Xie_Beni and S_Dbw. As VQ_fk_nps always has the lowest values for Xie_Beni and S_Dbw, such experimental results have confirmed the robustness and effectiveness of VQ_fk_nps, for handling different amounts of incomplete data in educational data sets. Using the resulting clusters, several concrete groups of the 2\(\mathrm{nd}\)-year students (or 3\(\mathrm{rd}\)-year students or 4\(\mathrm{th}\)-year students) at the same level of study performance can be determined and our support can be planned and provided appropriately for each group of the similar students. Besides, the resulting completed data can play a role of a good input for other mining tasks including educational data classification and association analysis.

For further comparison with the related works, this section examines several existing works such as [1, 2, 7‐9, 23, 25, 27] in incomplete data clustering. Among these works, Refs. [1, 2, 9, 23] updated incomplete data while doing data clustering, Wang [25] translated incomplete data into so-called fuzzy observations before generating clusters, and Cottrell and Letrémy [7] estimated incomplete data after attaining clusters.

As one of the first works, Hathaway and Bezdek [9] developed four different strategies handling incomplete data in fuzzy clustering: the whole data strategy (WDS), the partial distance strategy (PDS), the optimal completion strategy (OCS), the nearest prototype strategy (NPS) similar to OCS except for using the nearest prototypes. As a kernel-based extension to OCSFCM, a kernel-based fuzzy c-means algorithm (KFCM) was proposed in [27] using a kernel-induced metric in the data space instead of the conventional Euclidean metric and the optimal completion strategy for incomplete data handling. In comparison, VQ_fk_nps is different from NPSFCM and OCSFCM in [9] and KFCM in [27] in the following aspects. In Initialization phase, we suggested to use a mean of all the known values at each dimension to fill in incomplete data in VQ_fk_nps while OCSFCM and NPSFCM algorithms had no mention of such a particular initialization. In addition, VQ_fk_nps uses a kernel-based approach to produce the clusters with arbitrary shapes while those algorithms used a partitioning-based approach forming only the hyper-spherical shapes of the resulting clusters. Based on OCS and fuzzy SOM algorithm, Abidi and Yahia [2] proposed OCS-FSOM and an extension of OCS-FSOM called Multi-OCSFSOM. In these algorithms, a learning rate is used as a fuzzy membership value of the current input vector in the output cluster. Besides, the algorithms in [2] require the maximal iteration number for the learning process. This might lead to an early convergence. Differently, our work does not fix the number of iterations.

Wang [25] is another work based on SOM algorithm by transforming incomplete data into so-called fuzzy observations. This approach depended on the domains at the dimensions where missing values exist and a large number of fuzzy observations would be generated for each input. Based on SOM, Cottrell and Letrémy [7] clustered incomplete data in the complete data subspace by ignoring the dimensions with missing values during the learning process. After the learning process, missing value estimation is performed using the (weighted) mean values of the class of each vector. For a comparison with Cottrell and Letrémy [7], we adapted this approach to obtain a simplified algorithm ImpSOM in the previous section. However, Cottrell and Letrémy [7] might lose the details of the vectors to be clustered if the number of dimensions with missing values gets larger. Moreover, the missing data imputation was not tightly involved in the cluster forming process.

As one of the most recent works, Vatanen [23] has proposed a revision of handling missing values to the batch SOM algorithm which is called Imputation SOM. Unlike Refs. [7, 23] did not ignore the missing values in the learning process. Indeed, Vatanen [23] used the current value of the corresponding prototype, i.e. a mean value, to fill each missing component of a vector. To some extent, the missing value updates in [23] are similar to that of VQ_fk_nps. Differently, instead of using the current prototype, VQ_fk_nps uses the nearest prototype of each vector after the update of all reference vectors via the update of the distance matrix has been done in the feature space. In [8], a SOM-based method has been introduced for data imputation in incomplete data matrices. Although not focusing on the resulting clusters, Folguera et al. [8] is somewhat related to a SOM-based incomplete data clustering approach. Their method needs a part of complete data vectors to pre-train a SOM and then impute incomplete data. Thus, Folguera et al. [8] is not applicable to our work because the educational application domain has the data sets where there is no such a set of complete data vectors from the 2\(\mathrm{nd}\)-year, 3\(\mathrm{rd}\)-year, and 4\(\mathrm{th}\)-year students in an academic credit system. Using the mean shift algorithm as introduced in [6], AbdAllah and Shimshoni [1] considered handling incomplete data by means of so-called MD\(_{E}\) distance; but did not supply any incomplete data handling scheme.

Finally, among a large number of the existing works, it is hard to foresee which incomplete data handling techniques are certainly appropriate for a particular domain and also work well with any existing unsupervised learning algorithms. So, a study of handling incomplete data in a clustering task is needed for obtaining an effective cluster model in general and in the education domain particularly. In addition, VQ_fk_nps has the merit of discovering the non-spherical clusters of better quality in the incomplete educational data sets by means of a kernel-based clustering process in the feature space. This approach has not yet been supported by any existing works.

As of this moment, we focus on which incomplete data clustering approach is appropriate for our educational domain by making kernel-based vector quantization robust and effective. In the future, we will further evaluate our approach for a more diversity of complete data sets. It is also interesting to consider obtaining a parameter-free kernel-based vector quantization approach whose parameter values are automatically derived from the inherent characteristics of each data set.