KR101589038B1 - Method and device for generating random noise data preserving the correlation on privacy preserving time-series databases - Google Patents

Abstract

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a privacy protection technique for time series data, and more particularly, to a random noise generation method for time series data that preserves not only privacy protection but also correlation.
According to the present invention, it is possible to provide a user with a random noise disturbance technique that maintains correlation with time series data as well as privacy protection.

Description

TECHNICAL FIELD The present invention relates to a noise generation method and apparatus for preserving correlation in a privacy protection of a time series database,

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a privacy protection technique for time series data, and more particularly, to a random noise generation method for time series data that preserves not only privacy protection but also correlation.

In particular, the present invention relates to a simple and efficient method of matching the signatures of time series original entries and corresponding noise entries to preserve the correlation as well as privacy protection.

Recently, privacy protection issues for time series data widely used in various fields such as finance, medical care, and weather are actively researched.

To protect the privacy of time series data, a random noise generation approach is widely used. This approach is also called an additive random noise technique. First, it generates a random noise with an even or Gaussian distribution, and then adds this noise to the original time series to create a disturbed time series.

The data provider then provides only the disturbed time series to the data miner, and the data miner obtains the mining results from the disturbed time series. Since only this disturbed data is disclosed, a third party data miner (or attacker) can not easily find sensitive information from the published data, and thus this method can protect the privacy of the original time series.

However, the random noise disturbance technique has a problem that the correlation between the time series can not be preserved due to noise addition. That is, the correlation is related to the two data (or variables), and by using the correlation, the direction of change of the other data value can be predicted from the change of one data value.

However, in the random noise disturbance technique, when there is a high correlation between data, a large amount of noise should be added in order to prevent leakage of the original, while a large amount of noise may cancel or distort the original time series correlation . This has the disadvantage of causing incorrect results in predictive mining applications or correlation-based queries.

1. Korean Patent Publication No. 10-2012-0090812 2. Korean Patent No. 10-13313500000 3. Korean Patent Publication No. 10-2013-0093202

1. Ahn, Ahn, "Privacy-Protected Time Series Data Mining", Journal of KISS: Database 40 (2) 124-133, April 2013. 2. Kim, Hye-Sook et al., "Noise Leveling Effect in Privacy Protection Clustering of Time Series Data," IEICE Transactions on Computers, Vol. 16, No. 3, March 2010, pp.356-360

It is an object of the present invention to provide a noise generating method and apparatus for maintaining a correlation in a random noise disturbance technique of privacy protection.

In order to accomplish the above-mentioned problems, the present invention provides a noise generation method for maintaining a correlation in a random noise disturbance technique of privacy protection.

The noise generation method includes:

A normalization conversion step of converting time series data of a time series data set into normalization;

A random noise generation step of generating a random noise to be correlated based on the normalized time series data; And

And generating a disturbance time series data by the generated random noise.

In this case, the normalization conversion step may include: obtaining an average value of the time series data set; Obtaining a standard deviation of the time series data set based on an average value of the acquired time series data sets; And And normalizing each time series data of the time series data set using the obtained average value and standard deviation.

The random noise generating step may include: obtaining random noise by a Gaussian function; Obtaining random noise having the same sign as the sign of each time series data among the obtained random noises; And obtaining each time-series data disturbed by the obtained random noise of the same sign.

At this time, if the sign of the time series data is not changed by the obtained random noise, the random noise is used as it is, and if the sign is different, random noise is generated again.

Meanwhile, the random noise generating step may include: obtaining random noise by a Gaussian function; Acquiring a random noise having the same sign of the time series data disturbed by the sign and the random noise of each time series data among the obtained random noises; And obtaining each time-series data disturbed by the obtained same random noise.

On the other hand, the random noise generation step includes obtaining random noises by the Gaussian function; Obtaining random noise that has been changed to the same sign as the sign of each time series data among the obtained random noises; And obtaining each time-series data disturbed by the obtained random noise changed to the same sign.

At this time, even if the sign of the random noise is different from the entry of each time series data, if the entry of the disturbance time series data has the same sign as the entry of each time series data, the random noise is used as it is.

The absolute size of the entry of the disturbance time series data may be smaller than the absolute size of the entry of each time series data.

In addition, even if the entry of each time-series data and the entry of the disturbance time-series data have the same sign, the random noise is again generated if the random noise has a different sign from the entry of the time-series data.

Also, since the entry of each time series data and the random noise have the same sign, the absolute size of the entry of the disturbance time series data is larger than the absolute size of each time series entry.

Further, even if the entry of each time series data and the entry of the disturbance time series data have the same sign, the sign of the random noise is changed if the sign of the random noise does not match the entry of each time series data.

In addition, the sign of the random noise sign of the entry of each time series data is consistent, and the absolute size of the entry of the disturbance time series data is larger than the absolute size of each time series entry.

(여기서, X_n은 정규화된 시계열 데이터, X는 각 시계열 데이터, x_i(1≤i≤n)는 각 시계열 데이터(X)의 엔트리, avg(X)는 각 시계열 데이터의 평균값, σ_x는 표준편차를 나타낸다)에 의해 획득되는 것을 특징으로 할 수 있다.Further, the normalized time series data is expressed by the following equation

(Wherein, X _n is the normalized time series, X is each of time-series data, x _i (1≤i≤n) is an entry, avg (X of the respective time-series data (X)) is an average value for each time-series data, σ _x is Quot; indicates a standard deviation).

On the other hand, another embodiment of the present invention is a system comprising: a user input for receiving user input; And a normalization conversion unit for converting the time series data of the time series data set into normalization according to user input; A noise acquiring unit for generating a random noise to be correlated based on the normalized time series data; And a data generation unit for generating disturbance time series data by the generated random noise.

According to the present invention, it is possible to provide a user with a random noise disturbance technique that maintains correlation with time series data as well as privacy protection.

1 is a block diagram of a noise generating apparatus 100 for preserving a correlation according to an embodiment of the present invention.
2 is a flowchart illustrating a noise generation process for preserving a correlation according to an embodiment of the present invention.
FIG. 3 is a flowchart showing the normalization conversion step (S210) of the time series data shown in FIG. 2 in more detail.
FIG. 4 is a flowchart illustrating a random noise acquisition step (S220) in which the correlation shown in FIG. 2 is preserved according to an embodiment of the present invention in more detail.
FIG. 5 is a flowchart illustrating a random noise acquisition step (S220) in which the correlation shown in FIG. 2 is preserved according to another embodiment of the present invention in more detail.
FIG. 6 is a flowchart illustrating a random noise acquisition step S220 in which the correlation shown in FIG. 2 is preserved according to another embodiment of the present invention.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It is to be understood, however, that the invention is not to be limited to the specific embodiments, but includes all modifications, equivalents, and alternatives falling within the spirit and scope of the invention.

Like reference numerals are used for similar elements in describing each drawing.

The terms first, second, etc. may be used to describe various components, but the components should not be limited by the terms. The terms are used only for the purpose of distinguishing one component from another.

For example, without departing from the scope of the present invention, the first component may be referred to as a second component, and similarly, the second component may also be referred to as a first component. The term "and / or" includes any combination of a plurality of related listed items or any of a plurality of related listed items.

Unless otherwise defined, all terms used herein, including technical or scientific terms, have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs.

Terms such as those defined in commonly used dictionaries are to be interpreted as having a meaning consistent with the contextual meaning of the related art and are to be interpreted as either ideal or overly formal in the sense of the present application Should not.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, a noise generation method and apparatus for preserving correlation in privacy protection of a time series database according to an embodiment of the present invention will be described in detail with reference to the accompanying drawings.

1 is a block diagram of a noise generating apparatus 100 for preserving a correlation according to an embodiment of the present invention. Referring to FIG. 1, the noise generation apparatus 100 for storing the correlation includes a time series data set 110 storing a time series data source, a noise generation unit 120, and the like. The noise generation unit 120 includes a user input unit 121 for inputting a user command, a normalization conversion unit 122 for normalizing and converting the time series data inputted from the time series data aggregation unit 110, A data acquisition unit 124 for generating disturbance time series data by the acquired random noise, and a data acquisition unit 124 for acquiring random noise for maintaining the correlation between the user input through the user input unit 121 And a controller 125 for controlling the operation of the noise generating apparatus 100 in response to the command.

The user input unit 121 generates input data for controlling the operation of the noise generating apparatus 100 for storing a correlation. For example, it may be input through the user input unit such as a given time series data set or an allowance value, a selection of a disturbance time series data generation method, and a standard deviation of a Gaussian function.

The normalization conversion unit 122 normalizes and converts the time series data included in the time series data set unit 110.

The noise acquisition unit 123 generates random noise for each time series entry based on the transformed time series data and the received disturbance time series data generation method.

The data generating unit 124 generates the disturbance time series data using the generated random noise.

The controller 125 controls components of the noise generating apparatus 100 for preserving the correlation.

The time series data set unit 110 is a time series data source. Of course, the time series data set unit 110 is shown as being a part of the noise generation apparatus 100, but may be a data source received from the outside through a wired and / or wireless communication network.

2 is a flowchart illustrating a noise generation process for preserving a correlation according to an embodiment of the present invention. Referring to FIG. 2, time series data of each time series data set is normalized and converted (S210).

Then, based on the converted time series data, a random noise is acquired for maintaining correlation (S220). This random noise acquisition has three ways of generating a random noise that is correlated with the time series data according to the user's selection. 4 to 6, which will be described later.

2, when random noise is added to the time series data and the signs of the time series data and the disturbance time series data are matched by the random noise, the disturbance time series data is correlated with the original time series data while the privacy is protected (S230).

FIG. 3 is a flowchart showing the normalization conversion step (S210) of the time series data shown in FIG. 2 in more detail. First, in order to facilitate the understanding of the invention, it is assumed that each time series data included in the time series data set is time series data having a length n in an embodiment of the present invention.

Referring to FIG. 3, a noise generator (100 in FIG. 1) for preserving correlation acquires an average value of a time series data set (S310).

Thereafter, the standard deviation of the time series data set is obtained based on the average value of the obtained time series data set (S320).

Meanwhile, according to an embodiment of the present invention, the noise generation apparatus 100 for preserving the correlation normalizes each time-series data of the time-series data set according to the average value and the standard deviation of the acquired time-series data set (S330) . For example, each time series data X of the time series data set may be obtained by subtracting the average value for each entry of the time series data and dividing the average value by the standard deviation to obtain normalized time series data. It is summarized as follows.

Wherein, X _n is the normalized time series, X is an entry for each time-series data, x _i (1≤i≤n) is each of time-series data (X), avg (X) is the mean value of the respective time-series data, σ _x is the standard Represents the deviation.

FIG. 4 is a flowchart illustrating a random noise acquisition step (S220) in which the correlation shown in FIG. 2 is preserved according to an embodiment of the present invention in more detail. Referring to FIG. 4, the noise generation apparatus (100 in FIG. 1) for preserving the correlation stores a standard deviation value of a Gaussian function given by the user for every entry of the time series data X having a length of n, The random noise is obtained by the Gaussian function (S410).

At this time, random noise is generated repeatedly until the following condition is satisfied (S420).

Here, x _i (1? _I ? N) is an entry of time series data X and n _i (1? _I ? N) represents random noise.

If the sign of the time series data does not change due to the random noise, the random noise is used as it is, and a new random noise is generated if the sign is different.

The random noise generation characteristic of the noise generation apparatus (100 in FIG. 1) for preserving the correlation according to another embodiment of the present invention is as follows.

(X _i + n _i ) of the disturbance time-series data is different from the entry (x _i ) of the time-series data X, even if the sign of the random noise n _i is different from the entry x _i of the time- _i ), the random noise (n _i ) is used as it is.

(2) The absolute magnitude (= | x _i + n _i |) of the entry of the disturbance time series data may be less than the absolute magnitude (= | x _i |) of the existing time series entry.

According to the above feature (1), the above procedure can distort the distribution of the random noise, that is, the average and standard deviation of the random noise. That is, the mean and standard deviation of the random noise in accordance with the reproduction name as random noise repeated until it satisfies the equation (x _{i and (x i + n i) <} 0) may be different, respectively, and 0 and σ.

FIG. 5 is a flowchart illustrating a random noise acquisition step (S220) in which the correlation shown in FIG. 2 is preserved according to another embodiment of the present invention in more detail. Referring to FIG. 5, the noise generation apparatus 100 for storing the correlation stores a Gaussian function given by a user for every entry (x _i , 1? I? N) of the time series data X having a length n Random noise (n _i , 1? _I ? N) is obtained by a standard deviation value and an average 0 Gaussian function (S510).

At this time, random noise is repeatedly generated until the expression (x _i · n _i <0) is satisfied (S520). If the random noise and the sign of the time series data are the same, the process is used as it is, and random noise is generated again until the same sign is obtained.

The random noise generation characteristic of the noise generation apparatus 100 for preserving the correlation according to an embodiment of the present invention is as follows.

(1) Entry (x _i) and the entry of disturbing the time-series data (x _i + n _i) of a random noise generating process and different from, the time-series data shown in Figure 4 is that, even if of the same symbols, the random noise (n _i) And generates a random noise (n _i ) if it has a sign different from the entry (x _i ) of the time series data.

(2) Since the entries (x _i ) and random noise (n _i ) of the time series data have the same sign, the absolute size (= | x _i + n _i |) of entries of the disturbance time- (= | x _i |).

FIG. 6 is a flowchart illustrating a random noise acquisition step S220 in which the correlation shown in FIG. 2 is preserved according to another embodiment of the present invention. Referring to FIG. 6, the noise generation apparatus 100 for storing the correlation stores a Gaussian function given by a user for every entry (x _i , 1? I? N) of the time series data X having a length n The random noise (n _i , 1? _I ? N) is obtained by the standard deviation value and the average Gaussian function of 0 (S610).

At this time, if the expression (x _i · n _i <0) is not satisfied, the sign of the random noise n _i is forcibly changed (-n _i ) to match the entry (x _i ) of the time series data (S620).

If the random noise and the sign of the time series data are the same, the process is identical to the random noise generation process shown in FIG. 5, but if not, the random noise is re- Are forcedly changed to match the sign.

The random noise generation characteristic of the noise generation apparatus 100 for preserving the correlation according to another embodiment of the present invention is as follows.

(1) a random noise generating process and the difference is that even if there is an entry (x _i) and the entry of disturbing the time-series data (x _i + n _i) of the time series data of the same sign entry of the time series data shown in Figure 4 (x _i ) And the random noise (n _i ) do not coincide with each other, the sign of the random noise (n _i ) is changed.

(2) The sign of the random noise (n _i ) and the entry (x _i ) of the time series data coincide with each other and the absolute size (= | x _i + n _i | always greater than) |) is the absolute size (= the previous time-series entry | x _i.

According to the above two features, the above process can also distort the correlation between the noise distribution and the time series data similarly to the random noise generation process shown in FIG.

The correlation preserving noise generation method according to an embodiment of the present invention can improve the degree of preservation of the correlation as well as the privacy in time series data disturbance. That is, the correlation preservation noise generation method of the present invention can be applied to predictive mining applications and correlation consideration queries requiring privacy very effectively.

In addition, those skilled in the art will recognize that the various illustrative logical blocks and algorithms described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. In order to clearly illustrate this interchangeability of hardware and software, various exemplary blocks and steps have been described above generally in terms of their functionality.

Whether such functionality is implemented as hardware or software depends upon the design constraints and specific applications imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the exemplary embodiments of the present invention.

The various illustrative logical blocks described in connection with the embodiments disclosed herein may be implemented or performed with a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) Discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein.

A general purpose processor may be a microprocessor, but, in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in a memory such as a random access memory (RAM), a flash memory, a read only memory (ROM), an electrically programmable ROM (EPROM), an electrically erasable programmable ROM (EEPROM), registers, CD-ROM, or any other form of storage medium known in the art.

An exemplary storage medium is coupled to the processor such that the processor can read information from, and write information to, the storage medium. Alternatively, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC. The ASIC may reside in a user terminal. Alternatively, the processor and the storage medium may reside as discrete components in a user terminal.

In one or more exemplary embodiments, the functions described may be implemented in hardware, software, firmware, or any combination thereof. When implemented in software, the functions may be stored or transmitted as one or more instructions or code on a computer-readable medium. The computer-readable medium includes both a communication medium and a computer storage medium, including any medium that facilitates transfer of a computer program from one place to another. The storage medium may be any available media that can be accessed by a computer. By way of example, and not limitation, such computer-readable media can be stored in RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, And any other medium which can be used to carry or store the desired program code and which can be accessed by a computer.

Also, any connection is properly termed a computer-readable medium. For example, if the software is transmitted from a web site, server, or other remote source using wireless technologies such as coaxial cable, fiber optic cable, twisted pair, digital subscriber line (DSL), or infrared, wireless and microwave, Wireless technologies such as cable, fiber optic cable, twisted pair, DSL, or infrared, radio, and microwave are included within the definition of media. As used herein, discs and discs include compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disc and Blu-ray disc, ) Typically reproduce data autonomously, but discs use lasers to optically reproduce the data. Also, combinations of the above may be included within the scope of computer-readable media.

100: Noise generating device
110: Time series data set section
120: Noise generating unit
121: user input section
122: normalization conversion unit
123: Noise acquisition unit
124:
125:

Claims (14)

A noise generation method for preserving correlation,
A normalization conversion step of converting time series data of a time series data set into normalization;
A random noise generation step of generating a random noise to be correlated based on the normalized time series data; And
And generating a disturbance time series data by the generated random noise;
Wherein the normalization conversion step comprises:
Obtaining an average value of the time series data set;
Obtaining a standard deviation of the time series data set based on an average value of the acquired time series data sets; And
And normalizing each time series data of the time series data set using the obtained average value and standard deviation.
delete The method according to claim 1,
Wherein the random noise generating step comprises:
Obtaining random noises by the Gaussian function;
Obtaining random noise having the same sign as the sign of each time series data among the obtained random noises; And
And obtaining each time-series data disturbed by random noises of the obtained same code Noise generation method for correlation preservation.
The method of claim 3,
Wherein the random noise is used as it is if the signs of the time series data are not changed by the obtained random noise, and the random noise is generated again when the signs are different.
The method according to claim 1,
Wherein the random noise generating step comprises:
Obtaining random noises by the Gaussian function;
Acquiring a random noise having the same sign of the time series data disturbed by the sign and the random noise of each time series data among the obtained random noises; And
And obtaining each time-series data disturbed by the obtained same random noise.
The method according to claim 1,
Wherein the random noise generating step comprises:
Obtaining random noises by the Gaussian function;
Obtaining random noise that has been changed to the same sign as the sign of each time series data among the obtained random noises; And
And obtaining each time series data disturbed by random noises changed to the obtained same code.
The method of claim 3,
Wherein random noise is used as it is when entries of disturbance time series data have the same sign as entries of each time series data even if the sign of random noise is different from the entry of each time series data.
The method of claim 3,
Wherein the absolute size of the entry of the disturbance time series data is smaller than the absolute size of the entry of each time series data.
5. The method of claim 4,
And random noise is generated again if the random noise is different from the entry of the time series data even if the entry of each time series data and the entry of the disturbance time series data have the same sign.
5. The method of claim 4,
Wherein entries of the time series data and random noise have the same sign so that the absolute size of the entries of the disturbance time series data is larger than the absolute size of each time series entry.
6. The method of claim 5,
Wherein the code of the random noise is changed when the entry of each time series data and the entry of the time series data have the same sign but the sign of the random noise does not coincide with the entry of each time series data. Way.
6. The method of claim 5,
Wherein an entry of each time series data matches a sign of random noise and an absolute size of an entry of the disturbance time series data is larger than an absolute size of each time series entry.
The method according to claim 1,
The normalized time series data is expressed by the following equation

(Wherein, X _n is the normalized time series, X is each of time-series data, x _i (1≤i≤n) is an entry, avg (X of the respective time-series data (X)) is an average value for each time-series data, σ _x is And the standard deviation is obtained by the following equation.
A user input for receiving user input; And
A normalization conversion unit for converting time series data of a time series data set into normalization according to user input;
A noise acquiring unit for generating a random noise to be correlated based on the normalized time series data; And
And a data generation unit for generating disturbance time series data by the generated random noise,
Wherein the normalization conversion unit comprises:
And acquiring a mean value of the set of time series data, obtaining a standard deviation of the time series data set based on an average value of the obtained time series data set, normalizing each time series data of the time series data set using the obtained average value and standard deviation And a noise reduction unit for noise reduction.

Images