Transcript PPT
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Discovering the constraintbased association rules in an
archive for unique Bulgarian
bells
Tihomir Trifonov, Tsvetanka Georgieva
Department of Mathematics and Informatics,
University of Veliko Tarnovo “St. Cyril and St. Methodius”,
Bulgaria
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
This paper presents an application that discovers the
constraint-based association rules.
It allows the association analysis of the different
characteristics of the bells.
Detailed information about the examined bells is
maintained in an audio and video archive of unique
Bulgarian bells.
The application is realized with Java and SQL and
provides the possibility for finding the association rules of
the data obtained after applying the methods of digital
processing of signals for analysis of bell sounds.
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006
2
Eleventh
Tenth International
International
Conference
Conference
onon
System
System
Analysis
Analysis
and
and
Information
Information
Technologies,
Technologies,
Kyiv,
Kyiv,
Ukraine,
Ukraine,
2008
2009
Discovering the association rules is a data mining task
[3, 7] in which the goal is to find interesting relationships
between the attributes of the analyzed data.
Once found, the association rules can be used for
supporting decision making in different areas.
In numerous cases the algorithms generate a large
number of association rules, often thousands or even
millions.
It is almost impossible for the end users to encompass or
validate such a large number of association rules,
limiting the results of the data mining is therefore helpful.
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006 3
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Association Rules
Let I = {I1, I2, … , In} be a set of n different values of attributes. Let
R be a relation, where each tuple t has a unique identifier and
contains a set of items, such that t I. An association rule is an
implication of the form X → Y, where X, Y I are sets of items with
XY = . The set X is called an antecedent, and Y –a consequent.
There are two parameters associated with a rule:
the support of the association rule X → Y is the proportion (in
percentages) of the number of the tuples in R, which contain X Y to
the total number of the tuples in the relation;
the confidence of the association rule X → Y is the proportion (in
percentages) of the number of the tuples in R, which contain X Y to
the number of the tuples, which contain X.
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006 4
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Association Rules
The task of association rules mining is to generate all
association rules which have values of the parameters
support and confidence, exceeding the previously given
respectively minimal support min_supp and minimal
confidence min_conf.
Therefore the discovery of the association rule requires
finding the sets of items, which have a support, more than the
previously defined minimal threshold min_supp. These sets
are called frequent itemsets.
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006 5
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Constraint-based Association Rules
To increase the efficiency of existing algorithms for data
mining, during the mining process constraints are applied
with the goal for these association rules, of which only
those interesting to the user are generated, instead of all
association rules.
The constraint-based association rule mining aims to
find all rules from given dataset, which satisfy the
constraints required from the users.
For discovering only the rules corresponding to the
specific patterns, in [4] the meta-rules are applied. The
format of the interesting rules is defined by using a
template, the algorithm generates only these rules, which
correspond to this template.
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006 6
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Constraint-based Association Rules
A meta-rule [4] is a rule template from the following type
P1 P2 … Pm → Q1 Q2 … Ql
where Pi (i = 1, …, m) and Qj (j = 1, …, l) are instantiated
predicates or predicate variables, p = m + l is the number
of the predicates in the rule.
This paper presents an application, which allows the user
to set constraints for searched rules and finds constraintbased association rules.
The application is used for performing the association
analysis on the different characteristics of the bells, the
information for which is kept in an archive produced for
the goal.
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006 7
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Discovering the constraint-based association
rules in an archive for unique Bulgarian bells
Detailed data about the analysis of bells is stored in an
audio and video archive of the unique Bulgarian bells
[10]. The data of the archive is accessible from
http://www.math.bas.bg/bells/belleng.html
For each bell, information is maintained for its unique
identifier, location, type, geometrical dimensions, weight,
material, condition, creator, year or period of creation,
description, estimation of its historical value, digital
photos, sound and video files, spectrograms.
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006 8
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Discovering the constraint-based association
rules in an archive for unique Bulgarian bells
A program is realized with MatLab [11] for analysis of the
sounds of the bells by using various methods for digital
signal processing (DSP) – spectral analysis by means of
the Discrete Fourier Transform (DFT), digital filter, wavelet
analysis.
The partials of the sounds of the bells are found by
applying the digital filter.
The information about the previously calculated partials of
the sounds of the different bells is stored in the archive.
The represented application discovers the constraintbased association rules in an archive for unique Bulgarian
bells. It is realized by using the languages Java and SQL.
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006 9
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Discovering the constraint-based association
rules in an archive for unique Bulgarian bells
To the user that starts the application, the following
possibilities, are provided:
Setting the attributes, being subject to analysis;
Setting the minimal value of the support min_supp and
the minimal value of the confidence min_conf;
Setting the conditions (Boolean expression) for the
values of the attributes, which can participate or not in
the antecedent and the consequence of the searched
rules.
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006
10
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Choosing the attributes; defining the minimal support, the minimal confidence, the conditions for
the values of the attributes; outputting the found rules
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006
13
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Discovering the constraint-based association
rules in an archive for unique Bulgarian bells
The figure shows an example result from the execution of the
realized program with given values of the minimal support,
minimal confidence and conditions for the values of the
attributes. For instance, let the following rule be generated from
the archive for unique Bulgarian bells:
SecondParial(“600 Hz”) → FirstPartial(“320 Hz”)
with values of the support s = 0.025 and the confidence c = 0.5.
This rule means, that for monastery bells with second partial 600
Hz one of the most frequent values of the first partial is 320 Hz
(with 50.00% confidence) and the monastery bells with value
600 Hz of their second partial represent 2.5% from all bells,
included in the study.
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006
14
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Discovering the constraint-based association
rules in an archive for unique Bulgarian bells
When representing the association rules in a tabular view all
found rules are exposed in a table, where each row matches to a
rule and provides information for the support and the confidence
of this rule.
All rules can be showed in different orders – according to the
values of the attributes, participating in the antecedents and the
consequents of the discovered rules; according to the values of
the parameters support and confidence in ascending or
descending order.
In this manner the user has a more clear and complete view of
the rules and can more easily locate a special rule. The tabular
view facilitates adopting a large number of rules.
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006
15
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Monastery “St. Transfiguration” near the town of Veliko Tarnovo
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006
16
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Church “St. Nikolay” in Veliko Tarnovo, View close to the bell
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006
17
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
The connection between BellDB and MatLab provides possibility for analyzing the
sounds of the bells and to search a concrete bell by a sample of its sound.
Real sound of the given bell and its 3D spectrogram, computed in MatLab
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006
18
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Data acquisition of the experimental data (PULSE 11, B&K)
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006
19
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
R. Agrawal, T. Imielinski, A. Swami, Mining Association Rules between Sets of Items in Large Databases, In Proc. of
the ACM SIGMOD International Conference on Management of Data,1993.
R. Agrawal, R. Srikant, Fast Algorithms for Mining Association Rules, Proc. of the Int. Conf. on Very Large
Databases, 1994.
A. A. Barsegyan, M. S. Kupriyanov, V. V. Stepanenko, I. I. Holod, Technologies for data analysis: Data Mining, Visual
Mining, Text Mining, OLAP, BHV-Peterburg, 2008 (in Russian).
Y. Fu and J. Han, Meta-rule-guided mining of association rules in relational databases, In Proc. of the Int. Workshop
on Integration of Knowledge Discovery with Deductive and Object-Oriented Databases, 1995.
T. Georgieva, Discovering Branching and Fractional Dependencies in Databases, Data and Knowledge Engineering,
Elsevier, vol. 66, № 2, 2008.
M. Kamber, J. Han, J. Chiang, Using Data Cubes for Metarule-Guided Mining of Multi-Dimensional Association Rules,
Technical Report, CMPT–TR–97–10, School of Computing Sciences, Simon Fraser University, 1997.
M. Kantardzic, Data Mining: Concepts, Models, Methods, and Algorithms, John Wiley & Sons, 2003.
S. Kotsiantis and D. Kanellopoulos, Association Rules Mining: A Recent Overview, GESTS International Transactions
on Computer Science and Engineering, Vol.32 (1), 2006.
R. Ng, L. Lakshmanan, J. Han, A. Pang, Exploratory Mining and Pruning Optimizations of Constrained Association
Rules, In Proceedings of the ACM SIGMOD Conference on Management of Data, 1998.
T. Trifonov ,T. Georgieva, Web based approach to managing audio and video archive for unique Bulgarian bells, In
Proc. of the Tenth Int. Conf. on science and technology "System Analysis and Information Technologies", Kiev, 2008.
T. Trifonov ,T. Georgieva, The bell chime – an acoustical, mathematical and technological challenge, In Proceedings
of the National Scientific Conference on Acoustics, Varna, 2008.
The Bell Project “Research and Identification of Valuable Bells of the Historic and Culture Heritage of Bulgaria and
Development of Audio and Video Archive with Advanced Technologies” Website,
http://www.math.bas.bg/bells/belleng.html
The work was supported partially by the Bulgarian National Science Fund under Grant KIN-1009/2006
20
Eleventh International Conference on System Analysis and Information Technologies, Kyiv, Ukraine, 2009
Благодаря за
вниманието!
Thank you for
your attention!
Спасибо за
внимание!
The work was supported partially by the
Bulgarian National Science Fund under Grant
KIN-1009/2006
21