Patent Publication Number: US-11641346-B2

Title: Data anonymity method and data anonymity system

Description:
TECHNICAL FIELD 
     The disclosure relates in general to a data anonymity method and a data anonymity system. 
     BACKGROUND 
     A data set may have direct-identifiers, quasi-identifiers (i.e. indirect-identifiers) and event logs. k-anonymity algorithm is used for data anonymity. For the direct-identifiers, the k-anonymity algorithm includes the step of replacing the content of the direct-identifiers by pseudonym. For the quasi-identifiers, the k-anonymity algorithm includes the steps of classifying the contents of the quasi-identifiers as several equivalence classes; generalizing the equivalence classes until the amount of the content of each of the equivalence classes is larger than k. However, the event logs corresponding the same direct-identifiers could be linked as an event sequence. The variability of the event sequences is larger than the event logs. If the steps described above are implemented for the event sequences, much information will be lost. 
     SUMMARY 
     The disclosure is directed to a data anonymity method and a data anonymity system. A data set having quasi-identifiers and event logs could be anonymized without loss much information. 
     According to one embodiment, a data anonymity method is provided. The data anonymity method includes the following steps. A data set comprising a plurality of direct-identifiers, a plurality of quasi-identifiers and a plurality of event logs each of which includes an activity and a timestamp is obtained. A content of each of the direct-identifiers is replaced by a pseudonym. The quasi-identifiers are classifying, via a group-by algorithm with k-anonymity, as a plurality of equivalence classes each of which has a quantity larger than k. The activities corresponding to each of the direct-identifiers are linked according to the timestamps to obtain a plurality of event sequences. A similarity hierarchy tree is obtained according to a plurality of edit distances among the event sequences. The event sequences are grouped according to the similarity hierarchy tree with k-anonymity to obtain at least one group whose size is larger than or equal to k. The event sequences which are in the group are generalized. 
     According to another embodiment, a data anonymity system is provided. The data anonymity system includes an inputting unit, a pseudonym unit, a classifying unit, a linking unit, a tree creating unit, a grouping unit and a generalizing unit. The inputting unit is for obtaining a data set comprising a plurality of direct-identifiers, a plurality of quasi-identifiers and a plurality of event logs each of which includes an activity and a timestamp. The pseudonym unit is for replacing a content of each of the direct-identifiers by a pseudonym. The classifying unit is for classifying, via a group-by algorithm with k-anonymity, the quasi-identifiers as a plurality of equivalence classes each of which has a quantity larger than k. The linking unit is for linking the activities corresponding to each of the direct-identifiers according to the timestamps to obtain a plurality of event sequences. The tree creating unit is for obtaining a similarity hierarchy tree according to a plurality of edit distances among the event sequences. The grouping unit is for grouping the event sequences according to the similarity hierarchy tree with k-anonymity to obtain at least one group whose size is larger than or equal to k. The generalizing unit is for generalizing the event sequences which are in the group. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG.  1    shows a block diagram of a data anonymity system according to one embodiment. 
         FIG.  2    shows a flowchart of a data anonymity method according to one embodiment. 
         FIG.  3    shows a data set according to one embodiment. 
         FIG.  4    shows the data set whose direct-identifiers are replaced. 
         FIG.  5    shows the data set whose quasi-identifier has been generalized and whose activities are linked. 
         FIG.  6    shows a similarity hierarchy tree. 
         FIGS.  7  to  9    illustrate the step S 140  according to one embodiment. 
         FIG.  10    illustrates the step S 150  according to one embodiment. 
         FIG.  11    shows a group whose size is 6. 
         FIG.  12    illustrates the information loss of different data anonymity methods. 
         FIG.  13    shows a flow chart of a data anonymity method according another embodiment. 
         FIG.  14    illustrates the steps in  FIG.  13   . 
     
    
    
     In the following detailed description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the disclosed embodiments. It will be apparent, however, that one or more embodiments may be practiced without these specific details. In other instances, well-known structures and devices are schematically shown in order to simplify the drawing. 
     DETAILED DESCRIPTION 
     Please refer to  FIG.  1   , which shows a block diagram of a data anonymity system  1000  according to one embodiment. The data anonymity system  1000  includes an inputting unit  110 , a pseudonym unit  111 , a classifying unit  112 , a linking unit  120 , a tree creating unit  130 , a grouping unit  140  and a generalizing unit  150 . The inputting unit  110  is a wireless transmission module, a data transmission cable, a card reader, or a data bus. The pseudonym unit  111 , the classifying unit  112 , the linking unit  120 , the tree creating unit  130 , the grouping unit  140  and the generalizing unit  150  is a circuit, a chip, or a circuit board. In the data anonymity system  1000 , a similarity hierarchy tree TR is created to assist the grouping of a plurality of event sequences SQ, such that the event sequences SQ could be generalized. The operation of those elements in the data anonymity system  1000  is illustrated via a flowchart as below. 
     Please refer to  FIG.  2   , which shows a flowchart of a data anonymity method according to one embodiment. In step S 110 , the inputting unit  110  obtains a data set DS comprising a plurality of direct-identifiers DI, a plurality of quasi-identifiers QI and a plurality of event logs EL. Please refer to  FIG.  3   , which shows the data set DS according to one embodiment. In the example pf  FIG.  3   , each of the event logs EL includes an activity AT and a timestamp TT. For example, the direct-identifier DI may be an identity card number or name; the activity AT may be the medical procedure; the quasi-identifier QI may be the age. 
     Next, please refer to  FIG.  4   , which shows the data set DS whose direct-identifiers DI are replaced. In step S 111 , the pseudonym unit  111  replaces the contents of the direct-identifiers DI by pseudonyms. 
     Afterwards, please refer to  FIG.  5    which shows the data set whose quasi-identifier QI has been generalized and whose activities AT are linked. In step S 112 , the classifying unit  112  classifies, via a group-by algorithm with k-anonymity, the quasi-identifiers QI as a plurality of equivalence classes EC each of which has a quantity larger than k. For example, the quasi-identifiers QI may be the ages “1, 2, 3, . . . , 99.” In each equivalence class EC, the content of the quasi-identifier QI is identical. The equivalence classes EC may be “age is 20”, “age is 25”, “age is 30”, “age is 35”, . . . and so on. The ages “1, 2, 3, 4, 5” could be combined into the age “5”; the ages “6, 7, 8, 9, 10” could be combined into the age “10”; the ages “11, 12, 13, 14, 15” could be combined into the age “15”; and so on. The ages “1, 2, 3, . . . , 99” are classified as “5, 10, 15, 20, 25, . . . , 90, 95.” 
     Next, in step S 120 , the linking unit  120  links the activities AT corresponding to each of the direct-identifiers DI according to the timestamps TT to obtain a plurality of event sequences SQ. For example, the activities AT “ER Registration”, “ER triage”, “ER Sepsis Triage” have been linked via “@” to obtain one event sequence SQ “@ER Registration@ER triage@ER Sepsis Triage.” In this step, the activities AT in each of the event sequences SQ are sorted over time. For example, “ER Registration”, “ER triage”, “ER Sepsis Triage” are recorded in chronological order, so the event sequence SQ records as “@ER Registration@ER triage@ER Sepsis Triage.” 
     Then, please refer to  FIG.  6   , which shows a similarity hierarchy tree TR. In step S 130 , the tree creating unit  130  obtains the similarity hierarchy tree TR according to a plurality of edit distances among the event sequences SQ. The edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other. If the edit distances among some of the event sequences SQ are less than a predetermined value, those event sequences SQ are classified as one cluster. 
     Referring to  FIG.  6   , all of the event sequences SQ are classified as a plurality of first level clusters f 0 , f 1 , . . . , f 138 . The amounts of the content of the first level clusters f 0 , f 1 , . . . , f 138  are similar. The first level clusters f 0 , f 1 , . . . , f 138  respectively have first centers c 11 , c 12 , . . . , c 1138 . The first centers c 11 , c 12 , . . . , c 1138  are the medians of the first level clusters f 0 , f 1 , . . . , f 138 . 
     The first centers c 11 , c 12 , . . . , c 1138  are classified as a plurality of second level clusters e 0 , e 1 , . . . , e 23 . The amounts of the content of the second level clusters e 0 , e 1 , . . . , e 23  are similar. The second level clusters e 0 , e 1 , . . . , e 23  respectively have second centers c 21 , c 22 , . . . , c 223 . The second centers c 21 , c 22 , . . . , c 223  are the medians of the second level clusters e 0 , e 1 , . . . , e 23 . 
     The second centers c 21 , c 22 , . . . , c 223  are classified as a plurality of third level clusters d 0 , . . . , d 7 . The amounts of the content of the third level clusters d 0 , . . . , d 7  are similar. The following levels are analogized in this way. 
     Then, please refer to  FIGS.  7  to  9   , which illustrate the step S 140  according to one embodiment. In step S 140 , the grouping unit  140  groups the event sequences SQ according to the similarity hierarchy tree TR with k-anonymity to obtain at least one group whose size is larger than or equal to k. For example, k is 3. 
     As shown in the example of  FIG.  7   , for the equivalence class EC which is “age is 20”, six kinds of event sequences SQ (“@ER Registration@ER Triage@CRP@LacticAcid@Leuc . . . ”, “@ER Registration@ER Triage@CRP@Leucocytes@ER S . . . ”, “@ER Registration@ER Triage@ER Sepsis Triage@”, “@ER Registration@ER Triage@ER Sepsis Triage@IV . . . ”, “@ER Registration@ER Triage@ER Sepsis Trage@Le . . . ”, “@ER Registration@ER Triage@Leucocytes@CRP@Lact . . . ”) are shown. The grouping unit  140  groups the five identical event sequences SQ (“@ER Registration@ER Triage@ER Sepsis Triage@”) whose quantity is maximum to obtain a group G 1 . The size of the group G 1  is larger than k, i.e. 3. After grouping the five identical event sequences SQ (“@ER Registration@ER Triage@ER Sepsis Triage@”), six event sequences SQ (“@ER Registration@ER Triage@CRP@LacticAcid@Leuc . . . ”, “@ER Registration@ER Triage@CRP@Leucocytes@ER S . . . ”, “@ER Registration@ER Triage@ER Sepsis Triage@IV . . . ”, “@ER Registration@ER Triage@ER Sepsis Trage@Le . . . ”, “@ER Registration@ER Triage@Leucocytes@CRP@Lact . . . ”) are remained. 
     Referring to  FIG.  8   , for the equivalence class EC which is “age is 20”, each of the six remained event sequences SQ is labeled as one of the first level clusters f 0  to f 138 . For example, “@ER Registration@ER Triage@CRP@LacticAcid@Leuc . . . ” is labeled as the first level cluster f 14 ; “@ER Registration@ER Triage@ER Sepsis Triage@Le . . . ” is labeled as the first level cluster f 83 ; “@ER Registration@ER Triage@ER Sepsis Triage@IV . . . ” is labeled as the first level cluster f 54 ; and so on. The grouping unit  140  groups the three event sequences SQ which are labeled as the first level cluster f 83  to obtain a group G 2  whose size is 3. The size of the group G 2  is equal to k, i.e. 3. After grouping the three event sequences SQ according to the first level cluster f 83 , three event sequences SQ (“@ER Registration@ER Triage@CRP@LacticAcid@Leuc . . . ”, “@ER Registration@ER Triage@ER Sepsis Triage@IV . . . ”, “@ER Registration@ER Triage@Leucocytes@CRP@Lact . . . ”) which are labeled as different first level clusters f 14 , f 54 , f 121  are remained. 
     Referring to  FIG.  9   , each of the three remained event sequences SQ (“@ER Registration@ER Triage@CRP@LacticAcid@Leuc . . . ”, “@ER Registration@ER Triage@ER Sepsis Triage@IV . . . ”, “@ER Registration@ER Triage@Leucocytes@CRP@Lact . . . ”) is labeled as one of the second level clusters e 0  to e 23 . For example, “@ER Registration@ER Triage@CRP@LacticAcid@Leuc . . . ” is labeled as the second level cluster e 7 ; “@ER Registration@ER Triage@ER Sepsis Triage@IV . . . ” is labeled as the second level cluster e 7 ; “@ER Registration@ER Triage@Lecicytes@Lact . . . ” is labeled as the second level cluster e 16 . Among the three remained event sequences SQ, the second level cluster e 7  is the largest group and the size thereof is 2. The size of this group is not larger or equal to k, i.e. 3. So the three remained event sequences SQ could not be grouped according to the second level cluster e 7 . 
     Referring to  FIG.  9   , each of the three remained event sequences SQ is further labeled as one of the third level clusters d 0  to d 7 . For example, “@ER Registration@ER Triage@CRP@LacticAcid@Leuc . . . ” is labeled as the third level cluster d 5 ; “@ER Registration@ER Triage@ER Sepsis Triage@IV . . . ” is labeled as the third level cluster d 5 ; “@ER Registration@ER Triage@Lecicytes@Lact . . . ” is labeled as the third level cluster d 5 . The grouping unit  140  groups three the event sequences SQ which are labeled as the third level cluster d 5  to obtain a group G 3  whose size is 3. The size of the group G 3  is equal to k, i.e. 3. 
     Referring to  FIG.  10    which illustrates the step S 150  according to one embodiment. As shown in  FIGS.  9  and  10   , the event sequences SQ are grouped in the group G 1 , the group G 2  and the group G 3 . In the group G 1 , all of the event sequences SQ are identical, so the event sequences SQ in the group G 1  are not needed to be generalized. 
     As shown in  FIGS.  9  and  10   , in step S 150 , the generalizing unit  150  generalizes the event sequences SQ which are in the group G 2 . In the group G 2 , the quantity of “@ER Registration@ER Triage@ER Sepsis Triage@Le . . . ” is 2, and the quantity of “@ER Registration@ER Triage@CRP@Leucocytes@ER S . . . ” is 1. “@ER Registration@ER Triage@ER Sepsis Triage@Le . . . ” has largest quantity. Each of the event sequences SQ in the group G 2  is replaced by a generalization sequence “@ER Registration@ER Triage@ER Sepsis Triage@Le . . . ” whose quantity is largest. 
     As shown in  FIGS.  9  and  10   , in step S 150 , the generalizing unit  150  generalizes the event sequences SQ which are in the group G 3 . Each of the event sequences SQ in the group G 3  is replaced by a generalization sequence “@ER Registration@ER Triage@CRP@LacticAcid@Leuc . . . ”. 
     Base on above, a data set DS having quasi-identifiers QI and event logs EL could be anonymized without loss much information. 
     If the size of the group is larger than (n−1)*k and less than or equal to n*k, the event sequences SQ in this group are replaced by n generalization sequences. For example, please refer to  FIG.  11   , which shows a group G 4  whose size is 6. In  FIG.  11   , the size of the group G 4  is 6 which is equal to 2*k, the event sequences SQ in the group G 4  are replaced by 2 generalization sequences (“@ER Registration@ER Triage@ER Sepsis Triage@Le . . . ” and “@ER Registration@ER Triage@CRP@Leucocyies@ER S . . . ”). 
     For another example, if the size of the group is 7 which is larger than (3−1)*k and less than 3*k, the event sequences SQ in this group will be replaced by 3 generalization sequences. 
     Please refer to  FIG.  12   , which illustrates the information loss of different data anonymity methods. Curve C 1  illustrates the information loss of the present disclosed data anonymity method. Curve C 2  illustrates the information loss of a conventional data anonymity method. As shown in  FIG.  12   , for any value of k, the variants of the event sequences SQ of the curve C 1  is much higher than that of the curve C 2 . Thus, the information loss of the present disclosed data anonymity method is much less than that of the conventional data anonymity method. 
     Please refer to  FIG.  13    and  FIG.  14   .  FIG.  13    shows a flow chart of a data anonymity method according another embodiment, and  FIG.  14    illustrates the steps in  FIG.  13   . In one embodiment, the timestamps may be anonymized without loss much information. In step S 210 , the generalizing unit  150  generalizes the timestamps. For example, “2019-3-26”, “2019-7-28” and “2019-10-30” have been generalized as “3”, “7” and “10” respectively. 
     Then, in step S 220 , the linking unit  120  link the timestamps corresponding to each of the direct-identifiers DI to obtain a plurality of timestamps sequences TTS, such as “[3, 7, 10]”, “[2, 4, 9]”, “[1, 3, 11].” 
     Next, in step S 230 , the generalizing unit  150  generalizes the timestamps sequences TTS. For example, “[3, 7, 10]”, “[2, 4, 9]”, and “[1, 3, 11]” are replaced by “[[1-4], [7-11]].” In this step, [1-4] overlaps with all of the timestamps sequences TTS and [7-11] overlaps with all of the timestamps sequences TTS. The “[[1-4], [7-11]]” has the lowest information loss. The information loss of [t1, t2] is calculated by the following equation (1):
 
(t2−t1)/(maximum of the timestamp−minimum of the timestamp)  (1)
 
Base on above, the timestamps could be anonymized without loss much information.
 
     According to the embodiments disclosed above, the event sequences SQ and the timestamps sequences TTS could be anonymized without loss much information. 
     It will be apparent to those skilled in the art that various modifications and variations could be made to the disclosed embodiments. It is intended that the specification and examples be considered as exemplary only, with a true scope of the disclosure being indicated by the following claims and their equivalents.