15049854
On optimal rule discovery
In machine learning and data mining, heuristic and association rules are two dominant schemes for rule discovery. Heuristic rule discovery usually produces a small set of accurate rules, but fails to find many globally optimal rules. Association rule discovery generates all rules satisfying some constraints, but yields too many rules and is infeasible when the minimum support is small. Here, we present a unified framework for the discovery of a family of optimal rule sets and characterize the relationships with other rule-discovery schemes such as nonredundant association rule discovery. We theoretically and empirically show that optimal rule discovery is significantly more efficient than association rule discovery independent of data structure and implementation. Optimal rule discovery is an efficient alternative to association rule discovery, especially when the minimum support is low.
12799351
Mining risk patterns in medical data
In this paper, we discuss a problem of finding risk patterns in medical data. We define risk patterns by a statistical metric, relative risk, which has been widely used in epidemiological research. We characterise the problem of mining risk patterns as an optimal rule discovery problem. We study an anti-monotone property for mining optimal risk pattern sets and present an algorithm to make use of the property in risk pattern discovery. The method has been applied to a real world data set to find patterns associated with an allergic event for ACE inhibitors. The algorithm has generated some useful results for medical researchers.
16063524
(α, k)-anonymity: an enhanced k-anonymity model for privacy preserving data publishing
Privacy preservation is an important issue in the release of data for mining purposes. The k-anonymity model has been introduced for protecting individual identification. Recent studies show that a more sophisticated model is necessary to protect the association of individuals to sensitive information. In this paper, we propose an (α, k)-anonymity model to protect both identifications and relationships to sensitive information in data. We discuss the properties of (α, k)-anonymity model. We prove that the optimal (α, k)-anonymity problem is NP-hard. We first presentan optimal global-recoding method for the (α, k)-anonymity problem. Next we propose a local-recoding algorithm which is more scalable and result in less data distortion. The effectiveness and efficiency are shown by experiments. We also describe how the model can be extended to more general case.
1046695
Achieving k-Anonymity by Clustering in Attribute Hierarchical Structures
Individual privacy will be at risk if a published data set is not properly de-identified. k-anonymity is a major technique to de-identify a data set. A more general view of k-anonymity is clustering with a constraint of the minimum number of objects in every cluster. Most existing approaches to achieving k-anonymity by clustering are for numerical (or ordinal) attributes. In this paper, we study achieving k-anonymity by clustering in attribute hierarchical structures. We define generalisation distances between tuples to characterise distortions by generalisations and discuss the properties of the distances. We conclude that the generalisation distance is a metric distance. We propose an efficient clustering-based algorithm for k-anonymisation. We experimentally show that the proposed method is more scalable and causes significantly less distortions than an optimal global recoding k-anonymity method.
6271246
Mining Optimal Class Association Rule Set
We define an optimal class association rule set to be the minimum rule set with the same prediction power of the complete class association rule set. Using this rule set instead of the complete class association rule set we can avoid redundant computation that would otherwise be required for mining predictive association rules and hence improve the efficiency of the mining process significantly. We present an efficient algorithm for mining the optimal class association rule set using an upward closure property of pruning weak rules before they are actually generated. We have implemented the algorithm and our experimental results show that our algorithm generates the optimal class association rule set, whose size is smaller than 1/17 of the complete class association rule set on average, in significantly less time than generating the complete class association rule set. Our proposed criterion has been shown very effective for pruning weak rules in dense databases.
1837455
AFBV: a scalable packet classification algorithm
Packet classification is a central function of a number of network activities, such as routing and firewall management. The packet classifier has a ordered rule database, one rule for each type of packets, and all arriving packets are classified into equivalent classes based on the first rule they match. With the development of the Internet, the database size can only grow with time. Consequently, scalability becomes an important issue for packet classification algorithm. This project is addressing the scalability problem in the selection of rules for packet classification. There is significant previous work in this area. Much previous work executed in linear time with the number of rules. Our work is an improvement on the ABV scheme of Baboescu and Varghese [1], which in turn is an improvement in the straightforward linear Lucent bit vector scheme (BV) [2]. The BV scheme produces bit vectors of all rules for each field, and selects the rules applicable to the complete header by first finding the bit vectors corresponding to each field, then intersecting them, and the first set bit in the consequent bit vector implies the position of the rule in the database. ABV made two observations: first the set bits in the bit vectors are sparse and second a packet matches no more than a few rules. Hence, ABV improves BV to achieve logarithmic time in two steps. First, ABV rearranges the rules by sorting, so that those rules that match specific prefixes are near each other in the list. Second, it aggregates bits in each field to reduce memory accesses, but increasing the possibility of false matches. The rule rearrangement mitigates the false matches to some extent, but also incurs additional cost. First, rule rearrangement makes it necessary to find all matches, instead of first match in BV. Second, it is not easy to find an effective rearrangement method. Third, rules need to be mapped back to the original order so as to find the rule with the lowest order. Our scheme, the Aggregated and Folded Bit Vector algorithm (AFBV) inherits the idea of bit vector and aggregation from BV and ABV, but discards rule rearrangement and introduce a new concept: folding. All bits in a predefined range r (r is called folding range, usually equal to multiple aggregate sizes), whose positions have the same mod-f value are OR-ed together, the result occupying that position mod f, thus folding the bit vector (f is called folding size). Only when there are at least one bit set at the same mod-f position can one get false matches, while in ABV, a match among any bits within an aggregation group can lead to a false match. Once there is a match in the folded bit vector at position k (k is inclusively between 0 and f-1), the possible real match position must take the form (I · f + k). Therefore, folding helps not only filter out false matches but also locate the real match positions. This scheme will also not produce any false negatives (missing a match). Thus, correctness is guaranteed. Besides the folding range and the folding size, the number of folding is another important parameter in AFBV. By using multiple folding with different sizes, we can enhance the detecting and locating ability of the folded vectors. First, only if there are matches in all the intersections of the folded vectors may there be real matches in the original vectors. The gain here is that mostly we do not need to fetch the whole original bit vector to conclude a false match as required in BV and ABV. Second, with proper selection on the folding sizes, multiple folding greatly reduces the number of the possible match positions than single folding. The gain here is that in case of real matches, we only need to fetch parts instead of the whole original bit vectors. In addition to the aggregate bit vectors, AFBV needs to store the folded bit vectors, which incurs about 10% additional storage requirements, and could be even smaller. AFBV offers the following benefits: Only the first matched rule need to be found; no mapping back cost is needed; without rule rearrangement, pre-processing is much simple; a large aggregate size can be applied because the folded vectors reduce false matches. In our simulations of relative performance we compare the Lucent BV algorithm, the ABV algorithm and our AFBV algorithm, and evaluate both performance and space utilization. Preliminary results on different-sized databases show that AFBV outperforms ABF and BV on average, and can achieve the similar level of performance in worst cases, with about a 10% increase in memory requirements, for the additional, folded vectors.
42802236
Rule Evaluations, Attributes, and Rough Sets: Extension and a Case Study
Manually evaluating important and interesting rules generated from data is generally infeasible due to the large number of rules extracted. Different approaches such as rule interestingness measures and rule quality measures have been proposed and explored previously to extract interesting and high quality association rules and classification rules. Rough sets theory was originally presented as an approach to approximate concepts under uncertainty. In this paper, we explore rough sets based rule evaluation approaches in knowledge discovery. We demonstrate rule evaluation approaches through a real-world geriatric care data set from Dalhousie Medical School. Rough set based rule evaluation approaches can be used in a straightforward way to rank the importance of the rules. One interesting system developed along these lies in HYRIS (HYbrid Rough sets Intelligent System). We introduce HYRIS through a case study on survival analysis using the geriatric care data set.
2572958
RACCOON: a peer-based system for data integration and sharing
Recent database applications see the emerging need to support data integration in distributed, peer-to-peer environments, in which autonomous peers (sources) connected by a network are willing to exchange data and services with each other. To address related research challenges, we are developing a system called "RACCOON", which allows different sources to integrate and share their data. We use an application to show several important features of the RACCOON system. The system also suggests semantic mappings for the user to choose. We show the two different querying modes, particularly how a query is expanded using the semantic mappings in the extended querying mode to compute as many answers to the query as possible.
15549324
A Rough Set Based Model to Rank the Importance of Association Rules
Association rule algorithms often generate an excessive number of rules, many of which are not significant. It is difficult to determine which rules are more useful, interesting and important. We introduce a rough set based process by which a rule importance measure is calculated for association rules to select the most appropriate rules. We use ROSETTA software to generate multiple reducts. Apriori association rule algorithm is then applied to generate rule sets for each data set based on each reduct. Some rules are generated more frequently than the others among the total rule sets. We consider such rules as more important. We define rule importance as the frequency of an association rule among the rule sets. Rule importance is different from rule interestingness in that it does not consider the predefined knowledge on what kind of information is considered to be interesting. The experimental results show our method reduces the number of rules generated and at the same time provides a measure of how important is a rule.
15668602
A Survey of Software Development with Open Source Components in Chinese Software Industry
Chinese software companies are increasingly using Open Source Software (OSS) components in system development. Integrating such components into new software systems leads to challenges related to component selection, component integration and testing, licensing compliance, and system maintenance. Although these issues have been investigated industrially in other countries, few state-of-the-practice studies have so far been performed in China and with a representative subset of software companies. It is therefore difficult for Chinese software companies to be aware of special issues, or to plan improvement of OSS-related processes. This paper describes a questionnaire-based survey in Chinese software companies of software development with existing OSS components. Data from 47 finished development projects in 43 companies have been collected. The results show that use of web search engines was the most common method to locate OSS components. Local expertise combined with requirements compliance was the most decisive factors when choosing an identified component. To avoid legal exposure, the common strategy was to use components without licensing constraints. About 84% of the components needed bug fixing or other code changes, rarely relies on support from the OSS community. However, close participation with the OSS community was rare, although most developers meant that this was important.