Implementation of Genetic Algorithm for developing knowledge centric environment in higher education

Abstract

Knowledge defines the action of an entity in a particular work setting. Developing a model for knowledge creation helps to gain a competitive advantage in the work scenario of any organization. There is also a requirement in the non-profit sector like education to optimize the functioning by deducing knowledge from the massive amount of data that gets accumulated. The paper illustrates the implementation of Genetic Algorithm based knowledge creation technique which could be applied in higher education scenario quantifying knowledge on various parameters and eventually helping in making guided decisions in the environment.

Keywords

Classification entropy Genetic Algorithm higher education knowledge

1. Introduction

Comparison of different solutions in an iterative manner, leads to optimization on certain output criteria. The process of comparison goes on till a favorable solution is reached. Hence in order to acquire a favorable solution in numerous problems of the real world, maximization or minimization of a certain output criteria should be carried out [1]. Optimization in the functioning of non-profit education sector could be achieved by adopting measures that lead towards knowledge creation. Researchers have taken up this subject to carry out this work of importance [2].

Knowledge can be viewed as problem definitions, validated models, concepts, arguments, beliefs, descriptions, problem statements, etc. [3]. Knowledge which is a direct precursor of our decisions, eventually help in making guided decisions in the environment [4]. The subject of knowledge discovery in database (KDD) has been taken up by various researchers in sectors pertaining to medical, education, insurance, etc. [5, 6].

In the popular book “The knowledge creating company”, the authors put forth the view that the success of Japanese companies relies on the skill set and expertise at the knowledge creation level [7]. Keeping the same in the light, knowledge progression in an organization can be exhibited through Fig. 1.

Figure 1.

Knowledge progression.

One of the major achievements of the field of Artificial Intelligence (AI) is to provide a range of ways to represent knowledge [8]. Knowledge in a system can be represented by IF-THEN rules illustrating causal relationships, a frame-based system, a semantic network, or through an artificial neural network depicting connection weights.

The knowledge that can be represented in form of IF-THEN rules, bring out the relationship between various attributes under study and adopt a segmental approach, each describing primarily independent and relatively minor piece of knowledge [9]. The study undertakes the creation of knowledge set through generation of classification rules. Genetic Algorithm (GA) is used to develop efficient classifier in the study and hence achieve a knowledge set comprising of rules that can be further used to exploit relationships among the independent attributes.

For achieving optimization, GA is a robust and suitable technique. It carries out directional search in an effective manner. Moreover through the procedures of selection, crossover, and mutation GA finally converges over successive generations to achieve global (or near global) optimum. The technique follows the following scheme until best solutions are acquired.

Random initialization of population (p)

Determining fitness of population (p)

repeat

•

Selection of parents from population (p)

•

Performing crossover on parents, leading to creation of population (p $+$ 1)

•

Performing mutation of population (p $+$ 1)

•

Determining fitness of population (p $+$ 1)

until best solution is reached

The paper is organized as follows. Section 2 discusses the related work. Section 3 elaborates the methodology adopted in the study explaining the application of GA procedures to the considered problem. The results acquired on implementation of the experiment in MATLAB R2015a are explained in Section 4. The interpretation and analysis of the results are also stated in the same section. Finally, the conclusion is drawn along with the statement of future directions in Section 5.

2. Related work

As is known, knowledge building can be achieved through extraction of information from the huge amount of data accumulated by organizations. Knowledge centric activities could be associated with number of important processes that exist in educational organization like planning of strategies, admission, curriculum development, teaching-learning, examination and evaluation, research initiatives, bonding with alumni, etc. [10].

Data mining (DM) technique is the process of discovering relationships from huge volumes of data. Further DM technique of Classification rule mining can be considered as a means to establish relationships between entities that are not visible openly. Experimental results show that the technique of classification rule mining well supplemented by genetic algorithm discovers rules having higher classification performance to unknown data [11].

Several GA designs, for discovering classification rules, have been proposed by the researchers. The researchers [12] in their work proposed IF-THEN rules that make use of generalized uniform population method. A uniform operator inspired from the uniform population method is used to obtain high quality chromosomes. In the work [13], GA is used to discover IF-THEN rules where each chromosome corresponds to classification rule. Here the genotype (number of genes) in the chromosome is kept fixed varying the phenotype (number of rule conditions). In their work [14] constructed IF-THEN rules using GA approach where the fitness function considers four important factors, error rate, entropy, rule consistency and hole ratio. Even Hybridized GA with Tabu search was proposed to do classification rule mining [15]. The authors [16] proposed a Hybrid Elite Genetic Algorithm and Tabu Search method to optimize the premise and consequent parameters of fuzzy rules for the design of fuzzy system of Takagi- Sugeno zero order.

Table 1
Attributes of the study

Attribute name	Attribute type	Description
CEM	Independent	Performance of the students continuously evaluated by the faculty member with respect to class assignments, marks obtained in class test, performance in viva-voce etc. (Maximum Marks $-$ 30)
SP	Independent	Performance of the student in previous semester measured in terms of Semester Grade Point Average (Maximum Pointer 10)
A	Independent	Attendance of the student in the considered course of Mathematics II (Maximum Attendance $-$ 100%)
AS	Independent	Performance of the student in allied subjects (e.g.) Physics
BSM	Independent	Student’s performance in Mathematics I (base course for Mathematics II)
ETM	Dependent	Student’s performance in the end term examination of the course under consideration

Figure 2.

Entropy of the independent attributes.

Subsequently the approach of GA was further extended by various researchers by using multi-objective genetic algorithm approach (MOGA) for mining classification rules from large databases. In the work [17], researcher used Lexicographic Pareto Based Multi-Objective Genetic Algorithm to extract useful rules from Iris Data set. In their work [18] proposed a multi-objective genetic algorithm with a hybrid crossover operator for optimizing objectives like predictive accuracy, comprehensibility and interestingness of the rules simultaneously. Later the researchers compared this rule discovery procedure with simple genetic algorithm approach with a weighted sum of all the above objectives.

3. Adopted methodology

The procedure starts with the initialization of population comprising of random members. Student’s characteristics related to performance of the students in final term examination are codified in terms of bit sequences. This initial population is used to randomly select two individuals to create offspring exhibiting great potential. These newly generated offspring will have high scoring capabilities due to the inheritance of characteristics from their high scoring parents.

Replacement of non-high scoring offspring could be carried out by high scoring individuals, generated through the work keeping the population size intact. Working through this process leads to production of offspring with high scoring intelligence.

3.1 Attributes under study

The study was carried out using the following attributes shown in Table 1.

The entropy value for each dependent attribute is then calculated, which is a measure of uncertainty associated with a random variable. In case, $D$ is a dataset comprising of $d$ data samples. In the event of $x$ distinct classes, $C_{i}(i=1\ldots x)$ , consider $d_{i}$ to be the number of data samples of $D$ in class $C_{i}(i=1\ldots x)$ . The expected entropy needed to classify a given sample in $D$ is shown by Eq. (1).

$\displaystyle-\sum\limits_{i=1}^{x}pr_{i}\log_{2}pr_{i}$ (1)

where is the probability that an arbitrary sample belongs to class $C_{i}$ .

It should be noted that higher entropy signifies higher uncertainty and lower entropy represent lower uncertainty, which is desirable [19]. The independent attributes were assessed on the basis of their entropy value. The results are shown in Fig. 2.

3.2 Encoding of attributes

Attributes can be encoded using binary values. On application of this procedure, continuous values of the attributes may be transformed into binary values, and vice versa. As understood, binary digits are used to work with binary encoded GA, let $N_{\textit{gene}}$ bits be used to represent attribute $a$ in the study. If $N_{\textit{gene}}=$ 3, eight possible values of $a$ can be produced [20]. Table 2 depicts encoding of attributes present in the study.

Table 2
Encoding of attributes

Attribute – CEM (Maximum Marks 30)		Attribute – SP (Maximum Value 10)
Marks lying between	Codes	SGPA between	Codes
0–3	000	0–2	000
4–7	001	2.1–4	001
8–11	010	4.1–5	010
12–15	011	5.1–6	011
16–19	100	6.1–7	100
20–23	101	7.1–8	101
24–27	110	8.1–9	110
28–30	111	9.1–10	111
Attribute – BSM (Maximum Marks 100)		Attribute – A (Maximum Attendance 100 %)
Marks lying between	Codes	Attendance	Codes
0–20	000	Below 65%	000
21–40	001	65.1–70%	001
41–50	010	70.1–75%	010
51–60	011	75–80%	011
61–70	100	80.1–85%	100
71–80	101	85.1–90%	101
81–90	110	90.1–95%	110
91–100	111	95.1–100%	111
Attribute – AS (Maximum Marks 100)		Attribute – ETM (Maximum Marks 100)
Marks lying between	Codes	Marks lying between	Codes
0–20	000	0–20	000
21–40	001	21–40	001
41–50	010	41–50	010
51–60	011	51–60	011
61–70	100	61–70	100
71–80	101	71–80	101
81–90	110	81–90	110
91–100	111	91–100	111

The chromosome in work is made up of 5 attributes, each encoded with $N_{\textit{gene}}=$ 3 bits. Attributes are represented using binary encoding, but to compute the fitness function often continuous values are required. Therefore before evaluation of the fitness function, chromosomes are to be decoded. This can be done through a mapping function which maps binary string representation (genotype) to solution (phenotype). Equation (2) depicts the mapping function $F$ .

$\displaystyle F(u,l,n,c)=\left[{\frac{(u-l)\textit{decode}(c)}{2n-1}}\right]$ (2)

Where $u=$ upper bound, $l=$ lower bound, $c$ – chromosome, $n=$ chromosome length (in bits).

3.3 Setting of optimization parameters

GA optimization parameters used for the study are presented in Table 3.

Table 3
Optimization parameters

Optimization parameters	Particulars
GA type	Simple
Chromosome pepresentation	Binary
Population size	10
Selection	Roulette wheel
Crossover operator	Binary
Mutation type	Bit flip
Number of iterations	10
Type of fitness function	Weighted aggregation
Termination criteria	On reaching 25 generations

Table 4

Result after 25 generations run

Generation	Bit sequence matching the dataset in each generation	No. of repetitions
1	110110101010110	2
	100111010111111	4
	101111110111110	2
	110110110111000	2
	110111111101111	2
3	None of the bit sequence matched the dataset	–
4	None of the bit sequence matched the dataset	–
5	None of the bit sequence matched the dataset	–
6	None of the bit sequence matched the dataset	–
7	None of the bit sequence matched the dataset	–
8	None of the bit sequence matched the dataset	–
9	101001111111011	1
10	110110101010110	2
11	100111010111111	4
	110110110111000	2
	110111111101111	2
12	None of the bit sequence matched the dataset	–
13	None of the bit sequence matched the dataset	–
14	None of the bit sequence matched the dataset	–
15	None of the bit sequence matched the dataset	–
16	None of the bit sequence matched the dataset	–
17	None of the bit sequence matched the dataset	–
18	100110101101100	2
19	101111010101111	2
20	101111111110111	2
	111010111101111	2
21	None of the bit sequence matched the dataset	–
22	None of the bit sequence matched the dataset	–
23	110110101100001	2
	111010111111101	2
	111111101110111	2
24	None of the bit sequence matched the dataset	–
25	101101110111110	2

3.4 Initial population & fitness function

The population comprises of a group of chromosomes. The initial population is randomly generated and evaluated over a fitness function. With the help of the fitness function, quantification of the optimality of a chromosome could be achieved. Quantification of the chromosomes may lead to ranking of a particular solution against all the other solutions.

A five attribute, weighted fitness function shown in Eq. (4.1), is stated for optimizing the end term performance of the students in the course of Mathematics II. It can be seen that every attribute ( $v_{1}\ldots v_{5}$ ) in Eq. (4.1), is multiplied with their corresponding weights, which are in fact the entropy values of the attributes (Eq. (1)). Authors [21] in their study suggested a weighted aggregation model following genetic approach for optimization of performance of student in a course pertaining to higher education. Here the fitness function had variables weighted on information gain.

Table 5
Antecedent part of the rule

Pattern	Attributes	Interpretation
100	CEM	16–19 (Maximum Marks 30)
111	SP	9.1–10 (Maximum SGPA 10)
010	AS	41–50 (Maximum Marks 100)
111	A	95.1–100% (Maximum Attendance 100%)
111	BSM	91–100 (Maximum Marks 100)

4. Experimental study

The experiment has been performed using MATLAB R2015a on a system with Intel(R) core (TM) i3-4005U CPU @ 1.70 GHz, 1700 Mhz, 2 Core(s), 4 Logical Processor(s) and 4.00 GB installed physical memory (RAM).

Table 6
Class assignment

Class label	Count
000	0
001	0
010	0
011	0
100	1
101	0
110	0
111	3

Table 7

Confusion matrix

		Actual class
		Class	Not class
Predicted class	Class	$tp=$ 3	$fp=$ 1
	Not class	$fn=$ 317	$tn=$ 4679

Table 8

Performance metrics for evaluating the rule

Measure	Interpretation	Formula	Value (%)
Accuracy	Percentage of test set tuples that are correctly classified.	$\frac{\text{tp}+\text{tn}}{\text{tp}+\text{tn}+\text{fp}+\text{fn}}$	93.64
Recall	Measure mentions the proportion of cases in the dataset depicting the predicted class C that is actually represented by the rule	$\frac{\text{tp}}{\text{tp}+\text{fn}}$	0.93
Specificity	Measure mentions the true negative recognition rate	$\frac{\text{tn}}{\text{tn}+\text{fp}}$	99.9
Precision	Percentage of tuples that the classifier labeled as positive are actually positive	$\frac{\text{tp}}{\text{tp}+\text{fp}}$	75

4.1 Description of the dataset

The experiment was carried on a dataset having 5000 records and five attributes, all of them categorical.

$\displaystyle{F}({v1,v2,v3,v4,v5})=2.924590\ast v1$ $\displaystyle\quad+\,2.920805\ast v2+2.928679\ast v3$ (3) $\displaystyle\quad+\,2.911252\ast v4+2.630926\ast v5$

where $v1=$ CEM, $v2=$ SP, $v3=$ AS, $v4=$ A, $v5=$ BSM.

4.2 Simulated results

On running the algorithm for 25 generations, the result set is shown below in Table 4. It has been observed that on running 10 iterations in 25 generation, the maximum occurrence of bit sequence in the dataset is 4.

4.3 Result interpretation

The bit pattern 100111010111111 obtained can now be converted into the antecedent part of the rule as shown in Table 5.

To obtain the consequent part of the rule, the class label can be assigned by the following below mentioned computation in Eq. (4).

$\displaystyle\frac{\textit{Antecedent}_{ij}}{\textit{Consequent}_{j}}$ (4)

Where $\textit{Antecedent}_{ij}$ – Number of instances in the database where antecedent is true of $i^{\text{th}}$ chromosome and $j^{\text{th}}$ class.

$\textit{Consequent}_{j}$ – Number of instances of $j^{\text{th}}$ class in the database.

The class label assigned to the chromosome is the one for which the value of Eq. (4) is highest. On applying the above mentioned criteria, the probable class labels were compared for their count in the database and the following counts for the respective class labels were obtained, which are presented in Table 6.

Hence the selected class label is 111, which translates to end term marks lying between 91–100. Therefore the rule that is coined is given below.

Continuous Evaluation Marks (CEM) are between 16–19 (Max marks 30)

${}^{\wedge}$ Performance in previous semester (SP) between 9.1–10

${}^{\wedge}$ Performance in allied subjects (AS) between 41–50 (Max marks 100)

${}^{\wedge}$ Attendance (A) between 95.1–100%

${}^{\wedge}$ Performance in Base Subjects (BSM) between 91–100 (Max marks 100)

THEN

The End Term Marks (ETM) are between 91-100 (Max Marks 100)

4.4 Result analysis

Consider that the rule generated, is of the form: IF A THEN C where

$\displaystyle A\to\textit{Antecedent of the rule}$ $\displaystyle C\to\textit{Consequent (Predicted Class) of the rule}$

Confusion Matrix can be used to summarize the performance of a rule, in terms of True Positive (tp), True Negative (tn), False Positive (fp) and False Negative (fn) values.

Where tp $=$ True Positives $=$ Total cases in dataset satisfying Antecedent and Consequent of the rule.

fp $=$ False Positives $=$ Total cases in dataset satisfying Antecedent but not Consequent of the rule.

fn $=$ False Negatives $=$ Total cases in dataset not satisfying Antecedent but satisfying Consequent of the rule.

tn $=$ True Negatives $=$ Total cases in dataset not satisfying Antecedent nor Consequent of the rule.

The confusion matrix is presented in Table 7.

Various metrics that can be derived from the confusion matrix are listed in Table 8.

5. Conclusion and future scope

The study uses GA for establishing relationships between attributes that are not visible openly. The single objective implementation of GA which identifies students’ characteristics associated with maximization of final performance in a course of higher education proves to be a useful deduction. Such an inference assumes importance in curriculum planning, an important aspect of any academic institution. This kind of work will make a sizeable contribution towards professional growth and advancement of the students.

The study can be further extended to implement rule generation through multi objective genetic algorithm (MOGA).

Footnotes

Acknowledgments

We acknowledge the support provided by the management of Corporate Groups of Institutes, Bhopal (India) for providing us the necessary backing to carry out the research activity presented in the paper.

References

Simon

, Evolutionary Optimization Algorithm Biologically-Inspired and Population-Based Approaches to Computer Intelligence, Wiley Pub, 2013.

Gupta

Mehrotra

and Sharma

T.K.

, Role of decision tree in supplementing tacit knowledge for Hypothetico-Deduction in higher education, International Journal of System Assurance, Engineering & Management, 2016.

Gupta

Mehrotra

and Singh

, Achieving excellence through knowledge mapping in higher education institution, International Journal of Computer Application (2012), 5–10.

Firestone

J.M.

, Knowledge management: A framework for analysis and measurement, 2000.

Firat

Arslan

A.K.

Colak

and Harputluoglu

, Estimation of risk factors associated with colorectal cancer: an application of knowledge discovery in databases, Kuwait Journal of Science 43(2) (2016).

Moses

, A survey of data mining algorithms used in cardiovascular disease diagnosis from multi-lead ECG data, Kuwait Journal of Science 42(2) (2015).

Nonaka

and Takeuchi

, The knowledge-creating company: How Japanese companies foster creativity and innovation for competitive advantage, London ua, 1995.

Shadbolt

and Milton

, From knowledge engineering to knowledge management, British Journal of Management 10(4) (1999), 309–322.

Rich

Knight

and Nair

S.B.

, Artificial Intelligence, TMH, New Delhi, 2010.

10.

Gupta

Mehrotra

and Sharma

T.K.

, Genetic based Weighted Aggregation model for optimization of student’s performance in Higher Education, in: Proceedings of Fifth International Conference on Soft Computing for Problem Solving Volume 436 of the Series Advances in Intelligent Systems and Computing, 2015, pp. 877–887.

11.

Al-Maqaleh

B.M.

and Shahbazkia

, A genetic algorithm for discovering classification rules in data mining, International Journal of Computer Applications 41(18) (2012).

12.

Gündoğan

K.K.

Alataş

and Karci

, Mining classification rules by using genetic algorithms with non-random initial population and uniform operator, Turkish Journal of Electrical Engineering & Computer Sciences 12(1) (2004), 43–52.

13.

Fidelis

M.V.

Lopes

H.S.

and Freitas

A.A.

, Discovering comprehensible classification rules with a genetic algorithm, in: In Evolutionary Computation, 2000. Proceedings of the 2000 Congress on. IEEE, Vol. 1, 2000, pp. 805–810.

14.

Yang

Widyantoro

D.H.

Ioerger

and Yen

, An entropy-based adaptive genetic algorithm for learning classification rules, in: In Evolutionary Computation, 2001. Proceedings of the 2001 Congress on. IEEE, Vol. 2, 2001, pp. 790–796.

15.

Zhong-Yang

Lei

and Yu-Fang

, A classification rule mining method using hybrid genetic algorithm, in: Proceedings of IEEE Region 10 Conference (TENCON 2004) Chiang Mai, Thailand: IEEE, 2004, pp. 207–210.

16.

Talbi

and Belarbi

, Designing fuzzy rule base using hybrid elite genetic algorithm and tabu search: Application for control and modeling, International Journal of Hybrid Intelligent Systems 10(4) (2013), 205–214.

17.

Dutta

, Classification Rules Generation for Iris Data Using Lexicographic Pareto Based Multi Objective Genetic Algorithm, in: Proceedings of 3rd International Conference on Intelligent Systems and Networks (IISN 2009), At Klawad, Haryana, India, 2009, pp. 173–177.

18.

Dehuri

Patnaik

Ghosh

and Mall

, Application of elitist multi-objective genetic algorithm for classification rule generation, Applied Soft Computing 8(1) (2008), 477–487.

19.

Han

and Kamber

, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers, Canada, 2000.

20.

Haupt

R.L.

and Haupt

S.E.

, Practical Genetic Algorithms, John Wiley & Sons Inc Publications, 2004.

21.

Gupta

Mehrotra

and Sharma

T.K.

, Identifying knowledge indicators in Higher Education Organization, in: Proceedings of International Conference on Information and Communication Technologies (ICICT 2014), Kochi, India, 2014.

Implementation of Genetic Algorithm for developing knowledge centric environment in higher education

Abstract

Keywords

1. Introduction

Table 1 Attributes of the study

3.1 Attributes under study

Table 2 Encoding of attributes

Table 3 Optimization parameters

Table 5 Antecedent part of the rule

Table 6 Class assignment

4.3 Result interpretation

5. Conclusion and future scope

Footnotes

Acknowledgments

References

Table 1
Attributes of the study

Table 2
Encoding of attributes

Table 3
Optimization parameters

Table 5
Antecedent part of the rule

Table 6
Class assignment