# Frequent Symptom Sets Identification from Uncertain Medical Data in Differentially Private Way

Authors: Zhe Ding; Zhen Qin; Zhiguang Qin
Journal: Scientific Programming
 (2017)

---

## Abstract

Data mining techniques are applied to identify hidden patterns in large amounts of patient data. These patterns can assist physicians in making more accurate diagnosis. For different physical conditions of patients, the same physiological index corresponds to a different symptom association probability for each patient. Data mining technologies based on certain data cannot be directly applied to these patients’ data. Patient data are sensitive data. An adversary with sufficient background information can make use of the patterns mined from uncertain medical data to obtain the sensitive information of patients. In this paper, a new algorithm is presented to determine the topK most frequent itemsets from uncertain medical data and to protect data privacy. Based on traditional algorithms for mining frequent itemsets from uncertain data, our algorithm applies sparse vector algorithm and the Laplace mechanism to ensure differential privacy for the top K most frequent itemsets for uncertain medical data and the expected supports of these frequent itemsets. We prove that our algorithm can guarantee differential privacy in theory. Moreover, we carry out experiments with four real-world scenario datasets and two synthetic datasets. The experimental results demonstrate the performance of our algorithm.


---

## Body

## 1. Introduction

The Internet of Things (IoT) involves a lot of different base technologies, such as wireless sensors, data management, and cloud computing [1]. Today, IoT technology is successfully applied in the field of eHealth [2–4]. Medical personnel can utilize IoT technology to collect large amounts of patient data that can assist them in providing better medical services to patients [5, 6].Frequent itemsets mining is applied in fields such as eHealth and bioinformatics. Traditional algorithms for mining frequent itemsets from medical data are based on certain data [7] and can be applied to discover hidden symptom patterns from a huge amount of data on patient symptoms. These patterns can be used by health managers to provide better healthcare for users [8]. For example, in [9, 10], the Apriori algorithm was applied to identify prevalent diseases and analyze medical billing. However, the Apriori algorithm mines frequent itemsets from certain data. In medicine, for different physical conditions of patients, the same physiological index corresponds to a different symptom association probability for each patient. As a result, there is uncertainty in patient data. Therefore, traditional algorithms for mining frequent itemsets from certain data cannot be directly applied to patient data.Another important factor is that medical records contain sensitive patient information. An adversary with sufficient background information can make use of frequent patterns mined from patient data to obtain the sensitive information of patients. Hence, it is very important to protect patient privacy when mining frequent itemsets from medical data [11].The set of symptoms that a patient suffers from constitute the patient’s data. Because of the probabilities associated with these symptoms, there is uncertainty in patient data. A large amount of patient data constitutes uncertain data. In the field of medicine, there are plenty of researches on symptom association probability. For example, one study monitored oesophageal pH over a 24 h period to obtain symptom association probability, which was then utilized to evaluate the association between a patient’s symptoms and gastroesophageal reflux [12]. By analyzing the large amounts of patient data, Beglinger et al. determined the probability that a patient suffering from Huntington’s disease also had obsessive and compulsive symptoms [13]. By analyzing the data of patients suffering from irritable bowel syndrome, Arsiè et al. determined the probability that indicated the association between meal ingestion and abdominal pain symptoms for patients suffering from irritable bowel syndrome [14]. In this paper, based on symptom association probability obtained by medical technology, we focus on how to mine frequent itemsets from uncertain medical data, while also protecting data privacy. In the uncertain medical data, each item corresponds to a symptom of patients.In this paper, a new algorithm, denoted as U-PrivMining (uncertain medical data differentially private frequent itemsets mining), is proposed to mine the topK most frequent itemsets from uncertain medical data in a differentially private way. In uncertain medical data, each item corresponds to a symptom of patients. U-PrivMining has two phases. In the first phase, based on traditional algorithms for mining frequent itemsets from uncertain data, spare vector algorithm and the Laplace mechanism are applied to ensure differential privacy for all the frequent itemsets mined from uncertain medical data. In the second phase, based on the frequent itemsets, the Laplace mechanism is applied to ensure differential privacy for the top K most frequent itemsets for uncertain data, as well as the expected supports of these frequent itemsets. We used the spare vector algorithm to improve the efficiency of our algorithm. The spare vector algorithm was used to mine the top K most frequent itemsets from certain data and guaranteed differential privacy in [15]. One major advantage of the spare vector algorithm is that information disclosure affecting differential privacy occurs only for count queries above the threshold; negative answers do not count against the “privacy budget” [15]. The sparse vector algorithm is also suitable for guaranteeing differential privacy when mining frequent itemsets from uncertain data. For certain data, the fixed occurrence counting of an itemset has been applied to determine whether the itemset is frequent. For mining frequent itemsets based on expected support from uncertain data, the expectation of support of an itemset has been utilized to judge whether the itemset is frequent [16]. To summarize, our key contributions are the following:(i)
A new algorithm is proposed to mine the topK most frequent itemsets from uncertain medical data and ensure differential privacy. Traditional algorithms for mining frequent itemsets in differential privacy ways are based on certain data and thus cannot be directly applied to process uncertain medical data.(ii)
Through privacy analysis, we prove that U-PrivMining guarantees differential privacy in theory. Our experimental results on four real-world scenario datasets and two synthetic datasets illustrate the efficiency of U-PrivMining.This paper is organized as follows. Section2 presents an overview of related work on eHealth, IoT, frequent itemsets mining for uncertain data, and differential privacy. In Section 3, some notations used in this paper are introduced. The U-PrivMining algorithm and the proof that U-PrivMining satisfies differential privacy in theory are presented in Section 4. In Section 5, the performance of U-PrivMining is evaluated with six datasets. In the last section, we conclude our work.


## 2. Related Works

eHealth applies IoT technology to provide better healthcare services to users. In 2009, Niyato et al. proposed a remote and mobile patient monitoring system that applies heterogeneous wireless access to monitor the biosignals of patient mobility [17]. In 2015, based on the limitations of traditional cellular networks for eHealth services, Yi et al. designed a transmission scheduling mechanism for delay-sensitive medical packets in an eHealth network [18]. The eHealth system based on IoT used monitoring devices to collect large amounts of patient data. Data mining can find hidden patterns in these data, which can assist medical personnel in providing improved medical services to patients. In 2009, Karaolis et al. proposed an algorithm that used mining association rules to assess the risk of coronary events [19]. When traditional data mining technologies are applied to medical data, many useless patterns are discovered. In 2013, Lee et al. proposed a novel algorithm for mining association rule to determine the relationship between blood factors and disease history [20]. This algorithm reduced the number of useless patterns mined from medical data. In 2014, Park et al. used association rules mined from medical data to identify risk behaviors in daily life [21].The phenomenon of data uncertainty is very common. Traditional algorithms for mining frequent itemsets based on certain data cannot be directly applied to mine frequent itemsets from uncertain data. There are two categories of research on mining frequent itemsets from uncertain data [22]. The first category is mining frequent itemsets based on expected support. In 2007, Chui et al. proposed the notion of expected support and proposed the U-Apriori algorithm based on the Apriori algorithm [23]. The second category is probabilistic frequent itemsets mining. In 2012, the characteristics of Poisson binomial distribution were introduced to mine probabilistic frequent itemsets [24]. In 2012, Bernecker et al. proposed an algorithm based on the frequent pattern tree to mine probabilistic frequent itemsets from uncertain data [25].Protecting the privacy of patient data is challenge for eHealth and plenty of studies have been conducted on eHealth security [26–33]. Differential privacy can ensure that when one record in the input database of mechanism A is changed, the output of A is insensitive to the change [34]. In 2006, Dwork et al. proposed the Laplace mechanism to ensure differential privacy for real-valued output [35]. In 2010, Bhaskar et al. proposed an algorithm based on truncated frequencies to ensure differential privacy for the top K most frequent itemsets for certain data [36]. In 2012, Li et al. introduced the notion of basis set to ensure differential privacy for mining the top K most frequent itemsets from certain data [37]. In 2014, Lee et al. applied sparse vector algorithm and the Laplace mechanism to guarantee differential privacy for the top K frequent itemsets mined from certain data [15]. In 2015, Su et al. introduced a smart splitting method to mine frequent itemsets from certain data and ensure differential privacy [38].Although there are many studies on mining frequent itemsets from certain data in differentially private ways, research on mining frequent itemsets from uncertain data in differentially private ways remains few. This paper focuses on research on mining the topK most frequent itemsets from uncertain data in differentially private ways.


## 3. Preliminaries

The fundamental notions of mining frequent itemsets from uncertain data [23] and differential privacy [34, 35] will be reviewed in this section. These fundamental notions are used throughout this paper. The terms “item” and “symptom” are used interchangeably; “itemset” and “symptom set” can be swapped.


### 3.1. Frequent Itemsets Mining for Uncertain Data

LetV=v1,v2,…,vm be a set of m items andT=t1,t2,…,tn as uncertain data with n records. Each record ti=vi1,Pvi1∈ti,…,vik,Pvik∈ti1≤i≤n is a set of uncertain items. For vij,Pvij∈ti∈ti,vij∈V is assigned with existential probability Pvij∈ti, which indicates the likelihood that vij appears in ti. For example, let V={hypotension,eatingdisorder,anemia,neurasthenia}. The uncertain data is shown in Table 1. We can obtain the information from Table 1 as follows. T=t1,t2 and t1={(hypotension:0.3),(eatingdisorder:0.1)}, which means that user t1 may be suffering from hypotension and eating disorder. The probability of {hypotension} existing in t1 is equal to 0.3; in other words, Phypotension∈t1=0.3. This means that the probability of user t1 suffering from hypotension is equal to 0.3.Table 1
Uncertain data.
ID
Records
t
1
(hypotension: 1), (eating disorder: 0.3)
t
2
(anemia: 1), (hypotension: 0.7), (neurasthenia: 0.6)A set of possible worlds (possible certain database), denoted asW=w1,w2,…,wW, can be inferred from uncertain data T. According to the existing probabilities Pvj∈ti, each possible world wg1≤g≤W is illustrated by generating ti∈T. Table 2 shows a set of possible worlds inferred from the uncertain data shown in Table 1. For instance, the possible world w2={{hypotension},{anemia,hypotension}} in Table 2 means that the user t1 is suffering from hypotension and user t2 is suffering from anemia and hypotension.Table 2
Possible worlds.
W
Possible world
P
w
i
w
1
h
y
p
o
t
e
n
s
i
o
n, anemia
0.084
w
2
h
y
p
o
t
e
n
s
i
o
n, anemia,hypotension
0.196
w
3
h
y
p
o
t
e
n
s
i
o
n, anemia,neurasthenia
0.126
w
4
h
y
p
o
t
e
n
s
i
o
n, anemia,hypotension,neurasthenia
0.294
w
5
e
a
t
i
n
g
d
i
s
o
r
d
e
r
,
h
y
p
o
t
e
n
s
i
o
n, anemia
0.036
w
6
e
a
t
i
n
g
d
i
s
o
r
d
e
r
,
h
y
p
o
t
e
n
s
i
o
n, anemia,hypotension
0.084
w
7
e
a
t
i
n
g
d
i
s
o
r
d
e
r
,
h
y
p
o
t
e
n
s
i
o
n, anemia,neurasthenia
0.054
w
8
e
a
t
i
n
g
d
i
s
o
r
d
e
r
,
h
y
p
o
t
e
n
s
i
o
n, anemia,hypotension,neurasthenia
0.126We assume that all the records in the uncertain data and all the uncertain items in the same record are mutually independent. The probability of a possible worldwg, denoted as Pwg, can be obtained by the following [23]:(1)Pwg=∏i=1n∏x∈Twg,tiPx∈ti·∏y∉Twg,ti1-Py∈ti,where Twg,ti denotes the set of items contained in record ti and belonging to wg. The expected support of itemset X, denoted as SeX, can be obtained by the following [23]:(2)SeX=∑i=1WPwi×SX,wi,where SX,wg is the support count of itemset X in possible world wg. For Table 2, in w2, we can obtain the information as Pw2=1×1-0.3×1×0.7×1-0.6=0.196,Tw2,t1=hypotension and Tw2,t2=anemia,hypotension.


### 3.2. Differential Privacy

Differential privacy can ensure that output of the analysis mechanism is insensitive to changes in input records. If an analysis mechanism ensures differential privacy, its output will be insensitive to the addition or removal of a record from the input database. As a result, the output cannot be used by adversaries to gain access to a patient’s record using their background information [35]. Many studies on privacy protection are based on two assumptions. The first assumption is that the background information of adversaries is already known to the security manager. The second one is that the security manager has known which information should be kept private for users. Differential privacy can protect sensitive information of users without that information [34]. Two databases, D1 and D2, are a pair of neighboring databases if and only if they differ by no more than one record.Definition 1 (є-differential privacy [34]).
LetRangeA be the domain of a random algorithm A’s output. D and D′ are any pair of neighboring datasets. If (3) is satisfied, then algorithm A guarantees є-differential privacy.(3)PAD=S≤eє·PAD′=S,where є is the privacy budget of differential privacy and S∈Range(A).
The sensitivity is used to obtain the maximal possible difference value between outputs for any pair of neighboring datasets.Definition 2 (sensitivity [34]).
Given the functionf:Dn→Rd, the sensitivity of f, denoted as Δf, can be obtained by(4)Δf=maxfD-fD′1,where D and D′ are any pair of neighboring datasets.Definition 3 (the Laplace mechanism [35]).
Given datasetD, let Q=q1,q2,…,qp be a query sequence and the sensitivity of Q is ΔQ. Letξ1,ξ2,…,ξpbe a vector, in which ξi1≤i≤parei.i.d. drawn from the Laplace distribution whose scale and mean are ΔQ/є and 0, respectively. The algorithm(5)AD=QD+ξ1,ξ2,…,ξpguarantees є-differential privacy.Lemma 4 (composition lemma [34]).
Given a sequence of algorithm, denoted asf=f1,f2,…,fd, if each algorithmfi1≤i≤dguarantees єi-differential privacy, then f ensures∑i=1dєi-differential privacy.


## 3.1. Frequent Itemsets Mining for Uncertain Data

LetV=v1,v2,…,vm be a set of m items andT=t1,t2,…,tn as uncertain data with n records. Each record ti=vi1,Pvi1∈ti,…,vik,Pvik∈ti1≤i≤n is a set of uncertain items. For vij,Pvij∈ti∈ti,vij∈V is assigned with existential probability Pvij∈ti, which indicates the likelihood that vij appears in ti. For example, let V={hypotension,eatingdisorder,anemia,neurasthenia}. The uncertain data is shown in Table 1. We can obtain the information from Table 1 as follows. T=t1,t2 and t1={(hypotension:0.3),(eatingdisorder:0.1)}, which means that user t1 may be suffering from hypotension and eating disorder. The probability of {hypotension} existing in t1 is equal to 0.3; in other words, Phypotension∈t1=0.3. This means that the probability of user t1 suffering from hypotension is equal to 0.3.Table 1
Uncertain data.
ID
Records
t
1
(hypotension: 1), (eating disorder: 0.3)
t
2
(anemia: 1), (hypotension: 0.7), (neurasthenia: 0.6)A set of possible worlds (possible certain database), denoted asW=w1,w2,…,wW, can be inferred from uncertain data T. According to the existing probabilities Pvj∈ti, each possible world wg1≤g≤W is illustrated by generating ti∈T. Table 2 shows a set of possible worlds inferred from the uncertain data shown in Table 1. For instance, the possible world w2={{hypotension},{anemia,hypotension}} in Table 2 means that the user t1 is suffering from hypotension and user t2 is suffering from anemia and hypotension.Table 2
Possible worlds.
W
Possible world
P
w
i
w
1
h
y
p
o
t
e
n
s
i
o
n, anemia
0.084
w
2
h
y
p
o
t
e
n
s
i
o
n, anemia,hypotension
0.196
w
3
h
y
p
o
t
e
n
s
i
o
n, anemia,neurasthenia
0.126
w
4
h
y
p
o
t
e
n
s
i
o
n, anemia,hypotension,neurasthenia
0.294
w
5
e
a
t
i
n
g
d
i
s
o
r
d
e
r
,
h
y
p
o
t
e
n
s
i
o
n, anemia
0.036
w
6
e
a
t
i
n
g
d
i
s
o
r
d
e
r
,
h
y
p
o
t
e
n
s
i
o
n, anemia,hypotension
0.084
w
7
e
a
t
i
n
g
d
i
s
o
r
d
e
r
,
h
y
p
o
t
e
n
s
i
o
n, anemia,neurasthenia
0.054
w
8
e
a
t
i
n
g
d
i
s
o
r
d
e
r
,
h
y
p
o
t
e
n
s
i
o
n, anemia,hypotension,neurasthenia
0.126We assume that all the records in the uncertain data and all the uncertain items in the same record are mutually independent. The probability of a possible worldwg, denoted as Pwg, can be obtained by the following [23]:(1)Pwg=∏i=1n∏x∈Twg,tiPx∈ti·∏y∉Twg,ti1-Py∈ti,where Twg,ti denotes the set of items contained in record ti and belonging to wg. The expected support of itemset X, denoted as SeX, can be obtained by the following [23]:(2)SeX=∑i=1WPwi×SX,wi,where SX,wg is the support count of itemset X in possible world wg. For Table 2, in w2, we can obtain the information as Pw2=1×1-0.3×1×0.7×1-0.6=0.196,Tw2,t1=hypotension and Tw2,t2=anemia,hypotension.


## 3.2. Differential Privacy

Differential privacy can ensure that output of the analysis mechanism is insensitive to changes in input records. If an analysis mechanism ensures differential privacy, its output will be insensitive to the addition or removal of a record from the input database. As a result, the output cannot be used by adversaries to gain access to a patient’s record using their background information [35]. Many studies on privacy protection are based on two assumptions. The first assumption is that the background information of adversaries is already known to the security manager. The second one is that the security manager has known which information should be kept private for users. Differential privacy can protect sensitive information of users without that information [34]. Two databases, D1 and D2, are a pair of neighboring databases if and only if they differ by no more than one record.Definition 1 (є-differential privacy [34]).
LetRangeA be the domain of a random algorithm A’s output. D and D′ are any pair of neighboring datasets. If (3) is satisfied, then algorithm A guarantees є-differential privacy.(3)PAD=S≤eє·PAD′=S,where є is the privacy budget of differential privacy and S∈Range(A).
The sensitivity is used to obtain the maximal possible difference value between outputs for any pair of neighboring datasets.Definition 2 (sensitivity [34]).
Given the functionf:Dn→Rd, the sensitivity of f, denoted as Δf, can be obtained by(4)Δf=maxfD-fD′1,where D and D′ are any pair of neighboring datasets.Definition 3 (the Laplace mechanism [35]).
Given datasetD, let Q=q1,q2,…,qp be a query sequence and the sensitivity of Q is ΔQ. Letξ1,ξ2,…,ξpbe a vector, in which ξi1≤i≤parei.i.d. drawn from the Laplace distribution whose scale and mean are ΔQ/є and 0, respectively. The algorithm(5)AD=QD+ξ1,ξ2,…,ξpguarantees є-differential privacy.Lemma 4 (composition lemma [34]).
Given a sequence of algorithm, denoted asf=f1,f2,…,fd, if each algorithmfi1≤i≤dguarantees єi-differential privacy, then f ensures∑i=1dєi-differential privacy.


## 4. U-PrivMining Algorithm

This section introduces the U-PrivMining algorithm to determine the topK most frequent itemsets from uncertain data, in which each item corresponds to a symptom of patients, in a differentially private way. The process of U-PrivMining consists of two phases. In the first phase, the assigned privacy budget is equal toє1=α·є. In the second phase, the assigned privacy budget is equal to є2=1-α·є. The parameterα∈0,1is applied to control the value of the privacy budgets assigned in the two phases. In this study, we choseα=1/3for all uncertain data. However, this choice may not be optimal. It appears that the optimal allocation depends on the characteristics of the uncertain medical data and value of K [36].


### 4.1. Description of U-PrivMining

The whole process of U-PrivMining is introduced in this section. U-PrivMining is composed of two phases. In the first phase, we can obtainθ so that the expected supports of the top K most frequent itemsets are greater than or equal to θ. The privacy budget allocated to this step is equal toє1=1/3·є. On the basis of traditional algorithm for mining frequent itemsets from uncertain data, we apply the sparse vector algorithm [15] and Laplace mechanism to ensure є/3-differential privacy for this phase. The steps in the first phase of U-PrivMining are as follows.Step 1.
The expected support of theKth most frequent itemset, denoted as Sk, is obtained by utilizing traditional algorithms for mining frequent itemsets based on expected support from uncertain data.Step 2.
The noisy threshold, denoted asS⌢K, can be obtained by(6)S⌢K=SK+Lap12є,where Lap12/є is the noisy data generated by the Laplace distribution, whose mean and scale are 0 and 12/є, respectively.Step 3.
On the basis of traditional algorithms for mining frequent itemsets from uncertain data, the sparse vector algorithm is applied to obtain all the frequent itemsets whose assessment expected supports are greater than or equal to the noisy thresholdS⌢K. The assessment expected support of an itemset X, denoted as S⌢eX can be obtained by(7)S⌢eX=SeX+Lap4є,where SeX is the expected support of itemset X and Lap4/є is the noisy data generated by the Laplace distribution, whose mean and scale are 0 and 4/є, respectively.Step 4.
All the frequent itemsets obtained in Step3 and the expected supports of these itemsets are taken as the output of this phase.In the second phase, according to the output of the first phase, U-PrivMining can obtain the topK most frequent itemsets for uncertain data and the noisy expected supports of these frequent itemsets. The privacy budget allocated to the second phase is equal to є2=2/3·є. The privacy budgets allocated to ensure differential privacy for the top K most frequent itemsets for uncertain data and for the expected supports of these itemsets for uncertain data are equal to є2,1=β·є2 and є2,2=1-β·є2, respectively. The second phase of U-PrivMining is described below.LetH=h1,h2,…,hH be a set of itemsets obtained in the first phase of U-PrivMining. Let Sehi1≤i≤H be the expected support of itemset hi. The steps in the second phase of U-PrivMining are as follows.Step 1 (ifH is less than or equal to K, β is equal to 0).
All the itemsets inH belong to the top K most frequent itemsets for uncertain data. And then Step 3 is directly executed.Step 2 (ifH is greater than K, β is equal to 0.5).
The perturbation expected supports of all the itemsets inH can be obtained. The perturbation expected support of itemset hi1≤i≤H, denoted as ςHi, can be obtained by(8)ςhi=Sehi+ξi,where ξ1,ξ2,…,ξHare mutually independent and drawn from the Laplace distribution, whose mean and scale are 0 and H/є2,1, respectively. The top K most frequent itemsets for the perturbation expected supports in H are the top K most frequent itemsets for uncertain data.Step 3.
LetR=r1,r2,…,rK be the set of the top K most frequent itemsets for uncertain data, which are obtained in above steps. The noisy expected supports of all the itemsets in R can be obtained. The noisy expected support of itemset ri1≤i≤K can be obtained by(9)σri=Seri+λi,where λ1,λ2,…,λKare mutually independent and drawn from the Laplace distribution whose mean and scale are equal to 0 andK/є2,2, respectively.Step 4.
The topK most frequent itemsets for uncertain data and the noisy expected supports of these itemsets are taken as the output of U-PrivMining.


### 4.2. Privacy Analysis for U-PrivMining

In this section, we prove that U-PrivMining isє-differentially private. In order to prove that U-PrivMining guarantees differential privacy, we introduce the notions of count query set and threshold query set.Definition 5 (count query set [15]).
LetS=s1,s2,…,sS be a set of itemsets with S itemsets. A count query set is composed of a number of queries. Let CQ=q1,q2,…,q|S| be the count query set, where each query qi1≤i≤|S| asks for the expected support of the ith itemset in S.Definition 6 (threshold query set [15]).
LetS=s1,s2,…,s|S| be a set of itemsets with S itemsets. A threshold query set is composed of a number of threshold queries. Let TQ=q1,q2,…,qS be the threshold query set, where each qi1≤i≤S returns 1 if S⌢si≥S⌢K1≤i≤S; otherwise qi returns 0.
According to the definition of count query set, the sensitivity of the count query and count query set can be obtained as follows.Lemma 7.
LetCQ=q1,q2,…,qH be a count query set. The sensitivity of qi1≤i≤H andCQ are equal to 1 and H, respectively.Proof.
According to (2), we can obtain the other method to compute the expected support of an itemset X, denoted as SeX, as follows [23]:(10)SeX=∑i=1n∏x∈XPx∈ti,where n is the number of records in an uncertain data T and ti1≤i≤n is a record in T. Let T and T′ be a pair of neighbor databases. Let D=t∣t∈T∩t∈T′ be the intersection of T and T′. Let T, T′, and D be the total size of T, T′, and D, respectively. Let SeTX and SeT′Xbe the expected supports of itemset X for T and T′, respectively. According to (10), the values of SeTX and SeT′X can be computed as follows:(11)SeTX=∑j=1T∏x∈XPx∈tj=∑j=1D∏x∈XPx∈tj+∏x∈XPx∈d1SeT′X=∑j=1T′∏x∈XPx∈tj=∑j=1D∏x∈XPx∈tj+∏x∈XPx∈d2⇓SeTX-SeT′X1≤1,where d1=t∣t∈T∩t∉T′ andd2=t∣t∈T′∩t∉T. As a result, the sensitivity of each query qi1≤i≤H is equal to 1. Since there are H queries inCQ, the sensitivity ofCQ is equal to H.Based on the sensitivity of the count query and count query set for uncertain data, we can conclude that U-PrivMining guaranteesє-differential privacy. The proof procedure is outlined below.Theorem 8.
The first phase of U-PrivMining isє/3-differentially private.Proof.
According to Lemma7, the sensitivity of obtaining SK is equal to 1. As a result, according to the Laplace mechanism, it is є/12-differentially private to generate the noisy threshold S⌢K. Let S⌢KD1 and S⌢KD2 be the noisy threshold for a pair of neighboring databases D1 and D2, respectively. According to Definition 1, (12) is satisfied.(12)PS⌢KD1=x≤PS⌢KD2=x·eє/12.
LetH=h1,h2,…,hH be the set of itemsets. The threshold query set is applied to model the set of answers as a vector Q=q1,q2,…,qH where qi=11≤i≤H if S⌢ehi≥S⌢K1≤i≤H; otherwise qi=0. Given any pair of neighboring databases D1 and D2, V1 and V2 denote the output distribution on Q when D1 and D2 are input neighbor databases, respectively. Then, (13) is satisfied (the details of the proof are shown in [15]).(13)V1QV2Q≤eє/3.
Thus, the first phase of U-PrivMining ensuresє/3-differential privacy.Theorem 9.
The second phase of U-PrivMining is2є/3-differentially private.Proof.
According to Lemma7, the sensitivity of obtaining the expected support of an itemset is equal to 1. Therefore, the sensitivity of obtaining the expected support of all frequent itemsets in H is equal to H. In H that is greater than K, according to the Laplace mechanism, the scale of the Laplace distribution, which is used to ensure differential privacy for the top K most frequent itemsets, is equal to H/є2,1. Hence, obtaining the top K most frequent itemsets ensures є2,1-differential privacy. The sensitivity of obtaining the expected supports of the top K most frequent itemsets is equal to K. According to the Laplace mechanism, the noisy data, which is used to obtain the noisy expected support of the top K frequent itemsets, obeys the Laplace distribution whose scale is equal to K/є2,2. Hence, it ensures є2,2-differential privacy for obtaining noisy expected supports of the top K most frequent itemsets for uncertain data. As a consequence, according to Lemma 4, the second phase of U-PrivMining guarantees 2є/3-differential privacy.According to analysis of the two phases of U-PrivMining, we can conclude that the first and second phases areє/3-differentially private and 2є/3-differentially private, respectively. According to Lemma 4, U-PrivMining is є-differentially private.


## 4.1. Description of U-PrivMining

The whole process of U-PrivMining is introduced in this section. U-PrivMining is composed of two phases. In the first phase, we can obtainθ so that the expected supports of the top K most frequent itemsets are greater than or equal to θ. The privacy budget allocated to this step is equal toє1=1/3·є. On the basis of traditional algorithm for mining frequent itemsets from uncertain data, we apply the sparse vector algorithm [15] and Laplace mechanism to ensure є/3-differential privacy for this phase. The steps in the first phase of U-PrivMining are as follows.Step 1.
The expected support of theKth most frequent itemset, denoted as Sk, is obtained by utilizing traditional algorithms for mining frequent itemsets based on expected support from uncertain data.Step 2.
The noisy threshold, denoted asS⌢K, can be obtained by(6)S⌢K=SK+Lap12є,where Lap12/є is the noisy data generated by the Laplace distribution, whose mean and scale are 0 and 12/є, respectively.Step 3.
On the basis of traditional algorithms for mining frequent itemsets from uncertain data, the sparse vector algorithm is applied to obtain all the frequent itemsets whose assessment expected supports are greater than or equal to the noisy thresholdS⌢K. The assessment expected support of an itemset X, denoted as S⌢eX can be obtained by(7)S⌢eX=SeX+Lap4є,where SeX is the expected support of itemset X and Lap4/є is the noisy data generated by the Laplace distribution, whose mean and scale are 0 and 4/є, respectively.Step 4.
All the frequent itemsets obtained in Step3 and the expected supports of these itemsets are taken as the output of this phase.In the second phase, according to the output of the first phase, U-PrivMining can obtain the topK most frequent itemsets for uncertain data and the noisy expected supports of these frequent itemsets. The privacy budget allocated to the second phase is equal to є2=2/3·є. The privacy budgets allocated to ensure differential privacy for the top K most frequent itemsets for uncertain data and for the expected supports of these itemsets for uncertain data are equal to є2,1=β·є2 and є2,2=1-β·є2, respectively. The second phase of U-PrivMining is described below.LetH=h1,h2,…,hH be a set of itemsets obtained in the first phase of U-PrivMining. Let Sehi1≤i≤H be the expected support of itemset hi. The steps in the second phase of U-PrivMining are as follows.Step 1 (ifH is less than or equal to K, β is equal to 0).
All the itemsets inH belong to the top K most frequent itemsets for uncertain data. And then Step 3 is directly executed.Step 2 (ifH is greater than K, β is equal to 0.5).
The perturbation expected supports of all the itemsets inH can be obtained. The perturbation expected support of itemset hi1≤i≤H, denoted as ςHi, can be obtained by(8)ςhi=Sehi+ξi,where ξ1,ξ2,…,ξHare mutually independent and drawn from the Laplace distribution, whose mean and scale are 0 and H/є2,1, respectively. The top K most frequent itemsets for the perturbation expected supports in H are the top K most frequent itemsets for uncertain data.Step 3.
LetR=r1,r2,…,rK be the set of the top K most frequent itemsets for uncertain data, which are obtained in above steps. The noisy expected supports of all the itemsets in R can be obtained. The noisy expected support of itemset ri1≤i≤K can be obtained by(9)σri=Seri+λi,where λ1,λ2,…,λKare mutually independent and drawn from the Laplace distribution whose mean and scale are equal to 0 andK/є2,2, respectively.Step 4.
The topK most frequent itemsets for uncertain data and the noisy expected supports of these itemsets are taken as the output of U-PrivMining.


## 4.2. Privacy Analysis for U-PrivMining

In this section, we prove that U-PrivMining isє-differentially private. In order to prove that U-PrivMining guarantees differential privacy, we introduce the notions of count query set and threshold query set.Definition 5 (count query set [15]).
LetS=s1,s2,…,sS be a set of itemsets with S itemsets. A count query set is composed of a number of queries. Let CQ=q1,q2,…,q|S| be the count query set, where each query qi1≤i≤|S| asks for the expected support of the ith itemset in S.Definition 6 (threshold query set [15]).
LetS=s1,s2,…,s|S| be a set of itemsets with S itemsets. A threshold query set is composed of a number of threshold queries. Let TQ=q1,q2,…,qS be the threshold query set, where each qi1≤i≤S returns 1 if S⌢si≥S⌢K1≤i≤S; otherwise qi returns 0.
According to the definition of count query set, the sensitivity of the count query and count query set can be obtained as follows.Lemma 7.
LetCQ=q1,q2,…,qH be a count query set. The sensitivity of qi1≤i≤H andCQ are equal to 1 and H, respectively.Proof.
According to (2), we can obtain the other method to compute the expected support of an itemset X, denoted as SeX, as follows [23]:(10)SeX=∑i=1n∏x∈XPx∈ti,where n is the number of records in an uncertain data T and ti1≤i≤n is a record in T. Let T and T′ be a pair of neighbor databases. Let D=t∣t∈T∩t∈T′ be the intersection of T and T′. Let T, T′, and D be the total size of T, T′, and D, respectively. Let SeTX and SeT′Xbe the expected supports of itemset X for T and T′, respectively. According to (10), the values of SeTX and SeT′X can be computed as follows:(11)SeTX=∑j=1T∏x∈XPx∈tj=∑j=1D∏x∈XPx∈tj+∏x∈XPx∈d1SeT′X=∑j=1T′∏x∈XPx∈tj=∑j=1D∏x∈XPx∈tj+∏x∈XPx∈d2⇓SeTX-SeT′X1≤1,where d1=t∣t∈T∩t∉T′ andd2=t∣t∈T′∩t∉T. As a result, the sensitivity of each query qi1≤i≤H is equal to 1. Since there are H queries inCQ, the sensitivity ofCQ is equal to H.Based on the sensitivity of the count query and count query set for uncertain data, we can conclude that U-PrivMining guaranteesє-differential privacy. The proof procedure is outlined below.Theorem 8.
The first phase of U-PrivMining isє/3-differentially private.Proof.
According to Lemma7, the sensitivity of obtaining SK is equal to 1. As a result, according to the Laplace mechanism, it is є/12-differentially private to generate the noisy threshold S⌢K. Let S⌢KD1 and S⌢KD2 be the noisy threshold for a pair of neighboring databases D1 and D2, respectively. According to Definition 1, (12) is satisfied.(12)PS⌢KD1=x≤PS⌢KD2=x·eє/12.
LetH=h1,h2,…,hH be the set of itemsets. The threshold query set is applied to model the set of answers as a vector Q=q1,q2,…,qH where qi=11≤i≤H if S⌢ehi≥S⌢K1≤i≤H; otherwise qi=0. Given any pair of neighboring databases D1 and D2, V1 and V2 denote the output distribution on Q when D1 and D2 are input neighbor databases, respectively. Then, (13) is satisfied (the details of the proof are shown in [15]).(13)V1QV2Q≤eє/3.
Thus, the first phase of U-PrivMining ensuresє/3-differential privacy.Theorem 9.
The second phase of U-PrivMining is2є/3-differentially private.Proof.
According to Lemma7, the sensitivity of obtaining the expected support of an itemset is equal to 1. Therefore, the sensitivity of obtaining the expected support of all frequent itemsets in H is equal to H. In H that is greater than K, according to the Laplace mechanism, the scale of the Laplace distribution, which is used to ensure differential privacy for the top K most frequent itemsets, is equal to H/є2,1. Hence, obtaining the top K most frequent itemsets ensures є2,1-differential privacy. The sensitivity of obtaining the expected supports of the top K most frequent itemsets is equal to K. According to the Laplace mechanism, the noisy data, which is used to obtain the noisy expected support of the top K frequent itemsets, obeys the Laplace distribution whose scale is equal to K/є2,2. Hence, it ensures є2,2-differential privacy for obtaining noisy expected supports of the top K most frequent itemsets for uncertain data. As a consequence, according to Lemma 4, the second phase of U-PrivMining guarantees 2є/3-differential privacy.According to analysis of the two phases of U-PrivMining, we can conclude that the first and second phases areє/3-differentially private and 2є/3-differentially private, respectively. According to Lemma 4, U-PrivMining is є-differentially private.


## 5. Experiments

In our experiments, four real-world scenario datasets and two synthetic datasets were utilized to verify the efficiency of U-PrivMining, which can be downloaded from [39]. The parameters of these public datasets are shown in Table 3, where the number of items in the datasets is denoted as m and the number of transactions in the dataset is denoted as n. The maximal length of transactions in the dataset is denoted as maxt. The average length of transactions in the dataset is denoted as avgt. In order to add uncertainty to these datasets, an existential random probability in the range of 0,1 is assigned to each item in each transaction.Table 3
Dataset.
Dataset
m
n
maxt
avgt
Accidents
468
340183
51
33.8
Kosarak
41270
990002
2498
8.1
Pumsb
2113
49046
74
74
Pumsb star
2088
49046
63
50.5
T10I4D100K
870
100000
29
10.1
T40I10D100K
942
100000
77
39.6


### 5.1. Evaluation Metrics

U-PrivMining applies the Laplace mechanism and the spare vector algorithm to ensure differential privacy for the topK most frequent itemsets for uncertain data and the expected supports of these frequent itemsets. The Laplace mechanism can protect the privacy of U-PrivMining’s output by adding noisy data to the output of mining frequent itemsets from uncertain data. Thus, theF-score and relative error (RE) are applied to evaluate the influence of noisy data on the experimental results.Definition 10 (F-score [15]).
LetF be the set of the top K most frequent itemsets for uncertain data and F⌢ be the set of the frequent itemsets obtained by U-PrivMining. TheF-score can be obtained by(14)F-score=2×precision×recallprecision+recall,where precision=F∩F⌢/F⌢ and recall=F∩F⌢/F.Definition 11 (relative error [15]).
LetSeX and σX be the expected support of itemset X for uncertain data and the noisy expected support of itemset X, respectively, which is obtained in the second phase of U-PrivMining. The RE can be obtained by(15)RE=medianX∈F⌢SeX-σXSeX.
As described in Definition10, for all the itemsets mined by U-PrivMining, the precision is utilized to evaluate the proportion of itemsets mined by U-PrivMining and belonging to the correct top K most frequent itemsets for uncertain data. The recall is also used to evaluate the proportion of itemsets mined by U-PrivMining and belonging to the correct top K most frequent itemsets for uncertain data. TheF-score is the harmonic mean of both precision and recall. When the number of the frequent itemsets obtained from the first phase of U-PrivMining is greater than or equal to K, the value of F and F⌢ is equal to K. As a result, the value ofF-score and recall is equal to the value of precision.As described in Definition11, the value of RE is utilized to evaluate the influence of the noisy data on the noisy expected supports of the top K most frequent itemsets for uncertain data. There may be extremely large or small values in the experimental results. The median was not skewed because these values were extremely large or small. Therefore, the median was applied to evaluate the relative error.


### 5.2. Analysis of Experimental Results

U-PrivMining can identify the topK most frequent itemsets from uncertain data in differentially private way. In traditional algorithms for mining the top K most frequent itemsets from uncertain data and certain data, the K values were predetermined by users or domain experts [7]. In order to evaluate the influence of privacy budget on theF-score and RE, we conducted four group experiments. The K values were set as 50, 100, 150, and 200, respectively.Figure1 shows the results of theF-score obtained by U-PrivMining running on the six public datasets under different privacy budget values. As it can be seen from the figure, when K value is fixed, theF-score fluctuates and is close to 1 with increasing privacy budget. In the first phase of U-PrivMining, the algorithm obtains noisy data to generate noisy threshold and assessment expected supports of itemsets. According to (6) and (7), the greater the value of the privacy budget, the smaller the scale of Laplace distribution used to generate the noisy data in this step. In the second phase of U-PrivMining, the algorithm can obtain the top K most frequent itemsets by adding noisy data to the expected support. The noisy data is drawn from the Laplace distributions, whose mean and scale are equal to 0 and H/є2,1, respectively. As a result, theF-score improves and is close to 1 with increasing privacy budget. From Figure 1, we can conclude that the lower the expected supports of the top K most frequent itemsets for the uncertain data, the lower the convergence speed of theF-score. For the T10I4D100K dataset, the expected supports of the top K most frequent itemsets are less than other datasets. Therefore, the convergence speed of U-PrivMining running on the T10I4D100K data set is lower than that of U-PrivMining running on the other datasets. U-PrivMining applied the Laplace mechanism to ensure data privacy. Hence, if the noisy data is relatively greater for the expected supports of the top K most frequent itemsets, then theF-score of U-PrivMining is relatively lower.Figure 1
F-score by varying privacy budget.
(a)
K
=
50
(b)
K
=
100
(c)
K
=
150
(d)
K
=
200Figure2 shows the RE results obtained by U-PrivMining running on six public datasets under different privacy budget values. When K is a fixed value, with increasing privacy budget, the value of RE fluctuates and is close to 0. The noisy expected support of an itemset is obtained by adding the noisy data drawn from the Laplace distribution to the expected support of the itemset. As a consequence, when the K and privacy budget values are fixed values, the expected supports of the top K most frequent itemsets for the different datasets are lower, and the RE of U-PrivMining is higher. When the privacy budget is a fixed value, and, with increasing K, the lower expected supports of the top K most frequent itemsets for different datasets, the higher RE of U-PrivMining. For the same dataset and privacy budget, RE values increase with increasing K. The noisy expected support of an itemset can be obtained by adding the noisy data drawn from the Laplace distribution to the expected support of the itemset.Figure 2
RE by varying privacy budget.
(a)
K
=
50
(b)
K
=
100
(c)
K
=
150
(d)
K
=
200


### 5.3. Discussion

In the field of medicine, for different physical conditions of patients, the same physiological index corresponds to a different symptom association probability for each patient. There are plenty of medical technologies to obtain symptom association probability for patients. There is uncertainty in patient data. However, existing algorithms for mining frequent itemsets from medical data in differentially private ways are all based on certain data and cannot be directly used for uncertain medical data. Therefore, in this paper, we proposed the U-PrivMining algorithm, which can mine the topK most frequent itemsets from uncertain medical data and ensure differential privacy. The experimental results verified the effectiveness of U-PrivMining.


## 5.1. Evaluation Metrics

U-PrivMining applies the Laplace mechanism and the spare vector algorithm to ensure differential privacy for the topK most frequent itemsets for uncertain data and the expected supports of these frequent itemsets. The Laplace mechanism can protect the privacy of U-PrivMining’s output by adding noisy data to the output of mining frequent itemsets from uncertain data. Thus, theF-score and relative error (RE) are applied to evaluate the influence of noisy data on the experimental results.Definition 10 (F-score [15]).
LetF be the set of the top K most frequent itemsets for uncertain data and F⌢ be the set of the frequent itemsets obtained by U-PrivMining. TheF-score can be obtained by(14)F-score=2×precision×recallprecision+recall,where precision=F∩F⌢/F⌢ and recall=F∩F⌢/F.Definition 11 (relative error [15]).
LetSeX and σX be the expected support of itemset X for uncertain data and the noisy expected support of itemset X, respectively, which is obtained in the second phase of U-PrivMining. The RE can be obtained by(15)RE=medianX∈F⌢SeX-σXSeX.
As described in Definition10, for all the itemsets mined by U-PrivMining, the precision is utilized to evaluate the proportion of itemsets mined by U-PrivMining and belonging to the correct top K most frequent itemsets for uncertain data. The recall is also used to evaluate the proportion of itemsets mined by U-PrivMining and belonging to the correct top K most frequent itemsets for uncertain data. TheF-score is the harmonic mean of both precision and recall. When the number of the frequent itemsets obtained from the first phase of U-PrivMining is greater than or equal to K, the value of F and F⌢ is equal to K. As a result, the value ofF-score and recall is equal to the value of precision.As described in Definition11, the value of RE is utilized to evaluate the influence of the noisy data on the noisy expected supports of the top K most frequent itemsets for uncertain data. There may be extremely large or small values in the experimental results. The median was not skewed because these values were extremely large or small. Therefore, the median was applied to evaluate the relative error.


## 5.2. Analysis of Experimental Results

U-PrivMining can identify the topK most frequent itemsets from uncertain data in differentially private way. In traditional algorithms for mining the top K most frequent itemsets from uncertain data and certain data, the K values were predetermined by users or domain experts [7]. In order to evaluate the influence of privacy budget on theF-score and RE, we conducted four group experiments. The K values were set as 50, 100, 150, and 200, respectively.Figure1 shows the results of theF-score obtained by U-PrivMining running on the six public datasets under different privacy budget values. As it can be seen from the figure, when K value is fixed, theF-score fluctuates and is close to 1 with increasing privacy budget. In the first phase of U-PrivMining, the algorithm obtains noisy data to generate noisy threshold and assessment expected supports of itemsets. According to (6) and (7), the greater the value of the privacy budget, the smaller the scale of Laplace distribution used to generate the noisy data in this step. In the second phase of U-PrivMining, the algorithm can obtain the top K most frequent itemsets by adding noisy data to the expected support. The noisy data is drawn from the Laplace distributions, whose mean and scale are equal to 0 and H/є2,1, respectively. As a result, theF-score improves and is close to 1 with increasing privacy budget. From Figure 1, we can conclude that the lower the expected supports of the top K most frequent itemsets for the uncertain data, the lower the convergence speed of theF-score. For the T10I4D100K dataset, the expected supports of the top K most frequent itemsets are less than other datasets. Therefore, the convergence speed of U-PrivMining running on the T10I4D100K data set is lower than that of U-PrivMining running on the other datasets. U-PrivMining applied the Laplace mechanism to ensure data privacy. Hence, if the noisy data is relatively greater for the expected supports of the top K most frequent itemsets, then theF-score of U-PrivMining is relatively lower.Figure 1
F-score by varying privacy budget.
(a)
K
=
50
(b)
K
=
100
(c)
K
=
150
(d)
K
=
200Figure2 shows the RE results obtained by U-PrivMining running on six public datasets under different privacy budget values. When K is a fixed value, with increasing privacy budget, the value of RE fluctuates and is close to 0. The noisy expected support of an itemset is obtained by adding the noisy data drawn from the Laplace distribution to the expected support of the itemset. As a consequence, when the K and privacy budget values are fixed values, the expected supports of the top K most frequent itemsets for the different datasets are lower, and the RE of U-PrivMining is higher. When the privacy budget is a fixed value, and, with increasing K, the lower expected supports of the top K most frequent itemsets for different datasets, the higher RE of U-PrivMining. For the same dataset and privacy budget, RE values increase with increasing K. The noisy expected support of an itemset can be obtained by adding the noisy data drawn from the Laplace distribution to the expected support of the itemset.Figure 2
RE by varying privacy budget.
(a)
K
=
50
(b)
K
=
100
(c)
K
=
150
(d)
K
=
200


## 5.3. Discussion

In the field of medicine, for different physical conditions of patients, the same physiological index corresponds to a different symptom association probability for each patient. There are plenty of medical technologies to obtain symptom association probability for patients. There is uncertainty in patient data. However, existing algorithms for mining frequent itemsets from medical data in differentially private ways are all based on certain data and cannot be directly used for uncertain medical data. Therefore, in this paper, we proposed the U-PrivMining algorithm, which can mine the topK most frequent itemsets from uncertain medical data and ensure differential privacy. The experimental results verified the effectiveness of U-PrivMining.


## 6. Conclusion

In this paper, we proposed a new algorithm to mine the topK most frequent itemsets from uncertain medical data, where each item corresponds to a patient symptom, while protecting data privacy. These frequent itemsets can assist physicians in making diagnoses. Through theoretical and experimental analyses, we can conclude that not only does U-PrivMining ensure differential privacy but, with increasing privacy budget, the top K most frequent itemsets obtained by U-PrivMining and the noisy expected supports of these frequent itemsets are close to the true top K most frequent itemsets and expected supports of these itemsets for uncertain data, respectively. However, the privacy budget allocation may not be optimal. The optimization of privacy budget allocation will be focus of future research.



---

*Source: 7545347-2017-05-11.xml*