Search

In the recent years, the number of scientific publications has increased substantially. A way to measure the impact of a publication is to count the number of citations to the paper. Thus, citations are being used as a proxy for a researcher’s contribution and influence in a field. Citation classification can provide context to the citations. To perform citation classification, supervised techniques are normally used. To the best of our knowledge there are no research that performs this task in a unsupervised manner. In this paper we present two techniques to cluster citations automatically without human intervention. This paper presents two novel techniques to cluster citations according to their contents (semantic) and the citation sentence styles (syntactic). The techniques are validated using external test sets from existing supervised citation classification studies.

Discovering association rules efficiently is an important data mining problem. We define sporadic rules as those with low support but high confidence; for example, a rare association of two symptoms indicating a rare disease. To find such rules using the well-known Apriori algorithm, minimum support has to be set very low, producing a large number of trivial frequent itemsets. To alleviate this problem, we propose a new method of discovering sporadic rules without having to produce all other rules above the minimum support threshold. The new method, called Apriori-Inverse, is a variation of the Apriori algorithm that uses the notion of maximum support instead of minimum support to generate candidate itemsets. Candidate itemsets of interest to us fall below a maximum support value but above a minimum absolute support value. Rules above maximum support are considered frequent rules, which are of no interest to us, whereas rules that occur by chance fall below the minimum absolute support value. We define two classes of sporadic rule: perfectly sporadic rules (those that consist only of items falling below maximum support) and imperfectly sporadic rules (those that may contain items over the maximum support threshold). This article is an expanded version of Koh and Rountree (2005).

Current drift detection techniques detect a change in distribution within a stream. However, there are no current techniques that analyze the change in the rate of these detected changes. We coin the term stream volatility, to describe the rate of changes in a stream. A stream has a high volatility if changes are detected frequently and has a low volatility if changes are detected infrequently. We are particularly interested in a volatility shift which is a change in the rate of change (e.g. From high volatility to low volatility). We introduce and define the concept of stream volatility, and propose a novel technique to detect volatility on data streams in the presence of concept drifts. In the experiments we show our algorithm to be both fast and efficient. We also propose a new algorithm for drift detection called SEED that is faster and more memory efficient than the existing state-of-the-art drift detection approach. A faster drift detection algorithm has a flow-on benefit to the subsequent volatility detection stage because both algorithms run concurrently on the data stream.

Recommender systems using Collaborative Filtering techniques are capable of make personalized predictions. However, these systems are highly vulnerable to profile injection attacks. Group attacks are attacks that target a group of items instead of one, and there are common attributes among these items. Such profiles will have a good probability of being similar to a large number of user profiles, making them hard to detect. We propose a novel technique for identifying group attack profiles which uses an improved metric based on Degree of Similarity with Top Neighbors (DegSim) and Rating Deviation from Mean Agreement (RDMA). We also extend our work with a detailed analysis of target item rating patterns. Experiments show that the combined methods can improve detection rates in user-based recommender systems.

Recommender systems are highly vulnerable to attacks. Attackers who introduce biased ratings in order to affect recommendations, have been shown to be effective against collaborative filtering algorithms. In this paper, we study the use of statistical metrics to detect rating patterns of attackers. Two metrics, Rating Deviation from Mean Agreement (RDMA) and Degree of Similarity with Top Neighbors (DegSim), are used for analysing rating patterns between malicious profiles and genuine profiles in shilling attacks. Building upon this, we propose and evaluate an algorithm for detecting shilling attacks in recommender systems using a statistical approach. We look at two attack models: random attack and average attack. The experimental results show that our detection technique based on target item analysis is an effective approach in detecting shilling attacks for both the random and average attack model.

Knowledge Discovery and Data (KDD) mining helps uncover hidden knowledge in huge amounts of data. However, recently, different researchers have questioned the capability of traditional KDD techniques to tackle the information extraction problem in an efficient way while achieving accurate results when the amount of data grows. One of the ways to overcome this problem is to treat data mining as an optimization problem. Recently, a huge increase in the use of Swarm Intelligence (SI)-based optimization techniques for KDD has been observed due to the flexibility, simplicity, and extendibility of these techniques to be used for different data mining tasks. In this chapter, the authors overview the use of Particle Swarm Optimization (PSO), one of the most cited SI-based techniques in three different application areas of KDD, data clustering, outlier detection, and recommender systems. The chapter shows that there is a tremendous potential in these techniques to revolutionize the process of extracting knowledge from big data using these techniques.

Current approaches to drift detection assume that stable memory consumption with slight variations with each stream is suitable for all programs. This is not always the case and there are situations where small variations in memory are undesirable such as drift detectors on medical vital sign monitoring systems. Under these circumstances, it is not sufficient to have a memory use that is predictable on average, but instead memory use must be fixed. To detect drift using fixed memory in a stream, we propose DualWin: a technique that keeps two samples of controllable size, one is stored in a sliding window, which represents the most recent stream elements, and the other is stored in a reservoir, which uses reservoir sampling to maintain an image of the stream since the previous drift was detected. Through experimentation, we find that DualWin obtains a rate of true positive detection which is comparable to ADWIN2, a rate of false positive detection which is much lower, an execution time which is faster, and a fixed memory consumption.

Social networks play an important role in everyday life. Nowadays there is various research that concentrates on detecting communities within these networks. Traditionally most of the community detection algorithms focus on detecting disjoint networks. However there is a need for overlapping community detection. In recent years there have been some attempts at detecting overlapping communities. Most of these techniques concentrate on just detecting these communities, none of this research tries to detect the maximal set of these communities which gives more stability. In this paper we propose a new method called Maximal-DSHRINK that allows us to detect the maximal set of overlapping communities within a social network. We show that the maximal set provides us with better quality in terms of modularity gain.

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.

Most association rule mining techniques concentrate on finding frequent rules. However, rare association rules are in some cases more interesting than frequent association rules since rare rules represent unexpected or unknown associations. All current algorithms for rare association rule mining use an Apriori level-wise approach which has computationally expensive candidate generation and pruning steps. We propose RP-Tree, a method for mining a subset of rare association rules using a tree structure, and an information gain component that helps to identify the more interesting association rules. Empirical evaluation using a range of real world datasets shows that RP-Tree itemset and rule generation is more time efficient than modified versions of FP-Growth and ARIMA, and discovers 92-100% of all the interesting rare association rules. Additional evaluation using synthetic datasets also shows that RP-Tree is more efficient, in addtion to showing how the execution time of RP-Tree changes with transaction length and rare-item itemset size.

Since the introduction of FP-growth using FP-tree there has been a lot of research into extending its usage to data stream or incremental mining. Most incremental mining adapts the Apriori algorithm. However, we believe that using a tree based approach would increase performance as compared to the candidate generation and testing mechanism used in Apriori. Despite this, FP-tree still requires two scans through a dataset. In this paper we present a novel tree structure called Single Pass Ordered Tree, SPO-Tree, that captures information with a single scan for incremental mining. All items in a transaction are inserted/sorted based on their frequency. The tree is reorganized dynamically when necessary. SPO-Tree allows for easy maintenance in an incremental or data stream environment.

Citation classification is the task of assigning a category to a reference or citation. The current sets of categories or classes proposed in the literature vary in size and they are based on the analysis of a small sample of citation sentences. We are developing a process to automatically generate such categories and base them on the analysis of a large corpus of papers. Part of the generation process involves selecting the main verb relevant to the reference being cited in the sentence. In this paper we present our recently developed technique that automatically identifies the relevant verb in a citation sentence. The technique uses heuristic rules, which are dependent on the results of a semantic role labeler. Four test sets were collected, and the common annotations of the test sets annotated by three people were used to assess the accuracy of the rules. Through experimentation we show that the average accuracy achieved using our technique that automatically extracts verbs from citation sentences across the four test sets is reasonable at 75%.

The rate of change of drift in a data stream can be of interest. It could show, for example, that a strand of bacteria is becoming more resistant to a drug, or that a machine is becoming unreliable and requires maintenance. While concept drift in data streams has been widely studied, no one has studied the rate of change in concept drift. In this paper we define three new drift types: relative abrupt drift, relative moderate drift and relative gradual drift. We propose a novel algorithm that tracks changes in drift intensity relative to previous drift points within the stream. The algorithm is based on mapping drift patterns to a Gaussian function. Our experimental results show that the algorithm is robust and achieving accuracy levels above 90%.

Due to a marked increase in the number of web users and their activities, many application areas that use patterns generated from their activities has been proposed. Web-based implicit recommender systems are one such application. An implicit recommender system is a tool that helps guide a user to a particular web resource based on implicit data. Implicit data comes from the web users activities without their active participation. Building such a system is a complex process due to two reasons, there is a huge amount of data and the quality of the data is poor. In this research, we tackle the first problem of generating patterns efficiently for recommender system by proposing Hierarchical Particle Swarm Optimization based clustering (HPSO-clustering). HPSO-clustering is a clustering approach based on Particle Swarm Optimization which combines both the properties of hierarchical and partitional clustering. We grouped the users' session into different clusters. Recommendations for an active user are generated from these clusters. In this paper we report the results of accuracy of recommendations. We achieved an overall 60% to 65% of precision for an active user, while in some clusters the precision achieved was 100% when top 5 ranked recommendations were selected.

There has been some research in the area of rare pattern mining where the researchers try to capture patterns involving events that are unusual in a dataset. These patterns are considered more useful than frequent patterns in some domain, including detection of computer attacks, or fraudulent credit transactions. Until now, most of the research in this area concentrates only on finding rare rules in a static dataset. There is a proliferation of applications which generate data streams, such as network logs and banking transactions. Applying techniques for static datasets is not practical for data streams. In this paper we propose a novel approach called Streaming Rare Pattern Tree (SRP-Tree), which finds rare rules in a data stream environment using a sliding window, and show that it is faster than current approaches.

To combat online auction fraud, researchers have developed fraud detection and prevention methods. However, it is difficult to effectively evaluate these methods using commercial or synthetic auction data. For commercial data, it is not possible to accurately identify cases of fraud. For synthetic auction data, the conclusions drawn may not extend to the real world. The availability of realistic synthetic auction data, which models real auction data, will be invaluable for effective evaluation of fraud detection algorithms. We present an agent-based simulator that is capable of generating realistic English auction data. The agents and model are based on data collected from the TradeMe online auction site. We evaluate the generated data in two ways to show that it is similar to the TradeMe data. Evaluation of individual features show that correlation is greater than 0.9 for 8 of the 10 features, and evaluation using multiple features gives a median accuracy of 0.87.

Although frequent pattern mining techniques have been extensively studied, the extension of their application onto data streams has been challenging. Due to data streams being continuous and unbounded, an efficient algorithm that avoids multiple scans of data is needed. In this paper we propose Kernel-Tree (KerTree), a single pass tree structured technique that mines frequent patterns in a data stream based on forecasting the support of current items in the future state. Unlike previous techniques that build a tree based on the support of items in the previous block, KerTree performs an estimation of item support in the next block and builds the tree based on the estimation. By building the tree on an estimated future state, KerTree effectively reduces the need to restructure for every block and thus results in a better performance and mines the complete set of frequent patterns from the stream while maintaining a compact structure.

Since the introduction of FP-growth using FP-tree there has been a lot of research into extending its usage to data stream or incremental mining. Most incremental mining adapts the Apriori algorithm. However, we believe that using a tree based approach would increase performance as compared to the candidate generation and testing mechanism used in Apriori. Despite this FP-tree still requires two scans through a dataset. In this paper we present a novel tree structure called Single Pass Ordered Tree SPO-Tree that captures information with a single scan for incremental mining. All items in a transaction are inserted/sorted based on their frequency. The tree is reorganized dynamically when necessary. SPO-Tree allows for easy maintenance in an incremental or data stream environment.

Most association rule mining techniques concentrate on finding frequent rules. However, rare association rules are in some cases more interesting than frequent association rules since rare rules represent unexpected or unknown associations. All current algorithms for rare association rule mining use an Apriori level-wise approach which has computationally expensive candidate generation and pruning steps. We propose RP-Tree, a method for mining a subset of rare association rules using a tree structure, and an information gain component that helps to identify the more interesting association rules. Empirical evaluation using a range of real world datasets shows that RP-Tree itemset and rule generation is more time efficient than modified versions of FP-Growth and ARIMA, and discovers 92-100% of all the interesting rare association rules.

Association rule mining is an important data mining task that discovers relationships among items in a transaction database. Most approaches to association rule mining assume that all items within a dataset have a uniform distribution with respect to support. Therefore, weighted association rule mining (WARM) was introduced to provide a notion of importance to individual items. Previous approaches to the weighted association rule mining problem require users to assign weights to items. This is infeasible when millions of items are present in a dataset. In this paper we propose a method that is based on a novel Valency model that automatically infers item weights based on interactions between items. Our experimentation shows that the weighting scheme results in rules that better capture the natural variation that occurs in a dataset when compared to a miner that does not employ such a weighting scheme.

The notion of finding rare association rules is like finding precious gems in an open field; it is a daunting task but, if successful, it is very rewarding. Association rule mining systems, such as Apriori, generally employ an exhaustive search algorithm. While these algorithms are in theory capable of finding rare association rules, they become intractable if the minimum level of support is set low enough to find rare rules. Such algorithms are therefore inadequate for finding rare associations, and also suffer from the rare item problem. Research to solve this problem has become more prevalent in recent times. The main goal of rare association rule mining is to discover relationships among sets of items in a transactional database that occur infrequently. This chapter presents a survey on the current trends and approaches in the area of rare association rule mining.

Rare association rule mining has received a great deal of attention in the past few years. In this chapter, the authors propose a multi methodological approach to the problem of rare association rule mining that integrates three different strands of research in this area. Firstly, the authors make use of statistical techniques such as the Fisher test to determine whether itemsets co-occur by chance or not. Secondly, they use clustering as a pre-processing technique to improve the quality of the rare rules generated. Their third strategy is to weigh itemsets to ensure upward closure, thus checking unbounded growth of the rule base. Their results show that clustering isolates heterogeneous segments from each other, thus promoting the discovery of rules which would otherwise remain undiscovered. Likewise, the use of itemset weighting tends to improve rule quality by promoting the generation of rules with rarer itemsets that would otherwise not be possible with a simple weighting scheme that assigns an equal weight to all possible itemsets. The use of clustering enabled us to study in detail an important sub-class of rare rules, which we term absolute rare rules. Absolute rare rules are those are not just rare to the dataset as a whole but are also rare to the cluster from which they are derived.

Data Stream mining presents unique challenges compared to traditional mining on a random sample drawn from a stationary statistical distribution. Data from real-world data streams are subject to concept drift due to changes that take place continuously in the underlying data generation mechanism. Concept drift complicates the process of mining data as models that are learnt need to be updated continuously to reflect recent changes in the data while retaining relevant information that has been learnt from the past. In this paper, we describe a Concept Based Decision Tree (CBDT) learner and compare it with the CVDFT algorithm, which uses a sliding time window. Our experimental results show that CBDT outperforms CVFDT in terms of both classification accuracy and memory consumption.

Transaction clustering has received a great deal of attention in the past few years. Its functionality extends well beyond traditional clustering algorithms which basically perform a near-neighbourhood search for locating groups of similar instances. The basic concept underlying transaction clustering stems from the concept of large items as defined by association rule mining algorithms. Clusters formed on the basis of large items that are shared between instances offer an attractive alternative to association rule mining systems. Currently, none of the techniques proposed offer a good solution to scenarios where large items overlap across clusters. In this paper we overcome the aforementioned limitations by using cluster seeds that represent initial centroids. Seeds are generated from sets of transaction items that occur together above a certain threshold and such seeds may overlap in their itemsets across clusters.

Association rules are patterns that offer useful information on dependencies that exist between the sets of items. Current association rule mining techniques such as apriori often extract a very large number of rules. To make sense of these rules we need to order or group the rules in some fashion such that the useful patterns are highlighted. The study of this process involves the investigation of an “interestingness” in the rules. To date, various measures have been proposed but unfortunately, these measures present inconsistent information about the interestingness of a rule. In this chapter, we show that different metrics try to capture different dependencies among variables. Each measure has its own selection bias that justifies the rationale for preferring it compared to other measures. We present an experimental study of the behaviour of the interestingness measures such as lift, rule interest, Laplace, and information gain. Our experimental results verify that many of these measures are very similar in nature. From the findings, we introduce a classification of the current interestingness measures.

Discovering association rules efficiently is an important data mining problem. We define sporadic rules as those with low support but high confidence; for example, a rare association of two symptoms indicating a rare disease. To find such rules using the well-known Apriori algorithm, minimum support has to be set very low, producing a large number of trivial frequent itemsets. To alleviate this problem, we propose a new method of discovering sporadic rules without having to produce all other rules above the minimum support threshold. The new method, called Apriori-Inverse, is a variation of the Apriori algorithm that uses the notion of maximum support instead of minimum support to generate candidate itemsets. Candidate itemsets of interest to us fall below a maximum support value but above a minimum absolute support value. Rules above maximum support are considered frequent rules, which are of no interest to us, whereas rules that occur by chance fall below the minimum absolute support value. We define two classes of sporadic rule: perfectly sporadic rules (those that consist only of items falling below maximum support) and imperfectly sporadic rules (those that may contain items over the maximum support threshold). This article is an expanded version of Koh and Rountree (2005).

Typically association rule mining only considers positive frequent itemsets in rule generation, where rules involving only the presence of items are generated. In this paper we consider the complementary problem of negative association rule mining, which generates rules describing the absence of itemsets from transactions. We describe a new approach called MINR (Mining Interesting Negative Rules) to efficiently find all interesting negative association rules. Here we only consider the presence or absence of itemsets that are strongly associated. Our approach does not require a user defined support threshold, and is based on pruning items that occur together by coincidence. For every individual itemset we calculate two custom thresholds based on their support: the positive and negative chance thresholds. We compared our implementation against Pearson φ correlation.

Most previous research into association rule data mining has focused on finding frequent rules; rules with high support and high confidence. However detecting rare or sporadic association rules, which have low support and high confidence, is a worthwhile task as well, as they represent rare, but potentially interesting and important associations. Mining rare or sporadic rules is a difficult data mining problem, and most previous approaches use an Apriori [1] like method [2-9]. However in order for Apriori to find rare rules, minimum support must be set very low, which results in a large amount of redundant rules and a long runtime. We previously proposed the Apriori-Inverse [10] and MIISR [11] algorithms to find sporadic rules quickly and efficiently. This paper provides an insight into the qualitative results produced by our proposed algorithms. We explore a specific real-world case study in more detail to get a qualitative understanding, namely the Dermatology dataset, for the diagnosis of the Erythemato-Squamous diseases. We show that traditional unmodified Apriori is not well suited to this task, and that our proposed algorithms are capable of producing interesting sporadic rules without having any expert domain knowledge.

In our research, we consider transfer learning scenarios where a target learner does not have access to the source data, but instead to hypotheses or models induced from it. This is called the Hypothesis Transfer Learning (HTL) problem. Previous approaches concentrated on transferring source hypotheses as a whole. We introduce a novel method for selectively transferring elements from previous hypotheses learned with Support Vector Machines. The representation of an SVM hypothesis as a set of support vectors allows us to treat this information as privileged to aid learning during a new task. Given a possibly large number of source hypotheses, our approach selects the source support vectors that more closely resemble the target data, and transfers their learned coefficients as constraints on the coefficients to be learned. This strategy increases the importance of relevant target data points based on their similarity to source support vectors, while learning from the target data. Our method shows important improvements on the convergence rate on three classification datasets of varying sizes, decreasing the number of iterations by up to 56% on average compared to learning with no transfer and up to 92% compared to regular HTL, while maintaining similar accuracy levels.

As common criteria in data mining methods, the frequency-based interestingness measures provide a statistical view of the correlation in the data, such as sequential patterns. However, when the authors consider domain knowledge within the mining process, the unexpected information that contradicts existing knowledge on the data has never less importance than the regularly frequent information. For this purpose, the authors present the approach USER for mining unexpected sequential rules in sequence databases. They propose a belief-driven formalization of the unexpectedness contained in sequential data, with which we propose 3 forms of unexpected sequences. They further propose the notion of unexpected sequential patterns and implication rules for determining the structures and implications of the unexpectedness. The experimental results on various types of data sets show the usefulness and effectiveness of our approach.