Data mining is the enemy of privacy preservation. In the wrong hands data mining can lead to an individual's identity being stolen, loans and health insurance coverage can be denied and an individual can become a victim to financial fraud. However, in the right hands, terrorists can be identified, scientists find treatments which work better than others, and doctors are aided in treatment and diagnosis decisions. So, to minimize the problems that can be caused by attackers (those seeking to gain confidential knowledge about individuals), the new and active fields of Privacy Preserving Data Publishing (PPDP) and Privacy Preserving Data Mining (PPDM) have been developed. 

Researchers in PPDP and PPDM have disclosed their concerns of an attackers' negative use of such a helpful tool. For instance, Wang \cite{Wang08} wrote:
 
\begin{quote}
Recent development in privacy-preserving data mining has proposed many efficient and practical techniques for hiding sensitive patterns or information from been discovered by data mining algorithms.
\end{quote}
Zhang \cite{Zhang07} also noted that although successful in many applications, data mining poses special concerns for private data. Other researchers such \cite{Hintogdlu10, Li09, Atzori08, Hand06}, have gone further, showing how easily an attacker could uncover an individuals private/confidential data using readily available data mining tools. So, in order to take advantage of the good which can result from data mining while protecting the privacy of individuals, researchers have come up with many privacy protection techniques in the areas of PPDP and PPDM. 

PPDP covers methods and tools used to disguise raw data for publishing, while PPDM covers methods and tools used to limit the amount of extra information gained by an attacker after performing some data mining task on published data. In spite of their relatively short existence, there are a plethora of published privacy protecting techniques designed to address a number of different scenarios. Therefore, to narrow the scope of this paper, we will focus on PPDP and the simple scenario of disguising one data-set for publication.

To explore this, the paper answers the following questions:

\begin{itemize}
\item What is PPDP?
\item Why is PPDP important?
\item What is considered a breach of privacy?
\item What are the methods used to avoid privacy breaches?
\item How are privacy preserving algorithms evaluated?
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What is PPDP?}

Similarly, researchers agree that PPDP involves the use of techniques to disguise the micro-data records which contain information about specific individuals, while delivering a useful data-set for analysis. This is indicated clearly by Fung \cite{Fung10}, who noted that PPDP is a collection of methods and tools for publishing data in a hostile environment so that the published data remains practically useful while individual privacy is preserved. Along the same lines, Domingo et. al. \cite{Domingo10} states:
\begin{quote}
Statistical disclosure control (also known as privacy-preserving data mining) of microdata is about releasing data-sets containing the answers of individual respondents protected in such a way that: (i) the respondents corresponding to the released records cannot be re-identified; (ii) the released data stay analytically useful.
\end{quote}
Also, according to LeFevre \cite{LeFevre08}, protecting individual privacy is an important problem in microdata distribution and publishing. Anonymization algorithms typically aim to satisfy certain privacy definitions with minimal impact on the quality of the resulting data.   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\section{Why is PPDP important?}

The importance of PPDP can be answered with a question: \emph{What is data mining without data?}

It is established that data mining is beneficial to many domains such as medical, security, credit fraud and many others. Unfortunately, if the data-sets used in these data mining tasks include a lot of sensitive individual data, the results can lead to privacy breaches. A popular example is the re-identification of William Weld, the former Governor of the state of Massachusetts. Values in quasi identifiers (QIDs) (discussed in Section 5) were linked to his record in a published medical database. More recently, when AOL released the query logs of its users for the purpose of research, Ms. Thelma Arnold was re-identified by the examination of query terms \cite{Fung10}. 

Such breaches lowers the confidence of data providers in publishing disguised data with the expectation of no breaches. In the previous example AOL had no choice but to quickly remove the data-set. So a drawback is that data holders are less likely to publish data for research and the benefits of data mining are not realized in these domains.

%Avoid people being discriminated against. Getting loans, or health insurance or identity theft.

%In general then, the more data these organisation have, the better. On the other hand, the more private data which is collated and disseminated, the more individuals are at risk of crimes such as identity theft and financial fraud, not to mention the simple invasion of privacy that such data collection represents.\cite{Hand06}

%Data mining models themselves pose a privacy breach e.g. sensitive and confidential information maybe mined from aggregate results (e.g. an implication that HIV-positive individuals tend to reside in a particular geographic region). guest editorial
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What is considered a breach of privacy?}

In order to realize privacy breaches, one needs to define what constitutes a privacy breach for a particular data-set. There are different levels of privacy. Some levels are determined by individuals in the data-set or by the creators of a privacy policy. An optimal result of a privacy model is defined by Dalenius \cite{Dalenius77} where he states that access to published data should not enable the attacker to learn anything extra about any target victim, compared to no access to the database, even with the presence of any attacker's background knowledge obtained from other sources \cite{Fung10}. Unfortunately, achieving this ideal is impossible, and so, solutions have focused on trade-offs.

Fung \cite{Fung10}, considers two categories of privacy models, 1) considers that a privacy threat occurs when an attacker is able to link a record owner to a record in a published data table to a sensitive attribute in a published data table, to the published data table itself. These are specified as, record linkage, attribute linkage and table linkage respectively. 2) The published data should provide the attacker with little additional information beyond the background knowledge.

Brickell \cite{Brickell08}, defines a privacy model called sensitive attribute disclosure which occurs when the attacker or adversary learns information about an individual's sensitive attributes. In other words, it captures the gain in the adversaries knowledge due to his observations of the disguised data-set. Also ``Microdata privacy can be understood as prevention of membership disclosure" where the attacker should not learn whether a particular individual is included in the database.

In 2007, Wang \cite{Wang07} put forward other definitions of privacy. The article explains:
\begin{quote}
There have been two types of privacy concerning data mining. The first type of privacy, called output privacy, is that the data is minimally altered so that the mining result will not disclose certain privacy. The second type of privacy, called input privacy, is that the data is manipulated so that the mining result is not affected or minimally affected.
\end{quote}

For the scenario used in this work, we assume a privacy definition of \emph{high}, where an attacker is unsuccessful at getting more information from the sanitized data-set. The methods used are described in the following section.
   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{What are the methods used to avoid privacy breaches?}

The idea of disguising a data-set is known as anonymization. This is performed on the original data-set to ``satisfy a specified privacy requirement" \cite{Fung10} resulting in a modified data-set being published. There are five general categories for anonymization, 1) generalization, 2) suppression, 3) anatomization, 4) permutation and 5) perturbation. Most methods and tools created for preserving privacy fall into one or more of these categories. 

Before we expand on the above categories, we introduce some information about the structure of the original data-sets:

\begin{quote}
\emph{D(Explicit-Identifier, Quasi-Identifier, Sensitive-Attributes, Non-Sensitive-Attributes)}, \newline
where Explicit-Identifier is a set of attributes, such as name and social security number, containing information that explicitly identifies record owners; Quasi-Identifier (QID) is a set of attributes that could potentially identify record owners; Sensitive-Attributes consists of sensitive person-specific information such as disease, salary, and disability status; and Non-Sensitive-Attributes contains all attributes that do not fall into the previous three categories \cite{Fung10}.
\end{quote}

\subsection{Generalization and suppression}

According to \cite{Fung10}, generalization or suppression hides some details in QID. If attribute values are numerical, generalization resembles discretization in that exact values are replaced by an interval that covers the exact values. With categorical values, specific values are replaced by general ones, for instance, date of birth, becomes month of birth, or $professional$ replaces $engineer$ and $lawyer$. Suppression replaces some values with a special value. This could be looked upon as $blocking$ where special values are replace by a question mark ($?$) \cite{Verykios04}. 

$k-anonimity$ is one of the methods which makes each record in the table be indistinguishable with k-1 other records by suppression or generalization \cite{Park10}. There are limitations with k-anonymity including the fact that it does not hide whether a given individual is in the database, or that it does not protect against attacks based on background knowledge \cite{Brickell08}. To overcome these problems, researchers have proposed many variations of k-anonymity \cite{Park10, Matatov10, Zhu09}.

\subsection{Anatomization and permutation}

Anatomization and permutation both accomplish a similar task, that is, the de-association of the relationship between the QID and the sensitive attributes. However, anatomization does it by releasing ``the data on QID and the data on the sensitive attribute in two separate tables..." with  ``one common attribute, $GroupID$" \cite{Fung10}. On the other hand, permutation de-associates the relationship between a QID and a numerical sensitive attribute. This is done by partitioning a set of data records into groups and shuffling the sensitive values within each group \cite{Zhang07}.

\subsection{Perturbation}

A precise definition of perturbation is put forward by \cite{Fung10}:
\begin{quote}
The general idea is to replace the original data values with some synthetic data values, so that the statistical information computed from the perturbed data does not differ significantly from the statistical information computed from the original data.
\end{quote}

It is important to note that the perturbed data records do not correspond to real world record owners. Also, methods used for perturbation include, additive noise, data swapping and synthetic data generation.


%\cite{Yang10}
%\cite{Wong09}
%\cite{Liu08, Nin06}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{How are privacy preserving algorithms evaluated?}

Three evaluation methods are outlined in \cite{Torra09}. These measures are 1) Information loss measures, 2) Disclosure risk measures and 3) Scores. According to \cite{Torra09}, information loss measures are designed to establish in which extent published data is still valid for carrying out the experiments planned on the original data. They take into account the similarity between the original data set and the protected one, as well as the differences between the results that would be obtained with the original data set and the results that would be obtained from the disguised data-set. \cite{Torra09} further explains that disclosure risk measures are used to evaluate the extent in which the protected data ensures privacy and that $scores$, is a summary both information loss and disclosure risk, that is, when these two measures are commensurate, it is possible just to combine them using the average.


%\cite{Torra09} develop cluster specific information loss measures
%\cite{Gionis09}
%\cite{Xu06}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Conclusion}

%What scenario will I focus on and explore in future work?

%We consider a scenario where...
%First define the privacy constraints.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Are there any sampling or reduction techniques used?
%\cite{Nin09, Torra04}
