In this paper, we're going to describe the core features of the R package seqClustR [14] dedicated to sequence clustering. Sequence clustering is a data mining technique that groups similar sequences into clusters based on their similarities. Sequence clustering is useful when there are unknown number of similar sequences that need to be identi ed to gain valuable insights. The main feature of this package is that it provides easy access to di erent algorithms such as Edit Distance with Hierarchical Clustering, Markov ModelBased Clustering, Dynamic Time Warping, and K-Means to perform sequence clustering. We nd that di erent algorithms can create very di erent clusters and lead us to very di erent conclusions. So to get a reliable understanding of the sequences, we need to apply various sequence clustering algorithms and explore the data from multiple points of view. This paper illustrates how you could create di erent clusters from di erent algorithms, extract event log data for each cluster and visualize them. We have provided an example in section 4 showing step by step procedure to run sequence clustering on the National Assessment of Educational Progress (NAEP) dataset.
In this paper, we'll present the seqClustR package, which
implements di erent clustering algorithms on sequence data
in R. Sequence data contains information about the di
erent activities performed over time. Working with sequence
data can be hard sometimes; but it can probably provide
better insights by making use of the temporal dimension
[
In process mining, sequence clustering plays an important role by grouping similar sequences and providing helpful insights, especially when we have little knowledge about various types of processes hidden in the data. For example, a business process data might have di erent versions of a single process within it. Sequence clustering is used in different domains: in bioinformatics to group similar biological sequences; in marketing to identify di erent purchasing behaviors of customers; in education to identify di erent learner behaviors. In education, while using digital content learners exhibit di erent types of behaviors: gaming the system behavior; o -task behavior; carelessness behavior. Performing sequence clustering on educational sequence data can help us group similar learners together and then we can compare their performance to understand which learner behavior models have a positive impact on learners' growth.
In recent years, a lot of educational data has been
collected through digital learning platforms at an increasing
rate. With more learners joining the digital platforms and
more types of content being created for them, we are
observing a lot of clickstream data. Clickstream data shows us the
sequence of activities that learners went through while
being on the platform. Gaining insights from such data could
help us identify di erent learner behaviors [
Understanding a learner behavior from process models using
sequence data can be complex with high-dimensional data.
The sequence data can contain a high number of distinct
activities and all the activities need not be equally important
or have enough learner data; we could perform exploratory
data analysis on the data to understand which activities are
important. Activities that don't provide much information
can make the models more complex and harder to interpret
[
This package is designed to cluster sequence data. The
package uses event log [
For clustering the sequence data with the help of Edit Distance, we chose Hierarchical Clustering Algorithm. To make it convenient to choose the number of clusters, we plot the Hierarchical Clustering tree for the users so that they can make an informed decision about it. 3.1.2 Markov Model Based Clustering (seq_markov_clustering) Markov Model-based clustering is a probabilistic model-based approach to cluster sequence data. The Markov Model-based clustering method is similar to K-Means, where the cluster centroids in Markov Model are Markov transition probability matrices and the data points are Markov transition probability matrices for the sequences. An entry Aab in a Markov transition probability matrix A can be interpreted as the conditional probability that a learner will do activity b after doing the activity a, independent of any previous activities. 3.1.3 Dynamic Time Warping (seq_dtw_clustering) Dynamic Time Warping is a distance-based clustering algorithm that measures similarity between two temporal sequences, which can vary in speed. In the context of educational data, we can say that two learners that perform a sequence of activities in the same order but vary in the number of times each activity was done would have 0 Dynamic Time Warping distance. For example, two learners with sequences (a, b, c) and (a, b, b, c, c) would have 0 Dynamic Time Warping distance. Dynamic Time Warping can be used to analyze any data that contain a sequence of actions over time, it has also been used to cluster educational sequence data previously [15]. We've used Dynamic Time Warping clustering algorithm from the R package Dynamic Time Warping [13] in our seqClustR package. 3.1.4 K-Means Clustering (seq_kmeans_clustering) K-Means Clustering Algorithm identi es K number of centroids and allocates each data point to the nearest cluster to minimize the within-cluster sum of squares.
In our approach, we calculate the number of times each activity was done for each case and then normalize it by the sequence length. These features were then passed to K-Means Clustering Algorithm.
In this section, we'll explain how practitioners can use the package to perform sequence clustering on their data. We'll show an example of how to prepare the sequence data that can be passed to the clustering algorithms and then how we can visualize the clusters. 4.1 Data We've used NAEP's Process Data for Math test from 2017 which included data of 2500 learners. NAEP test is used by the US government to measure learner knowledge across the country. This data was part of the NAEP Data Mining Competition 2019 whose goal was to nd e ective and ineffective learner test-taking behaviors. The test was divided into two blocks of 30 min where Block A's data was supposed to be used to predict learner's performance on Block B. There were 8 di erent question types but for the analysis, we're only working with data from Block A and considering Multiple-Choice Questions as it had the majority of the questions in the test.
Description Unique identi er of the learner Block of the NAEP test, A or B Unique question identi er Type of Question learner Activity Metadata of learner's Activity Event Timestamp
Activity ID
Before applying any clustering algorithm to the data, we
need to perform data preprocessing steps to reduce data
complexity. Our data preprocessing steps included
removing activities that didn't have enough learner events and
removing events where data for any of the event log attributes
mentioned in table 1 were missing.
t
h
g
i
e
H
0
0
0
0
2
0
0
0
0
1
0
For clustering, we need to convert the sequence data into
event log format. We have used STUDENTID as Case ID,
Observable as Activity ID, and EventTime as Timestamp.
For the missing attributes, we can manually add them [
After converting the sequence data into event logs format, we can start applying clustering algorithms on it. As an example, we've performed Edit Distance Based Hierarchical Clustering on the event log data that we prepared in Section 4.1. When we pass the event log into the respective function, we are shown a Hierarchical Cluster Tree (Figure 2) in the graphics window, and we get a user prompt to select whether we would like to cut the tree by number of groups or by height. On selecting one of the options we need to enter the value corresponding to it. The output of the function would be a list containing the tted model and the cluster assignments by case id. l i b r a r y ( s e q C l u s t R ) c l u s t e r <− s e q e d i t d i s t a n c e c l u s t e r i n g ( e v e n t l o g )
Visualization is a powerful tool that can help us explore
common behavioral patterns exhibited by learners. We've
got two clusters from the event log in Section 4.2, to nd out
how both of them di er from each other based on common
learner behavior patterns we'll make visualizations for these
clusters (Figures 3 and 4). We've made process models for
both the clusters using fuzzymineR package [
e v e n t l o g 2 [ [ "1 " ] ] ) v i z f u z z y model ( m e t r i c s = m e t r i c s , node s i g t h r e s h o l d = 0 . 1 , edge s i g t h r e s h o l d = 0 . 3 , edge s i g t o c o r r r a t i o = 1 )
Performing sequence clustering using hierarchical clustering with edit distance method on the NAEP data provided us two clusters that exhibit di erent behaviors. Cluster 1 (Figure 3) shows that for 56% of the times learners directly click on one of the choices after they have presented a multiple choice question; 32% of the times when learners are presented with a multiple-choice question they rst use the calculator and then click on one of the choices. The di erent behaviors exhibited by learners in cluster 1 could be because of varying item di culties, where an easy item might not require the use of the calculator but for more di cult item learners might need it.
In cluster 2 (Figure 4), learners show a di erent behavioral pattern, they tend to go through di erent steps before clicking on one of the choices; 39% of the times when learners are presented with a multiple-choice question they rst use the calculator but unlike cluster 1, they do some scratchwork before clicking on one of the choices; learners tend to click on di erent choices a signi cant number of times before submitting their nal answer and moving on to the next item; learners also use the eliminate answer choice tool signi cantly in cluster 2.
The R package seqClustR provides the means to perform di erent clustering algorithms on sequence data by reducing the complexity of preparing data for each algorithm in a di erent way, by just converting the sequence data into event logs we can run multiple clustering algorithms and compare them. In this paper, we've shown how to prepare sequence data, perform sequence clustering, and visualize the clusters. In future, we would like to add more clustering algorithms and add a functionality in the package to do qualitative comparisons of clusters as well.
We would like to thank the organizers of the 2019 NAEP Data Mining Challenge for providing the data. We hope that the seqClustR package would support and inspire more research on sequence data. [13] A. Sarda-Espinosa. dtwclust: Time Series Clustering Along with Optimization for the Dynamic Time Warping Distance, 2019. R package version 5.5.6. [14] A. Sharma and N. Patel. seqClustR.
https://github.com/aditya9352/seqClustR. [15] S. Shen and M. Chi. Clustering student sequential trajectories using dynamic time warping. International Educational Data Mining Society, 2017. [16] B. Shih, K. R. Koedinger, and R. Scheines. Discovery of student strategies using hidden markov model clustering. In the Proceedings of the 6th International Conference on Educational Data Mining. Citeseer, 2010. [17] N. Trcka, M. Pechenizkiy, and W. van der Aalst.
Process mining from educational data. Handbook of educational data mining, pages 123{142, 2010. [18] O. Zaiane. Web usage mining for a better web-based learning environment. 2001. [19] M. Zhou, Y. Xu, J. C. Nesbit, and P. H. Winne.
Sequential pattern analysis of learning logs: Methodology and applications. Handbook of educational data mining, 107:107{121, 2010.
Figure 3: Process Model for Cluster 1 Figure 4: Process Model for Cluster 2