SSA-Caterpillar in Group Anonymity

Nowadays, it is a common practice to protect various types of statistical data before publishing them for different researches. For instance, when conducting extensive demographic surveys such as national census, the collected data should be at least depersonalized to guarantee proper level of privacy preservation. In practice, even more complicated methods of data protection need to be used. All these methods can be generally divided into two classes. The first ones aim at providing individual data anonymity, whereas the other ones are focused on protecting information about a group of respondents. In this paper, we propose a novel technique of providing group anonymity in statistical data using singular spectrum analysis (SSA).Also, we apply SSA to defining hidden patterns in demographic data distribution.


I. INTRODUCTION
"He who controls the information, controls the world." This famous quote vividly expresses one of the main features of a post-industrial world. Today, necessity of collecting, storing, and especially processing different kinds of information is understood well by those who want to keep up with the pace of contemporary society.
Without a doubt, national population census is the most extensive activity of collecting large amounts of data. The aggregated census data often are accessible in suitable forms like statistical tables or graphs, and on suitable convenient media (paper publications or OLAP databases). Also, they are disseminated by means of suitable channels such as publishers and the Internet [1]. At the same time, big samples of the primary census data usually are reduced to one microfile containing gathered information about respondents, possibly, in a coded form (see Table 1). Obviously, necessary precautions should be taken beforehand in order to guarantee acceptable level of data privacy.  By data privacy we understand a user protection against discovery and further misuse of identity by other users [2, p. 69]. According to ISO/IEC 15408-2:2008, privacy consists of four family functional requirements, anonymity being the principal one.
In the following subsection, we will cover some approaches to providing anonymity in microfiles.

A. Anonymity
In a consolidated proposal for terminology [3], anonymity of a subject means that the subject is not identifiable (uniquely characterized) within a set of subjects. So, in this work, we will treat both individual and group anonymity as a particular subject's property of being unidentifiable within a microfile. But, as individual anonymity concerns individual microfile records (such as citizens, households, and enterprises), group anonymity has to do mainly with certain sets of records defined in a specific way (to be discussed later on in this paper).
All the methods of providing individual anonymity are usually referred to as part of privacy preserving data publishing (PPDP) methods. The name clearly states that some kind of modification should be applied to the data before making them widely accessed. A state-of-the-art survey of PPDP is given in [4]. Here, we will only outline the most frequently used individual anonymity methods.
So-called perturbative PPDP methods achieve data anonymity by altering dataset records in a particular way. For instance, randomization [5] implies adding noise to initial data so that it is hard to identify records with outstanding attribute values. Another approach lies in gaining k-anonymity [6], which means that at least k dataset records correspond to a specific attribute values' combination. And, of course, it is possible to swap attribute values between data records [7].
Among recently developed perturbative PPDP methods we could mention using Fourier transform [8] and singular value decomposition [9].
All the methods mentioned earlier are mainly used in noninteractive privacy mechanisms when the trusted data collector publishes a cleansed version of the collected data. The other situation arises when applying interactive privacy mechanisms when the data collector provides means for the users through which they can make queries and obtain answers about the data. The latter case is somewhat easier to deal with, mainly due to the fact that the data collector already knows what kind of utility the user wants to receive. Nevertheless, there are some specific problems to face (for instance, even if information on a particular individual isn't present in the dataset at all, privacy breach can occur provided that additional sources of information are available). To cope with such issues, the concept of differential privacy has been introduced and successfully developed (e.g., refer to [10]).
Along with perturbative methods, one might also apply various non-perturbative methods such as data recoding and data suppression [11]. These methods, unlike perturbative ones, anonymize the data without altering them.
As opposed to PPDP methods, those ones for providing group anonymity should be capable of modifying not only particular respondents' attribute values but their distribution as well. Moreover, they have to ensure that data distortion being introduced is satisfactory. That is why completely new techniques need to be developed.
At the time this paper is being written, maybe the most complete source of how to provide group anonymity is [12]. The paper proposes a generic scheme of providing group anonymity and illustrates it with some practical examples.
One of the ways to provide group anonymity described in [12] is based on normalization process presented in [13]. This makes it possible to preserve major data statistical features, e.g. mean value and standard deviation. Though, it does not seem to be quite sufficient.
Another approach is based on applying wavelet transform (WT) [14] to initial data so that it helps to conceal important data features not likely to be given away. At the same time, it enables preserving data frequency peculiarities. But, this technique has some slight disadvantages, some of which are: 1) Insufficient Utility Preserving: The way utility is being preserved isn't clear enough.
2) Strong Dependence on the Algorithm: Choosing different wavelet bases yields completely different outcomes. At the same time, there are no well-defined means of defining which base should be chosen.
3) Tight Constraints while Modifying the Data: When performing data perturbation, the researcher is highly forced to modify dataset records in a way implied by the method itself.
All these disadvantages lead to a conclusion that using WT for providing group anonymity is a very much methodoriented technique. Fortunately, there exists quiet dissimilar approach which is free of all three downsides mentioned above. Indeed, applying SSA, as we propose it in this paper, gives a researcher powerful means of modifying initial data almost deliberately and simultaneous preserving data utility.

B. Singular Spectrum Analysis
Singular spectrum analysis (SSA) (traditionally called "Caterpillar" in papers written by Russian researchers) is a relatively novel technique for analyzing time series of quite dissimilar origin. SSA-Caterpillar method finds its applications in fields ranging from climate research [15] and geophysics [16] to processing time series with missing values [17] and detecting spatial data patterns [18].
Generally speaking [17], the method's aim is to split original time series into a sum of trend, periodic, and/or noise components. What makes this technique especially powerful is that the original series do not have to be stationary, the model of the trend can be completely indeterminate, and we do not even have to know anything about periodic components within the series.
Due to main peculiarities of the method, it cannot be fully automatized. This means that the last decision is always left to the researcher. Moreover, principle parameters of the method should be also picked by a human in each and every case independently. This leads to some complications in applying the method to analyzing large amounts of information. Though, despite this fact, it is mostly efficient in performing such tasks as series smoothing, predicting, and filling in missing signal values.
SSA-Caterpillar technique was independently developed in the UK and the USA, from one side, and Russia, from the other one. At present, there exist rather thorough and complete studies of the method full of practical examples, among which [19] and [20] can be mentioned.

A. Group Anonymity
In this subsection, we will present main steps of providing group anonymity in microfiles, though we will omit some facts not necessary for the further discussion. For more complete explanation and real-life illustrations, refer to [12].
Let us propose some necessary definitions. Definition 1. An identifier is a microfile attribute which unambiguously defines a certain respondent in a microfile.
Since keeping identifiers in the microfile when publishing it is the best way to violate individual privacy, they should be always removed from the dataset. Further on, we will presume that any microfile does not contain any identifier. Definition 2. We will call certain attributes Vital attributes help define subsets of microfile respondents to be protected when providing group anonymity. Definition 3. We will call an element () Specific vital value combinations distinguish those respondent categories whose distribution is supposed to be protected.
Definition 4. We will call an element () , S being a subset of microfile data elements corresponding to the p th attribute (called a parameter set), a parameter value. The attribute itself will be called a parameter attribute.
We usually use parameter values to arrange microfile data in some particular order, so that it becomes possible to treat them as certain series.
Definition 5. A group ( , ) G V P is an attribute set consisting of several vital attributes   12 , , ..., So, providing group anonymity actually lies in performing such microfile modifications (with respect to each group ik  separately) that sensitive data become completely confided. Or, speaking more formally, we can divide providing group anonymity into the following stages: 1) Data Preparation: Construct a (depersonalized) microfile M representing statistical data to be processed.
2) Defining Goals and Targets: Define one or several groups ( , ), iii G V P 1,..., ik  standing for respondents categories to be protected.
3) Group Anonymity Calculations: For each i from 1 to k: a) Choosing data representation: Pick a proper data representation (called goal representation) c) Performing goal representation's modification: (2) (also called modifying functional). Obtain a modified goal representation.
d) Obtaining the modified microfile. Define an inverse goal mapping function (3) Obtain a modified microfile. 4) Post-Processing: Prepare the modified microfile for publishing.
We introduced some new terms in the scheme above, so we would like to clarify them a bit before moving forward. Definition 6. A goal representation  (M, G) of a dataset M with respect to a group G is a dataset reflecting specific features of a group within the microfile in a way appropriate for providing group anonymity.
In general, this dataset could be of any possible form convenient for the researcher. In this paper, we will work with one particular goal representation called a quantity signal 12 ( , ,..., ) m q q q q  . It can be constructed by counting up all the respondents in a group with a certain pair of vital value combination and a parameter value, and arranging them afterwards in any order proper for a parameter attribute.
A quantity signal provides a quantitative statistical distribution of group members from initial microfile. In some situations, extremums of this distribution could lead to disclosing restricted information, which makes it a suitable goal representation.
Definition 7. A modifying functional  : of a dataset M with respect to a group G is any function, algorithm, or procedure which transforms initial goal representation into another one ensuring that group anonymity is reached.
Frankly saying, creating modifying functional is possibly the toughest, though yet utterly important part of the whole providing group anonymity process. In this paper, we will pay most attention to one version of modifying functional based on applying SSA-Caterpillar technique.

B. SSA-Caterpillar
In the current subsection, we will discuss main steps of the classical SSA-Caterpillar algorithm. Also, we will propose some pieces of advice on how to correctly pick method's parameters to receive needed outcome. We will heavily base our explanation on [21].
So, let us be given initial non-zero time series   01 ,..., . Then, to split the series into trend, periodic, and noise components, we need to carry out following steps: 1) Embedding: Transform the series into a so-called trajectory matrix: In (4) id  , we can present decomposition of (4) the following way: In (5), Singular value decomposition (5) is optimal in the sense that it provides the best approximation of (4) among all the other matrices of rank lower than d.
From (6), it is evident that the original trajectory matrix (4) can now be viewed as the following sum: The last thing to complete is to return back from the matrix representation of our data to the series one. 4) Diagonal Averaging: Transfer each resulting matrix (6) into a time series.
To carry this operation out, let us first introduce the following notation: Finally, applying (8) to resulting matrices from (7), we obtain time series representation of our initial dataset:  I consists of only one element, then its form will strongly resemble the one of the corresponding eigenvector. This means that if any eigenvector is periodic than the corresponding time series might be periodic as well. Moreover, the series trend is highly supposed to correspond to the eigenvector with relatively low frequency.
2) Two rather close singular values could be the sign of a periodic time series component. This means that we can extract periodic components by grouping resulting matrices corresponding to such pairs of singular values.
3) The greater is the eigenvalue, the greater is the contribution of the corresponding time series component to the time series in general.
4) Relatively small eigenvalue tending to zero are likely to point at noise time series components.

5)
There is no need in choosing window length L greater than N/2. This is true because singular value decompositions of trajectory matrices obtained with window lengths L and 1 NL  are equivalent.
6) In most cases, the greater is L, the more accurate is time series decomposition. That's why it seems reasonable to take L as big as possible (and, according to the previous hint, the most appealing option is N/2). Though, in some particular cases like extracting periodic component it is advisable to pick window length being multiple of the component's period.

С. Applying SSA-Caterpillar to Group Anonymity
In this subsection, we will discuss how exactly SSA-Caterpillar technique might be applied to providing group anonymity in a microfile.
According to the group anonymity scheme presented at the beginning of this Section, the only possible stage to make use of SSA-Caterpillar is constructing the modifying functional (2). But, first we need to define what restrictions does this functional have to satisfy.
On one hand, the modifying functional has to be efficient for altering the quantity signal obtained from the original dataset. In this paper, we propose to alter the quantity signal by replacing its trend component from (9) with another one ensuring that original extremums of the signal are changed. In this case, we are able to conceal any extreme quantities from vital values' distribution which might occur to be securityintensive.
On the other hand, it is vitally necessary to make sure that data utility isn't reduced much. It is obvious that SSA-Caterpillar method is especially convenient for extracting periodic components from the original signal. Such components may be very important for statistical, demographic, and sociological researches (and this is why microfile data are used for in the first place).
So, we come to conclusion, that modifying trend component of the quantity signal with simultaneous preserving all the other components (including periodic ones) seems to be a rather adequate way of providing group anonymity in a microfile. In the next Section, we will illustrate this concept with a practical example based on real-life data.

III. PRACTICAL EXAMPLE
According to the group anonymity scheme from Section II, the first step we have to take is to build up a microfile with the data needed to be protected. We decided to work with the 5-Percent Public Use Microdata Sample File provided by the U.S. Census Bureau [22] concerning the 2000 U.S. census of population and housing microfile data in California.
The second step requires defining groups to be protected. For simplicity of calculations, we took only one group corresponding to the military personnel distributed by their age.
It is important to note here that due to the nature of the group under protection, we limited our parameter set down to values from 17 to 56 years of age. The graphical representation of the signal can be found in Fig. 4a.
As we can clearly notice, there are huge extremums at the 3 rd , the 4 th , the 5 th , and the 6 th signal positions. To provide group anonymity, we need to replace the quantity signal's trend with another one, so that these extremums are not that outstanding.
In general, we could try to transfer these extremums to some other signal elements, or make an attempt at creating new alleged maximums. But, both of these approaches either yield not very truthful data, or cannot be completed in terms of trend substituting. That is why our only option left is to somehow smooth the signal so that these extremums cannot be marked out.
At the same time, as we mentioned in the previous Section, we need to preserve periodic components of the signal to reduce loss of data utility. To be able to accomplish both tasks, we need to decompose the signal first.
For that matter, we decided to take the value of 20 as the window length (mainly because the length of the whole signal is 40). After performing quite obvious steps of constructing trajectory matrix X according to (4) and obtaining resulting matrices (5) (which we omit in this paper), we need to group the components to extract valuable periodic and trend ones.
To make correct choice, we need to follow the instructions given at the end of Subsection II-C, especially one saying about tracking down pairs of almost equal T XX eigenvalues likely to correspond to periodic signal components. That is why we present the square roots of these eigenvalues in Fig. 1a.
Unfortunately, there isn't any pair of similar eigenvalues present there. This means there is no evident periodic component within the original quantity signal. This situation is not quite preferable, because in this case there is no need in using such powerful technique as SSA-Caterpillar only to substitute the signal's trend. Though, it seems to be not very believable that the time series representing military personnel of the state of California does not contain any periodic component at all. Indeed, if we take a closer look at the data we are working with, we will find out that the main reason of such an incident is that California is the home state for San Diego military bases being the largest concentration of naval facilities in the world. So, we are strongly convinced that periodic components, if there is any, are simply suppressed by the outweighing number of young military men working at San Diego naval bases.
This signal is present in Fig. 4b. Once again, let us take a look at Fig. 1b representing T XX eigenvalues (though, now the trajectory matrix corresponds to signal q ). In this case, we can mark out two clearly visible pairs of eigenvalues likely to correspond to the periodic components. The first one is values 3 and 4, and the second one is values 5 and 6. Also, concluding from the magnitude of the first two eigenvalues, we can say that they correspond to the trend signal component. Taking this all into consideration, we can finally group all 20 signal components into the following index subsets: 1  After having obtained resulting matrices (6) and performing diagonal averaging (8), we can present our quantity signal as a sum of the following components: (1) ( In (10), (1) q stands for signal's trend, (2) q and (3) q both reflect periodic components, and (4) q will be treated as noise. Appropriate graphical representations can be seen in Fig. 2, and numerical values go as follows (we present here only three decimal numbers, though all the calculations had been carried out with much higher proximity): (1)  Judging from Fig. 2b and Fig. 2c, we can confidently admit that there are two periodic components in the quantity signal under analysis. The first one has a period of 20, and the second one seems to possess a period of 4. This is a very interesting result, though we are not qualified sociologists to make any proper conclusions about what these periods stand for. Nevertheless, such information has to be preserved for further studies.
It is important to emphasize that though signal components have slightly changed, main periodic components' features (like their period, phase and so on) have persisted. This is exactly what we understand by utility preserving.

IV. CONCLUSIONS AND FURTHER STUDIES
In this paper, we tried to attract attention to some novel techniques in the field of providing anonymity in statistical data, and also attempted to introduce new ways of preserving data utility while altering them in predefined manner.
For the first time, we proposed to apply SSA-Caterpillar to providing group anonymity in population census microfiles, and addressed its main peculiarities. At the same time, we showed that this technique can be efficiently used not only for concealing data distribution features, but also for analyzing them simultaneously. Of course, comprehensive interpreting should be done by qualified sociologists and demographers. And, last but not least, we illustrated the strong importance of correct sampling procedure. Having excluded from consideration an evident cause of incorrect data distribution, we got an opportunity of obtaining meaningful results in the output.
Still, there are some goals to be achieved in the future: 1) Modifying the Signal: There has to be developed more formal way of picking up new trend component of the signal.
2) Data Interpreting: It would be more helpful to be able to interpret data components from the sociological point of view to define those ones to be preserved in any case, and those ones to be lost without major consequences.
3) Data Adjusting: After having altered appropriate goal representations, it is necessary to construct modified microfiles. There needs to be proposed a convenient way of evaluating loss of data utility implied by such constructing procedures.