Automatic Item Weight Generation for Pattern Mining and its Application

Automatic Item Weight Generation for Pattern Mining and its Application

Yun Sing Koh (The University of Auckland, New Zealand), Russel Pears (Auckland University of Technology, New Zealand) and Gillian Dobbie (The University of Auckland, New Zealand)
Copyright: © 2011 |Pages: 20
DOI: 10.4018/jdwm.2011070102
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Association rule mining discovers relationships among items in a transactional database. Most approaches assume that all items within a dataset have a uniform distribution with respect to support. However, this is not always the case, and weighted association rule mining (WARM) was introduced to provide importance to individual items. Previous approaches to the weighted association rule mining problem require users to assign weights to items. In certain cases, it is difficult to provide weights to all items within a dataset. In this paper, the authors propose a method that is based on a novel Valency model that automatically infers item weights based on interactions between items. The authors experiment shows that the weighting scheme results in rules that better capture the natural variation that occurs in a dataset when compared with a miner that does not employ a weighting scheme. The authors applied the model in a real world application to mine text from a given collection of documents. The use of item weighting enabled the authors to attach more importance to terms that are distinctive. The results demonstrate that keyword discrimination via item weighting leads to informative rules.
Article Preview

1. Introduction

Association rule mining (Agrawal et al., 1993) aims to extract interesting correlations, frequent patterns, associations or casual structures among sets of items in transactional databases. The relationships are not based on the inherent properties of the data themselves but rather based on the co-occurrence of the items within the database. There has been much work carried out in this area (Ashrafi et al., 2004; Daly & Taniar, 2004; Cokrowijoyo & Taniar, 2005; Koh et al., 2006; Ashrafi et al., 2007; Tzanis & Berberidis, 2007;Taniar et al., 2008; Giannikopouloset al., 2010). The original motivation for seeking association rules came from the need to analyze supermarket transactional data also known as market basket analysis. An example of a common association rule is bread → butter. This indicates that a customer buying bread would also buy butter. Association rules have been widely used in a wide variety of domains, however, traditional rule mining techniques are vulnerable to the “rule explosion problem”. Even modest sized datasets can produce thousands of rules, and as datasets get larger, the number of rules produced becomes unmanageable. This highlights a key problem in association rule mining; keeping the number of generated itemsets and rules in check, whilst identifying interesting rules amongst the plethora generated.

In the classical model of association rule mining, all items are treated with equal importance. In reality, most datasets are skewed with imbalanced data. By applying the classical model to these datasets, important but critical rules which occur infrequently may be missed. For example consider the rule: stiff neck, fever, aversion to light → meningitis. Meningitis occurs relatively infrequently in a medical dataset, however if it is not detected early the consequences can quickly become fatal. Recent research (Cai et al., 1998; Sun & Bai, 2008; Wang et al., 2000; Yan & Li, 2006) has used item weighting to emphasize such rules that rarely manifest but are nonetheless very important. For example, items in a market basket dataset may be weighted based on the profit they generate. However, most datasets do not come with preassigned weights and so the weights must be manually assigned, which is time consuming and maybe error-prone. Research in the area of weighted association rule mining has concentrated on formulating efficient algorithms for exploiting pre-assigned weights rather than deducing item weights from a given transactional database. We believe that it is possible to deduce the relative importance of items based on their interactions with each other. In application domains where expert’s input on item weights is either unavailable or impractical, an automated approach to assigning weights to items can contribute significantly to distinguishing high value rules from those with low value.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing