Proceedings of International Conference on
Technology and Social Science 2018 (ICTSS 2018)
Invited Paper

Optimization of Attributes Elimination Orderin a Privacy-Enhanced Survey System
Atsushi Iwai
Faculty of Social and Information Studies, Gunma University, 4-2 Aramaki-mach,
Maebashi City, Gunma Prefecture, 371-8510, Japaniwai@gunma-u.ac.jp
Keywords: attributes elimination, privacy preservation, social survey, anonymity

Abstract. This study presents a design for the optimization of the attributes elimination order in a
privacy-enhanced survey system. The target survey system comprises a framework that analyzes the
input data to find elements that can cause an information leakage and a mechanism to correct such
flaws by modifying the questionnaire design in the database. The original framework employs themethod of eliminating attributes in the modification of the questionnaire design, and the order of theelimination must be predetermined by researchers. This study presents a new design for automatizing
the selection of the best elimination order.

1. Introduction
This study presents a design for the optimization of the attributes elimination order in a
privacy-enhanced survey system. By expanding on survey systems that were designed in previous
studies, a formal description of the new enhanced survey system design is to be demonstrated.
The target survey system comprises a framework that analyzes the input data to find elements that
could cause an information leakage and a mechanism to correct such flaws by modifying thequestionnaire design in the database. Technical tools for enhancing privacy such as k-anonymity by
Sweeny ([6]) and l-diversity by Machanavajjhala et al. ([5]) are widely known. However, theseframeworks do not address the problem of protecting personal information from the survey assessors.
In several survey projects that focus on evaluation by users, such as class evaluation or hospital
evaluation, the privacy from organization staff is important for preventing the deterioration of thequality of the obtained data. The target system is expected to be advantageous in the case of this typeof surveys.
The original framework, however, employs the eliminating attributes method in the modificationof the questionnaire design, and the order of the elimination should be predetermined by researchers.
This study presents a new design for automating the selection of the best elimination order.
2. Previous Studies
This study focuses on the typical survey system design presented in the previous studies [1], [3],[4]. The basic design approach is exemplified as follows for the purpose of illustrating the inherent
issues: A course evaluation was conducted in a small class comprising 3 male and 15 female students
with a single question sheet that contained a question concerning gender and other questions
regarding the course evaluation. This could be potentially harmful to the male students’ privacy andcould result in a deterioration in the quality of the obtained data. However, if the question sheet was
divided into two parts, with one part including only the gender question and the other part only theProceedings of International Conference on
Technology and Social Science 2018 (ICTSS 2018)
Invited Paper
course evaluation questions, then no privacy problem would arise to compromise the quality of thestudents’ answers. The target system processes this division operation after all the students havefinished responding to the questionnaire and when it finds problematic questions that can lead to
information leakage. The division process is realized as a database operation for modifying the tablestructure related to the questionnaire design. As the computational process is triggered automaticallyand is perfectly completed before a lecturer obtains the output of the system, no information leakage
is possible.
This system design is based on the hypothesis that all the questions in a question sheet can bedivided into two categories, X and Y. X is defined as a category comprising individual attributes,
such as gender or age. Y is defined as a category comprising individual attitudes such as the course
evaluation. For each Y category question, a cross tabulation of several X-category questions is likely
to yield special cells wherein only a small number of respondents exist, and these cells are likely tocause some unintended information leakage. In surveys with multiple X-category questions, thequestion sheet is divided by considering each X item one by one, i.e., the process of protecting
privacy takes the form of attributes elimination.

Figure 1 An Example of Questionnaire Design Modification Process ([1])
Figure 1 illustrates an example of a questionnaire design modification comprising the process of
the attributes elimination ([1]). In this example, the question sheet has three X items: q7, q10, andq11, and the rest of the questions are all Y items. The researcher is interested in the X items in theorder of q7, q10, and q11. The answer dataset for each of the Y items first has a relationship with thethree X items. However, according to the anonymity level examined, it drops from the layer A3
toward the layer A0 (the layer An represents the answer dataset that retains its relationship with n X
items.) For example, A0 comprises the answer data for q6, q8, and q9 but has no relationship with an
X item. A1 comprises the answer data of q2 and q5 but has one relationship with an X item (q7).
In this framework, the anonymity level is calculated with a combinatorial-approach measure whichtakes the form of log (MCN). It measures the degree of difficulty in dividing members into particular
categories, like the positive-answer group and the negative-answer group. (In the formula of log(MCN) M typically denotes the total number of all people and N denotes the number of people who
answered positively (or negatively). Please refer to section 4 of [2] for the mathematical details of
this measure.)
It should be noted that the question items should belong to the same layer if the researcher
conducts a multiple variable analysis. In this example, it is assumed that the researcher intends to
conduct a multiple variable analysis with the answer results of q6, q8, and q9. These questions
comprise a question block, for which the result of the anonymity level test equals the result of thelowest test result obtained for each question independently.

Proceedings of International Conference on
Technology and Social Science 2018 (ICTSS 2018)
Invited Paper
However, in this original framework, the order of elimination should be predetermined byresearchers and the result of the calculation is dependent on the order. In an unfortunate case, itwould result in elimination of a large number of X category items and the limitation of obtained
information. For an example, if the predetermined order leads to the elimination of all X category
items for each of Y category item, the researcher will have no information about the correlation
between an X category item and a Y category item.
3. Optimization Design of the Attributes Elimination Order
This section presents a new design for automating the selection of the best elimination order. The
basic approach of this paper is as follows: 1) the system attempts to calculate all the possible
elimination orders, and 2) it determines the result that retains the greatest amount of X-item
information and outputs it.
One of the most critical points to design is the measure for evaluating the remaining X-item
information. This paper employs an evaluation method of counting the remaining X-item data (eachnumber is incremented by 1 in preparation for further use).

Figure 2 A Comparison of Two Modification Processes
Figure 2 shows two application examples of the counting method. In each case, it is assumed thatthe question sheet originally has three X items: q9, q10, and q11 but no predetermined order was set
by the researcher. The rest of the questions are Y items. In case [i], the system attempted to use theelimination order of q11, q10, and q9. The summation of the X-item number for each Y-item equals
17 (each circle refers to the X-item numbers). In case [ii], the system attempted to use the elimination
order of q10, q11, and q9. This result equals 18 and is better than that obtained in case [i]. The
number of possible elimination orders equal |X|!, which is the same as the number of repetitions of
this calculation.
Although this test does not reflect relational aspects such as the multiple analysis possibility, it cancompare multiple possible output data patterns efficiently and is considered to be a reasonable
comparison method.
4. Formal Description of Expanded Privacy-Enhanced Survey System
This section details the design of the expanded privacy-enhanced survey system. The essential
incremental part for the purpose of this study is introducing ZMAP and ZSET functions. While thedesign follows the hospital evaluation version described in [4], the core functions are also applicableto other versions. Furthermore, although the formal description of some functions differs fromprevious related studies, without these core functions and their application in the routines, theProceedings of International Conference on
Technology and Social Science 2018 (ICTSS 2018)
Invited Paper
process would be mathematically equivalent to the process described in [3] and [4] (both areaccessible online).
The formal description of the system implementation is as follows:[Sets of Respondents and Questions]
P denotes the set of all the respondents or patients. Using the respondent number i(i ≤ i ≤ N ) , wecan define P as follows:
P = {1,2, … , N }Q represents the set of all the questions in a question form. Each element of Q is classified as either
X and Y items. Each element of X is classified as BPI and MD. The X items x 1 ,x 2 , … , x n
represent individual attributes that are observable by medical staff. The Y items y 1 ,y 2 , … , y m
represent individual attitudes that are not observable even by medical staff. BPI items
bpi1, bpi2 ,…, bpii represent basic personal information and MD items md 1, md 2,…, md d
medical data.

BPI = {bpi1 ,bpi 2 ,…, bpii }MD = {md 1,md 2,…, md d }X = {x1 ,x 2 ,…, x n }Y = { y1,y 2 ,…, y m }X = BPI ∪ MD

Q= X ∪ Y

Z = {z 1,z 2 ,… , z n } = ZSET ( zmap ), zmap ∈ ZMAP ( X )The function ZMAP (X ) returns the set of all possible one-to-one mappings from X to
Z(=X)={ z 1,z 2 , … , z n }. The function ZSET (zmap) returns the set Z according to the mapping
information zmap ∈ ZMAP (X ) . The index numbers of Z items z 1,z 2 ,…, z n denote the supposed
priority (an item with a relatively large index number is eliminated faster in the database). Since X isa finite set, one can add a total order to X. That is to say, X can be regarded to be a totally ordered set.
The function ZMAP (X ) transforms the total order of X. The function ZSET (zmap) returns one ofthe possible totally ordered sets whose base set is the same as that of X and whose total order isobtained by ZMAP (X ) .
[Respondents’ Answers]
For ∀q ∈ Q , D (q ) represents the domain of the answer to the question q. The 3-tuple (i, q, a)
indicates that a respondent i ∈ P selected the answer a ∈ D(q) for the question q ∈ Q . T0
denotes the set of all such 3-tuples and contains the information of all the answers provided by all the
respondents. For ∀q ∈ Y , DC (q) is defined as the set of all D (q ) elements that are sensitive
alternatives that require their selectors to be concealed. That is, Dc(q ) represents the set of theProceedings of International Conference on
Technology and Social Science 2018 (ICTSS 2018)
Invited Paper
alternatives of a negative evaluation.
[Question Block]A question block is defined as a non-empty subset of Y . Different questions that belong to aquestion block are expected to be analyzed together using multivariate analysis methods. Eachquestion belongs one of the question blocks. When the total number of question blocks is M
( Block j (1 ≤ j ≤ M ) ), for all j (1 ≤ j ≤ M ) , the following holds true.
Block j ≠ φi ≠ j → Block i ∩ Block j = φ
Y =  Block j
1≤ j ≤ M

For each Block j (1 ≤ j ≤ M ) , (the initial value of) the set of answers AB j (1 ≤ j ≤ M ) can be defined
as follows:
AB j = Select (T0 , 2, Z ∪ Block j )Here, Select(S1, j, S2 ) is a function that selects the 3-tuple of S1 when the j-th element of the
3-tuple belongs to set S 2 , and returns the subset of S1 . Similarly, Del(S1 , j, S2 ) is a function thateliminates the 3-tuple of S1 when the j-th element of the 3-tuple belongs to set S 2 , and returns thesubset of S1 . Prj ( S , j ) is a function that returns the set of all j-th elements of the 3-tuples thatbelong to S . Similarly, Rand ( S , j ) is a function that swaps the j-th elements of all the 3-tuples of
S and returns the set that can be obtained as a result of the calculation.
[Grouping of Respondents by Individual Attributes]
For Prj ( AB j , 2) ∩ Z = {z1 , z2 , ..., zk },Dz ( AB j ) = D( z1 ) × D( z2 ) ×× D( zk )is defined. As each element of {z1 , z 2 ,..., z k } represents a question regarding individual attributes,
the answer of i ∈ Prj ( AB j ,1) is related to one point of Dz ( AB j ) (in the case of Dz ( AB j ) = φ , weconsider this point to be φ ). The respondent group that relates to point z of Dz ( AB j ) is denoted as
Grp ( AB j , z)(⊂ P) (in the case of Dz ( AB j ) = φ , Grp ( AB j , z) = P ).

[Finding Risky Elements]
Level ( AB j , z, q) , which represents the anonymity level observed at z ∈ Dz ( AB j ) and q ∈ B j with
AB j , is defined as follows:
Level ( AB j , z, q) = log (| DATA |!
)| DATA − DATAc |!× | DATAc |!

Here, DATA and DATAc are the abbreviations of DATA ( AB j , z, q) and DATAc ( AB j , z, q) , which
are defined as follows:Proceedings of International Conference on
Technology and Social Science 2018 (ICTSS 2018)
Invited Paper
DATA( AB j , z , q ) = Select ( AB j ,1, Grp ( AB j , z )) ∩ Select ( AB j ,2,{q})DATAc ( AB j , z, q) = DATA ( AB j , z, q) ∩ Select ( AB j ,3, DC (q))
DATA( AB j , z , q )represents the set of all data at z ∈ Dz ( AB j ) and q ∈ B j with AB j .

DATAc ( AB j , z , q ) represents the set of DATA ( AB j , z, q) elements, the answer of which belongs to
DC (q) .

Flag ( AB j ) denotes the function used for determining whether the operation of modifying thedatabase is required for protecting privacy with AB j , i.e., it returns a value of 1 if the following
condition holds and 0 if the condition does not hold.

minz∈Dz ( AB j ), q∈B j ,| DATAc | > 0( Level ( AB j , z, q)) < LevelThHere, LevelTh represents the threshold value for determining the existence of a risk.
[Main Routine to Enhance Privacy]
Step 1:
For all zmap ∈ ZMAP (X ) do the following:
Sub-step 1:
For each AB j (1 ≤ j ≤ M ) , perform the following procedure:i) If Prj ( AB j ,2) ∩ Z = φ or Flag ( AB j ) = 0 , then proceed to Step 2.
ii) If Prj ( AB j , 2) ∩ Z ≠ φ and Flag ( AB j ) = 1, AB j = Del ( AB j , 2, {z|Prj ( AB , 2)∩Z | }) and repeat Step 1.
jSub-step 2:
Perform the following procedure:i) AAttributes = Rand ( Del (T0 ,2, Y ), 1)ii) For k (0 ≤ k ≤ n =| Z |) ,Ak = Rand ( ( AB ), 1)j|Prj ( AB j , 2 )∩Z | =kiii) Delete the data except for that of AAttributes , A0 , A1 , A2 ,…, Aniv) Record AAttributes , A0 , A1 , A2 ,…, An
and the score of EvalOrder =!
!"#$%!!( 𝑆𝑒𝑙𝑒𝑐𝑡 𝐴!"#$% , 2, 𝑍

+ 1 ×|𝑆𝑒𝑙𝑒𝑐𝑡(𝐴!"#$% , 2, 𝑌)|)

Step 2:i) For the maximum value of EvalOrder, output AAttributes , A0 , A1 , A2 ,…, An .
ii) If there are multiple zmap s that give the same maximum value, one is selected at random.
5. Concluding Remarks
This study presents an optimization design for the attributes elimination order in a
privacy-enhanced survey system. By expanding on a survey system designed in previously presented
studies, a formal description of the new system was demonstrated. Although the implementation ofProceedings of International Conference on
Technology and Social Science 2018 (ICTSS 2018)
Invited Paper
the system described in the last section is still an ongoing task, it is expected to be feasible, as aprototype system described in [3] has already been implemented and evaluated.
The optimization function, however, can deteriorate the level of the respondents' privacy as it canenable people to guess the original input answers. There is a trade-off between the privacy of the
respondents and the usability of the output data that the researchers obtain. However, from theviewpoint of the respondent's privacy, the original predetermining method is not the most secure
either. For example, if the order of elimination is determined for each question at random by thesystem, it will be more difficult to guess the original input answer data. This is a new area ofinvestigation and a task for the next stage of this study.
Acknowledgements
This study was supported by a grant from the Telecommunications Advancement Foundation.
References[1] A. Iwai, "A Framework of Social Survey System that Prevents Personal Information Leakage by
Automatic Modification of Questionnaire Design", in Proceedings of 18th symposium onsocio-information systems, pp. 127-132, 2012.
[2] A. Iwai, "Evaluation of an Anonymity Measure as an Index of Voting Privacy", Journal of
Socio-Informatics, Vol.5, No.1, pp11-25, 2012.
[3] A. Iwai, "Reviewing Privacy-Enhanced Social Survey System that Employs Combinatorial
Anonymity Measure", IMECS2016 (International Multi-Conference of Engineering andComputer Scientist 2016) proceedings, pp.311-316, 2016.
[4] A. Iwai, "A Design of Privacy-Enhanced Survey System that can be Used for Hospital
Evaluation by Patients", Proceedings of ICMEMIS2017(1st International Conference on
Mechanical, Electrical and Medical Intelligent System), 2017.
[5] A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam, "ℓ-diversity: Privacy
beyond k-anonymity", Proceedings of IEEE International Conference on Data Engineering(ICDE), pp. 24–35, 2006.
[6] L. Sweeney, "k-Anonymity: A Model for Protecting Privacy", International Journal of
Uncertainty Fuzziness and Knowledge Based Systems, Vol. 10, No. 5, pp. 55, 2002.