- 1 -
中国科技论文在线
A Discretization Algorithm Based on Information Distance
Criterion and Ant Colony Optimization Algorithm
Jia Lixin, Zhu Wenzhi
(School of Electrical Engineering, Xi'an Jiao Tong 'an 710049)
Foundations: Specialized Research Fund for The Doctoral Program of Higher Education(No. 20070698059);
Specialized Research Fund for The Doctoral Program of Higher Education(No. 20090201110019).
Brief author introduction:Jia Lixin(1968-), male, associate professor, main area of research is industrial
intelligent control.
Abstract: Discretization algorithms have played an important role in data mining, which is widely
applied in industrial control. Since the current discretization methods can not accurately reflect the
degree of the class-attribute interdependency of the industrial database, a new discretization algorithm,
which is based on information distance criterion and ant colony optimization algorithm(ACO), is
proposed. The paper analyses the information measures of the interdependence between two discrete
variables, and an improved information distance criterion is generated to evaluate the class-attribute
interdependency of the discretization scheme. In the algorithm, The ACO is applied to detect the
optimal discretization scheme, and a new pheromone matrix is defined on the construction of the
optimization, and an effective heuristic values assignment approach, which is used with the criterion
values of discretization scheme, is proposed. We performed the experiments on a real industrial
database. Experiment results verify that the proposed algorithm can produce a better discretization
results.
Keywords:Discretization;Data mining;Entropy;Ant colony optimization
0 Introduction
The industrial database is grown exponentially with the rapid development of industrial
automation technology. And extracting useful knowledge from such huge database is often an
unable task, so data mining has become a research focus recently [1]. Data mining has been widely
used in industrial process, such as, the construction of the classification rules as control rules base
and identification of the fuzzy model of a controlled plant [2-3]. The real-industrial data mining
tasks often involve continuous attributes, and a discretization algorithm should be used to
discretize those continuous attributes. Compared with continuous
attributes, the discrete attributes are more easy to understand, use and explain, and the
database can be simplified. For the discrete attributes are closer to knowledge-level representation,
data mining algorithm using the discretized data should obtain more compact and more
meaningful results for industrial control.
Discretization is a technique to partition continuous attributes into a finite set of intervals and
associate with each interval a distinct value. We can treat the discretized intervals as nominal
values during the data mining processing. In general, to discretize continuous attributes can be
broken into two steps. First, the number of discrete intervals should be selected. Only a few
discretization algorithms can perform the selection of the optimal intervals number; in most cases,
the users have to specify the number of the intervals or give a heuristic rule [4]. Second, the width
or the boundaries of intervals should be determined to define the range of values of a continuous
feature. In detail, the discretization algorithms can be categorized in five different axes: they are
supervised versus unsupervised, static versus dynamic, global versus local, top-down versus
bottom-down, and direct versus incremental [5]. Unsupervised method does not take in account of
relationship between pre-assigned classes and the discretized intervals while supervised method
does. The unsupervised method partitions the continuous features into subranges by user specified
- 2 -
中国科技论文在线
width or frequency [6], and it is vulnerable to outliers and the continuous values with non-uniform
distribution. To overcome this shortcoming, supervised method uses the classes information to
find proper and meaningful intervals. Among the various supervised methods, there are two
prominent evaluation criterions. One is entropy criterion, such as in the following method:
Entropy-MDLP [7], CADD [8], and Maximum Entropy [9], etc. The other is the statistical criterion,
such as Chi2 [10], Khiops [11], Extended Chi2 [12], and so on.
A dynamic method discretizes continuous values when a classifier is built, such as in [13],
while in static method discretization is done prior to the classification task. Compared with
dynamic method, the static method is independent from the learning algorithms. The local method,
which uses only parts of instances for discretization, is usually associated with dynamic method.
On the contrary, global method uses total instances and is always associated with static method.
The bottom-up method considers all the continuous values of the feature as cut-points and
removes some of them by merging intervals in each step. The Top-down method starts with empty
list of cut-points and adds new ones in each step, and its computational complexity is usually
better than the bottom-up method. For example, the time complexity of the method Extended Chi2
is O( km log m ), while that of the top-down method CAIM [14] is O(m log m), where k is the
number of the incremental steps and m is the number of the discretised intervals. On another
dimension of discretization methods: the direct method needs user to predefine the number of
discrete intervals, for example equal-width and equal-frequency methods. While the incremental
method starts with a simple discretization scheme and defines a stopping criterion to terminate
discretizing.
Based on the discussion above, we proposes a discretization algorithm based on information
distance criterion and ant colony optimization algorithm(ACO) for knowledge extracting on
industrial database. The paper analyses the information measures of the interdependence between
two discrete variables, and an improved information distance criterion is generated to evaluate the
quality of the discretization scheme. The algorithm automatically selects the number of discretized
intervals, the ACO is applied to detect the global optimal discretization scheme, and a new
pheromone matrix is defined on the construction of the optimization, and an effective heuristic
values assignment approach, which is used with the criterion values of discretization scheme, is
proposed. The organization of this paper is as in follows. Section 2 presents our analysis of the
class-attribute interdependency based on the information entropy, then gives a new discretization
criterion to evaluate discretization schemes. In section 3, The detailed discretization algorithm
based on ACO is described. In section 4, the experiments are presented to verify the proposed
algorithm. Finally, section 5 concludes the paper.
1 DISCRETIZATION CRITERION
Intuitively, the task of discretization is to minimize the number of discretized intervals, and
there is a limit imposed by the data representation. And in the viewpoint of Information entropy,
the algorithm has to maximize the interdependency between the classes and discretized intervals;
in other words, it has to minimize the information loss due to discretization. So we should make a
tradeoff between simplicity and accuracy. The basic concepts and definitions involved in this
paper are introduced in this section, then the new discretization criterion is proposed.
Basic Concepts and Definitions
Supposing that a data set consisting of M instances and S target classes, where each instance
belongs to only one of the S classes. A indicates any of the continuous attributes in the data set. A
- 3 -
中国科技论文在线
discretization algorithm partitions the continuous attribute A into k discrete intervals:
[ ] ( ] ( ]{ }0 1 1 2 1, , , , , ,k kd d d d d d−" (1)
where d0 and dk, respectively, are the minimal and maximal values of attribute A. Such a
discrete result is called a discretization scheme D on attribute A. The values in D are arranged in
ascending order, and constitute the boundary set BD={d0, d1, d2, …, dk-1, dk}. Since the boundary
set BD is certain corresponding to particular scheme D, then either BD or D can be used to
represent the discretization scheme. Treating the class variable and the discrete variable of the
attribute A as two random variables, we can form a contingency table according to the
discretization scheme D, shown in Table I.
Contingency Table for Attribute A and Discretization Scheme D
Interval Class
[d0,d1] … [dr-1,dr] … [dk-1,dk]
Class Total
C1 q11 … q1r … q1k M1+
… … … … … … …
Ci qi1 … qir … qik Mi+
… … … … … … …
CS qS1 … qSr … qSk MS+
Interval Total M+1 … M+r … M+k M
In Table 1, qir is the total number of data instances whose continuous values of attribute A
belonging to the ith class that are within the rth interval (dr-1,dr], for i=1, 2, …, S and r=1, 2, …, k.
Mi+ is the total number of instances belonging to the ith class, and it is unchanged no matter how
the discretization scheme D changes. M+r is the total number of data instances whose continuous
values of attribute A that are within the rth interval (dr-1, dr]. Because each value of attribute A can
only fall into one of the k intervals, so the distribution of class labels within each interval would
change with the change of the discretization scheme D.
Measurement of Class-Attribute Interdependency
Assuming that we have got a discretization scheme D for continuous attribute A as Table 1
shows. We define symbols C and F to denote the class variable and the discrete variable of
attribute A, respectively. For the rth interval Dr=(dr-1, dr], the joint probability of class labels pir
can be calculated as:
ir
ir
qp
M
= (2)
Then we get the marginal class probability pi+ and the marginal interval probability p+r as
follows:
i
i
Mp
M
+
+ = (3)
r
r
Mp
M
+
+ = (4)
where i=1, 2, 3, …, S and r=1, 2, 3, …, k.
In information theoretics, the entropy H(C) of the class variable C with discrete probability
distribution {p1+, p2+, …, pS+} can be written as:
2
1
( ) log
S
i i
i
H C p p+ +
=
= −∑ (5)
- 4 -
中国科技论文在线
Here, the base of the logarithm is two, so the unit of entropy is ''bit". And the entropy H(C)
represents the measure of the information uncertainty in the class variable C.
A discretization scheme D for the continuous attribute A is composed of k intervals, then the
conditional entropy HDr(C|F) denoting the information uncertainty of the class in the rth interval,
and HD(C|F), which quantifies the remaining information uncertainty of the class variable C after
the interval variable F is known, can be defined, respectively, as:
2
1
( | ) log
S
ir ir
Dr
i r r
p pH C F
p p= + +
= −∑ (6)
( | ) ( | )
r
r
D r D
D D
H C F p H C F+
∈
= ∑ (7)
2
1 1
log
k S
ir
ir
r i r
pp
p= = +
= −∑∑ (8)
Similarly, the mutual information ID(C;F) which measures the mutual dependence of the class
variable C and the interval variable F discretized by the scheme D can be calculated as:
( ; ) ( ) ( | )D DI C F H C H C F= − (9)
2
1 1
log
k S
ir
ir
r i i r
pp
p p= = + +
= ∑∑ (10)
From the definition of information measures above, we find that the mutual information
ID(C;F) quantifies the information uncertainty in the class variable C which is removed by
knowing the discrete variable F. Since the mutual information represents the amount of
information that knowing either variable provides about other, so the information measures can be
used as the measurement of class-attribute interdependency.
In detail, when a data set is given, the class variable C is fixed, and the class entropy H(C)
does not change with the change of discretization schemes. The conditional entropy HD (C|F)
increases as the probability distributions of classes in the discrete intervals becomes more uniform.
Since the conditional probability is used in conditional entropy HD (C|F), then as the number of
discrete internals increases, the probability distributions of classes in the discrete intervals become
more non-uniform. For increasing the class-attribute interdependency, the mutual information
measure prefers finer partitions of the continuous attribute A. In general, the more discrete
intervals, the more non-uniform distribution in each interval, the bigger mutual information value,
and better quality of a discretization scheme.
For a rth interval (dr-1, dr], from the property of the mutual information discussed above, it is
easy to find out that thenmore dense the classes distribution of a interval is, the better
classification ability the interval has. The conditional entropy of the rth interval HDr(C|F) should be
maximal if all the class probabilities are equally likely, pr=(1/S, 1/S, …, 1/S), where pir=pir / p+r ,
i=1, 2, …, S. And the maximal values will be log2(S). Conversely, HDr(C|F) gets its minimal value
0 when all the instances falling into this interval belong to one class, 1rip∀ = with 1 1
S r
ii
p= =∑ .
Therefore, the difference between a particular class probability distribution and the equal class
probability distribution mentioned above can validate the classification ability of the interval.
Then we define the information distance between the class conditional probability vector in rth
interval pr={p1r, p2r, …, psr} and the uniform class conditional probability vector pe= {1/S, 1/S, …,
1/S} as follows:
- 5 -
中国科技论文在线
2
1
1( ) ( )
S
r
r i
i
d p p
S=
= −∑ (11)
This paper avoids using the mutual information directly as the discretization criterion.
Because the mutual information prefers the finer partition, the discretization scheme generated
only by it will have a high class-attribute interdependency, but also be very complex and result in
a poor performance in predictive accuracy. So we propose a new discretization criterion based on
the information distance measure d(pr) described in Eq. (11). The new discretization criterion aims
to:
1): maximize the interdependency between the class variable C and the discrete variable F.
2): reduce the number of discrete intervals properly in a tradeoff between data simplicity and
information quality.
3): have a reasonable computation coast.
Discretization Criterion
The new discretization criterion based on the information distance measure d(pr) is proposed.
It measures the interdependency between the class variable C and the discrete variable F, for a
given discretization scheme D. And it is defined as:
1
2
max ( )
( , )
log
k r
rr
r
D
d p
MIDC C F
k
=
+=
∑
(12)
where k is the number of discrete intervals, r iterates through all intervals; maxr is the
maximum value among the rth column of the contingency table, M+r is the total number of data
instances whose continuous values of attribute A that are within the rth interval (dr-1, dr]; d(pr)
indicates the distance between the class conditional probability vector pr in rth interval and the
uniform class conditional probability vector pe.
we discuss the function as follows:
1): The larger the value of IDC, the higher the interdependency between the classes and the
discrete intervals.
2): If the biggest number of values in the contingency table within a particular interval
belongs to class Ci, then we call Ci the leading class within the interval. We use the conditional
probability of the leading class in rth interval, so the criterion will lead to the trend to maximizing
the leading class number within each interval without considering the whole class probability
distribution of each interval. Therefore, we add d(pr) to fix the disadvantage.
3): We treat the conditional probability of the leading class in rth interval as a weight to the
information distance measure d(pr). With this definition, the criterion would lead to a better result
with weighted considering the impact of every classes in the interval.
4): The criterion limits the number of discrete intervals in a proper range: the intervals in the
scheme can not be too many, for that will lead a overfitting problem. On the other hand, the
number k should not influence the IDC value too much either, for that will result in a unreasonable
discretization scheme. Therefore, we use log2 (k) instead of k.
5): The IDC takes on real values from the interval [0, 2log 1k k S S− ]. When the class
probability distribution is uniform for all the intervals in scheme D, it archives the minimal value 0.
On the contrary, when all the instances within each interval belong to one of the classes, the
maximal value 2log 1k k S S− can be got.
- 6 -
中国科技论文在线
2 THE DISCRETIZATION ALGORITHM BASED ON ACO
ALGORITHM
The discretization algorithm has to search the optimal global discretization scheme Dglobal
among all possible discretization schemes with the highest IDC value. And that is a highly
combinatorial and time consuming task. Other algorithms usually get the approximate optimal
discretization scheme by finding the local maximum values of the discretization criterion. To
overcome this shortage, we apply the ACO algorithm to detect the global optimal discretization
scheme.
Ant colony optimization (ACO) is a new paradigm of bio-inspired algorithms that has shown
very good behavior when solving hard combinatorial optimization, and many studies on this topic
are still being pursued[15]. We describe the searching approach based on ACO as follows:
In the boundary set decision point, more than one cut-point can be added to the discretization
scheme. Let cp={cp1, cp2, cp3, …, cpn} be the candidate cut-points set. For each boundary set
decision point, one of the n candidate cut-points is chosen to form a new discretization scheme. If
h is the number of the boundary set decisions in the global optimal discretization scheme detecting,
then we have to decide one from a total of nh boundary set combinations. This leads to a
combinational optimization problem.
One selection of cut-point from the candidate cut-points set cp for particular boundary set
decision corresponds to one ant move. For example, in Fig. 1 there are h boundary set decision
points denoted by BD1-BDh, and n candidate cut-points cp1-cpn for each boundary set decision
point. The ant moves through BD1, BD2, BD3, … and stops at BDh from the initial state. A bold
line marks the tour of this ant. The node visited by ant is selected as the cut-point added to the
boundary set for each boundary set decision point to form a new discretization scheme. For the
whole boundary set decision constructed by the ant in Fig. 1, the selected cut-points in BD1, BD2,
BD3, … and BDh are cp1, cp3, cp2, …, cpn, respectively.
Discretization scheme constructed by an ant tour, and the pheromone matrix
A colony of ants is generated and placed in the nest initially, and a terminal condition is
defined to determine where an ant trail stop. Searching for the best one among all possible
discretization schemes is based on the pheromone level, which is stored in a pheromone matrix
shown in Fig. 1, the size of the pheromone matrix is h*n and each entry in the matrix is denoted
- 7 -
中国科技论文在线
by ijτ , where i=1,…, h and j=1,…, n. When the ant arrives at the mth boundary set decision point
BDm, selection of the candidate cut-points of Bm+1 is based on the pseudorandom proportional rule:
we define a uniform distribution random variable q which takes the values from [0, 1], and a
parameter q0 whose value is within the interval [0, 1]. At iteration t, if 0q q≤ , for the vth ant, the
selection of cut-point in boundary set decision point BDi is according to (13); if q>q0, for the vth
ant, the selection is based on the transition probability defined by (14).
[ ] [ ]arg max ( )v
i
il ill Nj t
α βτ η∈= (13)
( ) ( )
( )
( ) ( )
v
i
ij ijv
ij
ij ij
l N
t t
P t
t t
α β
α β
τ η
τ η
∈
⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦= ⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦∑ (14)
where α , β control the relative weights of pheromone level and heuristic value
respectively. viN denotes the unused candidate cut-points set for the vth ant at the ith boundary set
decision point. Computing the heuristic value η usually requires apriori information about the
problem instance. So we use the IDC values calculated by tentatively adding the candidate
cut-points to the (i-1) scheme formed already as the heuristic values.
The pheromone trails ijτ on the ant tour are updated according to the IDC value of the
constructed discretization scheme calculated by (12). For each iteration, if a new global best ant is
found in this iteration, then pheromone trails on the tour traveled by the global-best ant are
updated; the new pheromone trail ( 1)ij tτ + is updated by
( 1) (1 ) ( ) ( )ij ij ijt t tτ ρ τ τ+ = − ++ (15)
where (0,1)ρ ∈ , is the pheromone trail evaporation rate, and ( ) 1 ( | )
gbij D
t H C FτΔ = .
Otherwise, no pheromone update is performed in this iteration. When the terminal condition is
satisfied, the ants will find the best cut-points combination of discretization scheme according to
the pheromone level and heuristic values.
The pseudocode of our discretization algorithm is as follows:
Input: Data set with i continuous attribute, M instances and S classes;
For each continuous attribute Ai do:
01: Find the minimum d0 and the maximum dn values of Ai;
02: Form the distinct values of Ai in ascending order.
03: Initialize all possible cut-points set cp with the minimum , maximum and all the
midpoints of all the distinct pairs;
04: Set the initial discretization scheme as D:{[d0,dn] and Globalidc=0;
05: Initialize the pheromone matrix, relative parameters, the amount of ants K, and iteration
limit T.
06: Set the initial iteration number t=0;
07: Set t=t+1;
08: For each one of the K ants, at the tth iteration, construct the discretization scheme as this
section describes;
09: Update and restore the global-best discretization scheme D and Globalidc value achieved
by the K ants;
10: Update the pheromone matrix as (15);
- 8 -
中国科技论文在线
11: If t T< , then go to 07, else terminate;
Output: The optimal discretization scheme D for continuous attribute Ai;
3 EXPERIMENT
To evaluate the proposed algorithm, experiments are done on a real industrial database. The
real database is the database of the ball mill grinding process. To facilitate our experiment, we
simplify the real database. The simplified database includes six attributes, the returned sand water
amount, the classifier additional water amount, the ball mill load, the mill current, the classifier
current and the pulp density. Since the values of the pulp density represents the ball mill working
conditions, we consider the pulp density attribute as the class attribute, and the rest of the
attributes are all continuous attributes. We randomly selects 140 instances from the industrial
database as the test database, and the number of classes is 4. The CAIM algorithm and the
proposed algorithm are used on the test database.
The CAIM algorithm does not have parameter to be set. In this paper, we apply the ACO to
detect the optimal discretization scheme, so we set the relative parameters as follows: the ant
number is set as 10, and parameters α and β are set as 1 and 2, respectively. The pheromone
trail evaporation rate ρ is set as . The parameter 0q used in the pseudorandom proportional
rule is set as . And the iteration limit T is 100. The IDC values of the five discretized attributes
on each iteration is shown in Fig. 2. The algorithm converges to a solution at about 50 iterations.
After 100 iterations, the algorithm finds the discretization schemes with the highest IDC values as
the optimal schemes.
The IDC values of the five discretized attributes on each iteration
A further experiment is performed to validate the quality of the discretization results
generated by CAIM and our algorithm. We compare the discretization results with the CAIR
criterion [14] as shown in (16), which is widely used to measure the interdependency of a
discretization scheme. The comparisons of the generated discretization schemes are shown in
Table 2.
2 2
1 1 1 1
1log log
k S k S
ir
ir ir
r i r ii r ir
pcair p p
p p p= = = =+ +
= ∑∑ ∑∑ (16)
- 9 -
中国科技论文在线
where ir irp q M= , i ip q M+ += and r rp q M+ += .
Summary of the two algorithms considered
Algorithm Mean cair Mean number of Intervals Mean time(sec.)
CAIM 4
Imfor-Disc 4
Table 2 collects the main average results of the two algorithm on the test database, where
Imfor-Disc denotes the proposed algorithm. The mean cair values of CAIM and Imfor-Disc are
and , respectively. The mean number of the discrete intervals of CAIM is 4, which
is the same as that of Imfor-Disc. Moreover, the mean discretization time of CAIM is , that
of Imfor-Disc is .
The cair values of the two algorithm on each discretized attribute are illustrated in Fig. 3. The
cair values of CAIM on the five discretized attribute are , , , and
. And the cair values of Imfor-Disc on the five discretized attribute are , ,
, and , respectively. Based on the comparison of the cair values, the
discretization schemes generated by the proposed algorithm would be better in the class-attribute
interdependency.
The cair values of the two algorithm on each discretized attribute
The experiments results show that the proposed algorithm can discretize the continuous
attribute of industrial database successfully, on the average, generate a good discretization scheme
with using ACO to optimize the schemes.
4 CONCLUSION
In this paper, a discretization algorithm based on information distance and ant colony
optimization algorithm for knowledge extracting on industrial database is proposed. The proposed
algorithm has some advantages as follows. First, it can discretize the continuous attributes of
industrial database effectively. Second, it uses the improved information distance criterion to
instead of the general entropy criterion, and the approach is more suitable for the discretization on
industrial database. Third, it applies ACO to detect the optimal discretization scheme, and raises
- 10 -
中国科技论文在线
the quality of the generated discretization scheme. Fourth, it uses the criterion values of the
discretization schemes as the heuristic values, and converges to a solution quickly. The experiment
results also verify the effectiveness of the proposed algorithm. Since our research is discretizing
the continuous attributes of industrial database, we would integrate the proposed algorithm and the
inductive rule mining algorithm to further verify the partition effectivity in our future work.
5 Acknowledgements (Optional)
This work was supported by The Research Fund for the Doctoral Program of Higher
Education.(20090201110019); The Research Fund for the Doctoral Program of Higher
Education.(20070698059);
References
[1] J. Han, M. Kamber. Data Mining: Concepts and Techniques [J]. Morgan Kaufman, 2001. 33(1): 149～160.
[2] Wang Han, Kong Lingfu. Study on a new method of incremental association rule data mining[J]. Chinese
Journal of Scientific Instrument, 2009: 438~443.
[3] Yong Zhang, Qing-dong Du, Shi-dong Yu, Jeng-Shyang Pan. RBF neural network based on fuzzy evolution
kalman filtering and application in mine safety monitoring[J]. 2009 Ninth International Conference on Hybrid
Intelligent Systems, 2009, 1: 467~470.
[4] . Ching, . Wong, and . Chan. Class-Dependent Discretization for Inductive Learning from
Continuous and Mixed Mode Data[J]. IEEE Trans. Pattern Analysis and Machine Intelligence, 1995, 17(7):
641~651.
[5] H. Liu, F. Hussain, . Tan, M. Dash. Discretization: an enabling technique[J]. Journal of Data Mining and
Knowledge Discovery, 2002, 6: 393~423.
[6] D. Chiu, A. Wong, and B. Cheung. Information Discovery through Hierarchical Maximum Entropy
Discretization and Synthesis[J]. Knowledge Discovery in Databases, 1991, G. Piatesky-Shapiro and .
Frowley, ed., MIT Press.
[7] U. Fayyad, K. Irani. Ent-Boost: Boosting using entropy measures for robust object detection[J]. PATTERN
RECOGNITION LETTERS, 2007, 7(9): 1083~1090.
[8] Simovici DA, Jaroszewicz S. An axiomatization of partition entropy[J]. IEEE Trans Inf Theory, 2002, 48(7):
2138~2142.
[9] A. Kumar, D. Zhang. Hand-geometry recognition using entropy-based discretization[J]. IEEE Transactions on
Information Forensics and Security, 2007, 2: 181~187.
[10] Wenyu Qu, Eqian Yan, Yu Sang. A novel Chi2 algorithm for discretization of continuous attributes. Progress
in WWW Research and Asia-Pacific Web Conference, 2008, 560~571.
[11] M. Boulle. Khiops: A Statistical Discretization Method of Continuous Attributes[J]. Machine Learning, 2004,
55: 53~59.
[12] . Su, . Hsu. An extended chi2 algorithm for discretization of real value attributes[J]. IEEE Transactions
on Knowledge and Data Engineering, 2005, 17: 437~441.
[13] . Quinlan. : Programs for Machine Learning[M]. San Mateo, Calif.: Morgan Kaufmann, 1993.
[14] L. Kurgan, . Cios. CAIM discretization algorithm[J]. IEEE Transactions on Knowledge and Data
Engineering, 2004, 16: 145~153.
[15] Mauro Birattari, Paola Pellegrini, Marco Dorigo. On the Invariance of Ant Colony Optimization[J]. IEEE
Transaction on Evolutionary Computation, 2007, 11(6): 732~743.
- 11 -
中国科技论文在线
基于信息距离与蚁群优化的离散化算法
贾立新，诸文智
（西安交通大学电气工程学院，西安 710049）
摘要：离散化算法是数据挖掘中十分重要的部分。由于现有的离散化方法无法准确地反映工
业数据库中类-属性间的关联性，本文基于信息距离准则和蚁群优化算法，提出一种新的离
散化方法。本文在分析两离散属性间关联性的信息量度的基础上，提出一种改进的信息距离
准则，用于对离散化模式的类-属性间关联度的评估。该方法应用蚁群优化算法来进行最优
离散化模式的选取，并根据问题描述构建了对应的信息素矩阵和启发式信息值。所提算法通
过真实工业数据库进行的仿真实验，结果表明该算法有效可靠。
关键词：模式识别与智能系统；离散化；数据挖掘；熵；蚁群优化
中图分类号：TP391
