# Privacy Protection Method for Multiple Sensitive Attributes Based on Strong Rule

Authors: Tong Yi; Minyong Shi
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

At present, most studies on data publishing only considered single sensitive attribute, and the works on multiple sensitive attributes are still few. And almost all the existing studies on multiple sensitive attributes had not taken the inherent relationship between sensitive attributes into account, so that adversary can use the background knowledge about this relationship to attack the privacy of users. This paper presents an attack model with the association rules between the sensitive attributes and, accordingly, presents a data publication for multiple sensitive attributes. Through proof and analysis, the new model can prevent adversary from using the background knowledge about association rules to attack privacy, and it is able to get high-quality released information. At last, this paper verifies the above conclusion with experiments.


---

## Body

## 1. Introduction

Data publishing is widely used in the field of information sharing and scientific research, and how to ensure the availability of data and the security of user’s privacy is the core content of studies. The data tables usually contain three types of attribute: identifier, which can identify the individual uniquely, for example, the social security number (SSN); quasi-identifier (QI), which cannot identify the individual uniquely but can provide individual information, for example, the country and age attributes; sensitive attribute (S), which is usually related to the privacy of users, for example, the disease attribute. The sensitive attribute needs to be protected in the published table. A series of data publishing methods [1–11] are presented, in order to prevent adversary from linking quasi-identifying attributes with public available dataset to reveal personal identity, and paper [1, 2] presents k-anonymity method, which partitions the table into equivalence groups (EG). Each equivalence group consists of at least k different records, and k-anonymity generalizes the quasi-identified attributes of records in the same equivalence groups. But the k-anonymity is faced with the risk of sensitive attribute disclosure due to lack of diversity. In order to solve this problem, [4] proposals L-diversity, which not only can satisfy the k-anonymity but also requires that there are at least L different sensitive attribute values in each equivalence group. In addition, privacy protection methods in [5–11] also improve the k-anonymity from different angles, respectively. But most of them only consider the situation of single sensitive attribute, so some privacy protection methods for multiple sensitive attributes are presented. Papers [12, 13] attempt to directly use L-diversity for multiple sensitive attributes, which result in a lot of information loss. Paper [14] protects users’ privacy through disturbing the order of sensitive attributes values in the same equivalence groups. But this method needs to add fake sensitive attribute values to EG, and it breaks the relationship between sensitive attributes, so useful relationships cannot be provided. The publication method in paper [15] can prevent adversary using nonmembership knowledge to attack data table, but its strict grouping condition will result in excessive information loss. According to the theory of paper [16], we can know that the publication methods of [12, 13, 15] cannot ensure good diversity and are vulnerable to background-join attack, so paper [16] divides the raw data table into several projected tables, puts the sensitive attributes which have strong dependency into the same projected table, and makes each projected table satisfy t-closeness at last. But this method ignores the association rules with high confidence, and the adversary can use the knowledge of these rules to get the privacy of users. In order to avoid the suppression of records, paper [17] presents a new publication method, which chooses to generalize each sensitive attribute, respectively. But like other privacy protection methods for multiple sensitive attributes, paper [17] ignores the inherent relationship between sensitive attributes, so the adversary can use the related background knowledge to attack privacy, and it is difficult for users to find valuable relationships from its released tables. In order to resolve this problem, this paper introduces the association rule into the design of privacy protection method and presents an improved data publishing model for multiple sensitive attributes based on the work of [17].


## 2. The Main Work of This Paper

Most existing researches on privacy preserving technology for multiple sensitive attributes have not taken the inherent relationship between sensitive attributes into account, so adversary sometimes can use the related background knowledge to attack the privacy of users, and some valuable relationships cannot be provided by released tables. Faced with this situation, we introduce the association rules into the research on data publishing. The main works of this paper are as follows.(1)
It analyses the data publishing model-Rating in paper [17], points out its weakness, and presents an attack method with strong rule (Section 3).
(2)
It takes relationship between different sensitive attributes into account, presents a mixed data publishing model based on Rating, then improves the algorithm of Rating, makes it more effective, and at last analyses and proves the correctness of the algorithm and the security of the mixed data publication model (Section4).
(3)
It proves that the new model has better quality of released information than Rating in theory (Section5).
(4)
Through the experiments, it verifies that the new data publishing model can provide better privacy, and it is able to preserve valuable relationships between sensitive attributes in released tables (Section6).


## 3. The Analysis of Rating

This section will introduce Rating [17] model briefly and present an attack method which can use strong rules to get users’ privacy from Rating.


### 3.1. Description of Symbol

TableT contains n records, record t = (
Q
I
1
,
Q
I
2
,
…
,
Q
I
i
,
S
1
,
S
2
,
…
,
S
j
), Q
I
1
,
Q
I
2
,
…
,
Q
I
i are i quasi-identifiers of T, and S
1
,
S
2
,
…
,
S
j are j sensitive attributes of T. t
.
Q
I
m
(
1
≤
m
≤
i
) represents the value of t in quasi-attribute Q
I
m. Similarly, t
.
S
m
(
1
≤
m
≤
j
) represents the value of t in sensitive attribute S
m.Definition 1 (generalization).
AssumeS is a sensitive attribute of table T, t
.
S
∈
Q, Q is a subset of S in table T, and generalization means using abstract value Q to replace specific value t
.
S. For example, in Table 1, t
1
.
S
1
=
a
1, we can use (
a
1
,
a
2
) to replace t
1
.
S
1 in Table 3.Table 1
Original table.
ID
Age
Country
S
1
S
2
S
3
1
23
China
a
1
b
1
c
2
2
35
India
a
4
b
2
c
1
3
29
Mexico
a
5
b
2
c
2
4
31
Japan
a
6
b
2
c
2
5
38
Mexico
a
1
b
1
c
2
6
23
Japan
a
1
b
1
c
1
7
36
America
a
1
b
2
c
1
8
38
America
a
2
b
5
c
2
9
21
Australia
a
2
b
2
c
1
10
36
Britain
a
2
b
3
c
1
11
22
China
a
2
b
4
c
2
12
25
India
a
4
b
3
c
2
13
23
Korea
a
5
b
4
c
1
14
33
Canada
a
6
b
1
c
1
15
36
Australia
a
3
b
2
c
2
16
38
Britain
a
3
b
5
c
1Definition 2 (L-diversity).
L is the parameter input by users. After generalization, for each sensitive S, if ∀
v
∈
t
.
S satisfies num
(
v
)
/
t
.
S
≤
1
/
L, record t satisfies L-diversity. Here num
(
v
) represents the number of v in t
.
S, and t
.
S represents the number of values in set t
.
S. If all records of model satisfy L-diversity, the model satisfies L-diversity.


### 3.2. Review of Rating

Rating generalizes each sensitive attribute, respectively, and can improve the quality of released information. Assume Table1 is the original data table, S
1
,
S
2
,
S
3 are sensitive attributes, and age and country are quasi-identifiers. L
=
2, Rating generates ID table (IDT) first, then uses the values of ID table to generalize the original data table, gets attribute table (AT), and at last releases IDT and AT. Tables 2 and 3 are IDT and AT, respectively, and both of them are released tables of Table 1.Table 2
Rating published IDT for Table1.
ID
j
S
1
S
2
S
3
ID1
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
ID2
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
ID3
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
ID4
(
a
4
,
a
5
)
(
b
2
,
b
3
)
(
c
2
,
c
1
)
ID5
(
a
3
,
a
6
)
(
b
2
,
b
5
)
(
c
2
,
c
1
)
ID6
(
a
6
,
a
5
)
(
b
4
,
b
3
)
(
c
2
,
c
1
)
ID7
(
a
3
,
a
2
)
(
b
4
,
b
1
)
(
c
2
,
c
1
)
ID8
(
a
1
,
a
4
)
(
b
5
,
b
2
)
(
c
2
,
c
1
)Table 3
Rating published AT for Table1.
ID
Age
Country
S
1
S
2
S
3
1
23
China
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
2
35
India
(
a
4
,
a
5
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
3
29
Mexico
(
a
4
,
a
5
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
4
31
Japan
(
a
3
,
a
6
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
5
38
Mexico
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
6
23
Japan
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
7
36
America
(
a
1
,
a
4
)
(
b
2
,
b
3
)
(
c
2
,
c
1
)
8
38
America
(
a
1
,
a
2
)
(
b
2
,
b
5
)
(
c
2
,
c
1
)
9
21
Australia
(
a
1
,
a
2
)
(
b
2
,
b
5
)
(
c
2
,
c
1
)
10
36
Britain
(
a
1
,
a
2
)
(
b
2
,
b
3
)
(
c
2
,
c
1
)
11
22
China
(
a
3
,
a
2
)
(
b
4
,
b
3
)
(
c
2
,
c
1
)
12
25
India
(
a
1
,
a
4
)
(
b
4
,
b
3
)
(
c
2
,
c
1
)
13
23
Korea
(
a
6
,
a
5
)
(
b
4
,
b
1
)
(
c
2
,
c
1
)
14
33
Canada
(
a
6
,
a
5
)
(
b
4
,
b
1
)
(
c
2
,
c
1
)
15
36
Australia
(
a
3
,
a
6
)
(
b
5
,
b
2
)
(
c
2
,
c
1
)
16
38
Britain
(
a
3
,
a
2
)
(
b
5
,
b
2
)
(
c
2
,
c
1
)S
i
I
D
j
(
1
≤
i
≤
3,1
≤
j
≤
8
) is a subset of sensitive attribute S
i, it satisfies that ⋃
j
=
1
8
S
i
I
D
j
=
domain
(
S
i
)
(
1
≤
i
≤
3
), domain
(
S
i
) refers to the set of all the S
i values in original table. After getting the IDT, we use the values of ID table to generalize original data table. If t
.
S
i
=
v and v
∈
S
i
I
D
j
(
1
≤
i
≤
3,1
≤
j
≤
8
), use S
i
I
D
j to replace v in original data table. For example, t
1
.
S
1
=
a
1 in Table 1, because a
1
∈
S
1
I
D
1
(
S
1
I
D
1
=
(
a
1
,
a
2
)
), and use (
a
1
,
a
2
) to replace t
1
.
S
1 in original table, so t
1
.
S
1
=
(
a
1
,
a
2
) in Table 3. AT displays the name of S
i
I
D
j in [17], and users can use the S
i
I
D
j name to get the corresponding S
i
I
D
j value in IDT. For convenient description, AT displays the S
i
I
D
j value directly in this paper.


### 3.3. The Weakness of Rating

Rating takes the generalization strategy which is suitable for multiple sensitive attributes and can improve the quality of released information. But Rating ignores the relationship between different sensitive attributes, and sometimes the users’ privacy disclosure may happen.Compared with data publishing for single sensitive attribute, multiple sensitive attributes not only mean the increase of the sensitive attributes’ number but also need more effective method to decrease the information loss, and adversary may use the relationship between sensitive attributes to attack privacy of user. So when designing the data publishing model for multiple sensitive attributes, the association rules should be taken into account. An attack method will be presented as follows.Assuming the original table can basically reflect the real world, if Bob knows his neighbor Alice is in Table3 and Alice is 23 years old and Chinese, Bob is sure that t
1 is Alice according to the quasi-identifier. Through Bob’s common sense of life or previous investigations, he knows that if event a
1 happens to someone, the probability of occurrence of b
1 is usually not less than 75%; namely, P
b
1
∣
a
1
≥
75
%. Then through the ID table Bob knows in this table that there are four people whose attribute S
1 values are a
1, so in these four people, there are at least three whose attribute S
2 values must be b
1. That is to say, there are at least three people whose S
1 values are a
1 while their S
2 values are b
1.So Bob begins to analyze attribute table, and he finds out that there are 8 records whoseS
1 value may be a
1, and these 8 records are t
1
,
t
5
,
t
6
,
t
7
,
t
8
,
t
9
,
t
10
,
t
12, but in these records, only 3 records’ S
2 values may be b
1, and these three records are t
1
,
t
5
,
t
6, respectively. Then Bob can be sure that t
1
.
S
1
=
t
5
.
S
1
=
t
6
.
S
1
=
a
1, t
1
.
S
2
=
t
5
.
S
2
=
t
6
.
S
2
=
b
1. And t
1 is Alice, so the privacy of Alice is disclosed.The above is an example of attack with association rules. Because Rating has not taken the correlation between sensitive attributes into account, if adversary masters corresponding background knowledge, the privacy of user may be disclosed. So in the next section, an improved model will be presented.


## 3.1. Description of Symbol

TableT contains n records, record t = (
Q
I
1
,
Q
I
2
,
…
,
Q
I
i
,
S
1
,
S
2
,
…
,
S
j
), Q
I
1
,
Q
I
2
,
…
,
Q
I
i are i quasi-identifiers of T, and S
1
,
S
2
,
…
,
S
j are j sensitive attributes of T. t
.
Q
I
m
(
1
≤
m
≤
i
) represents the value of t in quasi-attribute Q
I
m. Similarly, t
.
S
m
(
1
≤
m
≤
j
) represents the value of t in sensitive attribute S
m.Definition 1 (generalization).
AssumeS is a sensitive attribute of table T, t
.
S
∈
Q, Q is a subset of S in table T, and generalization means using abstract value Q to replace specific value t
.
S. For example, in Table 1, t
1
.
S
1
=
a
1, we can use (
a
1
,
a
2
) to replace t
1
.
S
1 in Table 3.Table 1
Original table.
ID
Age
Country
S
1
S
2
S
3
1
23
China
a
1
b
1
c
2
2
35
India
a
4
b
2
c
1
3
29
Mexico
a
5
b
2
c
2
4
31
Japan
a
6
b
2
c
2
5
38
Mexico
a
1
b
1
c
2
6
23
Japan
a
1
b
1
c
1
7
36
America
a
1
b
2
c
1
8
38
America
a
2
b
5
c
2
9
21
Australia
a
2
b
2
c
1
10
36
Britain
a
2
b
3
c
1
11
22
China
a
2
b
4
c
2
12
25
India
a
4
b
3
c
2
13
23
Korea
a
5
b
4
c
1
14
33
Canada
a
6
b
1
c
1
15
36
Australia
a
3
b
2
c
2
16
38
Britain
a
3
b
5
c
1Definition 2 (L-diversity).
L is the parameter input by users. After generalization, for each sensitive S, if ∀
v
∈
t
.
S satisfies num
(
v
)
/
t
.
S
≤
1
/
L, record t satisfies L-diversity. Here num
(
v
) represents the number of v in t
.
S, and t
.
S represents the number of values in set t
.
S. If all records of model satisfy L-diversity, the model satisfies L-diversity.


## 3.2. Review of Rating

Rating generalizes each sensitive attribute, respectively, and can improve the quality of released information. Assume Table1 is the original data table, S
1
,
S
2
,
S
3 are sensitive attributes, and age and country are quasi-identifiers. L
=
2, Rating generates ID table (IDT) first, then uses the values of ID table to generalize the original data table, gets attribute table (AT), and at last releases IDT and AT. Tables 2 and 3 are IDT and AT, respectively, and both of them are released tables of Table 1.Table 2
Rating published IDT for Table1.
ID
j
S
1
S
2
S
3
ID1
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
ID2
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
ID3
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
ID4
(
a
4
,
a
5
)
(
b
2
,
b
3
)
(
c
2
,
c
1
)
ID5
(
a
3
,
a
6
)
(
b
2
,
b
5
)
(
c
2
,
c
1
)
ID6
(
a
6
,
a
5
)
(
b
4
,
b
3
)
(
c
2
,
c
1
)
ID7
(
a
3
,
a
2
)
(
b
4
,
b
1
)
(
c
2
,
c
1
)
ID8
(
a
1
,
a
4
)
(
b
5
,
b
2
)
(
c
2
,
c
1
)Table 3
Rating published AT for Table1.
ID
Age
Country
S
1
S
2
S
3
1
23
China
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
2
35
India
(
a
4
,
a
5
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
3
29
Mexico
(
a
4
,
a
5
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
4
31
Japan
(
a
3
,
a
6
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
5
38
Mexico
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
6
23
Japan
(
a
1
,
a
2
)
(
b
1
,
b
2
)
(
c
2
,
c
1
)
7
36
America
(
a
1
,
a
4
)
(
b
2
,
b
3
)
(
c
2
,
c
1
)
8
38
America
(
a
1
,
a
2
)
(
b
2
,
b
5
)
(
c
2
,
c
1
)
9
21
Australia
(
a
1
,
a
2
)
(
b
2
,
b
5
)
(
c
2
,
c
1
)
10
36
Britain
(
a
1
,
a
2
)
(
b
2
,
b
3
)
(
c
2
,
c
1
)
11
22
China
(
a
3
,
a
2
)
(
b
4
,
b
3
)
(
c
2
,
c
1
)
12
25
India
(
a
1
,
a
4
)
(
b
4
,
b
3
)
(
c
2
,
c
1
)
13
23
Korea
(
a
6
,
a
5
)
(
b
4
,
b
1
)
(
c
2
,
c
1
)
14
33
Canada
(
a
6
,
a
5
)
(
b
4
,
b
1
)
(
c
2
,
c
1
)
15
36
Australia
(
a
3
,
a
6
)
(
b
5
,
b
2
)
(
c
2
,
c
1
)
16
38
Britain
(
a
3
,
a
2
)
(
b
5
,
b
2
)
(
c
2
,
c
1
)S
i
I
D
j
(
1
≤
i
≤
3,1
≤
j
≤
8
) is a subset of sensitive attribute S
i, it satisfies that ⋃
j
=
1
8
S
i
I
D
j
=
domain
(
S
i
)
(
1
≤
i
≤
3
), domain
(
S
i
) refers to the set of all the S
i values in original table. After getting the IDT, we use the values of ID table to generalize original data table. If t
.
S
i
=
v and v
∈
S
i
I
D
j
(
1
≤
i
≤
3,1
≤
j
≤
8
), use S
i
I
D
j to replace v in original data table. For example, t
1
.
S
1
=
a
1 in Table 1, because a
1
∈
S
1
I
D
1
(
S
1
I
D
1
=
(
a
1
,
a
2
)
), and use (
a
1
,
a
2
) to replace t
1
.
S
1 in original table, so t
1
.
S
1
=
(
a
1
,
a
2
) in Table 3. AT displays the name of S
i
I
D
j in [17], and users can use the S
i
I
D
j name to get the corresponding S
i
I
D
j value in IDT. For convenient description, AT displays the S
i
I
D
j value directly in this paper.


## 3.3. The Weakness of Rating

Rating takes the generalization strategy which is suitable for multiple sensitive attributes and can improve the quality of released information. But Rating ignores the relationship between different sensitive attributes, and sometimes the users’ privacy disclosure may happen.Compared with data publishing for single sensitive attribute, multiple sensitive attributes not only mean the increase of the sensitive attributes’ number but also need more effective method to decrease the information loss, and adversary may use the relationship between sensitive attributes to attack privacy of user. So when designing the data publishing model for multiple sensitive attributes, the association rules should be taken into account. An attack method will be presented as follows.Assuming the original table can basically reflect the real world, if Bob knows his neighbor Alice is in Table3 and Alice is 23 years old and Chinese, Bob is sure that t
1 is Alice according to the quasi-identifier. Through Bob’s common sense of life or previous investigations, he knows that if event a
1 happens to someone, the probability of occurrence of b
1 is usually not less than 75%; namely, P
b
1
∣
a
1
≥
75
%. Then through the ID table Bob knows in this table that there are four people whose attribute S
1 values are a
1, so in these four people, there are at least three whose attribute S
2 values must be b
1. That is to say, there are at least three people whose S
1 values are a
1 while their S
2 values are b
1.So Bob begins to analyze attribute table, and he finds out that there are 8 records whoseS
1 value may be a
1, and these 8 records are t
1
,
t
5
,
t
6
,
t
7
,
t
8
,
t
9
,
t
10
,
t
12, but in these records, only 3 records’ S
2 values may be b
1, and these three records are t
1
,
t
5
,
t
6, respectively. Then Bob can be sure that t
1
.
S
1
=
t
5
.
S
1
=
t
6
.
S
1
=
a
1, t
1
.
S
2
=
t
5
.
S
2
=
t
6
.
S
2
=
b
1. And t
1 is Alice, so the privacy of Alice is disclosed.The above is an example of attack with association rules. Because Rating has not taken the correlation between sensitive attributes into account, if adversary masters corresponding background knowledge, the privacy of user may be disclosed. So in the next section, an improved model will be presented.


## 4. The Data Publishing for Multiple Sensitive Attributes Based on Strong Rules

In this section, we introduce the association rules and present a new data publishing model which can avoid attacking with strong rules between sensitive attributes. The records are divided into two categories; each category will be processed by different data publishing models, respectively. So this new data publishing model for multiple sensitive attributes is actually a mixed model.


### 4.1. Data Publishing Method Based on Sensitive Attributes Clustering (SAC)

The original data tableT will be divided into two tables: table SAC and table IR, process the two tables, respectively. This part introduces the division of table T and the processing of table SAC. We will introduce some definitions and parameters first.Definition 3 (association rules).
Assume that when eventA happens, the probability of occurrence of event B is s
(
0
≤
s
≤
1
); namely, A ⇒ B
:
s. A
⇒
B is an association rule.Definition 4 (support degree).
It represents the number of occurrences of an event. For example, in Table1, the number of a
1 is 4, so the support degree of a
1 is 4. Namely, support
(
a
1
)
=
4. support
(
a
1
,
b
1
) especially represents the simultaneity number of a
1 and b
1. In Table 1, there are 3 records satisfying t
.
S
1
=
a
1, t
.
S
2
=
b
1, so support
(
a
1
,
b
1
)
=
3.Definition 5 (confidence).
Assume whenA happens, the probability of occurrence of event B is s
(
0
≤
s
≤
1
), so the confidence of A
⇒
B is s. For example, in Table 1, there are 4 records whose S
1 values are a
1, and three of them have S
2 value b
1. So when a
1 appears, the probability of occurrence of b
1 is 3/4. Namely, confidence
(
a
1
⇒
b
1
)
=
3
/
4. It is not difficult to prove that confidence
(
a
1
⇒
b
1
)
=
support
(
a
1
,
b
1
)
/
support
(
a
1
).Usually we set minimum support degree threshold (min_support) and the minimum confidence threshold (min_confidence); if an association rule satisfies both these two thresholds, the rule is meaningful. In this paper, as long as one sensitive attribute valuev appears once, adversary may use it to attack the privacy of users, so the min_support is set to 1. And the min_confidence is set by users.Definition 6 (strong rule).
Assuming association ruleA
⇒
B [confidence = s
(
0
≤
s
≤
1
)], s ≥ min_confidence, so we call A
⇒
B strong rule.Usually the strong rule’s confidence is relatively higher, and adversary may use the strong rule to attack users’ privacy if adversary has the related background knowledge. On the other hand, we hope to preserve information of strong rule in the released data, because it is valuable. So we need to put the records containing strong rules into table SAC and process table SAC with consideration for strong rule. Record containing strong rules means that, for recordt, if ∃
t
.
S
x
,
t
.
S
y
(
1
≤
x
,
y
≤
j
), t
.
S
x
⇒
t
.
S
y is a strong rule, so record t contains strong rule. And for a value v, if there is a strong rule that A
⇒
B satisfies v
=
A or v
=
B, we call v strong value.


#### 4.1.1. Partition Table

Assuming the association rules in original data table are close to the situation of the real world, first use classic association rule mining algorithm-Apriori [18] to find out all the strong rules in table, according to min_confidence set by user (line 1). Then find a sensitive attribute S that has the largest number of strong values, put all other sensitive attributes into S
_
set
~, and if a record contains strong value in S
_
set
~, add it to table SAC (line 2). At last delete the records contained by SAC in original table, and get table IR (line 3), so the original table T is divided into two tables: SAC and IR. Obviously, the records which all contain strong association rules are in SAC, and all the strong values in IR belong to the same sensitive attribute, so there are no probability tilts caused by strong association rules in IR (please see Section 4.2.2).Algorithm 7 (partition table).
Input: original data tableT, min_confidence
Output: Table SAC, Table IR
(1) Accoding to min_confidence find out all strong rules with Apriori.
(2) Find the records which all contain strong values inS
_
set
~, and put them into table SAC.
(3) Table IR =T-Table SAC.


#### 4.1.2. Partition Sensitive Attributes

After partition table, begin to process the table SAC. In order to preserve the information of strong rules, cluster the sensitive attributes. First, we need to define the distance between sensitive attributes.Definition 8 (distance between sensitive attributes).
Given two sensitive attributesS
x, S
y
(
1
≤
x
,
y
≤
j
), the distance between the two sensitive attributes can be defined as(1)distanceSx,Sy=1,there  are  no  strong  rules  betweenSxandSy,0,there  are  strong  rules  betweenSxandSy.Here, if ∃
v
x
∈
domain
(
S
x
)
,
∃
v
y
∈
domain
(
S
y
), v
x
⇒
v
y, or v
y
⇒
v
x is strong rule, we say there are strong rules between S
x and S
y; else, there are no strong rules between S
x and S
y.Definition 9 (distance between sensitive attribute and cluster).
AssumingC is a cluster, S
x
(
1
≤
x
≤
j
) is a sensitive attribute, and the distance between C and S
x can be defined as(2)distanceSx,C=1,∀Sy∈C1≤y≤j,distacneSx,Sy=1,0,∃Sy∈C1≤y≤j,distacneSx,Sy=0.In this method, put the similar sensitive attributes into a same cluster, as long as the set of sensitive attributes is not empty, and generate new cluster constantly (line 1). For each new empty clusterC, pick a sensitive attribute S
x
(
1
≤
x
≤
j
) from sensitive attribute set S
_
set orderly, put S
x into C, and S
x is the first attribute of cluster C (line 2). Find out all such sensitive attributes S
y
∈
S
_
set
(
1
≤
y
≤
j
), and S
y satisfies that distance
(
S
y
,
C
)
=
0. Add S
y to C, and delete S
y in S
_
set (line 3 to line 4). Similarly, generate other clusters.After Algorithm10, we get the set of clusters: Cluster_Set = C
1
,
C
2
,
…
,
C
m, ∀
C
∈
Cluster
_
Set, and C is a subset of sensitive attributes set S
_
set = S
1
,
S
2
,
…
,
S
j.AssumingC
∈
Cluster
_
Set, C
=
S
x
,
S
y
,
S
z
(
1
≤
x
,
y
,
z
≤
j
), record t
∈
SAC, and the C value of t is t
.
C
=
(
t
.
S
x
,
t
.
S
y
,
t
.
S
z
).Algorithm 10 (partition sensitive attributes).
Input: Table SAC
Output: set of sensitive attributes’ cluster (Cluster_Set)
S
_
set is the set of sensitive attributes, S
_
set = S
1
,
S
2
,
…
,
S
j.
(1) While theS
_
set is not empty, repeat (2) to (5).
(2) Generate clusterC, add the first sensitive attribute S
x
(
1
≤
x
≤
j
) to C, S
_
set - S
x.
(3) For eachS
y
∈
S
_
set
(
1
≤
y
≤
j
), do (4).
(4) If distance(C
,
S
y) = 0, add S
y to C, S
_
set -S
y.
(5)Cluster
_
set
∪
C.


#### 4.1.3. Partition Records

This part will divide the Table SAC into several groups and anonymize the records in the same group.Algorithm 11 (partition records).
Input: Table SAC, Table IR, and Cluster_Set,L
Output: released Table SAC~
(1) While Table SAC is not empty, repeat (2) to (7).
(2) Generate a new groupG.
(3) Choose a recordt from Table SAC orderly, G
∪
t, SAC-t.
(4) WhileG
<
L, repeat (5) to (6).
(5) If∃
t
~
∈
SAC, this satisfies ∀
t
∈
G
,
1
≤
∀
x
≤
j
,
t
~
.
S
x
≠
t
.
S
x
,
G
∪
t
~, and SAC-t
~.
(6) Else choose recordt
~ from table IR orderly, t
~ satisfies ∀
t
∈
G
,
1
≤
∀
x
≤
j
,
t
~
.
S
x
≠
t
.
S
x,  G
∪
t
~, and IR-t
~.
(7)S
A
C
~
∪
G
(8) Permutate cluster values in each group randomly.In the algorithm of partition records, while table SAC is not empty, generate group constantly (lines 1-2). For each empty groupG, choose a record t from table SAC as G’s first record (line 3). Choosing t
~
∈
SAC, or t
~
∈
IR, t
~ does not have the same sensitive attributes values with G, and add t
~ to G, until the number of records in G is not less than L (line 4–6). Within each group, sensitive attributes values are permutated randomly in each cluster to break the linking between different clusters (line 8). That is to say, adjust the position of cluster values randomly. Finally, release S
A
C
~.Now take Table1 as an example, there are three steps on this process. Here, assume that L
=
2, min_confidence = 0.75.(1)
Partition table: both S
1 and S
2 have four strong values, and S
3 has no values, so S
_
set
~
=
S
1
,
S
3. We first find out that there are 4 records containing strong values in S
_
set
~, and they are t
1
,
t
5
,
t
6, and t
7, respectively. These 4 records make up table SAC (Table 4) and meanwhile, delete these 4 records in Table 1.
(2)
Partition sensitive attributes: generate a new cluster C
1, add S
1 to C
1, and now there remain two sensitive attributes in sensitive attributes set. Because there is strong rule a
1
⇒
b
1 between S
1 and S
2 and distance
(
C
1
,
S
2
)
=
0, add S
2 to C
1. But both distance
(
S
1
,
S
3
) and distance
(
S
2
,
S
3
) are 1, distance
(
C
1
,
S
3
)
=
1, S
3 cannot be added to C
1. And the only one attribute S
3 in sensitive attributes set makes up a cluster C
2 alone. So clustering is over, and we get two clusters C
1
=
S
1
,
S
2, C
2
=
S
3.
(3)
Partition records: according to the grouping condition, it cannot have the same sensitive attribute values in a group, t
1 and t
2 make up a group, similarly, and t
5 and t
9, t
6 and t
4, t
7 and t
8 make up groups, respectively (Table 5). After grouping, randomly permutate the cluster values in the same groups and release the table SAC~ (Table 6). For example, in group 1, permutate C
1 value (
a
1
,
b
1
), (
a
4
,
b
2
) randomly. Here, each group has two records, according to the random principle; after disturbing order, (
a
1
,
b
1
) may swap position with (a
4
,
b
2), or both (a
1
,
b
1) and (a
4
,
b
2) remain in the original positions. Similarly, for C
2, permutate C
2 value, c
1, c
2, randomly. Although through anonymity, the relationship between S
1 and S
2 is still preserved. On the other hand, linking between C
1 and C
2 has been broken. So this method preserves the links between sensitive attributes in the same clusters and breaks the links between sensitive attributes from different clusters.Table 4
The SAC table.
ID
Age
Country
S
1
S
2
S
3
1
23
China
a
1
b
1
c
2
5
38
Mexico
a
1
b
1
c
2
6
23
Japan
a
1
b
1
c
1
7
36
America
a
1
b
2
c
1Table 5
Partition records for Table4.
ID
Age
Country
S
1
S
2
S
3
Group ID
1
23
China
a
1
b
1
c
2
1
2
35
India
a
4
b
2
c
1
1
5
38
Mexico
a
1
b
1
c
2
2
9
21
Australia
a
2
b
2
c
1
2
6
23
Japan
a
1
b
1
c
1
3
4
31
Japan
a
6
b
2
c
2
3
7
36
America
a
1
b
2
c
1
4
8
38
America
a
2
b
5
c
2
4Table 6
Mixed model published SAC~ for Table 1.
ID
Age
Country
S
1
S
2
S
3
Group ID
1
23
China
a
4
b
2
c
2
1
2
35
India
a
1
b
1
c
1
1
5
38
Mexico
a
1
b
1
c
1
2
9
21
Australia
a
2
b
2
c
2
2
6
23
Japan
a
6
b
2
c
2
3
4
31
Japan
a
1
b
1
c
1
3
7
36
America
a
2
b
5
c
1
4
8
38
America
a
1
b
2
c
2
4Lemma 12.
Assuming adversary has the background knowledge about strong rules, for∀
t
∈
T, ∀
r
∈
S
t
r
o
n
g
_
R
u
l
e
_
S
e
t
(
T
), r
:
A
⇒
B, adversary is sure that t contains r with the probability:(3)Pt:A⟹B≤1L.
Here,S
t
r
o
n
g
_
R
u
l
e
_
S
e
t
(
T
) represents the set of strong rules in table T.Proof.
Ift
∈
IR, there are no records containing strong rules in table IR, so P
(
t
:
A
⇒
B
)
=
0. If t
∈
S
A
C
~, for each group G in S
A
C
~, G has at least L records; if there is record containing A
⇒
B in G, according to the nature of random permutation, each record in G contains A
⇒
B with equality probability 1
/
L, so we can know that even though adversary can be clear of how many records contain A
⇒
B through related background knowledge, P
(
t
:
A
⇒
B
) is not more than 1
/
L.In the example of Section3.3, for some records, adversary can make sure that they contain strong rules with probability 100%. S
A
C
~ table can prevent adversary from using strong rules to attack users’ privacy.


### 4.2. Improved Rating (IR)

The table IR will be processed by improved Rating. For each sensitive attributeS, Rating [17] hashes t
.
S in S by their values (each bucket corresponds to each value), and if S has m different values (v
1
,
v
2
,
…
,
v
m), it can get sequence = b
u
c
k
e
t
1
,
b
u
c
k
e
t
2
,
…
,
b
u
c
k
e
t
m, and assuming there are n
v
i
(
1
≤
i
≤
m
) in S, so the corresponding bucketi contains n
v
i in it. Every time Rating chooses the L buckets that have the largest size, gets a value from every one of these L buckets to make up a SID, uses SID to replace corresponding sensitive attribute values in original table, and gets attribute table, and the SID makes up ID table. Every time Rating generates an SID, it needs to reselect L buckets, because after the last generation of SID, the sizes of buckets have been updated. Paper [17] has not presented the algorithm of choosing L largest buckets, so this paper will present a heuristic algorithm of choosing buckets.


#### 4.2.1. Heuristic Algorithm for Choosing Buckets

This heuristic algorithm (Algorithm13) is actually a stable sorting algorithm, sort sequence in descending order, and choose the first L buckets from sequence. This algorithm will be called after updating the size of buckets. Let us introduce some parameters, and sequence[i] refers to the i
(
1
≤
i
≤
m
) bucket in the sequence:sequence[i].value: the attribute value in sequence[i],
sequence[i].size: the size of sequence[i],
sequence[i].size~: after updating size, the size of sequence[i], if 1
≤
i
≤
L, sequence[i].size~ = sequence[i].size-1; if L
<
i
≤
m, sequence[i].size~ = sequence[i].size,
sequence[i].position: the position of sequence[i], sequence[i].position = i,
sequence[i].position~: after sorting, the new position of sequence[i].Algorithm 13 (heuristic choosingL largest buckets).
Input: sequence,L,
Output: sequence satisfies stable descending order,
(1) If sequence[L].size~ < sequence[L
+
1].size~, do (2) to (5).
(2) Fori
=
1; i
<
L
+
1; i
+
+, repeat (3) to (5)
(3) If sequence[i].size~ < sequence[L
+
1].size~, do (4) to (5).
(4) Find sequence[j] and sequence[j
+
1] which satisfy sequence[j].size~ > sequence[i].size~ ≥ sequence[j
+
1]. size~
(5) removeQ = sequence
[
i
]
,
sequence
[
i
+
1
]
,
…
,
sequence
[
L
] to the position between sequence[j] and sequence[j
+
1]; meanwhile keep the relative position among Q, end loop.If the sequence always satisfies the stable descending order, there are Lemmas14 and 15 and Corollaries 16 and 17, and we will prove the correctness of algorithm.Lemma 14.
After updating size of buckets, if sequence[
L
].size~ ≥ sequence[
L
+
1
].size~, the position of all buckets in sequence does not need to be adjusted.Proof.
Using proof by contradiction, only the sizes ofsequence
[
1
]
,
sequence
[
2
]
,
…
,
sequence
[
L
] have been changed, so these buckets may need to adjust their position in the sequence. If sequence[i] (1
≤
i
<
L) needs to be removed to the back of sequence[j] (L
<
j
≤
m), then sequence[j].size~ > sequence[i].siz
e
~ and sequence[L
+
1].size~ ≥ sequence[j].siz
e
~ > sequence[i].size~. Because sequence[i].size ≥ sequence[L].size, and after generation, in both the sizes of sequence[i] and sequence[L] minus 1, there is sequence[i].size~ ≥ sequence[L].size~, we can get the contradictory conclusion:(4)sequenceL+1.size~>sequenceL.size~.Lemma 15.
If sequence[
j
].size~ > sequence[
i
].size~ ≥ sequence[
j
+
1
]
.
s
i
z
e
~
(
1
≤
i
,
i
+
1
≤
L
,
L
<
j
,
j
+
1
≤
m
), in order to preserve stable descending order, there are sequence[
j
].position~ < sequence[
i
].p
o
s
i
t
i
o
n
~ < sequence[
j
+
1
].p
o
s
i
t
i
o
n
~ and sequence[
i
+
1
]. position~ = sequence[
i
]
.
p
o
s
i
t
i
o
n
~
+
1.Proof.
Obviously, according to the nature of stable descending sorting, the new position of sequence[i] is between sequence[j] and sequence[j
+
1]. Here we will discuss the new position of sequence[i
+
1]. In addition to the situation in Lemma 15, the new position of sequence[i
+
1] has two possibilities, using the contradiction to proof, respectively.(1)
After adjusting, the position of sequence[i
+
1] will be sequence[i
+
1].position~ and sequence[i
+
1].position~ < sequence[i].position~. According to the nature of descending order, before generating SID, sequence[i].size ≥ sequence[i
+
1].size and sequence[i].position < sequence[i
+
1].position, after generating SID, in both the sizes of sequence[i] and sequence[i
+
1] minus 1, one has sequence[i].size~ ≥ sequence[i
+
1].size~. So sequence[i
+
1].position~< sequence[i].position~ contradicts the nature of stable descending order.
(2)
After adjusting, the position of sequence[i
+
1] will be sequence[i
+
1].position~, sequence[i
+
1].position~ > sequence[i].position~, and existing set Q
=
sequence
k
∣
1
≤
k
≤
m, and each sequence[k] ∈
Q satisfies that sequence[i].position~ < sequence[k].position~ < sequence[i
+
1].position~. If 1
≤
k
≤
L, according to the nature of stable descending order, sequence[i].size~ ≥ sequence[k].size~ ≥ sequence[i
+
1].size~, sequence[i].size ≥ sequence[k].size ≥ sequence[i
+
1].size, sequence[i].position < sequence[k].position < sequence[i
+
1].position, and we can get the contradictory conclusions: i
<
k
<
i
+
1. In another situation, if L
<
k
≤
m, one must have sequence[i].size~ ≥ sequence[k].size~ > sequence[i
+
1].size~ and sequence[k].size = sequence[i
+
1].size ≥ sequence[j].size; because the sizes of sequence[j] and sequence[k] have not changed, there is sequence[k].size~ ≥ sequence[j].size~, so we can get the contradictory conclusions: sequence[i].size~ ≥ sequence[j].size~.Corollary 16.
If sequence[
i
].size~ < sequence[
L
+
1
].size~, the new position of sequence[
i
] will be sequence[
i
].position~; for each sequence[
k
]
(
i
<
k
≤
L
), its new position is as follows: sequence[
k
].position~ = sequence[
i
].position~ + (
k
-
i
).Proof.
According to Lemma15, sequence[i
+
1].position~ = sequence[i].position~ + 1; for each sequence[k] (
i
<
k
≤
L), there exists sequence[k].position~ = sequence[k
-
1].position~ + 1, so for each sequence[k] (i
<
k
≤
L), it satisfies(5)sequencek.position~=sequencei.position~+k-i.Corollary 17.
After updating size of bucket, if sequence[
j
].size~ > sequence[
i
].size~ ≥ sequence[
j
+
1
].size~
(
L
<
j
,
j
+
1
≤
m
), here i
=
1 or (
1
<
i
≤
L, sequence[
i
-
1
].size~ ≥ sequence[
L
+
1
].size~
); to make sequence satisfy the stable descending order, one only needs to remove Q = sequence[
i
], s
e
q
u
e
n
c
e
[
i
+
1
]
,
…
,
s
e
q
u
e
n
c
e
[
L
] to the position between sequence[
j
] and sequence[
j
+
1
].Proof.
After updating size, only sizes ofsequence
[
1
]
,
sequence
[
2
]
,
…
,
sequence
[
L
] have changed, so only the positions of sequence
[
1
]
,
sequence
[
2
]
,
…
,
sequence
[
L
] may need to be adjusted. According to the nature of stable descending order sequence[
i].position~ = sequence[j].position~ + 1; according to Corollary 16, sequence[k].position~ = sequence[i].position~ + (k
-
i), (i
<
k
≤
L), and sequence[j
+
1].position~ = sequence[L].position~ + 1. So removing sequence[i], sequence
[
i
+
1
]
,
…
,
sequence
[
L
] to the position between sequence[j] and sequence[j
+
1] can make sequence satisfy stable descending order.
Here one analyzes the efficiency of this sorting algorithm. In the best situation, sequence[L].size~ ≥ sequence[L
+
1].size~, it only needs to compare sequence[L].size~ with sequence[L
+
1].size~ in this algorithm, and the time complexity is O
(
1
). The worst situation is that sequence[1].size~ < sequence[m].size~, the algorithm needs to compare m
-
L
+
1 times, and the time complexity is O
(
m
-
L
+
1
). The efficiency of this sorting algorithm is much better than most of existing sorting algorithms.


#### 4.2.2. SID Creation

This part will introduce the algorithm of creating SID. The definition of dangerous bucket will be introduced as follows.Definition 18 (dangerous bucket).
Assuming sequence is in sensitive attributeS, for each bucket B
∈
sequence, if B
.
size
/
n
≥
1
/
L, B is a dangerous bucket in S. Here, n is size of the domain (S).The SID creation can be seen in Algorithm19. For each sensitive attribute S
i, one generates its sequence and removes the dangerous buckets from sequence to SDB. Every time one generates a new S
i
I
D
j, for each bucket in SDB, removes one value from it to S
i
I
D
j (line 6), for each bucket of sequence[1], sequence[2], …, sequence[L-SDB] which have largest size, removes a value from it to S
i
I
D
j (line 7). When a S
i
I
D
j is completed, call for Algorithm 13 to sort the sequence. In the step of processing residual values, for each value v in a nonempty bucket, remove v to a S
i
I
D
j which does not contain value v (line 9).Algorithm 19 (SID creation).
Input:L, IR table
Output:S
i
I
D
j
(1) For each sensitive attributeS
i, do (2) to (9).
(2) Generate sequence.
(3) Find the dangerous buckets, and put them in SDB.
(4) Remove the dangerous buckets in sequence;
(5) When there are at leastL-SDB buckets in sequence which are not empty, generate a new S
i
I
D
j repeat (6) to (8).
(6) For each bucket in SDB, remove a value toS
i
I
D
j.
(7) For each bucket fromsequence[1], sequence[2], …, sequence[L-SDB
], remove a value to S
i
I
D
j;
(8) Call for Algorithm13 and use sequence and L-SDB as input; //processes the residual attribute values
(9) For each valuev in nonempty buckets, find a S
i
I
D
j which contains no value v, and remove v to S
i
I
D
j. If one cannot find this S
i
I
D
j, value v cannot be grouped.Lemma 20.
If bucketB is a dangerous bucket in sensitive attribute S
i, after completing a new S
i
I
D
j, B is still a dangerous bucket.Proof.
After completing a newS
i
I
D
j, the frequency of B.value is B
.
size
-
1
/
n
-
L, and n is the size of domain
(
S
i
). Before generating the new S
i
I
D
j, the frequency of B.value was B
.
size
/
n. If there is B
.
size
-
1
/
n
-
L
≥
B
.
size
/
n, Lemma 20 can be proved.
The left side of the equation is equal to(
B
.
size
-
1
)
∗
n
/
(
n
-
L
)
∗
n, and the right side of the equation is equal to B
.
size
∗
(
n
-
L
)
/
n
∗
(
n
-
L
); one only needs to prove that(6)B.size-1∗n≥B.size∗n-L.Because before generating the new S
i
I
D
j, B was dangerous bucket, and satisfied B
.
size
/
n
≥
1
/
L, has B
.
s
i
z
e
∗
L
≥
n, B
.
s
i
z
e
∗
n
-
n
≥
B
.
s
i
z
e
∗
n
-
B
.
s
i
z
e
∗
L so we can get (7)B.size-1∗n≥B.size∗n-L.Corollary 21.
If bucketB is a dangerous bucket, after completing a new S
i
I
D
j, B is still one of the L buckets which have the largest size.Proof.
Using proof by contradiction, if there is Set =bucket1, bucket2, …, b
u
c
k
e
t
L, for each bucket
∈
Set, it has larger size than B. According to Lemma 20, after generating a new S
i
I
D
j, the B
.
s
i
z
e
~
/
n
≥
1
/
L, so bucket satisfies b
u
c
k
e
t
.
s
i
z
e
~
/
n
≥
1
/
L, so there has(8)bucket1.size~n+bucket2.size~n+⋯+bucketL.size~n+B.size~n>1.
Get the contradictory conclusions:(9)bucket1.size~+bucket2.size~+⋯+bucketL.size~+B.size~>n.
From the above certification, we can find out that the dangerous bucket is always one of theL largest buckets, so each new S
i
I
D
j should take one value of dangerous bucket, and it does not need to consider dangerous bucket for sorting sequence. This method further improves the efficiency of the algorithm.
Besides, in this improved Rating, the algorithm for AT&IDT Creation is the same as in Rating, usesS
i
I
D
j to generalize corresponding value in IR table, after processing IR, gets AT, and then uses the set of S
i
I
D
j to make up IDT. At last release AT and IDT with the previous SAC~ table.
Here we assume adversary masters strong rules and summarize the security of mixed model. For released table SAC~, because each group contains at least L records without the same values and refers to Lemma 12, it is easy to know that SAC~ satisfy L-diversity. For released AT, we will discuss a problem of probability tilts first. For record t, after generalization if ∃
v
1
∈
t
.
S
x, ∃
v
2
∈
t
.
S
y
(
1
≤
x
,
y
≤
j
) satisfy v
1
⇒
v
2 which is a strong rule, there will be probability tilt between t
.
S
x and t
.
S
y obviously. And according to the method of partition table, all the strong values in AT belong to the same sensitive attribute, so the probability tilts will not happen in AT. Besides, each S
i
I
D
j consists of at least L different values, so AT also satisfies L-diversity. And through the above analysis, we know that mixed model is able to satisfy L-diversity.


## 4.1. Data Publishing Method Based on Sensitive Attributes Clustering (SAC)

The original data tableT will be divided into two tables: table SAC and table IR, process the two tables, respectively. This part introduces the division of table T and the processing of table SAC. We will introduce some definitions and parameters first.Definition 3 (association rules).
Assume that when eventA happens, the probability of occurrence of event B is s
(
0
≤
s
≤
1
); namely, A ⇒ B
:
s. A
⇒
B is an association rule.Definition 4 (support degree).
It represents the number of occurrences of an event. For example, in Table1, the number of a
1 is 4, so the support degree of a
1 is 4. Namely, support
(
a
1
)
=
4. support
(
a
1
,
b
1
) especially represents the simultaneity number of a
1 and b
1. In Table 1, there are 3 records satisfying t
.
S
1
=
a
1, t
.
S
2
=
b
1, so support
(
a
1
,
b
1
)
=
3.Definition 5 (confidence).
Assume whenA happens, the probability of occurrence of event B is s
(
0
≤
s
≤
1
), so the confidence of A
⇒
B is s. For example, in Table 1, there are 4 records whose S
1 values are a
1, and three of them have S
2 value b
1. So when a
1 appears, the probability of occurrence of b
1 is 3/4. Namely, confidence
(
a
1
⇒
b
1
)
=
3
/
4. It is not difficult to prove that confidence
(
a
1
⇒
b
1
)
=
support
(
a
1
,
b
1
)
/
support
(
a
1
).Usually we set minimum support degree threshold (min_support) and the minimum confidence threshold (min_confidence); if an association rule satisfies both these two thresholds, the rule is meaningful. In this paper, as long as one sensitive attribute valuev appears once, adversary may use it to attack the privacy of users, so the min_support is set to 1. And the min_confidence is set by users.Definition 6 (strong rule).
Assuming association ruleA
⇒
B [confidence = s
(
0
≤
s
≤
1
)], s ≥ min_confidence, so we call A
⇒
B strong rule.Usually the strong rule’s confidence is relatively higher, and adversary may use the strong rule to attack users’ privacy if adversary has the related background knowledge. On the other hand, we hope to preserve information of strong rule in the released data, because it is valuable. So we need to put the records containing strong rules into table SAC and process table SAC with consideration for strong rule. Record containing strong rules means that, for recordt, if ∃
t
.
S
x
,
t
.
S
y
(
1
≤
x
,
y
≤
j
), t
.
S
x
⇒
t
.
S
y is a strong rule, so record t contains strong rule. And for a value v, if there is a strong rule that A
⇒
B satisfies v
=
A or v
=
B, we call v strong value.


### 4.1.1. Partition Table

Assuming the association rules in original data table are close to the situation of the real world, first use classic association rule mining algorithm-Apriori [18] to find out all the strong rules in table, according to min_confidence set by user (line 1). Then find a sensitive attribute S that has the largest number of strong values, put all other sensitive attributes into S
_
set
~, and if a record contains strong value in S
_
set
~, add it to table SAC (line 2). At last delete the records contained by SAC in original table, and get table IR (line 3), so the original table T is divided into two tables: SAC and IR. Obviously, the records which all contain strong association rules are in SAC, and all the strong values in IR belong to the same sensitive attribute, so there are no probability tilts caused by strong association rules in IR (please see Section 4.2.2).Algorithm 7 (partition table).
Input: original data tableT, min_confidence
Output: Table SAC, Table IR
(1) Accoding to min_confidence find out all strong rules with Apriori.
(2) Find the records which all contain strong values inS
_
set
~, and put them into table SAC.
(3) Table IR =T-Table SAC.


### 4.1.2. Partition Sensitive Attributes

After partition table, begin to process the table SAC. In order to preserve the information of strong rules, cluster the sensitive attributes. First, we need to define the distance between sensitive attributes.Definition 8 (distance between sensitive attributes).
Given two sensitive attributesS
x, S
y
(
1
≤
x
,
y
≤
j
), the distance between the two sensitive attributes can be defined as(1)distanceSx,Sy=1,there  are  no  strong  rules  betweenSxandSy,0,there  are  strong  rules  betweenSxandSy.Here, if ∃
v
x
∈
domain
(
S
x
)
,
∃
v
y
∈
domain
(
S
y
), v
x
⇒
v
y, or v
y
⇒
v
x is strong rule, we say there are strong rules between S
x and S
y; else, there are no strong rules between S
x and S
y.Definition 9 (distance between sensitive attribute and cluster).
AssumingC is a cluster, S
x
(
1
≤
x
≤
j
) is a sensitive attribute, and the distance between C and S
x can be defined as(2)distanceSx,C=1,∀Sy∈C1≤y≤j,distacneSx,Sy=1,0,∃Sy∈C1≤y≤j,distacneSx,Sy=0.In this method, put the similar sensitive attributes into a same cluster, as long as the set of sensitive attributes is not empty, and generate new cluster constantly (line 1). For each new empty clusterC, pick a sensitive attribute S
x
(
1
≤
x
≤
j
) from sensitive attribute set S
_
set orderly, put S
x into C, and S
x is the first attribute of cluster C (line 2). Find out all such sensitive attributes S
y
∈
S
_
set
(
1
≤
y
≤
j
), and S
y satisfies that distance
(
S
y
,
C
)
=
0. Add S
y to C, and delete S
y in S
_
set (line 3 to line 4). Similarly, generate other clusters.After Algorithm10, we get the set of clusters: Cluster_Set = C
1
,
C
2
,
…
,
C
m, ∀
C
∈
Cluster
_
Set, and C is a subset of sensitive attributes set S
_
set = S
1
,
S
2
,
…
,
S
j.AssumingC
∈
Cluster
_
Set, C
=
S
x
,
S
y
,
S
z
(
1
≤
x
,
y
,
z
≤
j
), record t
∈
SAC, and the C value of t is t
.
C
=
(
t
.
S
x
,
t
.
S
y
,
t
.
S
z
).Algorithm 10 (partition sensitive attributes).
Input: Table SAC
Output: set of sensitive attributes’ cluster (Cluster_Set)
S
_
set is the set of sensitive attributes, S
_
set = S
1
,
S
2
,
…
,
S
j.
(1) While theS
_
set is not empty, repeat (2) to (5).
(2) Generate clusterC, add the first sensitive attribute S
x
(
1
≤
x
≤
j
) to C, S
_
set - S
x.
(3) For eachS
y
∈
S
_
set
(
1
≤
y
≤
j
), do (4).
(4) If distance(C
,
S
y) = 0, add S
y to C, S
_
set -S
y.
(5)Cluster
_
set
∪
C.


### 4.1.3. Partition Records

This part will divide the Table SAC into several groups and anonymize the records in the same group.Algorithm 11 (partition records).
Input: Table SAC, Table IR, and Cluster_Set,L
Output: released Table SAC~
(1) While Table SAC is not empty, repeat (2) to (7).
(2) Generate a new groupG.
(3) Choose a recordt from Table SAC orderly, G
∪
t, SAC-t.
(4) WhileG
<
L, repeat (5) to (6).
(5) If∃
t
~
∈
SAC, this satisfies ∀
t
∈
G
,
1
≤
∀
x
≤
j
,
t
~
.
S
x
≠
t
.
S
x
,
G
∪
t
~, and SAC-t
~.
(6) Else choose recordt
~ from table IR orderly, t
~ satisfies ∀
t
∈
G
,
1
≤
∀
x
≤
j
,
t
~
.
S
x
≠
t
.
S
x,  G
∪
t
~, and IR-t
~.
(7)S
A
C
~
∪
G
(8) Permutate cluster values in each group randomly.In the algorithm of partition records, while table SAC is not empty, generate group constantly (lines 1-2). For each empty groupG, choose a record t from table SAC as G’s first record (line 3). Choosing t
~
∈
SAC, or t
~
∈
IR, t
~ does not have the same sensitive attributes values with G, and add t
~ to G, until the number of records in G is not less than L (line 4–6). Within each group, sensitive attributes values are permutated randomly in each cluster to break the linking between different clusters (line 8). That is to say, adjust the position of cluster values randomly. Finally, release S
A
C
~.Now take Table1 as an example, there are three steps on this process. Here, assume that L
=
2, min_confidence = 0.75.(1)
Partition table: both S
1 and S
2 have four strong values, and S
3 has no values, so S
_
set
~
=
S
1
,
S
3. We first find out that there are 4 records containing strong values in S
_
set
~, and they are t
1
,
t
5
,
t
6, and t
7, respectively. These 4 records make up table SAC (Table 4) and meanwhile, delete these 4 records in Table 1.
(2)
Partition sensitive attributes: generate a new cluster C
1, add S
1 to C
1, and now there remain two sensitive attributes in sensitive attributes set. Because there is strong rule a
1
⇒
b
1 between S
1 and S
2 and distance
(
C
1
,
S
2
)
=
0, add S
2 to C
1. But both distance
(
S
1
,
S
3
) and distance
(
S
2
,
S
3
) are 1, distance
(
C
1
,
S
3
)
=
1, S
3 cannot be added to C
1. And the only one attribute S
3 in sensitive attributes set makes up a cluster C
2 alone. So clustering is over, and we get two clusters C
1
=
S
1
,
S
2, C
2
=
S
3.
(3)
Partition records: according to the grouping condition, it cannot have the same sensitive attribute values in a group, t
1 and t
2 make up a group, similarly, and t
5 and t
9, t
6 and t
4, t
7 and t
8 make up groups, respectively (Table 5). After grouping, randomly permutate the cluster values in the same groups and release the table SAC~ (Table 6). For example, in group 1, permutate C
1 value (
a
1
,
b
1
), (
a
4
,
b
2
) randomly. Here, each group has two records, according to the random principle; after disturbing order, (
a
1
,
b
1
) may swap position with (a
4
,
b
2), or both (a
1
,
b
1) and (a
4
,
b
2) remain in the original positions. Similarly, for C
2, permutate C
2 value, c
1, c
2, randomly. Although through anonymity, the relationship between S
1 and S
2 is still preserved. On the other hand, linking between C
1 and C
2 has been broken. So this method preserves the links between sensitive attributes in the same clusters and breaks the links between sensitive attributes from different clusters.Table 4
The SAC table.
ID
Age
Country
S
1
S
2
S
3
1
23
China
a
1
b
1
c
2
5
38
Mexico
a
1
b
1
c
2
6
23
Japan
a
1
b
1
c
1
7
36
America
a
1
b
2
c
1Table 5
Partition records for Table4.
ID
Age
Country
S
1
S
2
S
3
Group ID
1
23
China
a
1
b
1
c
2
1
2
35
India
a
4
b
2
c
1
1
5
38
Mexico
a
1
b
1
c
2
2
9
21
Australia
a
2
b
2
c
1
2
6
23
Japan
a
1
b
1
c
1
3
4
31
Japan
a
6
b
2
c
2
3
7
36
America
a
1
b
2
c
1
4
8
38
America
a
2
b
5
c
2
4Table 6
Mixed model published SAC~ for Table 1.
ID
Age
Country
S
1
S
2
S
3
Group ID
1
23
China
a
4
b
2
c
2
1
2
35
India
a
1
b
1
c
1
1
5
38
Mexico
a
1
b
1
c
1
2
9
21
Australia
a
2
b
2
c
2
2
6
23
Japan
a
6
b
2
c
2
3
4
31
Japan
a
1
b
1
c
1
3
7
36
America
a
2
b
5
c
1
4
8
38
America
a
1
b
2
c
2
4Lemma 12.
Assuming adversary has the background knowledge about strong rules, for∀
t
∈
T, ∀
r
∈
S
t
r
o
n
g
_
R
u
l
e
_
S
e
t
(
T
), r
:
A
⇒
B, adversary is sure that t contains r with the probability:(3)Pt:A⟹B≤1L.
Here,S
t
r
o
n
g
_
R
u
l
e
_
S
e
t
(
T
) represents the set of strong rules in table T.Proof.
Ift
∈
IR, there are no records containing strong rules in table IR, so P
(
t
:
A
⇒
B
)
=
0. If t
∈
S
A
C
~, for each group G in S
A
C
~, G has at least L records; if there is record containing A
⇒
B in G, according to the nature of random permutation, each record in G contains A
⇒
B with equality probability 1
/
L, so we can know that even though adversary can be clear of how many records contain A
⇒
B through related background knowledge, P
(
t
:
A
⇒
B
) is not more than 1
/
L.In the example of Section3.3, for some records, adversary can make sure that they contain strong rules with probability 100%. S
A
C
~ table can prevent adversary from using strong rules to attack users’ privacy.


## 4.1.1. Partition Table

Assuming the association rules in original data table are close to the situation of the real world, first use classic association rule mining algorithm-Apriori [18] to find out all the strong rules in table, according to min_confidence set by user (line 1). Then find a sensitive attribute S that has the largest number of strong values, put all other sensitive attributes into S
_
set
~, and if a record contains strong value in S
_
set
~, add it to table SAC (line 2). At last delete the records contained by SAC in original table, and get table IR (line 3), so the original table T is divided into two tables: SAC and IR. Obviously, the records which all contain strong association rules are in SAC, and all the strong values in IR belong to the same sensitive attribute, so there are no probability tilts caused by strong association rules in IR (please see Section 4.2.2).Algorithm 7 (partition table).
Input: original data tableT, min_confidence
Output: Table SAC, Table IR
(1) Accoding to min_confidence find out all strong rules with Apriori.
(2) Find the records which all contain strong values inS
_
set
~, and put them into table SAC.
(3) Table IR =T-Table SAC.


## 4.1.2. Partition Sensitive Attributes

After partition table, begin to process the table SAC. In order to preserve the information of strong rules, cluster the sensitive attributes. First, we need to define the distance between sensitive attributes.Definition 8 (distance between sensitive attributes).
Given two sensitive attributesS
x, S
y
(
1
≤
x
,
y
≤
j
), the distance between the two sensitive attributes can be defined as(1)distanceSx,Sy=1,there  are  no  strong  rules  betweenSxandSy,0,there  are  strong  rules  betweenSxandSy.Here, if ∃
v
x
∈
domain
(
S
x
)
,
∃
v
y
∈
domain
(
S
y
), v
x
⇒
v
y, or v
y
⇒
v
x is strong rule, we say there are strong rules between S
x and S
y; else, there are no strong rules between S
x and S
y.Definition 9 (distance between sensitive attribute and cluster).
AssumingC is a cluster, S
x
(
1
≤
x
≤
j
) is a sensitive attribute, and the distance between C and S
x can be defined as(2)distanceSx,C=1,∀Sy∈C1≤y≤j,distacneSx,Sy=1,0,∃Sy∈C1≤y≤j,distacneSx,Sy=0.In this method, put the similar sensitive attributes into a same cluster, as long as the set of sensitive attributes is not empty, and generate new cluster constantly (line 1). For each new empty clusterC, pick a sensitive attribute S
x
(
1
≤
x
≤
j
) from sensitive attribute set S
_
set orderly, put S
x into C, and S
x is the first attribute of cluster C (line 2). Find out all such sensitive attributes S
y
∈
S
_
set
(
1
≤
y
≤
j
), and S
y satisfies that distance
(
S
y
,
C
)
=
0. Add S
y to C, and delete S
y in S
_
set (line 3 to line 4). Similarly, generate other clusters.After Algorithm10, we get the set of clusters: Cluster_Set = C
1
,
C
2
,
…
,
C
m, ∀
C
∈
Cluster
_
Set, and C is a subset of sensitive attributes set S
_
set = S
1
,
S
2
,
…
,
S
j.AssumingC
∈
Cluster
_
Set, C
=
S
x
,
S
y
,
S
z
(
1
≤
x
,
y
,
z
≤
j
), record t
∈
SAC, and the C value of t is t
.
C
=
(
t
.
S
x
,
t
.
S
y
,
t
.
S
z
).Algorithm 10 (partition sensitive attributes).
Input: Table SAC
Output: set of sensitive attributes’ cluster (Cluster_Set)
S
_
set is the set of sensitive attributes, S
_
set = S
1
,
S
2
,
…
,
S
j.
(1) While theS
_
set is not empty, repeat (2) to (5).
(2) Generate clusterC, add the first sensitive attribute S
x
(
1
≤
x
≤
j
) to C, S
_
set - S
x.
(3) For eachS
y
∈
S
_
set
(
1
≤
y
≤
j
), do (4).
(4) If distance(C
,
S
y) = 0, add S
y to C, S
_
set -S
y.
(5)Cluster
_
set
∪
C.


## 4.1.3. Partition Records

This part will divide the Table SAC into several groups and anonymize the records in the same group.Algorithm 11 (partition records).
Input: Table SAC, Table IR, and Cluster_Set,L
Output: released Table SAC~
(1) While Table SAC is not empty, repeat (2) to (7).
(2) Generate a new groupG.
(3) Choose a recordt from Table SAC orderly, G
∪
t, SAC-t.
(4) WhileG
<
L, repeat (5) to (6).
(5) If∃
t
~
∈
SAC, this satisfies ∀
t
∈
G
,
1
≤
∀
x
≤
j
,
t
~
.
S
x
≠
t
.
S
x
,
G
∪
t
~, and SAC-t
~.
(6) Else choose recordt
~ from table IR orderly, t
~ satisfies ∀
t
∈
G
,
1
≤
∀
x
≤
j
,
t
~
.
S
x
≠
t
.
S
x,  G
∪
t
~, and IR-t
~.
(7)S
A
C
~
∪
G
(8) Permutate cluster values in each group randomly.In the algorithm of partition records, while table SAC is not empty, generate group constantly (lines 1-2). For each empty groupG, choose a record t from table SAC as G’s first record (line 3). Choosing t
~
∈
SAC, or t
~
∈
IR, t
~ does not have the same sensitive attributes values with G, and add t
~ to G, until the number of records in G is not less than L (line 4–6). Within each group, sensitive attributes values are permutated randomly in each cluster to break the linking between different clusters (line 8). That is to say, adjust the position of cluster values randomly. Finally, release S
A
C
~.Now take Table1 as an example, there are three steps on this process. Here, assume that L
=
2, min_confidence = 0.75.(1)
Partition table: both S
1 and S
2 have four strong values, and S
3 has no values, so S
_
set
~
=
S
1
,
S
3. We first find out that there are 4 records containing strong values in S
_
set
~, and they are t
1
,
t
5
,
t
6, and t
7, respectively. These 4 records make up table SAC (Table 4) and meanwhile, delete these 4 records in Table 1.
(2)
Partition sensitive attributes: generate a new cluster C
1, add S
1 to C
1, and now there remain two sensitive attributes in sensitive attributes set. Because there is strong rule a
1
⇒
b
1 between S
1 and S
2 and distance
(
C
1
,
S
2
)
=
0, add S
2 to C
1. But both distance
(
S
1
,
S
3
) and distance
(
S
2
,
S
3
) are 1, distance
(
C
1
,
S
3
)
=
1, S
3 cannot be added to C
1. And the only one attribute S
3 in sensitive attributes set makes up a cluster C
2 alone. So clustering is over, and we get two clusters C
1
=
S
1
,
S
2, C
2
=
S
3.
(3)
Partition records: according to the grouping condition, it cannot have the same sensitive attribute values in a group, t
1 and t
2 make up a group, similarly, and t
5 and t
9, t
6 and t
4, t
7 and t
8 make up groups, respectively (Table 5). After grouping, randomly permutate the cluster values in the same groups and release the table SAC~ (Table 6). For example, in group 1, permutate C
1 value (
a
1
,
b
1
), (
a
4
,
b
2
) randomly. Here, each group has two records, according to the random principle; after disturbing order, (
a
1
,
b
1
) may swap position with (a
4
,
b
2), or both (a
1
,
b
1) and (a
4
,
b
2) remain in the original positions. Similarly, for C
2, permutate C
2 value, c
1, c
2, randomly. Although through anonymity, the relationship between S
1 and S
2 is still preserved. On the other hand, linking between C
1 and C
2 has been broken. So this method preserves the links between sensitive attributes in the same clusters and breaks the links between sensitive attributes from different clusters.Table 4
The SAC table.
ID
Age
Country
S
1
S
2
S
3
1
23
China
a
1
b
1
c
2
5
38
Mexico
a
1
b
1
c
2
6
23
Japan
a
1
b
1
c
1
7
36
America
a
1
b
2
c
1Table 5
Partition records for Table4.
ID
Age
Country
S
1
S
2
S
3
Group ID
1
23
China
a
1
b
1
c
2
1
2
35
India
a
4
b
2
c
1
1
5
38
Mexico
a
1
b
1
c
2
2
9
21
Australia
a
2
b
2
c
1
2
6
23
Japan
a
1
b
1
c
1
3
4
31
Japan
a
6
b
2
c
2
3
7
36
America
a
1
b
2
c
1
4
8
38
America
a
2
b
5
c
2
4Table 6
Mixed model published SAC~ for Table 1.
ID
Age
Country
S
1
S
2
S
3
Group ID
1
23
China
a
4
b
2
c
2
1
2
35
India
a
1
b
1
c
1
1
5
38
Mexico
a
1
b
1
c
1
2
9
21
Australia
a
2
b
2
c
2
2
6
23
Japan
a
6
b
2
c
2
3
4
31
Japan
a
1
b
1
c
1
3
7
36
America
a
2
b
5
c
1
4
8
38
America
a
1
b
2
c
2
4Lemma 12.
Assuming adversary has the background knowledge about strong rules, for∀
t
∈
T, ∀
r
∈
S
t
r
o
n
g
_
R
u
l
e
_
S
e
t
(
T
), r
:
A
⇒
B, adversary is sure that t contains r with the probability:(3)Pt:A⟹B≤1L.
Here,S
t
r
o
n
g
_
R
u
l
e
_
S
e
t
(
T
) represents the set of strong rules in table T.Proof.
Ift
∈
IR, there are no records containing strong rules in table IR, so P
(
t
:
A
⇒
B
)
=
0. If t
∈
S
A
C
~, for each group G in S
A
C
~, G has at least L records; if there is record containing A
⇒
B in G, according to the nature of random permutation, each record in G contains A
⇒
B with equality probability 1
/
L, so we can know that even though adversary can be clear of how many records contain A
⇒
B through related background knowledge, P
(
t
:
A
⇒
B
) is not more than 1
/
L.In the example of Section3.3, for some records, adversary can make sure that they contain strong rules with probability 100%. S
A
C
~ table can prevent adversary from using strong rules to attack users’ privacy.


## 4.2. Improved Rating (IR)

The table IR will be processed by improved Rating. For each sensitive attributeS, Rating [17] hashes t
.
S in S by their values (each bucket corresponds to each value), and if S has m different values (v
1
,
v
2
,
…
,
v
m), it can get sequence = b
u
c
k
e
t
1
,
b
u
c
k
e
t
2
,
…
,
b
u
c
k
e
t
m, and assuming there are n
v
i
(
1
≤
i
≤
m
) in S, so the corresponding bucketi contains n
v
i in it. Every time Rating chooses the L buckets that have the largest size, gets a value from every one of these L buckets to make up a SID, uses SID to replace corresponding sensitive attribute values in original table, and gets attribute table, and the SID makes up ID table. Every time Rating generates an SID, it needs to reselect L buckets, because after the last generation of SID, the sizes of buckets have been updated. Paper [17] has not presented the algorithm of choosing L largest buckets, so this paper will present a heuristic algorithm of choosing buckets.


### 4.2.1. Heuristic Algorithm for Choosing Buckets

This heuristic algorithm (Algorithm13) is actually a stable sorting algorithm, sort sequence in descending order, and choose the first L buckets from sequence. This algorithm will be called after updating the size of buckets. Let us introduce some parameters, and sequence[i] refers to the i
(
1
≤
i
≤
m
) bucket in the sequence:sequence[i].value: the attribute value in sequence[i],
sequence[i].size: the size of sequence[i],
sequence[i].size~: after updating size, the size of sequence[i], if 1
≤
i
≤
L, sequence[i].size~ = sequence[i].size-1; if L
<
i
≤
m, sequence[i].size~ = sequence[i].size,
sequence[i].position: the position of sequence[i], sequence[i].position = i,
sequence[i].position~: after sorting, the new position of sequence[i].Algorithm 13 (heuristic choosingL largest buckets).
Input: sequence,L,
Output: sequence satisfies stable descending order,
(1) If sequence[L].size~ < sequence[L
+
1].size~, do (2) to (5).
(2) Fori
=
1; i
<
L
+
1; i
+
+, repeat (3) to (5)
(3) If sequence[i].size~ < sequence[L
+
1].size~, do (4) to (5).
(4) Find sequence[j] and sequence[j
+
1] which satisfy sequence[j].size~ > sequence[i].size~ ≥ sequence[j
+
1]. size~
(5) removeQ = sequence
[
i
]
,
sequence
[
i
+
1
]
,
…
,
sequence
[
L
] to the position between sequence[j] and sequence[j
+
1]; meanwhile keep the relative position among Q, end loop.If the sequence always satisfies the stable descending order, there are Lemmas14 and 15 and Corollaries 16 and 17, and we will prove the correctness of algorithm.Lemma 14.
After updating size of buckets, if sequence[
L
].size~ ≥ sequence[
L
+
1
].size~, the position of all buckets in sequence does not need to be adjusted.Proof.
Using proof by contradiction, only the sizes ofsequence
[
1
]
,
sequence
[
2
]
,
…
,
sequence
[
L
] have been changed, so these buckets may need to adjust their position in the sequence. If sequence[i] (1
≤
i
<
L) needs to be removed to the back of sequence[j] (L
<
j
≤
m), then sequence[j].size~ > sequence[i].siz
e
~ and sequence[L
+
1].size~ ≥ sequence[j].siz
e
~ > sequence[i].size~. Because sequence[i].size ≥ sequence[L].size, and after generation, in both the sizes of sequence[i] and sequence[L] minus 1, there is sequence[i].size~ ≥ sequence[L].size~, we can get the contradictory conclusion:(4)sequenceL+1.size~>sequenceL.size~.Lemma 15.
If sequence[
j
].size~ > sequence[
i
].size~ ≥ sequence[
j
+
1
]
.
s
i
z
e
~
(
1
≤
i
,
i
+
1
≤
L
,
L
<
j
,
j
+
1
≤
m
), in order to preserve stable descending order, there are sequence[
j
].position~ < sequence[
i
].p
o
s
i
t
i
o
n
~ < sequence[
j
+
1
].p
o
s
i
t
i
o
n
~ and sequence[
i
+
1
]. position~ = sequence[
i
]
.
p
o
s
i
t
i
o
n
~
+
1.Proof.
Obviously, according to the nature of stable descending sorting, the new position of sequence[i] is between sequence[j] and sequence[j
+
1]. Here we will discuss the new position of sequence[i
+
1]. In addition to the situation in Lemma 15, the new position of sequence[i
+
1] has two possibilities, using the contradiction to proof, respectively.(1)
After adjusting, the position of sequence[i
+
1] will be sequence[i
+
1].position~ and sequence[i
+
1].position~ < sequence[i].position~. According to the nature of descending order, before generating SID, sequence[i].size ≥ sequence[i
+
1].size and sequence[i].position < sequence[i
+
1].position, after generating SID, in both the sizes of sequence[i] and sequence[i
+
1] minus 1, one has sequence[i].size~ ≥ sequence[i
+
1].size~. So sequence[i
+
1].position~< sequence[i].position~ contradicts the nature of stable descending order.
(2)
After adjusting, the position of sequence[i
+
1] will be sequence[i
+
1].position~, sequence[i
+
1].position~ > sequence[i].position~, and existing set Q
=
sequence
k
∣
1
≤
k
≤
m, and each sequence[k] ∈
Q satisfies that sequence[i].position~ < sequence[k].position~ < sequence[i
+
1].position~. If 1
≤
k
≤
L, according to the nature of stable descending order, sequence[i].size~ ≥ sequence[k].size~ ≥ sequence[i
+
1].size~, sequence[i].size ≥ sequence[k].size ≥ sequence[i
+
1].size, sequence[i].position < sequence[k].position < sequence[i
+
1].position, and we can get the contradictory conclusions: i
<
k
<
i
+
1. In another situation, if L
<
k
≤
m, one must have sequence[i].size~ ≥ sequence[k].size~ > sequence[i
+
1].size~ and sequence[k].size = sequence[i
+
1].size ≥ sequence[j].size; because the sizes of sequence[j] and sequence[k] have not changed, there is sequence[k].size~ ≥ sequence[j].size~, so we can get the contradictory conclusions: sequence[i].size~ ≥ sequence[j].size~.Corollary 16.
If sequence[
i
].size~ < sequence[
L
+
1
].size~, the new position of sequence[
i
] will be sequence[
i
].position~; for each sequence[
k
]
(
i
<
k
≤
L
), its new position is as follows: sequence[
k
].position~ = sequence[
i
].position~ + (
k
-
i
).Proof.
According to Lemma15, sequence[i
+
1].position~ = sequence[i].position~ + 1; for each sequence[k] (
i
<
k
≤
L), there exists sequence[k].position~ = sequence[k
-
1].position~ + 1, so for each sequence[k] (i
<
k
≤
L), it satisfies(5)sequencek.position~=sequencei.position~+k-i.Corollary 17.
After updating size of bucket, if sequence[
j
].size~ > sequence[
i
].size~ ≥ sequence[
j
+
1
].size~
(
L
<
j
,
j
+
1
≤
m
), here i
=
1 or (
1
<
i
≤
L, sequence[
i
-
1
].size~ ≥ sequence[
L
+
1
].size~
); to make sequence satisfy the stable descending order, one only needs to remove Q = sequence[
i
], s
e
q
u
e
n
c
e
[
i
+
1
]
,
…
,
s
e
q
u
e
n
c
e
[
L
] to the position between sequence[
j
] and sequence[
j
+
1
].Proof.
After updating size, only sizes ofsequence
[
1
]
,
sequence
[
2
]
,
…
,
sequence
[
L
] have changed, so only the positions of sequence
[
1
]
,
sequence
[
2
]
,
…
,
sequence
[
L
] may need to be adjusted. According to the nature of stable descending order sequence[
i].position~ = sequence[j].position~ + 1; according to Corollary 16, sequence[k].position~ = sequence[i].position~ + (k
-
i), (i
<
k
≤
L), and sequence[j
+
1].position~ = sequence[L].position~ + 1. So removing sequence[i], sequence
[
i
+
1
]
,
…
,
sequence
[
L
] to the position between sequence[j] and sequence[j
+
1] can make sequence satisfy stable descending order.
Here one analyzes the efficiency of this sorting algorithm. In the best situation, sequence[L].size~ ≥ sequence[L
+
1].size~, it only needs to compare sequence[L].size~ with sequence[L
+
1].size~ in this algorithm, and the time complexity is O
(
1
). The worst situation is that sequence[1].size~ < sequence[m].size~, the algorithm needs to compare m
-
L
+
1 times, and the time complexity is O
(
m
-
L
+
1
). The efficiency of this sorting algorithm is much better than most of existing sorting algorithms.


### 4.2.2. SID Creation

This part will introduce the algorithm of creating SID. The definition of dangerous bucket will be introduced as follows.Definition 18 (dangerous bucket).
Assuming sequence is in sensitive attributeS, for each bucket B
∈
sequence, if B
.
size
/
n
≥
1
/
L, B is a dangerous bucket in S. Here, n is size of the domain (S).The SID creation can be seen in Algorithm19. For each sensitive attribute S
i, one generates its sequence and removes the dangerous buckets from sequence to SDB. Every time one generates a new S
i
I
D
j, for each bucket in SDB, removes one value from it to S
i
I
D
j (line 6), for each bucket of sequence[1], sequence[2], …, sequence[L-SDB] which have largest size, removes a value from it to S
i
I
D
j (line 7). When a S
i
I
D
j is completed, call for Algorithm 13 to sort the sequence. In the step of processing residual values, for each value v in a nonempty bucket, remove v to a S
i
I
D
j which does not contain value v (line 9).Algorithm 19 (SID creation).
Input:L, IR table
Output:S
i
I
D
j
(1) For each sensitive attributeS
i, do (2) to (9).
(2) Generate sequence.
(3) Find the dangerous buckets, and put them in SDB.
(4) Remove the dangerous buckets in sequence;
(5) When there are at leastL-SDB buckets in sequence which are not empty, generate a new S
i
I
D
j repeat (6) to (8).
(6) For each bucket in SDB, remove a value toS
i
I
D
j.
(7) For each bucket fromsequence[1], sequence[2], …, sequence[L-SDB
], remove a value to S
i
I
D
j;
(8) Call for Algorithm13 and use sequence and L-SDB as input; //processes the residual attribute values
(9) For each valuev in nonempty buckets, find a S
i
I
D
j which contains no value v, and remove v to S
i
I
D
j. If one cannot find this S
i
I
D
j, value v cannot be grouped.Lemma 20.
If bucketB is a dangerous bucket in sensitive attribute S
i, after completing a new S
i
I
D
j, B is still a dangerous bucket.Proof.
After completing a newS
i
I
D
j, the frequency of B.value is B
.
size
-
1
/
n
-
L, and n is the size of domain
(
S
i
). Before generating the new S
i
I
D
j, the frequency of B.value was B
.
size
/
n. If there is B
.
size
-
1
/
n
-
L
≥
B
.
size
/
n, Lemma 20 can be proved.
The left side of the equation is equal to(
B
.
size
-
1
)
∗
n
/
(
n
-
L
)
∗
n, and the right side of the equation is equal to B
.
size
∗
(
n
-
L
)
/
n
∗
(
n
-
L
); one only needs to prove that(6)B.size-1∗n≥B.size∗n-L.Because before generating the new S
i
I
D
j, B was dangerous bucket, and satisfied B
.
size
/
n
≥
1
/
L, has B
.
s
i
z
e
∗
L
≥
n, B
.
s
i
z
e
∗
n
-
n
≥
B
.
s
i
z
e
∗
n
-
B
.
s
i
z
e
∗
L so we can get (7)B.size-1∗n≥B.size∗n-L.Corollary 21.
If bucketB is a dangerous bucket, after completing a new S
i
I
D
j, B is still one of the L buckets which have the largest size.Proof.
Using proof by contradiction, if there is Set =bucket1, bucket2, …, b
u
c
k
e
t
L, for each bucket
∈
Set, it has larger size than B. According to Lemma 20, after generating a new S
i
I
D
j, the B
.
s
i
z
e
~
/
n
≥
1
/
L, so bucket satisfies b
u
c
k
e
t
.
s
i
z
e
~
/
n
≥
1
/
L, so there has(8)bucket1.size~n+bucket2.size~n+⋯+bucketL.size~n+B.size~n>1.
Get the contradictory conclusions:(9)bucket1.size~+bucket2.size~+⋯+bucketL.size~+B.size~>n.
From the above certification, we can find out that the dangerous bucket is always one of theL largest buckets, so each new S
i
I
D
j should take one value of dangerous bucket, and it does not need to consider dangerous bucket for sorting sequence. This method further improves the efficiency of the algorithm.
Besides, in this improved Rating, the algorithm for AT&IDT Creation is the same as in Rating, usesS
i
I
D
j to generalize corresponding value in IR table, after processing IR, gets AT, and then uses the set of S
i
I
D
j to make up IDT. At last release AT and IDT with the previous SAC~ table.
Here we assume adversary masters strong rules and summarize the security of mixed model. For released table SAC~, because each group contains at least L records without the same values and refers to Lemma 12, it is easy to know that SAC~ satisfy L-diversity. For released AT, we will discuss a problem of probability tilts first. For record t, after generalization if ∃
v
1
∈
t
.
S
x, ∃
v
2
∈
t
.
S
y
(
1
≤
x
,
y
≤
j
) satisfy v
1
⇒
v
2 which is a strong rule, there will be probability tilt between t
.
S
x and t
.
S
y obviously. And according to the method of partition table, all the strong values in AT belong to the same sensitive attribute, so the probability tilts will not happen in AT. Besides, each S
i
I
D
j consists of at least L different values, so AT also satisfies L-diversity. And through the above analysis, we know that mixed model is able to satisfy L-diversity.


## 4.2.1. Heuristic Algorithm for Choosing Buckets

This heuristic algorithm (Algorithm13) is actually a stable sorting algorithm, sort sequence in descending order, and choose the first L buckets from sequence. This algorithm will be called after updating the size of buckets. Let us introduce some parameters, and sequence[i] refers to the i
(
1
≤
i
≤
m
) bucket in the sequence:sequence[i].value: the attribute value in sequence[i],
sequence[i].size: the size of sequence[i],
sequence[i].size~: after updating size, the size of sequence[i], if 1
≤
i
≤
L, sequence[i].size~ = sequence[i].size-1; if L
<
i
≤
m, sequence[i].size~ = sequence[i].size,
sequence[i].position: the position of sequence[i], sequence[i].position = i,
sequence[i].position~: after sorting, the new position of sequence[i].Algorithm 13 (heuristic choosingL largest buckets).
Input: sequence,L,
Output: sequence satisfies stable descending order,
(1) If sequence[L].size~ < sequence[L
+
1].size~, do (2) to (5).
(2) Fori
=
1; i
<
L
+
1; i
+
+, repeat (3) to (5)
(3) If sequence[i].size~ < sequence[L
+
1].size~, do (4) to (5).
(4) Find sequence[j] and sequence[j
+
1] which satisfy sequence[j].size~ > sequence[i].size~ ≥ sequence[j
+
1]. size~
(5) removeQ = sequence
[
i
]
,
sequence
[
i
+
1
]
,
…
,
sequence
[
L
] to the position between sequence[j] and sequence[j
+
1]; meanwhile keep the relative position among Q, end loop.If the sequence always satisfies the stable descending order, there are Lemmas14 and 15 and Corollaries 16 and 17, and we will prove the correctness of algorithm.Lemma 14.
After updating size of buckets, if sequence[
L
].size~ ≥ sequence[
L
+
1
].size~, the position of all buckets in sequence does not need to be adjusted.Proof.
Using proof by contradiction, only the sizes ofsequence
[
1
]
,
sequence
[
2
]
,
…
,
sequence
[
L
] have been changed, so these buckets may need to adjust their position in the sequence. If sequence[i] (1
≤
i
<
L) needs to be removed to the back of sequence[j] (L
<
j
≤
m), then sequence[j].size~ > sequence[i].siz
e
~ and sequence[L
+
1].size~ ≥ sequence[j].siz
e
~ > sequence[i].size~. Because sequence[i].size ≥ sequence[L].size, and after generation, in both the sizes of sequence[i] and sequence[L] minus 1, there is sequence[i].size~ ≥ sequence[L].size~, we can get the contradictory conclusion:(4)sequenceL+1.size~>sequenceL.size~.Lemma 15.
If sequence[
j
].size~ > sequence[
i
].size~ ≥ sequence[
j
+
1
]
.
s
i
z
e
~
(
1
≤
i
,
i
+
1
≤
L
,
L
<
j
,
j
+
1
≤
m
), in order to preserve stable descending order, there are sequence[
j
].position~ < sequence[
i
].p
o
s
i
t
i
o
n
~ < sequence[
j
+
1
].p
o
s
i
t
i
o
n
~ and sequence[
i
+
1
]. position~ = sequence[
i
]
.
p
o
s
i
t
i
o
n
~
+
1.Proof.
Obviously, according to the nature of stable descending sorting, the new position of sequence[i] is between sequence[j] and sequence[j
+
1]. Here we will discuss the new position of sequence[i
+
1]. In addition to the situation in Lemma 15, the new position of sequence[i
+
1] has two possibilities, using the contradiction to proof, respectively.(1)
After adjusting, the position of sequence[i
+
1] will be sequence[i
+
1].position~ and sequence[i
+
1].position~ < sequence[i].position~. According to the nature of descending order, before generating SID, sequence[i].size ≥ sequence[i
+
1].size and sequence[i].position < sequence[i
+
1].position, after generating SID, in both the sizes of sequence[i] and sequence[i
+
1] minus 1, one has sequence[i].size~ ≥ sequence[i
+
1].size~. So sequence[i
+
1].position~< sequence[i].position~ contradicts the nature of stable descending order.
(2)
After adjusting, the position of sequence[i
+
1] will be sequence[i
+
1].position~, sequence[i
+
1].position~ > sequence[i].position~, and existing set Q
=
sequence
k
∣
1
≤
k
≤
m, and each sequence[k] ∈
Q satisfies that sequence[i].position~ < sequence[k].position~ < sequence[i
+
1].position~. If 1
≤
k
≤
L, according to the nature of stable descending order, sequence[i].size~ ≥ sequence[k].size~ ≥ sequence[i
+
1].size~, sequence[i].size ≥ sequence[k].size ≥ sequence[i
+
1].size, sequence[i].position < sequence[k].position < sequence[i
+
1].position, and we can get the contradictory conclusions: i
<
k
<
i
+
1. In another situation, if L
<
k
≤
m, one must have sequence[i].size~ ≥ sequence[k].size~ > sequence[i
+
1].size~ and sequence[k].size = sequence[i
+
1].size ≥ sequence[j].size; because the sizes of sequence[j] and sequence[k] have not changed, there is sequence[k].size~ ≥ sequence[j].size~, so we can get the contradictory conclusions: sequence[i].size~ ≥ sequence[j].size~.Corollary 16.
If sequence[
i
].size~ < sequence[
L
+
1
].size~, the new position of sequence[
i
] will be sequence[
i
].position~; for each sequence[
k
]
(
i
<
k
≤
L
), its new position is as follows: sequence[
k
].position~ = sequence[
i
].position~ + (
k
-
i
).Proof.
According to Lemma15, sequence[i
+
1].position~ = sequence[i].position~ + 1; for each sequence[k] (
i
<
k
≤
L), there exists sequence[k].position~ = sequence[k
-
1].position~ + 1, so for each sequence[k] (i
<
k
≤
L), it satisfies(5)sequencek.position~=sequencei.position~+k-i.Corollary 17.
After updating size of bucket, if sequence[
j
].size~ > sequence[
i
].size~ ≥ sequence[
j
+
1
].size~
(
L
<
j
,
j
+
1
≤
m
), here i
=
1 or (
1
<
i
≤
L, sequence[
i
-
1
].size~ ≥ sequence[
L
+
1
].size~
); to make sequence satisfy the stable descending order, one only needs to remove Q = sequence[
i
], s
e
q
u
e
n
c
e
[
i
+
1
]
,
…
,
s
e
q
u
e
n
c
e
[
L
] to the position between sequence[
j
] and sequence[
j
+
1
].Proof.
After updating size, only sizes ofsequence
[
1
]
,
sequence
[
2
]
,
…
,
sequence
[
L
] have changed, so only the positions of sequence
[
1
]
,
sequence
[
2
]
,
…
,
sequence
[
L
] may need to be adjusted. According to the nature of stable descending order sequence[
i].position~ = sequence[j].position~ + 1; according to Corollary 16, sequence[k].position~ = sequence[i].position~ + (k
-
i), (i
<
k
≤
L), and sequence[j
+
1].position~ = sequence[L].position~ + 1. So removing sequence[i], sequence
[
i
+
1
]
,
…
,
sequence
[
L
] to the position between sequence[j] and sequence[j
+
1] can make sequence satisfy stable descending order.
Here one analyzes the efficiency of this sorting algorithm. In the best situation, sequence[L].size~ ≥ sequence[L
+
1].size~, it only needs to compare sequence[L].size~ with sequence[L
+
1].size~ in this algorithm, and the time complexity is O
(
1
). The worst situation is that sequence[1].size~ < sequence[m].size~, the algorithm needs to compare m
-
L
+
1 times, and the time complexity is O
(
m
-
L
+
1
). The efficiency of this sorting algorithm is much better than most of existing sorting algorithms.


## 4.2.2. SID Creation

This part will introduce the algorithm of creating SID. The definition of dangerous bucket will be introduced as follows.Definition 18 (dangerous bucket).
Assuming sequence is in sensitive attributeS, for each bucket B
∈
sequence, if B
.
size
/
n
≥
1
/
L, B is a dangerous bucket in S. Here, n is size of the domain (S).The SID creation can be seen in Algorithm19. For each sensitive attribute S
i, one generates its sequence and removes the dangerous buckets from sequence to SDB. Every time one generates a new S
i
I
D
j, for each bucket in SDB, removes one value from it to S
i
I
D
j (line 6), for each bucket of sequence[1], sequence[2], …, sequence[L-SDB] which have largest size, removes a value from it to S
i
I
D
j (line 7). When a S
i
I
D
j is completed, call for Algorithm 13 to sort the sequence. In the step of processing residual values, for each value v in a nonempty bucket, remove v to a S
i
I
D
j which does not contain value v (line 9).Algorithm 19 (SID creation).
Input:L, IR table
Output:S
i
I
D
j
(1) For each sensitive attributeS
i, do (2) to (9).
(2) Generate sequence.
(3) Find the dangerous buckets, and put them in SDB.
(4) Remove the dangerous buckets in sequence;
(5) When there are at leastL-SDB buckets in sequence which are not empty, generate a new S
i
I
D
j repeat (6) to (8).
(6) For each bucket in SDB, remove a value toS
i
I
D
j.
(7) For each bucket fromsequence[1], sequence[2], …, sequence[L-SDB
], remove a value to S
i
I
D
j;
(8) Call for Algorithm13 and use sequence and L-SDB as input; //processes the residual attribute values
(9) For each valuev in nonempty buckets, find a S
i
I
D
j which contains no value v, and remove v to S
i
I
D
j. If one cannot find this S
i
I
D
j, value v cannot be grouped.Lemma 20.
If bucketB is a dangerous bucket in sensitive attribute S
i, after completing a new S
i
I
D
j, B is still a dangerous bucket.Proof.
After completing a newS
i
I
D
j, the frequency of B.value is B
.
size
-
1
/
n
-
L, and n is the size of domain
(
S
i
). Before generating the new S
i
I
D
j, the frequency of B.value was B
.
size
/
n. If there is B
.
size
-
1
/
n
-
L
≥
B
.
size
/
n, Lemma 20 can be proved.
The left side of the equation is equal to(
B
.
size
-
1
)
∗
n
/
(
n
-
L
)
∗
n, and the right side of the equation is equal to B
.
size
∗
(
n
-
L
)
/
n
∗
(
n
-
L
); one only needs to prove that(6)B.size-1∗n≥B.size∗n-L.Because before generating the new S
i
I
D
j, B was dangerous bucket, and satisfied B
.
size
/
n
≥
1
/
L, has B
.
s
i
z
e
∗
L
≥
n, B
.
s
i
z
e
∗
n
-
n
≥
B
.
s
i
z
e
∗
n
-
B
.
s
i
z
e
∗
L so we can get (7)B.size-1∗n≥B.size∗n-L.Corollary 21.
If bucketB is a dangerous bucket, after completing a new S
i
I
D
j, B is still one of the L buckets which have the largest size.Proof.
Using proof by contradiction, if there is Set =bucket1, bucket2, …, b
u
c
k
e
t
L, for each bucket
∈
Set, it has larger size than B. According to Lemma 20, after generating a new S
i
I
D
j, the B
.
s
i
z
e
~
/
n
≥
1
/
L, so bucket satisfies b
u
c
k
e
t
.
s
i
z
e
~
/
n
≥
1
/
L, so there has(8)bucket1.size~n+bucket2.size~n+⋯+bucketL.size~n+B.size~n>1.
Get the contradictory conclusions:(9)bucket1.size~+bucket2.size~+⋯+bucketL.size~+B.size~>n.
From the above certification, we can find out that the dangerous bucket is always one of theL largest buckets, so each new S
i
I
D
j should take one value of dangerous bucket, and it does not need to consider dangerous bucket for sorting sequence. This method further improves the efficiency of the algorithm.
Besides, in this improved Rating, the algorithm for AT&IDT Creation is the same as in Rating, usesS
i
I
D
j to generalize corresponding value in IR table, after processing IR, gets AT, and then uses the set of S
i
I
D
j to make up IDT. At last release AT and IDT with the previous SAC~ table.
Here we assume adversary masters strong rules and summarize the security of mixed model. For released table SAC~, because each group contains at least L records without the same values and refers to Lemma 12, it is easy to know that SAC~ satisfy L-diversity. For released AT, we will discuss a problem of probability tilts first. For record t, after generalization if ∃
v
1
∈
t
.
S
x, ∃
v
2
∈
t
.
S
y
(
1
≤
x
,
y
≤
j
) satisfy v
1
⇒
v
2 which is a strong rule, there will be probability tilt between t
.
S
x and t
.
S
y obviously. And according to the method of partition table, all the strong values in AT belong to the same sensitive attribute, so the probability tilts will not happen in AT. Besides, each S
i
I
D
j consists of at least L different values, so AT also satisfies L-diversity. And through the above analysis, we know that mixed model is able to satisfy L-diversity.


## 5. Analysis and Proof of Information Availability

This section analyzes the information loss of the new model from availability of association rules and the quality of published data table.


### 5.1. The Availability of Association Rules

In Rating model, all the relationships between different sensitive attributes are broken, the new model presented by this paper makes improvement, and all the strong rules can be preserved in released table.Lemma 22.
If the association rule is as follows:A
⇒
B
[confidence = s
(
0
≤
s
≤
1
)
], s ≥ m
i
n
_
c
o
n
f
i
d
e
n
c
e in the original data table, in the released data tables, the confidence of A
⇒
B is still s.Proof.
The released data tables contain SAC~ table, ID table, and the attribute table, and user can get the support degree of A from SAC~ table and ID table, namely, support(A), because in attribute table there is support
(
A
,
B
)
=
0, one only needs to get support(A
,
B) from the SAC~ table. So the confidence s of A
⇒
B is support(A
,
B)/support(A).
Here, we can see that the mixed model preserves all the strong association rules, and user can get the confidence of strong association rules from the released tables. And the Rating model breaks all the relationships between sensitive attributes and generates unnecessary information loss.


### 5.2. The Quality of Published Data Table

This part uses the reconstruction error (RCE) [9, 17] to measure the quality of the published tables. Assume original table T = (
Q
I
1
,
Q
I
2
,
…
,
Q
I
i
,
S
1
,
S
2
,
…
,
S
j) gets a i
+
j dimensional space D
S
i
+
j; for record t in table T, the probability density function (pdf) of t is(10)Ftx=1,ifx.QIp=t.QIp,x.Sq=t.Sq,1≤p≤i,1≤q≤j,0,otherwise.Here, thex is a i
+
j dimensional variable in D
S
i
+
j.For recordt in the released table of Rating, the pdf of t is(11)Ftratingx=∏q=1j1t.Sq,ifx.QIp=t.QIp,x.Sq∈t.Sq,1≤p≤i,1≤q≤j,0,otherwise.Assume the Cluster_Set =C
1
,
C
2
,
…
,
C
m in the mixed model, the Q
I
1
,
Q
I
2
,
…
,
Q
I
i
,
C
1
,
C
2
,
…
,
C
m defines a i
+
m dimensional space D
S
i
+
m. In the released tables of the mixed model, if t
∈
S
A
C
~, the pdf of t is (12)FtSAC~x=∏q=1m1t.Cq~,ifx.QIp=t.QIp,x.Cq∈t.Cq~,1≤p≤i,1≤q≤m,0,otherwise.Here,x is a i
+
m dimensional variable in D
S
i
+
m, t
.
C
q
~ represents the set of the possible values of t
.
C
q, and t
.
C
q
~ represents the number of the possible values. For example, in Table 6, a user wants to reconstruct the pdf of t
1; in his view, the t
1
.
C
1 can be (a
4
,
b
2) or (a
1
,
b
1) with equality probability 1/2, and t
1
.
C
2 can be c
2 or c
1 with equality probability 1/2, so the pdf of t
1 is(13)Ft1SAC~x=14,ifx.QIp=t1.QIp,x.C1=a4b2,x.C2=c2orx.QIp=t1.QIp,x.C1=a1b1,x.C2=c2,orx.QIp=t1.QIp,x.C1=a4b2,x.C2=c1orx.QIp=t1.QIp,x.C1=a1b1,x.C2=c11≤p≤i,0,otherwise.Ift
∈
AT, pdf of t is F
t
r
a
t
i
n
g
x. So in the released tables of mixed model, the pdf of t is(14)Ftmmx=FtSAC~x,t∈SAC~,Ftratingx,t∈AT.We can measure the distance between released tables of mixed model and original table as follows:(15)∑x∈SDi+mFtmmmmx-Ftx2.Here, assumet is a record in original table and t
mm is the form of t in released tables of mixed model. Similarly, t
rating is the form of t in released table of Rating, and the distance between released table of Rating model and original table is as follows:(16)∑x∈SDi+jFtratingratingx-Ftx2.The released table would have higher quality with the smaller distance. Take all the recordst
1
,
t
2
,
…
,
t
n into account, and the reconstruction error (RCE) of mixed model and Rating, respectively, are(17)∫k=1n∑x∈SDi+mFtmmmmx-Ftx2dk,∫k=1n∑x∈SDi+jFtratingratingx-Ftx2dk.Lemma 23.
If the original table contains strong rules, the RCE of mixed model is smaller than Rating model:(18)∫k=1n∑x∈SDi+mFtmmmmx-Ftx2dk<∫k=1n∑x∈SDi+jFtratingratingx-Ftx2dk.Proof.
To simplify the proof, assume both two models have no remaining attribute value to process, which meanst
mm
.
C
~ and t
rating
.
S satisfy t
mm
.
C
~
=
L, t
rating
.
S
=
L. In order to prove the conclusion, we only need to prove(19)∑x∈SDi+mFtmmmmx-Ftx2<∑x∈SDi+jFtratingratingx-Ftx2.For each t in AT table of mixed model, because the AT table satisfies the requirement of the Rating model, there exists ∑
x
∈
S
D
i
+
m
(
F
t
mm
mm
(
x
)
-
F
t
(
x
)
)
2
=
∑
x
∈
S
D
i
+
j
(
F
t
rating
rating
(
x
)
-
F
t
(
x
)
)
2. For each t in SAC~ table, one has(20)∑x∈SDi+mFtmmSAC~x-Ftx2=∑x.QIp=t.QIp,x.Cq=t.Cq1≤p≤i,1≤q≤m∏q=1m1tmm.Cq~-12+∑x.QIp=t.QIp,∃x.Cq≠t.Cq,x.Cq∈tmm.Cq~1≤p≤i,1≤q≤m∏q=1m1tmm.Cq~-02=∏q=1m1tmm.Cq~-12+∏q=1mtmm.Cq~-1∗∏q=1m1tmm.Cq~2=1-∏q=1m1tmm.Cq~.
Similarly, fort in released table of Rating, one has(21)∑x∈SDi+jFtratingratingx-Ftx2=1-∏q=1j1trating.Sq.
Because the original table has strong rules,m
<
j, t
mm
.
C
q
~
=
t
rating
.
S
q
=
L, (22)∏q=1j1trating.Sq<∏q=1m1tmm.Cq~,so1-∏q=1m1tmm.Cq~<1-∏q=1j1trating.Sq.
The mixed model has lower RCE than Rating, which means the released tables of mixed model are closer to the original table. The linking between sensitive attributes in the same cluster is preserved, so the mixed model has higher quality than the Rating.


## 5.1. The Availability of Association Rules

In Rating model, all the relationships between different sensitive attributes are broken, the new model presented by this paper makes improvement, and all the strong rules can be preserved in released table.Lemma 22.
If the association rule is as follows:A
⇒
B
[confidence = s
(
0
≤
s
≤
1
)
], s ≥ m
i
n
_
c
o
n
f
i
d
e
n
c
e in the original data table, in the released data tables, the confidence of A
⇒
B is still s.Proof.
The released data tables contain SAC~ table, ID table, and the attribute table, and user can get the support degree of A from SAC~ table and ID table, namely, support(A), because in attribute table there is support
(
A
,
B
)
=
0, one only needs to get support(A
,
B) from the SAC~ table. So the confidence s of A
⇒
B is support(A
,
B)/support(A).
Here, we can see that the mixed model preserves all the strong association rules, and user can get the confidence of strong association rules from the released tables. And the Rating model breaks all the relationships between sensitive attributes and generates unnecessary information loss.


## 5.2. The Quality of Published Data Table

This part uses the reconstruction error (RCE) [9, 17] to measure the quality of the published tables. Assume original table T = (
Q
I
1
,
Q
I
2
,
…
,
Q
I
i
,
S
1
,
S
2
,
…
,
S
j) gets a i
+
j dimensional space D
S
i
+
j; for record t in table T, the probability density function (pdf) of t is(10)Ftx=1,ifx.QIp=t.QIp,x.Sq=t.Sq,1≤p≤i,1≤q≤j,0,otherwise.Here, thex is a i
+
j dimensional variable in D
S
i
+
j.For recordt in the released table of Rating, the pdf of t is(11)Ftratingx=∏q=1j1t.Sq,ifx.QIp=t.QIp,x.Sq∈t.Sq,1≤p≤i,1≤q≤j,0,otherwise.Assume the Cluster_Set =C
1
,
C
2
,
…
,
C
m in the mixed model, the Q
I
1
,
Q
I
2
,
…
,
Q
I
i
,
C
1
,
C
2
,
…
,
C
m defines a i
+
m dimensional space D
S
i
+
m. In the released tables of the mixed model, if t
∈
S
A
C
~, the pdf of t is (12)FtSAC~x=∏q=1m1t.Cq~,ifx.QIp=t.QIp,x.Cq∈t.Cq~,1≤p≤i,1≤q≤m,0,otherwise.Here,x is a i
+
m dimensional variable in D
S
i
+
m, t
.
C
q
~ represents the set of the possible values of t
.
C
q, and t
.
C
q
~ represents the number of the possible values. For example, in Table 6, a user wants to reconstruct the pdf of t
1; in his view, the t
1
.
C
1 can be (a
4
,
b
2) or (a
1
,
b
1) with equality probability 1/2, and t
1
.
C
2 can be c
2 or c
1 with equality probability 1/2, so the pdf of t
1 is(13)Ft1SAC~x=14,ifx.QIp=t1.QIp,x.C1=a4b2,x.C2=c2orx.QIp=t1.QIp,x.C1=a1b1,x.C2=c2,orx.QIp=t1.QIp,x.C1=a4b2,x.C2=c1orx.QIp=t1.QIp,x.C1=a1b1,x.C2=c11≤p≤i,0,otherwise.Ift
∈
AT, pdf of t is F
t
r
a
t
i
n
g
x. So in the released tables of mixed model, the pdf of t is(14)Ftmmx=FtSAC~x,t∈SAC~,Ftratingx,t∈AT.We can measure the distance between released tables of mixed model and original table as follows:(15)∑x∈SDi+mFtmmmmx-Ftx2.Here, assumet is a record in original table and t
mm is the form of t in released tables of mixed model. Similarly, t
rating is the form of t in released table of Rating, and the distance between released table of Rating model and original table is as follows:(16)∑x∈SDi+jFtratingratingx-Ftx2.The released table would have higher quality with the smaller distance. Take all the recordst
1
,
t
2
,
…
,
t
n into account, and the reconstruction error (RCE) of mixed model and Rating, respectively, are(17)∫k=1n∑x∈SDi+mFtmmmmx-Ftx2dk,∫k=1n∑x∈SDi+jFtratingratingx-Ftx2dk.Lemma 23.
If the original table contains strong rules, the RCE of mixed model is smaller than Rating model:(18)∫k=1n∑x∈SDi+mFtmmmmx-Ftx2dk<∫k=1n∑x∈SDi+jFtratingratingx-Ftx2dk.Proof.
To simplify the proof, assume both two models have no remaining attribute value to process, which meanst
mm
.
C
~ and t
rating
.
S satisfy t
mm
.
C
~
=
L, t
rating
.
S
=
L. In order to prove the conclusion, we only need to prove(19)∑x∈SDi+mFtmmmmx-Ftx2<∑x∈SDi+jFtratingratingx-Ftx2.For each t in AT table of mixed model, because the AT table satisfies the requirement of the Rating model, there exists ∑
x
∈
S
D
i
+
m
(
F
t
mm
mm
(
x
)
-
F
t
(
x
)
)
2
=
∑
x
∈
S
D
i
+
j
(
F
t
rating
rating
(
x
)
-
F
t
(
x
)
)
2. For each t in SAC~ table, one has(20)∑x∈SDi+mFtmmSAC~x-Ftx2=∑x.QIp=t.QIp,x.Cq=t.Cq1≤p≤i,1≤q≤m∏q=1m1tmm.Cq~-12+∑x.QIp=t.QIp,∃x.Cq≠t.Cq,x.Cq∈tmm.Cq~1≤p≤i,1≤q≤m∏q=1m1tmm.Cq~-02=∏q=1m1tmm.Cq~-12+∏q=1mtmm.Cq~-1∗∏q=1m1tmm.Cq~2=1-∏q=1m1tmm.Cq~.
Similarly, fort in released table of Rating, one has(21)∑x∈SDi+jFtratingratingx-Ftx2=1-∏q=1j1trating.Sq.
Because the original table has strong rules,m
<
j, t
mm
.
C
q
~
=
t
rating
.
S
q
=
L, (22)∏q=1j1trating.Sq<∏q=1m1tmm.Cq~,so1-∏q=1m1tmm.Cq~<1-∏q=1j1trating.Sq.
The mixed model has lower RCE than Rating, which means the released tables of mixed model are closer to the original table. The linking between sensitive attributes in the same cluster is preserved, so the mixed model has higher quality than the Rating.


## 6. Experiment

The experiment uses the real dataset Adult (http://archive.ics.uci.edu/ml/datasets/Adult), we get 30718 records after deleting the incomplete ones, and the experiment consists of four parts: (1) execution time, (2) additional information loss, (3) accuracy rate of mining strong association rules, and (4) probability of privacy disclosure. We choose education, occupation, age, relationship as sensitive attributes, 2
Seducation, occupation, 3
Seducation, occupation, age, and 4
Seducation, occupation, age, relationship. If there are no special statements, the experiments use the default parameters: the number of records is 30718, and the min_confidence is 80%.


### 6.1. Execution Time

This paper presents an improved algorithm of Rating and mainly improves the algorithm of the SID creation, and the AT and IDT creation is the same as Rating. So this part will compare the improved algorithm of SID creation with the old one. Here, the old SID creation uses the stable bubble sort algorithm when choosing theL largest buckets. We set parameters L
=
3,2
S and choose a certain number of records randomly, and Figure 1 shows that the execution time of improved SID creation is much better than the old one, because of the heuristic search. And the improved SID creation is more suitable for the large dataset.Figure 1
The comparison of execution time,L
=
3,2
S.Figure2 shows the effect of sensitive attributes number on execution time. Because age has much more different values than other 3 sensitive attributes, Bubble sort needs more time to compare. After adding age attribute, the running time of SID creation increases rapidly. So the running time of SID creation is influenced seriously by the number of different values of sensitive attribute.Figure 2
The effect of sensitive attributes number on execution time,L
=
3,30
k.


### 6.2. Additional Information Loss

This part compares the additional information loss (AIL) [12] of mixed mode with the Rating. In order to make AIL more suitable for mixed model and Rating, we slightly change its definition. Assume sensitive S has m SID in IDT, the additional information loss of S is (23)AILS=∑i=1mSIDi-Lm∗L.Here,S
I
D
i represents the number of values in S
I
D
i.And the additional information loss of tableT is:(24)AILT=∑i=1jAILSij.Here,T has sensitive attributes S
1
,
S
2
,
…
,
S
j.Figure3 shows the AIL of the mixed model and Rating; when L increases, both the additional information losses of the two models increase basically. And the additional information loss of the mixed model is slightly more than the one of Rating but is always less than 0.03%, and the security of mixed model is enhanced. Here, Rating uses the stable bubble sort algorithm in SID creation. This part of experiment also finds an interesting phenomenon: if the sort algorithm in SID creation is unstable, the additional information loss will be much more than the stable sorting algorithm in SID. This phenomenon needs to be further studied.Figure 3
The comparison of additional information loss,2
S.Figure4 shows the effect of the minimum confidence on additional information loss. When the minimum confidence decreases, the additional information loss increases. Because more records are put in SAC table, the available sensitive attribute values in the IR table will be less, and additional information loss increases.Figure 4
The effect of minimum confidence on additional information loss,L
=
3,2
S.Figure5 shows the effect of number of sensitive attributes on additional information loss. Because all the sensitive attributes in Rating are processed independently, the AIL of Rating is almost not influenced by the number of sensitive attributes. For mixed model, when the number of sensitive attributes increases, more records are removed to SAC table, and values for grouping are less in IR table, so the AIL of mixed model grows with the sensitive attribute number but is still in the realm of acceptable.Figure 5
The effect of sensitive attribute number on additional information loss,L
=
4.


### 6.3. The Accuracy of Mining Strong Association Rules

Strong rules tend to be valuable in practice, so the ability to provide strong rules will be analyzed for publication models by this experiment. We use the method of Lemma22 to excavate strong association rules from the released tables of mixed model, and in the released tables of Rating and the raw data table, we use Apriori to calculate confidence of strong association rules.Figures6 and 7 show the average confidence of strong rules in the three tables. We can see that if all the records in SAC and all values in IR can be grouped, user can accurately calculate confidence of strong rules from the released tables of mixed model, and the results also verify the conclusion of Lemma 22. When L
=
5 in Figure 7, because the sensitive attribute relationship only has 6 different values and L is very close to 6, some records cannot be grouped in SAC, and they have to be deleted, and then the average confidence in mixed model deviates from the one in raw data table, but the difference is small. And the average confidence of strong rules in Rating greatly deviates from the one in raw data table; because Rating breaks all the relationships between sensitive attributes, it is difficult for users to calculate the confidence of strong rules from the released tables of Rating. Figures 8 and 9 show the similar results. Because mixed model has considered association rules between sensitive attributes, it can provide more valuable relationships than Rating in released tables.Figure 6
The average confidence of strong rules with varyingL, 2
S.Figure 7
The average confidence of strong rules with varyingL, 4
S.Figure 8
The average confidence of strong rules with varying the number of recordsL
=
3,2
S.Figure 9
The average confidence of strong rules with varying the number of records,L
=
3,4
S.


### 6.4. The Probability of Privacy Disclosure

We refer to the method of paper [15] and analyze the probability of disclosure in this experiment. Assume adversary has background knowledge about strong rules. Because the records containing no strong rules satisfy L-diversity according to [17] and previous analysis, we study the safety of records that contain strong rules in mixed model and Rating and analyze the probability that these records contain known strong rules from released tables. In Figure 10, x-dimension represents the probability of disclosure, and y-dimension represents the number of records. We can see that the probability records contain strong rules is 1/3 in the released tables of mixed model, mixed model can ensure a maximum of 1
/
L disclosure probability for records, and the conclusion of Lemma 12 is verified. On the other hand, because Rating has not considered the relationship between sensitive attributes, the disclosures probabilities for records in the released tables of Rating are more than 80%.Figure 10
The probability of disclosure,L
=
3,2
S.Figure11 shows the similar result, the disclosures probabilities for many records are more than 1
/
L
(
L
=
2
) in Rating, while mixed model ensures a maximum of 1/2 probability for records. Here we will discuss an extreme situation. Assume A
⇒
B is a strong rule, and in released tables of Rating, the number of records that actually contain A
⇒
B is m, and the number of records that may contain A
⇒
B is n; obviously, we have n
≥
m. But if A or B has very low frequency in raw data table, the n may be very small or even equals m. When n
=
m, adversary can be sure which records contain A
⇒
B in released tables of Rating. So we can see that the disclosures probabilities for several records of Rating are 100% in Figure 11. From these experiments, we can know that the mixed model can prevent adversary from attacking data table with related background knowledge, and it is able to provide better protection for privacy.Figure 11
The probability of disclosure,L
=
2,4
S.


### 6.5. Summary of Experiment

Section6.1 verifies the efficiency of the improved SID creation. And we know the additional information loss of mixed model is acceptable from the results of Section 6.2. Through the analysis of Sections 6.3 and 6.4, Rating cannot preserve strong rules in released tables, and as long as adversary masters background knowledge about these strong rules, Rating is unsafe. On the other hand, mixed model can provide strong rules for users forwardly and is able to ensure the security of privacy at the same time.


## 6.1. Execution Time

This paper presents an improved algorithm of Rating and mainly improves the algorithm of the SID creation, and the AT and IDT creation is the same as Rating. So this part will compare the improved algorithm of SID creation with the old one. Here, the old SID creation uses the stable bubble sort algorithm when choosing theL largest buckets. We set parameters L
=
3,2
S and choose a certain number of records randomly, and Figure 1 shows that the execution time of improved SID creation is much better than the old one, because of the heuristic search. And the improved SID creation is more suitable for the large dataset.Figure 1
The comparison of execution time,L
=
3,2
S.Figure2 shows the effect of sensitive attributes number on execution time. Because age has much more different values than other 3 sensitive attributes, Bubble sort needs more time to compare. After adding age attribute, the running time of SID creation increases rapidly. So the running time of SID creation is influenced seriously by the number of different values of sensitive attribute.Figure 2
The effect of sensitive attributes number on execution time,L
=
3,30
k.


## 6.2. Additional Information Loss

This part compares the additional information loss (AIL) [12] of mixed mode with the Rating. In order to make AIL more suitable for mixed model and Rating, we slightly change its definition. Assume sensitive S has m SID in IDT, the additional information loss of S is (23)AILS=∑i=1mSIDi-Lm∗L.Here,S
I
D
i represents the number of values in S
I
D
i.And the additional information loss of tableT is:(24)AILT=∑i=1jAILSij.Here,T has sensitive attributes S
1
,
S
2
,
…
,
S
j.Figure3 shows the AIL of the mixed model and Rating; when L increases, both the additional information losses of the two models increase basically. And the additional information loss of the mixed model is slightly more than the one of Rating but is always less than 0.03%, and the security of mixed model is enhanced. Here, Rating uses the stable bubble sort algorithm in SID creation. This part of experiment also finds an interesting phenomenon: if the sort algorithm in SID creation is unstable, the additional information loss will be much more than the stable sorting algorithm in SID. This phenomenon needs to be further studied.Figure 3
The comparison of additional information loss,2
S.Figure4 shows the effect of the minimum confidence on additional information loss. When the minimum confidence decreases, the additional information loss increases. Because more records are put in SAC table, the available sensitive attribute values in the IR table will be less, and additional information loss increases.Figure 4
The effect of minimum confidence on additional information loss,L
=
3,2
S.Figure5 shows the effect of number of sensitive attributes on additional information loss. Because all the sensitive attributes in Rating are processed independently, the AIL of Rating is almost not influenced by the number of sensitive attributes. For mixed model, when the number of sensitive attributes increases, more records are removed to SAC table, and values for grouping are less in IR table, so the AIL of mixed model grows with the sensitive attribute number but is still in the realm of acceptable.Figure 5
The effect of sensitive attribute number on additional information loss,L
=
4.


## 6.3. The Accuracy of Mining Strong Association Rules

Strong rules tend to be valuable in practice, so the ability to provide strong rules will be analyzed for publication models by this experiment. We use the method of Lemma22 to excavate strong association rules from the released tables of mixed model, and in the released tables of Rating and the raw data table, we use Apriori to calculate confidence of strong association rules.Figures6 and 7 show the average confidence of strong rules in the three tables. We can see that if all the records in SAC and all values in IR can be grouped, user can accurately calculate confidence of strong rules from the released tables of mixed model, and the results also verify the conclusion of Lemma 22. When L
=
5 in Figure 7, because the sensitive attribute relationship only has 6 different values and L is very close to 6, some records cannot be grouped in SAC, and they have to be deleted, and then the average confidence in mixed model deviates from the one in raw data table, but the difference is small. And the average confidence of strong rules in Rating greatly deviates from the one in raw data table; because Rating breaks all the relationships between sensitive attributes, it is difficult for users to calculate the confidence of strong rules from the released tables of Rating. Figures 8 and 9 show the similar results. Because mixed model has considered association rules between sensitive attributes, it can provide more valuable relationships than Rating in released tables.Figure 6
The average confidence of strong rules with varyingL, 2
S.Figure 7
The average confidence of strong rules with varyingL, 4
S.Figure 8
The average confidence of strong rules with varying the number of recordsL
=
3,2
S.Figure 9
The average confidence of strong rules with varying the number of records,L
=
3,4
S.


## 6.4. The Probability of Privacy Disclosure

We refer to the method of paper [15] and analyze the probability of disclosure in this experiment. Assume adversary has background knowledge about strong rules. Because the records containing no strong rules satisfy L-diversity according to [17] and previous analysis, we study the safety of records that contain strong rules in mixed model and Rating and analyze the probability that these records contain known strong rules from released tables. In Figure 10, x-dimension represents the probability of disclosure, and y-dimension represents the number of records. We can see that the probability records contain strong rules is 1/3 in the released tables of mixed model, mixed model can ensure a maximum of 1
/
L disclosure probability for records, and the conclusion of Lemma 12 is verified. On the other hand, because Rating has not considered the relationship between sensitive attributes, the disclosures probabilities for records in the released tables of Rating are more than 80%.Figure 10
The probability of disclosure,L
=
3,2
S.Figure11 shows the similar result, the disclosures probabilities for many records are more than 1
/
L
(
L
=
2
) in Rating, while mixed model ensures a maximum of 1/2 probability for records. Here we will discuss an extreme situation. Assume A
⇒
B is a strong rule, and in released tables of Rating, the number of records that actually contain A
⇒
B is m, and the number of records that may contain A
⇒
B is n; obviously, we have n
≥
m. But if A or B has very low frequency in raw data table, the n may be very small or even equals m. When n
=
m, adversary can be sure which records contain A
⇒
B in released tables of Rating. So we can see that the disclosures probabilities for several records of Rating are 100% in Figure 11. From these experiments, we can know that the mixed model can prevent adversary from attacking data table with related background knowledge, and it is able to provide better protection for privacy.Figure 11
The probability of disclosure,L
=
2,4
S.


## 6.5. Summary of Experiment

Section6.1 verifies the efficiency of the improved SID creation. And we know the additional information loss of mixed model is acceptable from the results of Section 6.2. Through the analysis of Sections 6.3 and 6.4, Rating cannot preserve strong rules in released tables, and as long as adversary masters background knowledge about these strong rules, Rating is unsafe. On the other hand, mixed model can provide strong rules for users forwardly and is able to ensure the security of privacy at the same time.


## 7. Summary

In view of the situation that most of existing privacy protection methods for multiple sensitive attributes have not taken the inherent relationship between different sensitive attributes into account, this paper presents that an attack method uses the association rules to get the users’ privacy and accordingly presents a protection model. Through theoretical and experimental analysis, we prove that the new protection model can provide better protection for privacy, and it is able to preserve useful relationships in released tables. Besides, in order to improve the efficiency of algorithm, we present an improved SID creation method, and prove it is more effective with experiment.



---

*Source: 464731-2015-08-20.xml*