# A Dynamic Mining Algorithm for Multi-granularity User's Learning Preference Based on Ant Colony Optimization

Shengjun Liu, Shengbing Chen, Hu Meng

► To cite this version:

Shengjun Liu, Shengbing Chen, Hu Meng. A Dynamic Mining Algorithm for Multi-granularity User's Learning Preference Based on Ant Colony Optimization. 2nd International Conference on Intelligence Science (ICIS), Oct 2017, Shanghai, China. pp.133-142, 10.1007/978-3-319-68121-4_14. hal-01820929

HAL Id: hal-01820929

https://inria.hal.science/hal-01820929

Submitted on 22 Jun 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
A Dynamic Mining Algorithm for Multi-granularity
User's Learning Preference Based on Ant Colony
Optimization

Shengjun Liu¹*, Shengbing Chen² and Hu Meng³

¹ Anhui USTC-GZ Information Technology CO. LTD, Hefei 230031, China

²Key Lab of Network and Intelligent Information Processing, Department of Computer Science and Technology, Hefei University, Hefei 230601, China

³ HEFEI City Cloud Data Center Co., Ltd. Hefei 230094, China
liusj@ustc-it.com

**Abstract.** Mining user's learning preference is one of the key issues in the per-
sonalized online learning system, which is of great significance technology for
modern educational. In this paper, using the hierarchical characteristics of the
knowledge points in the course domain, we defined the equivalence relation and
equivalence of knowledge points, and defined the structure of the knowledge
points quotient space. Then, the functions of support, pheromone concentration
and preference were defined on various levels, and an improved ant colony opti-
mization was proposed to handle the multi granularity data structure of quotient
space. An algorithm of multi-granularity Learning Preference Mining based on
Ant Colony Optimization (ACO-LPM) was proposed to address the problems
about too many learning knowledge points and too few user's test data in the
online personalized learning system. The pheromone has the characteristic of dy-
namic evaporation, so, the preference patterns mined by ACO-LPM can be
changed with the change of user interest in real time. The experimental results
show that the algorithm can mining the user's learning preferences in online
learning system effectively and efficiently.

**Keywords:** Quotient Space, Preference Mining, Ant Colony Optimization, Personalized Learning, Granular Computing.

Online learning, which breakthrough the constraints of time and space, provides a con-
venient and efficient learning platform for learners. It has become an important means
of modern education for its three characteristics: the various learning modalities, the
multiple teachers and students' role, and the rich learning resources. Personalized learn-
ing is the hotspot of online learning, which makes learners achieve the best learning
effect under the minimum time and the best learning experience according to learners'
learning characteristics and preference model. Researchers have done a lot of work in
this domain. Jiunn used neural network to analyze students' online browsing behavior
and get students' learning styles and learning preferences[1]. Du studied the personality
traits of learners and the association between learning behaviors, and used the data min-
ing algorithm to obtain the learner behavior model[2]. Qiu employed solomon learning
style scale for pre-test, and obtained user interest model through the data mining of user
learning history[3]. Lin and Yan studied the news recommendation in the mobile net-
work environment, constructed the keyword vector by using the spatial model, and
clustered the document according to the similarity degree, to obtain the gravity vector
of each document cluster and build the user preference model[4,5]. Ren put forward a
U-I-C user interest model, which obtained scenario user preferences by adding the
scene information in the user-project matrix[6]. Wang put forward the idea and method
of user preference based on ontology and label[7]. Wolfgang studied the scenario in-
formation of the users in the mobile environment and found the user preference infor-
mation by using the collaborative filtering algorithm[8]. Chen presented logistic curve
model and hyperbolic model to analyze the user behavior, and proposed a user prefer-
ence model based on multi-vector tree[9]. Pazzan used the expected information gain
to analysis the annotations of users when they were browsing the pages and get user
interest preferences[10]. Adomavicius mined the user's individual access records to
construct the user model by using the associated association rules and user's personal
information[11]. These methods have greatly improved the efficiency of the users' pref-
erences in different backgrounds and applications. However, because of the character-
istics of the massive knowledge points and the few test data, the problems of learning
preferences on knowledge points has not been solved yet, and becomes a hot issue.

Granular computation can reduce the complexity of the solution, which inspired by
mankind who can solve complex problems at different levels and solve them at the
appropriate size[12]. In recent years, Granular computation (such as quotient space,
rough set and fuzzy set) have been successfully applied to complex problems in many
fields such as industrial control, transportation, graphic image processing, decision sup-
port, and biological information[13]. With the consideration of all the facts ( the uni-
verse, structure, projection, etc.), quotient space can meet all needs of online learning
system, such as the domain of knowledge and the dependence analysis. In this paper,
we used quotient space theory to explore a dynamic mining algorithm for user's learning
preference based on Ant Colony Optimization.

1 Quotient Space Structure of Knowledge Points

In online learning system, each knowledge point corresponds to a concept, which comes
from the domain knowledge ontology, the knowledge points have a certain hierarchical
structure and complex dependencies. As shown in Figure 1, there is a inclusion relation
between the knowledge points in different level. At same level, the knowledge has
three relationships: pre-order, brotherhood, and equivalent. The knowledge point KP is
defined as follows:
<figure><img src="image_2.png" /><figcaption>Fig. 1. Topological relationship of knowledge points in junior middle school</figcaption></figure>

**Definition 1:** Knowledge point $K$ is a triple $(C, T, f)$, where $C$ is the corresponding concept of knowledge point $K$; $T$ is the topology of various relationships between knowledge points. The online learning system mainly has inclusion and pre-order structure; $f$ is the property of knowledge.

**Definition 2:** If the knowledge of the learning point $K_i$ need to use the knowledge point $K_j$, then $K_j$ is $K_i$'s pre-order knowledge (also known as preparatory knowledge), expressed as $K_j < K_i$.

**Definition 3:** If $K_u$ is the upper level knowledge point of $K_i$ and $K_j$, and $C_u \supseteq C_i + C_j$, $T_u \supseteq T_i + T_j$, then $K_u$ contains $K_i$ and $K_j$, $K_i$ and $K_j$ are brotherhood relations, $K_u$ is $K_i$ and $K_j$'s Father knowledge points.

Since $K_u$ is not the same level as $K_i$ and $K_j$, the internal relationship between $K_i$ and $K_j$ disappears naturally in the upper level, so $T_u \supseteq T_i + T_j$ is the operation of the parent node $K_u$ level.

From the above definition we can see that if the brotherhood of the knowledge points is denoted by $R$, then $R$ has both reflexivity, symmetry and transitivity, that is, $R$ is the equivalence relation. Using the brotherhood relationship $R$ constructs the equivalence class, the new triples $([C], [T], [f])$ form a larger granularity of knowledge space, which is identified by the parent knowledge point.

Constructing the equivalence class mapping $p: (C, T) \to ([C], [T])$ which is the continuous natural projection of the knowledge point concept space. So, it meet the conditions of false warranty principle and fidelity principle define as follows:

1. False warranty principle: If the problem in the quotient space has no solution, it must also has no solution in any finer space.

2. Fidelity principle: Assuming that the problem has solution in the semaphore quotient space $\{C1, T1, f1\}, \{C2, T2, f2\}, \{C3, T3, f3\}$, then it has a solution in its synthetic quotient space $\{C3, T3, f3\}$.

Using the false warranty principle and the fidelity principle, we can mine users' preferences on knowledge points in different granularity. The number of knowledge points were reduced by the equivalence. At the same time, the data sparse problems have also been cut down because the equivalent knowledge points have larger size.
The knowledge point space constructed by the brotherhood relationship *R* is shown in Fig. 2, the top is the root node, and its child node is called the inner node (corresponding to the equivalence class which *R* constructed). The inner node can also contain other inner nodes (finer equivalence), the bottom level is the leaf node, corresponding to the specific knowledge point. We call the sub-nodes of the root for the *1th* level, the sub-nodes of the *1th* level node for the *2th* level, and so on, the specific knowledge points for the *n*-th level.

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** The structure of knowledge points quotient space with brotherhood relationship</figcaption></figure>

In the structure of quotient space shown in Fig. 2, each level is a set of equivalence of a certain granularity. When a user study a leaf node (a specific knowledge point), each inner node on the path is considered to be accessed.

# 2 Functions Definition of Multi-granularity Ant Colony
Optimization

## 2.1 Ant Colony Optimization

Ant Colony Optimization (ACO) proposed by Dr. Marco Dorigo who inspired by the natural ant colony foraging process. Ants can find the shortest path from the food source to the nest in un-visual conditions. During the foraging process, the ants release pheromone, which is proportional to the quality of the food source, and sense the pheromone. Then ants tend to move in the direction of high pheromone concentration. Thus, the group behavior of the ant colony shows a positive feedback: the more ants travel on a path, the more probability the latter choose the path, so, the path with good quality and short distance will attract more ants, and the pheromone concentration grows faster[14].

## 2.2 Functions Definition of ACO in Multi-granularity Data

In order to apply the ACO to the mining of multi-granularity knowledge points of hierarchical structure, several functions such as support degree, pheromone concentration and preference function in ACO are defined as follows:
**Definition 4:** Support $\eta_l$ represents the probability that the user accesses path $l$, expressed as the access frequency of the path.

Let $K_{ij}$, $K_{im}$ be the two knowledge points (equivalence class) nodes of the $i$-th level, the number of nodes in $i$-th level is $n_i$, path $l(i, j, m)$ represents a certain path from node $K_{ij}$ to node $K_{im}$, the number of times the user visits the path $l(i, j, m)$ is expressed as $C_l(i, j, m)$. Then for the hierarchical interest pattern, its support $\eta_l(i,j,m)$ is:

$$ \eta_l(i,j,m) = \frac{C_l(i,j,m)}{\sum_{k=1}^{n_i} C_l(i,j,k)} \quad (1) $$

**Definition 5:** The pheromone concentration $\tau_l(t)$ represents the user's interest in access to a path $l$, fades with time and increase with the user accesses the path $l$.

$$ \tau_l(t+1) = (1-\rho) \tau_l(t) + \delta \Delta \tau_l \quad (2) $$

In formula (2), $\rho$ is pheromone volatilization coefficient, $\delta$ is pheromone concentration increment adjustment coefficient, $\Delta \tau_l$ is pheromone increased value, the formula is as follows:

$$ \Delta \tau_l = \frac{\tau_l(t) \times t + F_b}{t-1} - \tau_l(t) \quad (3) $$

In formula (3), $F_b$ is the feedback value of the user's access to the node at time $t+1$.

**Definition 6:** The preference function $P_l(t)$ represents the user's preference for path $l$, including two factors which are pheromone and support. Let $\tau_w(t)$, $\eta_w$ represent the pheromone and support of $w$-th path. Then the preference function $P_l(t)$ is defined as:

$$ P_l(t) = \frac{[\tau_l(t)]^\alpha \cdot [\eta_l]^\beta}{\sum_{w=1}^{n} [\tau_w(t)]^\alpha \cdot [\eta_w]^\beta} \quad (4) $$

In formula (4), $n$ is the total number of paths in this level. If the threshold of the preference function is given and the value of the preference function $P$ of all the path nodes is checked by (4), then the user's learning preference on multi-granularity knowledge points can be obtained.

## 3 Dynamic Mining Algorithm for Multi-granularity Learning Preferences

In this paper, we use the dynamic volatility of pheromone to dynamically mining the learning preferences on multi-granularity knowledge points. The main idea is that the user's knowledge learning activity corresponds to the ant's foraging behavior, the process of the users' learning knowledge points corresponds to the ants' foraging activity cycle. All of the users' learning actions are recorded in log files. Based on these log files, we can use ACO to find preferred function values of path nodes that formed by all knowledge points, and dynamically mine learning preferences for each knowledge point of the users, and then offer the users needed content for further study. Multi-
granularity Learning Preference Mining algorithm based on Ant Colony Optimization (ACO-LPM) described as follows:

Input: Pre-processed *m* learning records, preference function threshold *T*<sub>p</sub>

Output: learning preferences *H* of all levels in Multi-granularity knowledge space

**Step 1:** Initialize the ACO parameter, $t=0$, $\tau_l(t)=0$, $\eta_l=0$, $C_l=0$;

Initialize the knowledge point space tree, *Tree*=NULL;

Initialize the learning preference set, $H = (H_1, ..., H_n) = NULL$;

**Step 2:** According to the domain knowledge ontology, construct the quotient space tree of domain knowledge *Tree*;

**Step 3:** FOR (*i*=1 to *m*)

Find the first *i* log records corresponding to the path *l* in the tree *Tree*;

Calculate $F_b$ of all nodes on path *l*, update $C_l$, $\tau_l(t)$.

END FOR

**Step 4:** Calculate $\eta_l$ of all path nodes from equation (1);

**Step 5:** Initialize $\alpha$, $\beta$;

FOR (*i*=1 to *Tree.High*)

Calculate $P_l(t)$ of all path nodes in the i-th level;

If $P_l(t) > T_p$, then $P_l(t) \rightarrow H_i$;

END FOR

**Step 6:** Return *H*.

In step 4 of the above algorithm, *Tree.High* represents the height of the tree *Tree*.

The time complexity of the algorithm: according to the definition of the quotient space structure, if the average of each equivalence class is composed of *m* elements, then the number of nodes in the upper lever is *m*<sup>2</sup> times less than the number of nodes in the lower level in the multi-granularity knowledge quotient space structure. While the time complexity of standard ACO is O(*I*\**N*<sup>2</sup>\**k*), in which *I* is the number of iterations, *N* is the number of vertices, and *k* is the number of ants in the ant colony. So the time complexity of the i-th level is O(*I*\*(N/m<sup>2i</sup>)<sup>2\*k</sup>), which has a greater reduction compared to the original space. Meanwhile, because the data of user online learning is the same, so the training data of each node in i-level increased m<sup>2i</sup> times, which can effectively solve the problem of sparse data in the online learning system.

# 4 Experiment and Result

This section verified the effectiveness of the multi-granularity mining algorithm from two aspects: dynamic mining process display and practical application system. The experimental data was got from the online learning system, and the user learning behavior is recorded in log files. In order to record the user learning behavior, we added knowledge points information on the basis of the W3C extended log ExLF, which format is: "c-ip date time cs-username cs-method cs-uri-stem cs-user-agent sc-knowledgepoint cs-iscorrect sc-status sc-bytes". For example: "205.12.15.179 [01/Jul/2015:09:10:12] utest1 'GET /index/ course/?courseid=10379 HTTP/4.0' M050311 0 200 598". Table 1 listed the log identification and description:
<table><caption>**Table 1.** The log format definition based on W3C extended standard</caption><thead><tr><td>Field identifier</td><td>Description</td></tr></thead><tbody><tr><td>c-ip</td><td>IP address of client that accessed the server</td></tr><tr><td>date</td><td>The date when the transaction was completed</td></tr><tr><td>time</td><td>The time when the transaction was completed (use UTC standard by default)</td></tr><tr><td>cs-username</td><td>Authenticated user name (anonymous user with '-')</td></tr><tr><td>cs-method</td><td>Action method that the client performed (GET and POST)</td></tr><tr><td>cs-uri-stem</td><td>Full URL of the data source that has been accessed</td></tr><tr><td>cs(Referer)</td><td>Previous URL that the user browsed, the current page is linked from the URL</td></tr><tr><td>cs-user-agent</td><td>The browser version information used by the user client</td></tr><tr><td>sc-knowledgepoint</td><td>The knowledge points that the user visited</td></tr><tr><td>cs-iscorrect</td><td>Answer correctness (1 is correct, 0 is wrong)</td></tr><tr><td>sc-status</td><td>Returned status after the execution, described by HTTP or FTP</td></tr><tr><td>sc-bytes</td><td>The number of bytes sent by the server to the client</td></tr></tbody></table>

## 4.1 Dynamic Change Process Experiment of User Learning Preference

Dynamic mining is one of the advantages of the ACO-LPM algorithm. We took some log information to do simulation test on the situation of user's interest change. After the pre-processing of log records, knowledge that involved in one learning action combined with the case of right or wrong answer (*F*: wrong, *T*: right) as a record, such as: "K01F" represents the answer of knowledge K01 is wrong. Selected part of the knowledge of learning behavior data as follows:

<table><caption>**Table 2.** The data of user learning behavior</caption><thead><tr><td>Learning Record</td><td>Knowledge point learning situation list</td></tr></thead><tbody><tr><td>S001</td><td>K01F, K02F, K08T</td></tr><tr><td>S002</td><td>K01F, K02F, K06T, K09T, K12T</td></tr><tr><td>S003</td><td>K01T, K02F</td></tr><tr><td>S004</td><td>K01T, K02T, K07F</td></tr><tr><td>S005</td><td>K01T, K04T, K05F, K07F, K10T</td></tr><tr><td>S006</td><td>K03F, K07F, K08F</td></tr><tr><td>S007</td><td>K03T, K05T, K07F, K08F</td></tr><tr><td>S008</td><td>K02T, K03T, K07F, K08T, K15T</td></tr><tr><td>S009</td><td>K01T, K03T, K07T, K11T</td></tr></tbody></table>

Assuming that the minimum support is 2, the traditional mining algorithm will get frequent itemsets in consideration of the correctness of the answer {{K01K02: 3}},
{K03K07: 2}}( In order to facilitate the expression, we call item {K01K02} for item-
set1, item set {K03K07} for itemset2). However, if you carefully analyze the data flow,
you will find two facts: First, In the long run, the user has the preferences of knowledge
point K01K02, itemset1 coincidence occurs 3 times, and the error times with the correct
times of 2: 1; Second, recent user learning has changed, itemset1 did not appear in the
last 5 learning, but the itemset2 appeared 2 times, indicating that the user was con-
cern about itemset2 recently(Comprehensive practice of knowledge points K03 and
K07). In order to show the changes of frequent item sets more clearly and intuitive, we
added value of pheromone volatilization coefficient ρ and concentration incremental
coefficient δ, the parameters of ACO are defined as: ρ= 0.15, δ= 0.3, α = 1, β = 0.5.
The preference function curve of each item is shown in Fig. 3. It can be seen that at the
beginning of the training, the preference function value of the node is exponentially
increasing due to the user's continuous error at the knowledge point K01K02, and the
preference function value of the other knowledge points is zero; In the second half of
the training, the knowledge point K01K02 is gradually reduced because it has not been
accessed, but the preference value of the knowledge point K03K07 is gradually in-
creased with the access, and even more than the knowledge point K01K02. It can be
concluded that this algorithm can dynamically capture the current user's preference
when the user's preference changes.

<figure><img src="image_4.png" /><figcaption>Fig. 3. The curve of user learning preference function</figcaption></figure>

## 4.2 Experiment Data Analysis of Practical Application System

In order to verify the effectiveness of this method, we use the learning resources and
system logs of the online education online system of Anhui Education Publishing Net-
work Company (http://www.timeep.com/cms/index.html) on line in 2015 .We have ex-
tracted the user learning logs of junior high school mathematics, physics, chemistry, a
total of 12,000 log information, and recorded them in Math, Physics, Chemistry three
data sets.

After preprocessing above data, we used the current mainstream mining algorithms:
BP neural network (referred to as the BP-NN) and FP-growth algorithm for mining
frequent items (referred to as FP-growth), and multi-size paper ACO-LPM learning
preferences mining Algorithm, respectively, to test and verify the accuracy rate. In order to unify the format, ACO-LPM algorithm in this paper only mine for the first three granularity level. We set the ACO parameters as: $\rho=0.05$, $\delta=0.5$, $\alpha=1$, $\beta=0.5$. The accuracy of each learning preferences mining algorithms is shown in the following table:

<table><caption>**Table 3.** Accuracy comparison of the ACO-LPM with other algorithms</caption><thead><tr><th rowspan="2">Knowledge field</th><th rowspan="2">BP-NN</th><th rowspan="2">FP-growth</th><th colspan="3">ACO-LPM</th></tr><tr><th>Original space</th><th>Level-2</th><th>Level-1</th></tr></thead><tbody><tr><td>Math</td><td>69.5%</td><td>72.3%</td><td>73.7%</td><td>80.2%</td><td>85.7%</td></tr><tr><td>Physics</td><td>66.8%</td><td>68.6%</td><td>70.1%</td><td>75.5%</td><td>80.9%</td></tr><tr><td>Chemistry</td><td>66.2%</td><td>67.0%</td><td>68.7%</td><td>76.1%</td><td>81.7%</td></tr></tbody></table>

It can be seen from Table 3 that the ACO-LPM mining algorithm in this paper is superior to BP-NN and FP-growth algorithm as a whole. And with the level of the study increased, the accuracy of mining increases. This situation is not random, but by the character of hierarchical structure user interest, the higher the level, the user interest model contains more content, and the more vague concept, the higher the hit rate.

## 5 Conclusion

In online learning system, it is a great challenge to mining learning preferences on knowledge points because of the massive knowledge points, the few single user test data, and the change of user's learning preferences. Based on the Multi-granularity feature of knowledge points, this paper defines a quotient space structure of the knowledge points. On this basis, the ACO is introduced into the quotient space, and the multi-granularity dynamic mining algorithm is proposed by using the characteristics of pheromone dynamic volatility. Experiments show the effectiveness of the method.

## Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant No. 61672204), Natural Science Foundations of Higher Education Institutions of Anhui Province (Grant Nos. KJ2012B149, KJ2013A226, KJ2015A229, KJ2015A257), Key Projects of Domestic Visiting and Training for Middle-aged and Young Scholar in Anhui Province (Grant No. gfxZD2016211).
References

1. Jia-Jiunn Lo, Pai-Chuan Shu. Identifying Learning Styles by Observing Learners' Browsing Behavior. British Journal of Educational Technology (in press), 2008.

2. Du Jin, Zheng Qinghua. The Research of Mining Association Rules between Personality and Behavior of Learner under Web-Based Learning Environment. The 4th International Conference on Web-based Learning (ICWL 2005), July 31-August 3, 2005, Hong Kong, China.

3. Qiu Baishuang. Research on user model in adaptive learning system based on Semantic Web [D]. Northeast Normal University, Changchun, 2008 (in Chinese).

4. Ling Hongfei, Yang Yuansheng. The user table and update mechanism[J]. the Journal of Computer Research and Development., 2002, 39(7): 844-847 (in Chinese).

5. Yan Shukui. Design and implementation of user interest extraction system for mobile network news[D], Beijing University of Posts and Telecommunications, Beijing, 2012 (in Chinese).

6. Ren Ziting. Research on Personalized Recommendation user interest modeling in mobile environment[D], University of Electronic Science and Technology of China, Chengdu, 2015 (in Chinese).

7. Wang Hongming. Design and implementation of user preference extraction system based on ontology and tag[D], Beijing University of Posts and Telecommunications, Beijing, 2011 (in Chinese).

8. Wolfgang Woemd, Christian Schueiler, Rolf Wojtech. A Hybrid Recommender System for Context-aware Recommendations of Mobile Applications. In Proceedings-International Conference on Data Engineering, Workshops in Conjunction with the International Conference on Data Engineering-ICDE'07.2007.871-878.

9. Chen Shuran. Research on personalized service oriented user interest modeling and Application [D]. Chongqing University, 2007 (in Chinese).

10. Pazzani M. and Billsus D. Learning and Revising User Profiles: The identification of interesting Web sites. Machine Learning 27, 1997:313-331.

11. Adomavicius G. and Tuzhilin A. Using Data Mining Methods to Build Customer Profiles. IEEE Computer, Feb2001:74-82.

12. Zhang L, Zhang B. Dynamic Quotient Space Model and Its Basic Properties[J]. Pattern Recognition & Artificial Intelligence, 2012, 25(2):181-185 (in Chinese).

13. Wang G Y, Zhang Q H, Jun H U. An overview of granular computing[J]. Caai Transactions on Intelligent Systems, 2007, 2(6):8-26 (in Chinese).

14. Chen S, Lv G, Wang X. Offensive Strategy in the 2D Soccer Simulation League Using Multi-group Ant Colony Optimization[J]. International Journal of Advanced Robotic Systems, 2016, 13:1.