An Association Based Approach to Discovering
Ordering Rules
Dazhong Liu
School of Mathematics and Computer Science,
Baoding, Hebei University , P. R. China 071002
Abstract:
The work presented in this paper focuses on discovering ordering rules between
ordinal attributes. Generally speaking, rough set theory is the foundation of
many algorithms of mining ordering rules. We provide a new approach using
algorithm of mining association rules to solve this problem. The key to the
problem is to transform information tables into transaction database. The
comparison results demonstrate that the ordering rules mined by our method are
comprehensive and more interesting.
Keywords: Association rules, Data mining, Ordinal rules, Ordinal information
table
基于关联规则挖掘的序规则发现
摘要：论文研究了有序数据中序规则的发现。已有的算法主要基于粗集理
论挖掘序规则，我们提出了基于关联规则的挖掘方法。方法的关键是将信息
表转化为事务数据库。分析结果表明这一方法发现的规则更全面和有趣。
关键词：关联规则，数据挖掘，序规则，有序信息表
1 Introduction
Automated acquisition of knowledge is most important in Artificial Intelligence. If-then rules are
well-known techniques for representation of knowledge.
Traditionally, classification methods of machine learning or data mining are always used for
knowledge discovering. They commonly deal with attributes without considering ordinal
information. However, we may come across many practical applications such as ranking of
consumer products, ranking of universities and multi-criteria decision problem, etc. [1,8], which
1
have ordinal attributes. To make use of the potential ordinal nature, there are several literatures
have theoretically discussed the problem based on the rough sets theory introduced by Pawlak
[4].Iwinski [2, 3] introduced ordinal information system which concerns with the way for
representation and reduct of weak orders, Grecob et al. [8] studied decision rules generation in
the context of multicriteria decision making based on pairwise comparison table. Lee et al. [7],
proved that any weak order is equivalent to a family of nested sets correspond to the equivalence
classes in the classic rough set theory. In Sai et al. [1], the authors put forward a data analysis
model used to mine ordering rules.
Zhong et al. [9] gave the practical method of using ordinal information. All above studies
concern about the process of information table reducts and rule generation.
Sai et al. [1] are interested in finding the qualitative ordering rules described as “if the value of an
object x on an attribute a is ordered ahead of the value of another object y on the same attribute,
then x is ordered ahead of y”. In this paper, we focus on discovering the extension ordering rules ,
that is “if the value of an object x on an attribute a is ordered ahead of the value of another object
y on the same attribute, then x is ordered ahead of y on a certain attribute ". We adopt association
rule method [5, 10] different from rough set theory to find comprehensive ordering rules.
2 Finding Ordering Rules
2 .1 Ordered Informat ion Tables Overv iew
The ordered information table, IT= (T, R) is introduced by Sai et al. [1]. The table consists of two
elements. One is the standard information table T=(U,A,V,f), the other is a set of ordinal relation
on each attribute ,R={ >a,a∈A}. The standard information table formally represented as 4-tuple,
T= (U, A, V, f). Where U is a the universe of discourse with finite nonempty d objects,
U={x1,x2,…,xd}, A is a set of n attributes A= {a1, a2,…,an}, f is a set of functions, fa:U→Va ,a
∈A, where Va is a set of values for an attribute a and Va∈V. For every attribute a∈A, there is
a liner order >a on Va ,thus, it induces a weak order on U.
2 .2 Assoc ia t ion Rule Discovery Overv iew
Discovery of association rules is introduced by Agrawal et al [5, 6].The following is a formal
statement of the problem [5]: Let I = {i1, i2... im} be a set of items. Let D be a database of
transactions, each transaction T is a set of items, and each transaction have a unique identifier, viz.
TID. An association rule is an implication of the expression A ⇒ B, where itemsets A,B ⊂ I,
and A ∩ B = Φ. The confidence of rule A ⇒ B means support (A∪ B)/support (A). The
support (A) =x% means x% of transactions in D contain A.
Considering a set of transactions D, discovered association rules must satisfy the constrain that
their support and confidence greater than the user-specified minimum support and minimum
confidence respectively. It should be pointed out that association rules are only reflections of
relationships in a transaction database. The key association rules discovery algorithm is Apriori
2
[5], since its occurrence many enhanced algorithm have put forward [10]. Without losing
generality, we adopt Apriori [5].
2 .3 Process o f D iscover ing Order ing Rules
Given an ordinal information system, U is a finite nonempty set of objects, U={x1, x2, xd}, A is a
finite nonempty set of attributes, A= {a1, a2,an}, F is a set of order relation on each attribute,
F= .
},...,,{
21 naaa
>>>
The process of discovering ordering rules is as follows:
First of all ordered information tables (proposed in ) must be given.
Secondly, transform ordered information tables into transaction data tables. From ordered
information table, we compute each pare of object on a certain attribute.
Given ∀(xi,xj)∈UXU ,xi≠xj, for an given attribute ai∈A, if xi >{ai} xj then fai(xi, xj)= (ai,>)
else fai(xi, xj)= (ai,≤).So each object is translated into a transaction.
Thirdly, using Apriori to discover association rules from transaction data tables. The form of the
rule is (a1,p1),(a2,p2),…(am,pm) ⇒(ak,pk) (s,c) ,where aj (j=1,2,…m≤n)is one of attributes, pj
(j=1,2,…m≤n)and pk are “>” or “≤”, ak is different from aj (j=1,2,…m),s represents support
and c represents confidence in percentage.
Lastly, analyzing the discovery rules.
2 .4 An Example
An example is given to illustrate the process of rule discovery.
For purpose of comparison studies, we cite the table from [1] (some changed) in the following.
Table 1 ordered information table
a b c d o
p1 middle 3 months $200 heavy 1
p2 large 3 months $300 very heavy 3
p3 small 3 months $300 light 3
p4 small 3 months $250 very light 2
p5 small 2 months $200 very light 3
>a: small >a middle >a large,
>b: 3 months >b 2 months,
>c: $200 >c $250 >c $300,
>d: very light >d light >d heavy >d very heavy,
>o: 1 >o 2 >o 3.
3
According to the second step of above process, table 1 is transformed into transaction data table
showed in table 2
Table 2 ordered transaction dataset
object a b c d o
(1,2) (a,>) (b,≤) (c,>) (d,>) (o,>)
(1,3) (a,≤) (b,≤) (c,>) (d,≤) (o,>)
(1,4) (a,≤) (b,≤) (c,>) (d,≤) (o,>)
(1,5) (a,≤) (b,>) (c,≤) (d,≤) (o,>)
(2,1) (a,≤) (b,≤) (c,≤) (d,≤) (o,≤)
(2,3) (a,≤) (b,≤) (c,≤) (d,≤) (o,≤)
(2,4) (a,≤) (b,≤) (c,≤) (d,≤) (o,≤)
(2,5) (a,≤) (b,>) (c,≤) (d,≤) (o,≤)
(3,1) (a,>) (b,≤) (c,≤) (d,>) (o,≤)
(3,2) (a,>) (b,≤) (c,≤) (d,>) (o,≤)
(3,4) (a,≤) (b,≤) (c,≤) (d,≤) (o,≤)
(3,5) (a,≤) (b,>) (c,≤) (d,≤) (o,≤)
(4,1) (a,>) (b,≤) (c,≤) (d,>) (o,≤)
(4,2) (a,>) (b,≤) (c,>) (d,>) (o,>)
(4,3) (a,≤) (b,≤) (c,>) (d,>) (o,>)
(4,5) (a,≤) (b,>) (c,≤) (d,≤) (o,>)
(5,1) (a,>) (b,≤) (c,≤) (d,>) (o,≤)
(5,2) (a,>) (b,≤) (c,>) (d,>) (o,≤)
(5,3) (a,≤) (b,≤) (c,>) (d,>) (o,≤)
(5,4) (a,≤) (b,≤) (c,>) (d,≤) (o,≤)
Using Apriori algorithm, we find many more association rules. We chose some interesting rules
listed below:
R1’ (c,≤), (b,≤)⇒(o,≤) (%, %)
R2’ (c,>) ⇒ (o,>) (%, %)
R3’ (b,>) ⇒ (o,>) (%, %)
(a,>) ⇒(o,≤) (%, %)
(d,>) ⇒(o,≤ ) (%, %)
(d,>) ⇒(b,≤) (%, %)
(d,≤)⇒(a,≤ ) (%, %)
(a,≤)⇒(d,≤ ) (%, %)
4
(d,≤)⇒(o,≤ ) (%, %)
(c,≤)⇒(o,≤) (%, %)
(a,≤)⇒(o,≤ ) (%, %)
(o,≤)⇒(a,≤ ) (%, %)
(o,≤)⇒(b,≤ ) (%, %)
(b,≤)⇒(o,≤) (%, %)
(d,≤) ,(c,≤)⇒(a,≤) (%, %)
(c,≤), (a,≤)⇒(d,≤) (%, %)
(d,≤) ,(c,≤)⇒(o,≤) (%, %)
(d,≤) ,(a,≤)⇒(o,≤ ) (%, %)
(d,≤), (o,≤)⇒(a,≤) (%, %)
(d,≤), (b,≤)⇒(a,≤ ) (%, %)
(c,≤) ,(a,≤)⇒(o,≤ ) (%, %)
(c,≤) ,(o,≤)⇒(b,≤ ) (%, %)
(o,≤ ),(b,≤)⇒(c,≤) (%, %)
The first three discovered rules R1’,R2’and R3’ correspond to R1, R2 and R3 in [1] respectively.
The confidence is just the accuracy defined by [1].
2 .5 Discuss ion
Comparing with the constructed binary pare wise table in [1], the table in our method can be
regard as a multi-value table with ordering semantic meaning. It is convenient to mining using
association rule algorithm. From above example, we can see that the discovered ordinal
association rules are comprehensive and more interesting, although the rules are not truly
implicating rules. For example the two rules (d,≤)⇒(a,≤ ) (%, %) and (b,≤)⇒(o,
≤) (%, %) have higher support and confidence, reflecting close relationship between
attributes. Rule (b,≤)⇒(o,≤) (%, %) is more convictive then (b,>) ⇒ (o,>) (%,
%) with (accuracy= coverage=[1]) . Sometimes conflict will occur in the discovered
rules, this need giving higher support and confidence and other analysis. Due to the nature of
Apriori, it can not lose the knowledge contained in the transaction datasets. Therefore, the
discovered rules using method [1] must be a part of rules mined by the proposed method so long
as given smaller support and confidence.
5
3 Conclusions
We have demonstrated in this paper the new approach to mining ordering rules from ordinal
information system. The last mining steps are different from the framework of rough set method.
The result shows that more interesting ordinal rules can be found. It gives another method to
discover qualitative ordering rules. In the future, practical application and combination with other
data mining and machine learning methods will be discussed.
References
[1]Y. Sai, Y. Y. Yao, and N. Zhong, “Data analysis and mining in ordered information tables”, Proc. of the
IEEE Int'l Conf. on Data Mining 2001, pp. 497-504, 2001.
[2] . Iwinski, "Ordinal Information Systems, I", Bulletin of the Polish Academy of Sciences,
Mathematics, Vol. 36, -8, pp. 467-475, 1988.
[3]. Iwinski, "Ordinal Information Systems, II", Bulletin of the Polish Academy of Sciences, Technical
Sciences, ,No. 1,pp. 157-170, 1991
[4]Z. Pawlak, “Rough Sets”, International Journal of Information & Computer Sciences, Vol. 11, pp.
341-356, 1982.
[5] Agrawal R, Imielinski T, Swami A (1993) Mining associations between sets of items in massive
databases. In Buneman P, Jajodia S (eds). Proceedings of the ACM SIGMOD international conference
on management of data, Washington DC, May 1993, pp 207-216
[6] Agrawal R, Srikant R (1994) Fast algorithms for mining association rules. In: Proceedings of the 20th
international conference on very large databases (VLDB’94), Santiago, Chile, pp 487–499
[7]. Lee, . Yeung and . Tsang, "Ordinal Fuzzy Sets", IEEE Transactions on Fuzzy Systems,
Vol. 10, No. 6,pp. .
[8]S. Greco, B. Matarazzo and R. Slowinski, “Rough sets theory for multicriteria decision analysis”,
European Journal of Operational Research, Vol. 129 (2001), pp. 1-47, 2001.
[9], J. Dong 1, . Yao, S. Ohsuga,“Gastric cancer data mining with ordered information”，
Third International Conference, RSCTC 2002, Malvern, PA, USA, October 14-16, 2002. Proceedings, L
N C S , Volume 2475, pp. 467 - 478
[10] Christian Borgelt and Rudolf Kruse ,”Induction of Association Rules: Apriori Implementation”,15th
Conference on Computational Statistics (Compstat 2002, Berlin, Germany)Physica Verlag, Heidelberg,
Germany 2002
[11] Pawlak, Z. Information systems: theoretical foundations, Information Systems, 6, 205-218,1981.
[12] Pawlak, Z. Rough Sets, Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers,
Dordrecht, 1991.
6
1 Introduction
2 Finding Ordering Rules
Ordered Information Tables Overview
Association Rule Discovery Overview
Process of Discovering Ordering Rules
An Example
Discussion
3 Conclusions
References
