Frequent itemsets hiding: A performance evaluation framework

Sensitive knowledge hiding is an essential requirement to prevent disclosure of any sensitive knowledge holding in shared databases. The security of a database may be risked when it is made public as is: because the data mining tools are so sophisticated that the sensitive knowledge can easily be surfaced by receivers. This gives rise to a sanitization process which transforms the original database into another database, the released one, which does not hold the sensitive knowledge but can substitute the original otherwise. In case the sensitive knowledge is of the form frequent itemsets, the resulting concrete problem is called frequent itemsets hiding. A number of algorithms, exploiting different approaches and techniques, for frequent itemsets hiding problem is proposed in the literature. Since finding optimal solutions is NP-Hard, algorithms resort to certain heuristics having different levels of sophistication, complexity, efficiency and effectiveness. This paper presents an evaluation framework which implements recent algorithms belonging to different approaches and a set of metrics to gauge the performance and problem difficulties. The current work also presents an experimental study and its results where four algorithms and seven datasets are involved. Our results indicate that data distortion levels and runtime requirements are quite high, especially for difficult problem instances. Our conclusion is that there are new rooms for more sophisticated and tuneable (w.r.t. effectiveness/efficiency tradeoff) algorithms.

I. Introduction

Privacy preserving data mining, an active research area, is the study of privacy implications on data mining [1]–[4]. Although the topic has many aspects and versatile by nature, the privacy requirement is very simple; nobody’s privacy is risked due to data mining threats. However, fulfilling the simple requirement is usually not trivial as advanced data mining algorithms can uncover implicit private knowledge. Consider the database publishing scenario where data owner wishes to make his database public for some reason, e.g. to be used in related research activities. In case the database contains sensitive data, they can be simply suppressed to get the sanitized version. But what if it holds sensitive knowledge that is implied by the database content? In this case, database sanitization is clearly more involved as suppressing the sensitive knowledge while maintaining the database integrity is not straightforward as before. The problem is known as the knowledge hiding problem. Other privacy preserving data mining problems include data obfuscation/perturbation, secure multi-party computation, secure knowledge sharing and k-anonymity [2].