In Web-based environments, a site has the ability to recommend multiple items to a customer in each interaction. Traditionally, rules used to make recommendations either have single items in their consequents or have conjunctions of items in their consequents. Such rules may be of limited use when the site wishes to maximize the likelihood of the customer being interested in at least one of the items recommended in each interaction (with a session comprising multiple interactions). Rules with disjunctions of items in their consequents and conjunctions of items in their antecedents are more appropriate for such environments. We refer to such rules as disjunctive consequent rules. We have developed a novel mining algorithm to obtain such rules. We identify several properties of disjunctive consequent rules that can be used to prune the search space when mining such rules. We demonstrate that the pruning techniques drastically reduce the proportion of disjunctive rules explored, with the pruning effectiveness increasing rapidly with an increase in the number of items to be recommended. We conduct experiments to compare the use of disjunctive rules with that of traditional (conjunctive) association rules on several real-world data sets and show that the accuracies of recommendations made using disjunctive consequent rules are significantly higher than those made using traditional association rules. We also compare the disjunctive consequent rules approach with two other state-of-the-art recommendation approaches—collaborative filtering and matrix factorization. Its performance is generally superior to both these techniques on two transactional data sets. The relative performance on a very sparse click-stream data set is mixed. Its performance is inferior to that of collaborative filtering and superior to that of matrix factorization for that data set.

Organizations maintain informational websites for wired devices. The information content of such websites tends to change slowly with time, so a steady pattern of usage is soon established. User preferences, both at the individual and at the aggregate level, can then be gauged from user access log files. We propose a heuristic scheme based on simulated annealing that makes use of the aggregate user preference data to re-link the pages to improve navigability. This scheme is also applicable to the initial design of websites for wireless devices. Using the aggregate user preference data obtained from a parallel wired website, and given an upper bound on the number of links per page, our methodology links the pages in the wireless website in a manner that is likely to enable the “typical” wireless user to navigate the site efficiently. Later, when a log file for the wireless website becomes available, the same approach can be used to refine the design further.

Due to growing concerns about the privacy of personal information, organizations that use their customers' records in data mining activities are forced to take actions to protect the privacy of the individuals. A frequently used disclosure protection method is data perturbation. When used for data mining, it is desirable that perturbation preserves statistical relationships between attributes, while providing adequate protection for individual confidential data. To achieve this goal, we propose a kd-tree based perturbation method, which recursively partitions a data set into smaller subsets such that data records within each subset are more homogeneous after each partition. The confidential data in each final subset are then perturbed using the subset average. An experimental study is conducted to show the effectiveness of the proposed method.

Several approaches have been proposed for representing uncertain data in a database. These approaches have typically extended the relational model by incorporating probability measures to capture the uncertainty associated with data items. However, previous research has not directly addressed the issue of normalization for reducing data redundancy and data anomalies in probabilistic databases. We examine this issue. To that end, we generalize the concept of functional dependency to stochastic dependency and use that to extend the scope of normal forms to probabilistic databases. Our approach is a consistent extension of the conventional normalization theory and reduces to the latter.

In modern organizations, decision makers must often be able to quickly access information from diverse sources in order to make timely decisions. A critical problem facing many such organizations is the inability to easily reconcile the information contained in heterogeneous data sources. To overcome this limitation, an organization must resolve several types of heterogeneity problems that may exist across different sources. We examine one such problem called the entity heterogeneity problem, which arises when the same real-world entity type is represented using different identifiers in different applications. A decision-theoretic model to resolve the problem is proposed. Our model uses a distance measure to express the similarity between two entity instances. We have implemented the model and tested it on real-world data. The results indicate that the model performs quite well in terms of its ability to predict whether two entity instances should be matched or not. The model is shown to be computationally efficient. It also scales well to large relations from the perspective of the accuracy of prediction. Overall, the test results imply that this is certainly a viable approach in practical situations.

The ability of a computerized system to model the reasoning process of humans has become an important area of research. This research considers a probabilistic reasoning system for applications that require decision making under uncertain conditions. The reasoning system captures the uncertainty associated with different feasible outcomes, and based on historical data, provides users with a measure of this uncertainty. To make accurate predictions, the scheme requires that predictive variables that are not conditionally independent of each other given the outcome be grouped into compound attributes for the purpose of estimating probabilities. These compound attributes partition the entire set of predictive attributes into disjoint sets. An important design issue, then, is that the appropriate partitioning scheme be obtained before the reasoning scheme is used in practice. We formulate the problem of finding the optimal partitioning scheme, and present five different (although related) heuristic techniques to induce partitions from historical cases. Using simulated data, all five techniques are shown to capture accurately underlying dependencies across attributes when a reasonable amount of historical data is available for analysis. In situations where few historical cases are available, the induced structures are less accurate. In such situations, the performance of induced structures for making probability predictions is nevertheless found to be as good as that when using the true structure. Finally, we test for external validity by applying the techniques on a real-world dataset on credit applications for a bank. We show, using this dataset, that (i) the classificatory performance of the reasoning system using structures generated by the heuristic techniques is as good as the performance of the widely used decision tree induction algorithm C4.5, and (ii) the induced structures are able to provide reliable probability estimates for making decisions in environments with asymmetric misclassification costs.

Rule-based representation techniques have become popular for storage and manipulation of domain knowledge in expert systems. It is important that systems using such a representation are verified for accuracy before implementation. In recent years, graphical techniques have been found to provide a good framework for the detection of errors that may appear in a rule base. The authors present a graphical representation scheme that: 1) captures complex dependencies across clauses in a rule base in a compact yet intuitively clear manner and 2) is easily automated to detect structural errors in a rigorous fashion. Their technique uses a directed hypergraph to accurately detect the different types of structural errors that appear in a rule base. The technique allows rules to be represented in a manner that clearly identifies complex dependencies across compound clauses. Subsequently, the verification procedure can detect errors in an accurate fashion by using simple operations on the adjacency matrix of the directed hypergraph. The technique is shown to have a computational complexity that is comparable to that of other graphical techniques. The graphical representation coupled with the associated matrix operations illustrate how directed hypergraphs are a very appropriate representation technique for the verification task.

Presents a technique to construct efficient belief network structures for application areas where large amounts of data are available and information on the ordering of the variables can be obtained from domain experts. We identify classes of networks that are efficient for propagating beliefs. We formulate the problem as one of determining the belief network representation from a given class that best represents the data. We use the I-Divergence measure which is known to have certain desirable properties for evaluating different approximations. We present some theoretical findings that characterize the nature of solutions that are obtained. These theoretical results lead to an efficient solution procedure for finding the best network representation. We also discuss other information that may be reasonably obtained from experts, and show how such information leads to improving the efficiency of the technique to find the best network structure.

Although the relational model for databases provides a great range of advantages over other data models, it lacks a comprehensive way to handle incomplete and uncertain data. Uncertainty in data values, however, is pervasive in all real-world environments and has received much attention in the literature. Several methods have been proposed for incorporating uncertain data into relational databases. However, the current approaches have many shortcomings and have not established an acceptable extension of the relational model. In this paper, we propose a consistent extension of the relational model. We present a revised relational structure and extend the relational algebra. The extended algebra is shown to be closed, a consistent extension of the conventional relational algebra, and reducible to the latter.

Network structures, called belief networks, have been shown to be effective for representing uncertainty in expert systems. A problem faced when making inferences in belief networks is that schemes to propagate beliefs are generally of exponential complexity. A special class of networks, called trees, have been shown to provide an efficient framework for propagating beliefs. In this paper, we present a scheme called star-decomposition, originally proposed by Lazarsfeld [1966], to convert belief networks into trees. This scheme introduces auxiliary variables to represent higher order dependencies in tree structures. Such structures are called enhanced tree structures. We also describe a simple partitioning technique that creates local event groups which extends the applicability of star-decomposition. A framework is presented that identifies classes of belief networks that may be exactly represented using enhanced tree structures. For belief networks that are not amenable to exact representation, an enhanced tree structure preserves more dependencies in the belief network than representations that do not use the star-decomposition technique. The potential benefit of using enhanced trees as compared to simple tree structures is demonstrated.>