Full text
| |
| Author(s): |
Renan de Padua
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | São Carlos. |
| Institution: | Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) |
| Defense date: | 2015-02-27 |
| Examining board members: |
Solange Oliveira Rezende;
Gustavo Enrique de Almeida Prado Alves Batista;
Alípio Mário Guedes Jorge;
Ronaldo Cristiano Prati
|
| Advisor: | Solange Oliveira Rezende |
| Abstract | |
One of the existing data mining techniques is association rules, responsible for identifying relationships that occur in the data set. Although the association rule is one of the most widely used techniques, the amount of extracted patterns can overload the user in such a way that finding interesting patterns among the large amount of obtained patterns becomes a challenge. To solve this problem, a large part of the association-related work is focused on the post-processing step. These works generally propose a post-processing approaches that, according to a certain strategy, aims facilitating the search for interesting patterns. Nowadays, approaches have included the user knowledge in the domain and / or interests on the process. However, in the current existing approaches, the user knowledge and/or interest must be explicitly described by some formalism, requiring a considerable time and may even lead to incomplete and / or incorrect specifications. In addition, the user has no idea what probably is interesting or which patterns to begin the searching. Notice that one of the challenges of these approaches is to consider the knowledge and / or user interest. In addition, consider the number of rules the user will examine is necessary. The analysis of the rules by an expert is expensive and, in most cases, the user wants to explore the rules generated without limiting exploration to the knowledge he already has. Therefore, the user evaluate the fewest amount of rules possible is important and, based on this assessment, the post-processing approaches be able to assist in the search for the rules that he may consider interesting. So, in this work is proposed that the post-processing is treated as a transductive semi supervised classification problem, since it allows the user to label some rules based on two predefined classes (e.g. \"interesting\"or \"not interesting\"), in a way that just a small amount of the rule set needs to be explored and all other association rules are automatically labeled. Furthermore, you can implicitly capture the knowledge and / or user interest in the domain by labeling some rules. Thus, the rules need to be modeled to allow: (a) select the rules to be labeled by the user to implicitly capture their knowledge and / or interest; (b) propagate the rules\' labels classified by the user to all not labeled rules. To do so, the rules were modeled via networks in this work, due to: (i) a large amount of network measures can be used in conjunction with the information provided by the user, to make item (a) possible; (ii) label propagation algorithms can be used in order to make item (b) possible. Therefore, we highlight that the contributions of this work are the ability to extract knowledge and / or user interest according to database characteristics and direct the user exploration without previously defining what will be explored. In addition, the results demonstrate that the proposed approach is able to direct the user to the knowledge considered interesting, reducing the amount of rules to be explored. Finally, this work also contributes to demonstrate that treat the post-processing of association rules as a problem of propagation of labels is possible. (AU) | |
| FAPESP's process: | 13/12392-0 - Post-Processing Association Rules using networks and label propagation |
| Grantee: | Renan de Padua |
| Support Opportunities: | Scholarships in Brazil - Master |