text: This paper proposes a client-server decision tree learning method for outsourced private data. The privacy model is anatomization fragmentation: the server sees data values, but the link between sensitive and identifying information is encrypted with a key known only to clients. Clients have limited processing and storage capability. Both sensitive and identifying information thus are stored on the server. The approach presented also retains most processing at the server, and client-side processing is amortized over predictions made by the clients. Experiments on various datasets show that the method produces decision trees approaching the accuracy of a non-private decision tree, while substantially reducing the client's computing resource requirements.
  @cite_26: 
  @cite_7: 
  @cite_8: 
  @cite_9: 
  @cite_3: Mining of frequent patterns is one of the popular knowledge discovery and data mining (KDD) tasks. It also plays an essential role in the mining of many other patterns such as correlation, sequences, and association rules. Hence, it has been the subject of numerous studies since its introduction. Most of these studies find all the frequent patterns from collection of precise data, in which the items within each datum or transaction are definitely known and precise. However, there are many real-life situations in which the user is interested in only some tiny portions of these frequent patterns. Finding all frequent patterns would then be redundant and waste lots of computation. This calls for constrained mining, which aims to find only those frequent patterns that are interesting to the user. Moreover, there are also many reallife situations in which the data are uncertain. This calls for uncertain data mining. In this paper, we propose an algorithm to efficiently find constrained frequent patterns from collections of uncertain data.
  @cite_0: Privacy-preserving decision tree mining is an important problem that has yet to be thoroughly understood. In fact, the privacy-preserving decision tree mining method explored in the pioneer paper [1] was recently showed to be completely broken, because its data perturbation technique is fundamentally flawed [2]. However, since the general framework presented in [1] has some nice and useful features in practice, it is natural to ask if it is possible to rescue the framework by, say, utilizing a different data perturbation technique. In this paper, we answer this question affirmatively by presenting such a data perturbation technique based on random substitutions. We show that the resulting privacy-preserving decision tree mining method is immune to attacks (including the one introduced in [2]) that are seemingly relevant. Systematic experiments show that it is also effective.
  @cite_19: 
  @cite_27: Releasing person-specific data in its most specific state poses a threat to individual privacy. This paper presents a practical and efficient algorithm for determining a generalized version of data that masks sensitive information and remains useful for modelling classification. The generalization of data is implemented by specializing or detailing the level of information in a top-down manner until a minimum privacy requirement is violated. This top-down specialization is natural and efficient for handling both categorical and continuous attributes. Our approach exploits the fact that data usually contains redundant structures for classification. While generalization may eliminate some structures, other structures emerge to help. Our results show that quality of classification can be preserved even for highly restrictive privacy requirements. This work has great applicability to both public and private sectors that share information for mutual benefits and productivity.
  @cite_23: In many application domains, there is a need for learning algorithms that can effectively exploit attribute value taxonomies (AVT)--hierarchical groupings of attribute values--to learn compact, comprehensible and accurate classifiers from data--including data that are partially specified. This paper describes AVT-NBL, a natural generalization of the naive Bayes learner (NBL), for learning classifiers from AVT and data. Our experimental results show that AVT-NBL is able to generate classifiers that are substantially more compact and more accurate than those produced by NBL on a broad range of data sets with different percentages of partially specified values. We also show that AVT-NBL is more efficient in its use of training data: AVT-NBL produces classifiers that outperform those produced by NBL using substantially fewer training examples.
  @cite_5: We study the problem of mining frequent itemsets from uncertain data under a probabilistic framework. We consider transactions whose items are associated with existential probabilities and give a formal definition of frequent patterns under such an uncertain data model. We show that traditional algorithms for mining frequent itemsets are either inapplicable or computationally inefficient under such a model. A data trimming framework is proposed to improve mining efficiency. Through extensive experiments, we show that the data trimming technique can achieve significant savings in both CPU cost and I O cost.
  @cite_13: 
  @cite_17: 
summary: There have been studies in how to mine anonymized data. @cite_27 give a top-down specialization method (TDS) for anonymization so that the anonymized data allows accurate decision trees. @cite_5 and @cite_3 address the frequent itemset mining problem. proposes a clustering algorithm that handles the anonymized data as uncertain information @cite_9 . propose a hierarchical density based clustering method using fuzzy objects @cite_26 . discusses the problem of distance calculation for uncertain objects @cite_7 . Nearest Neighbor classification using generalized data is investigated by Martin @cite_19 . studies Naive Bayes using partially specified data @cite_23 . studies decision tree classifier with random substitutions @cite_0 . proposes a new Support Vector classification and Nearest Neighbor classification that deals with anonymized data @cite_8 . They extend the generalization based anonymization scheme to keep all necessary statistics and use these statistics to build effective classifiers. investigate learning C4.5 decision trees from datasets that satisfy differential privacy @cite_17 . propose a tree classifier based on random forests that is built from differentially private data @cite_13 .