CN102156755A - K-cryptonym improving method - Google Patents

Abstract

The invention discloses a K-anonymous improved method, which relates to the field of data mining, selects a quasi-identifier according to an original data set, determines a generalization mode, and establishes an initial generalization grid corresponding to the generalization mode; judges whether the initial generalization grid is is empty, if not, select the global optimal node from all the nodes in the initial generalized lattice according to the optimal node selection method, and obtain the first generalized lattice; perform anonymization processing on the data to be published according to the global optimal node, and obtain the anonymous The number of clusters; judge whether the number of anonymous clusters is less than the preset number, if yes, calculate the optimal node selection method for the first generalized lattice, and obtain the optimal node; if not, the anonymous cluster is an isolated cluster, and the first generalized lattice The grid performs secondary K-anonymous calculations to obtain the optimal node; generalizes the data to be released according to the generalization method corresponding to the optimal node, obtains the generalized data, and publishes the generalized data. The invention shortens the execution time and improves the accuracy of information.

Description

An improved K-anonymity method

technical field

The invention relates to K-anonymity in the field of data mining, in particular to an improved K-anonymity method.

Background technique

The commonly used processing methods for data anonymization are derived from the data processing methods in statistical databases, mainly through the loss of information on the attribute values in the published data in exchange for the accuracy of re-identifying some individuals through these attribute values, and at the same time It is possible to guarantee the availability of published data, and to achieve a balance between the accuracy of published data and privacy protection. Traditional privacy protection methods often sacrifice the accuracy of individual data records in order to ensure the overall trend of published data.

K-Anonymity (K-anonymity algorithm): K-anonymity (K-Anonymity) is different from traditional access control and other goal-based privacy protection technologies. It is a typical microdata release model (microdata is defined as an expression and description The data record of individual information is the carrier of individual information. These information include individual identification information (such as name, ID number, etc.), sensitive information (such as medical history, etc.), and some non-sensitive information (such as gender). Each information They are all used as a certain component of microdata (record) in the way of matching individual attributes and corresponding attribute values.). It requires that raw data be pre-processed to meet anonymity requirements before the processed data is published. It does not require restricting access to published data, but instead keeps data as statistically available as possible. Therefore, data generalization (generalization is an attribute of data, replacing the original value with a summary value to make it more meaningful) is a commonly used data preprocessing method. K anonymity means that in a set (here refers to a generalized set, which allows to contain the same element, similar to the concept of bag (Bag) or cluster (Cluster)) can only be no more than 1/k (k is a constant) The probability of any element is determined, that is, any element is required to have at least k-1 identical copy elements in the set. To express the concept of K-anonymity in a formal language, the attributes of individual records in the published data table are generally divided into three categories: identifier, quasi-identifier and sensitive attribute, and the concept of equivalence class is proposed. Here are the relevant definitions:

Identifiers: Identifier attributes refer to attributes that can directly identify the identity of an individual, such as name, ID number, social security number and other attributes, through which the specific individual can be directly determined.

实体表T的准标识符QI为属性组其中，

且满足f_g(f_c(p_i[QI]))＝p_i。换言之，同时存在于发布数据表和外部数据源表中，利用此两种数据表进行连接的推演来表示个人隐私信息的一组属性称为准标识符属性。准标识符属性也叫做类标识符属性。不同的发布数据表可以根据不同的情况划分不同的准标识符属性，一般情况下准标识符由专家选择，而非用户随便选取。一般情况下可以以年龄、教育程度、性别作为准标识符。Quasi-Indentifiers (QI): given entity set U, entity table T(A ₁ , A ₂ , LA _n ), f _c : U→T and f _g : T→U′, where,

The quasi-identifier QI of the entity table T is an attribute group in,

And it satisfies f _g (f _c (p _i [QI]))=p _i . In other words, a group of attributes that exist in both the published data table and the external data source table, and are deduced by using these two data tables to represent personal private information are called quasi-identifier attributes. Quasi-identifier properties are also called class-identifier properties. Different published data tables can be divided into different quasi-identifier attributes according to different situations. Generally, quasi-identifiers are selected by experts, not randomly selected by users. Generally, age, education level, and gender can be used as quasi-identifiers.

Sensitive attributes (Sensitive-Attributes, SA), personal privacy attributes. In the published data, the individual does not want other users to know the information attributes. For example, the salary level of the individual and the disease in the patient's medical record. When publishing data, in order to prevent the leakage of personal sensitive information, the identifier must be deleted, and the published data records only retain quasi-identifier attributes and sensitive attributes, which is called anonymization.

Equivalence group: An equivalence group composed of records whose projections on the quasi-identifier are exactly the same, that is, all records in the equivalence group have exactly the same attribute values on the quasi-identifier, and other attribute values can be different.

K-Anonymity: Given a data table T(A ₁ , A ₂ ...A _n ), QI is a quasi-identifier associated with T if and only if every sequence of values appearing in T[QI] is at least in T [QI] appears K times, then T satisfies K-anonymity. T[QI] represents the projection of the tuples in the T table on QI.

In real life, while disclosing information such as medical treatment, voting, and job hunting, it is necessary to hide the individual identification information of relevant patients, voters, and job applicants, and ensure that the published data cannot be used to derive these identification information. K-anonymity It is a very good optional model. When the data is released to the public database, and the owner of the data no longer continues to control the use and scope of the data, in this case, in order not to expose the identity of the data subject, remove all data item information related to individual identification. De-Identification (de-identification) identification) is a commonly used method.

The inventor finds that there is at least the following shortcoming in the prior art in the process of realizing the present invention:

The K-anonymity method in the prior art needs to compare all the nodes in the generalization grid when judging and comparing. When the scale of the generalization grid is relatively large, the execution time will be very long, which is very important for data processing. Unfavorable; this method is mostly globally optimal. Due to the inhomogeneity of data distribution, that is, there are isolated clusters (that is, a small number of sets), in order to meet the anonymous requirements, a higher generalization level has to be adopted. This obviously reduces the accuracy of the information.

Contents of the invention

In order to shorten the execution time and improve the accuracy of information, the present invention provides a K-anonymous improved method, which is described in detail below:

A kind of K-anonymous improved method, described method comprises the following steps:

(1) Select a quasi-identifier according to the original data set, determine the generalization mode by the quasi-identifier, and establish an initial generalization grid corresponding to the generalization mode;

(2) Judging whether the initial generalization lattice is empty, if yes, the process ends; if not, perform step (3);

(3) selecting the global optimal node from all the nodes of the initial generalization lattice according to the optimum node selection mode, and obtaining the first generalization lattice;

(4) Anonymize the data to be released according to the global optimal node, and obtain the number of anonymous clusters corresponding to the global optimal node;

(5) judging whether the quantity of the anonymous cluster is less than a preset quantity, if yes, perform step (6); if not, perform step (7);

(6) Performing the calculation of the optimal node selection method on the first generalized lattice to obtain the optimal node;

(7) The anonymous cluster is a non-isolated cluster, and the second K-anonymous calculation is performed on the first generalized lattice to obtain the optimal node;

(8) Generalize the data to be released according to the generalization method corresponding to the optimal node, obtain generalized data, publish the generalized data, and the process ends.

According to the optimal node selection method in step (3), the global optimal node is selected from all the nodes of the initial generalized lattice, and the first generalized lattice is obtained, specifically:

① Calculate the degrees of all nodes in the initial generalization lattice;

②Sorting all the nodes in the initial generalization lattice according to degree, and obtaining the node with the largest degree;

③ Judging whether the node with the largest degree satisfies K-anonymity, if yes, execute step ④; if not, execute step ⑤;

4. All parent nodes of the node with the largest degree are K-anonymous nodes, delete all ancestor nodes of the node with the largest degree, search the K-min set preserved in the original data set, and judge whether the K-min set is There is the ancestor of the node with the maximum degree, if yes, delete the ancestor of the node with the maximum degree from the K-min set; if not, perform step ⑥;

5. All descendant nodes of the node with the maximum degree are not K-anonymous nodes, delete the node with the maximum degree and all descendant nodes of the node with the maximum degree;

6. Calculate the information loss amount of all nodes in the K-min set, obtain the minimum information loss amount, use the node corresponding to the minimum information loss amount as the global optimal node, and obtain the first generalization lattice;

Wherein, calculating the amount of information loss of all nodes in the K-min set is specifically:

$\mathrm{<span\; class="notranslate">\; InfoLoss</span>}<span\; class="notranslate">\; =</span>\frac{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\frac{{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}{{\mathrm{<span\; class="notranslate">\; DGH</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}}{\mathrm{<span\; class="notranslate">\; N</span>}}$

Among them, N represents the number of quasi-identifiers in the tuple set, DGH _i represents the generalization level of the i-th quasi-identifier among N quasi-identifiers, and h _i represents the generalization degree of quasi-identifier i.

The beneficial effects of the technical solution provided by the invention are:

The invention provides an improved K-anonymity method. The method provided by the invention shortens the execution time, improves the accuracy of information, and meets the requirements in practical applications.

Description of drawings

Fig. 1 is the generalization mode of age Age provided by the present invention;

Fig. 2 is the generalization mode of gender Sex provided by the present invention;

Fig. 3 is the generalized grid of age Age and sex Sex provided by the present invention;

Fig. 4 is a flowchart of a K-anonymity improvement method provided by the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the implementation manner of the present invention will be further described in detail below in conjunction with the accompanying drawings.

In order to shorten the execution time and improve the accuracy of information, the embodiment of the present invention provides an improved K-anonymity method. The embodiment of the present invention is based on the K-anonymity algorithm for de-identifying private data. The processing is mainly to further optimize the generalization lattice after obtaining the optimal node, as described below for details:

101: Select a quasi-identifier according to the original data set, determine the generalization method by the quasi-identifier, and establish an initial generalization lattice corresponding to the generalization method;

表示该节点的在初始泛化格中的泛化等级(泛化高度)。两个或多个准标识符进行不同等级的泛化得到的结果构成准标识符泛化序列，这些准标识符泛化序列构成基于准标识符的泛化等级序列，称为泛化格。例如：年龄Age和性别Sex可以构成图3中的初始泛化格。根据各个准标识符相应的泛化方式可以建立初始泛化格，令T_i(A₁，…，A_k)和T_j(A₁，…，A_k)是两个不同表(即两者为初始泛化格Lattice中不同的节点，(A₁，…，A_n)为数据的k个准标识符，A_k为第i个准标识符的泛化等级或泛化高度)。泛化格中的每一个节点，表示一个准标识符一次泛化后的表，即为各准标识符泛化到此时对应的发布数据。Among them, the K-min set is saved after traversing the initial generalization lattice. See Figure 1, Figure 2 and Figure 3, for example: select the quasi-identifier Age and gender Sex from the original data set, and determine the generalization method by the quasi-identifier Age and sex Sex, the generalization method consists of the following generalization vectors: L(a ₁ ...a _i ...a _k ), where a _i represents the generalization level (generalization height) of each attribute of the node, and k is the number of attributes in the table; the generalization level:

Indicates the generalization level (generalization height) of the node in the initial generalization lattice. The results of different levels of generalization of two or more quasi-identifiers constitute a quasi-identifier generalization sequence, and these quasi-identifier generalization sequences constitute a quasi-identifier-based generalization level sequence, called a generalization lattice. For example: Age and Sex can constitute the initial generalization lattice in Figure 3. The initial generalization lattice can be established according to the corresponding generalization methods of each quasi-identifier, let T _i (A ₁ ,...,A _k ) and T _j (A ₁ ,...,A _k ) be two different tables (namely, both are different nodes in the initial generalization lattice Lattice, (A ₁ ,...,A _n ) are k quasi-identifiers of the data, A _k is the generalization level or generalization height of the i-th quasi-identifier). Each node in the generalization grid represents a table after one generalization of a quasi-identifier, that is, the corresponding published data of each quasi-identifier after generalization.

Wherein, the number of quasi-identifiers and generalization methods can be determined according to requirements in practical applications, and the embodiment of the present invention does not limit this during specific implementation.

102: Determine whether the initial generalization grid is empty, if yes, the process ends; if not, execute step 103;

103: Select the global optimal node from all the nodes of the initial generalized lattice according to the optimal node selection method, and obtain the first generalized lattice;

Among them, the steps of the optimal node selection method specifically include:

(1) Calculate the degree of all nodes in the initial generalized lattice;

Among them, all nodes in the initial generalization grid include parent nodes and child nodes, and the parent node is the upper layer node connected to the node; the child node is the lower layer node connected to the node; the calculation of the degree of each node is specifically: The product of the number of all parents of this node and the number of all direct children.

(2) Sort all the nodes in the initial generalized lattice according to degree, and obtain the node with the largest degree;

The sorting may adopt any sorting manner, for example, sorting from high to low or sorting from low to high, which is not limited in this embodiment of the present invention during specific implementation.

(3) Determine whether the node with the largest degree satisfies K-anonymity, if yes, execute step (4); if not, execute step (5);

(4) All parent nodes of the node with the largest degree are K-anonymous nodes, delete all ancestor nodes of the node with the largest degree, search the K-min set saved in the original data set, and judge whether there is an ancestor of the node with the largest degree in the K-min set , if yes, delete the ancestor of the node with the largest degree from the K-min set; if no, perform step (6);

Wherein, the ancestor node is specifically: the parent node of the node with the largest degree and the upper n layer nodes of the parent node, and the value of n is a positive integer greater than or equal to 1.

(5) All descendant nodes of the node with the maximum degree are not K-anonymous nodes, delete the node with the maximum degree and all descendant nodes of the node with the maximum degree;

(6) Calculate the information loss of all nodes in the K-min set, obtain the minimum information loss, and use the node corresponding to the minimum information loss as the global optimal node to obtain the first generalization lattice.

After the data is generalized, there will be a certain degree of distortion. The higher the degree of generalization, the greater the degree of data distortion. Publishing data is often used to analyze or research certain issues. Therefore, when publishing data, it is necessary not only to protect privacy leakage, but also to ensure that the published data has a small loss. Otherwise, even if the purpose of privacy protection is achieved, the published Data also loses value, and privacy protection doesn't make any sense.

Among them, the calculation of the information loss of all nodes in the K-min set is specifically:

$\mathrm{<span\; class="notranslate">\; InfoLoss</span>}<span\; class="notranslate">\; =</span>\frac{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\frac{{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}{{\mathrm{<span\; class="notranslate">\; DGH</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}}{\mathrm{<span\; class="notranslate">\; N</span>}}$

Among them, N represents the number of quasi-identifiers in the tuple set, DGH _i represents the generalization level of the i-th quasi-identifier among N quasi-identifiers, and h _i represents the generalization degree of quasi-identifier i. It can be seen from the above formula that the higher the degree of generalization, the greater the amount of information loss; the lower the degree of generalization, the smaller the amount of information loss.

104: Anonymize the data to be released according to the global optimal node, and obtain the number of anonymous clusters corresponding to the global optimal node;

Wherein, the data to be released is set according to the needs in the actual application, and the embodiment of the present invention does not limit it during specific implementation.

105: Determine whether the number of anonymous clusters is less than the preset number, if yes, execute step 106; if not, execute step 107;

106: Calculate the optimal node selection method for the first generalization lattice, and obtain the optimal node;

107: The anonymous cluster is a non-isolated cluster, and the second K-anonymous calculation is performed on the first generalized lattice to obtain the optimal node;

Among them, the second K-anonymity calculation for the first generalization lattice is specifically: taking out the i-th node in the minimum K anonymous node set; calculating the cluster information of the nodes of the first generalization lattice, including the node information representing each cluster And the corresponding capacity; take out the information of the jth cluster; add the information of the cluster; create a new lattice; calculate the information loss of the node on the data set firstdata; calculate the suppression rate of the secondary K-anonymity; perform on the data set seconddata K-anonymous calculation of suppression rate secondratio (degree-first algorithm); find out the node with the smallest amount of information loss in the smallest K-anonymous node set to obtain the optimal node.

Among them, the code for the secondary K-anonymous calculation is described below:

Input: size cluster cutoff value threshold

Output: minimum information loss smallinfo

Variables: firstdata is used to store isolated cluster data; seconddata is used to store secondary anonymous data; kmin is used to store the minimum set of K anonymous nodes

getnode(i): Take out the i-th node in the minimum K anonymous node set

getInfoOf(latticenode): Calculate the cluster information of the latticenode node, including the node information representing each cluster and the corresponding capacity

getcluster(j): Take out the information of the jth cluster

add(ClusterInfo.get(j)): Add cluster information

Lattice (Bnode, latticenode): create a new lattice

infoloss(latticenode, firstdata):

Calculate the information loss of the node latticenode on the dataset firstdata

SecondRatio(): Calculate the suppression rate of the secondary K-anonymity

Kmin(lattice, secondratio, seconddata): K-anonymous calculation of the suppression rate secondratio on the data set seconddata (degree priority algorithm)

GetsmallLatticenode(latticenode.kmin): Find the node with the smallest amount of information loss in the smallest K-anonymous node set

108: Generalize the data to be released according to the generalization method corresponding to the optimal node, obtain the generalized data, publish the generalized data, and the process ends.

To sum up, the embodiment of the present invention provides an improved K-anonymity method. The method provided by the embodiment of the present invention shortens the execution time, improves the accuracy of information, and meets the needs of practical applications.

Those skilled in the art can understand that the accompanying drawing is only a schematic diagram of a preferred embodiment, and the serial numbers of the above-mentioned embodiments of the present invention are for description only, and do not represent the advantages and disadvantages of the embodiments.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included in the protection of the present invention. within range.

Claims (2)

1. A kind of K-anonymous improved method is characterized in that, described method comprises the following steps: (1) Select a quasi-identifier according to the original data set, determine the generalization mode by the quasi-identifier, and establish an initial generalization grid corresponding to the generalization mode; (2) Judging whether the initial generalization lattice is empty, if yes, the process ends; if not, perform step (3); (3) selecting the global optimal node from all the nodes of the initial generalization lattice according to the optimum node selection mode, and obtaining the first generalization lattice; (4) Anonymize the data to be released according to the global optimal node, and obtain the number of anonymous clusters corresponding to the global optimal node; (5) judging whether the quantity of the anonymous cluster is less than a preset quantity, if yes, perform step (6); if not, perform step (7); (6) Performing the calculation of the optimal node selection method on the first generalized lattice to obtain the optimal node; (7) The anonymous cluster is a non-isolated cluster, and the second K-anonymous calculation is performed on the first generalized lattice to obtain the optimal node; (8) Generalize the data to be released according to the generalization method corresponding to the optimal node, obtain generalized data, publish the generalized data, and the process ends. 2. A kind of K-anonymity improved method according to claim 1, is characterized in that, described in step (3) selects global optimal node from all nodes of described initial generalization lattice according to optimal node selection mode. The superior node obtains the first generalization lattice, specifically: ① calculating the degrees of all nodes in the initial generalization lattice; ②Sorting all the nodes in the initial generalization lattice according to degree, and obtaining the node with the largest degree; ③ Judging whether the node with the largest degree satisfies K-anonymity, if yes, execute step ④; if not, execute step ⑤; 4. All parent nodes of the node with the largest degree are K-anonymous nodes, delete all ancestor nodes of the node with the largest degree, search the K-min set preserved in the original data set, and judge whether the K-min set is There is the ancestor of the node with the maximum degree, if yes, delete the ancestor of the node with the maximum degree from the K-min set; if not, perform step ⑥; 5. All descendant nodes of the node with the maximum degree are not K-anonymous nodes, delete the node with the maximum degree and all descendant nodes of the node with the maximum degree; 6. Calculate the information loss amount of all nodes in the K-min set, obtain the minimum information loss amount, use the node corresponding to the minimum information loss amount as the global optimal node, and obtain the first generalization lattice; Wherein, calculating the amount of information loss of all nodes in the K-min set is specifically: $\mathrm{<span\; class="notranslate">\; InfoLoss</span>}<span\; class="notranslate">\; =</span>\frac{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; N</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\frac{{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}{{\mathrm{<span\; class="notranslate">\; DGH</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}}{\mathrm{<span\; class="notranslate">\; N</span>}}$ Among them, N represents the number of quasi-identifiers in the tuple set, DGH _i represents the generalization level of the i-th quasi-identifier among N quasi-identifiers, and h _i represents the generalization degree of quasi-identifier i.

Images