一種模式信息損失最小化的序列類數據隱私保護方法
2023-11-04 04:30:42
專利名稱：一種模式信息損失最小化的序列類數據隱私保護方法
技術領域：
本發明涉及資料庫系統、數據隱私與模式信息提取技術，特別是涉及一種模式信 息損失最小化的序列類數據隱私保護方法。
背景技術：
時間序列數據被公認為是自然界和人類社會中一類非常重要的數據，其應用範圍 包括金融分析和社交行為追蹤等重要領域。近幾年來，傳感器網絡，RFID和無線定位設備 的快速發展，更加凸顯了時間序列數據的重要性。但是，值得注意的是，時間序列數據中也 包含著大量的隱私信息，如果不加以適當的保護，數據擁有者對數據隱私的擔憂將極大的 桎梏相關應用的發展。目前，時間序列數據的隱私保護問題還沒有得到很好的解決。主要原因是時間序 列數據與傳統表數據相比，其數據特徵相對複雜。時間序列數據的各個屬性在時間上存在 一種前後依賴的關係，整體表現為一種模式信息。模式匹配是時間序列數據的一類重要查 詢。k匿名是傳統表數據領域的一類重要的隱私保護技術。但是，如果將這種方法直接 應用於時間序列數據，其缺陷十分明顯。因為k匿名所要求的屬性值泛化會使時間序列的 模式信息遭到嚴重破壞，從而使得數據可用性大大降低。目前，一些與時間序列相關的隱私 保護技術也各自存在缺陷。TGA是一種基於幹擾的匿名技術，首先將時間序列進行分組，然 後在組內隨機重建時間序列，這種方法導致的模式信息損失也非常之大。BFP2KA是一種基 於字符串的隱私保護技術，通過構建前綴樹並對其進行剪枝來實現k匿名。雖然BFP2KA號 稱能夠保留模式，但其所謂的模式僅限於字符串的精確匹配，通用性受到很大的限制。
發明內容
本發明的目的在於提供一種模式信息損失最小化的序列類數據隱私保護方法，基 於k匿名技術，構建出一個新的匿名模型，S卩(k，P)匿名模型，在有效保護隱私的同時達到 模式信息損失最小化的效果，有效的解決了時間序列的隱私保護問題。本發明採用的技術方案的步驟如下1)建立一個廣義的時間序列模式定義模型，根據這個模型以及實際應用的模式挖 掘任務需求，選擇符合實際應用需求的模式定義函數集；2)根據步驟1)中提出的模式定義函數集，確定模式映射函數，時間序列的屬性分 為標識屬性，QI屬性和敏感屬性三種，時間序列的模式特徵由模式映射函數基於QI屬性來 進行提取；3)根據時間序列的屬性值以及時間序列的模式特徵，定義隱私攻擊類型，構建 (k，P)匿名模型以保護時間序列數據隱私；4)根據上述步驟2)中所述的時間序列的模式特徵，衡量整個原始數據集中任意 兩條時間序列之間的模式相似性，構建P子組，以達到模式信息損失最小化的效果；
5)基於步驟4)中形成的P子組，分析任意兩個P子組之間的QI屬性值的相似性， 以自底向上的聚類方式對P子組進行聚類，形成k匿名組，使得原始數據集最終滿足(k，P) 匿名模型的要求；6)定義(k，P)匿名模型的信息損失衡量策略，並分析其隱私洩露概率，完成對(k， P)匿名模型的可用性評估，同時根據分組結果，對時間序列數據進行屬性值的泛化，完成數 據發布。步驟1)中選用的模式定義模型，兼容已有文獻中所有的模式定義方式，對於一條 具體的時間序列r，其模式定義函數集形式化為ρ (r) =，m為系統變量，其 中，fi(l彡i彡m)為任意兩個或兩個以上屬性的相關性函數。步驟2)中的模式特徵應滿足以下兩個條件a)由原始時間序列經過特定的模式 映射函數得出；b)可根據該模式特徵對原始時間序列的模式進行重建。模式特徵從QI屬 性中提取，並作為一種獨立的形式發布。要求模式映射函數能夠使得重建後的模式與原始 時間序列模式的差異最小。步驟3)中構建的(k，P)匿名模型是一個雙層隱私保護模型，其具體含義如下a)在第一層約束中，整個原始數據集被要求在QI屬性上滿足k匿名的條件；b)在第二層約束中，在每一個k匿名組內，要求每一條時間序列的模式特徵都至 少與其他P-I條時間序列相同。步驟4)中提到的模式特徵的相似性衡量方式嚴重依賴於模式映射函數以及攻擊 者的背景知識。步驟6)中提到的信息損失，包括屬性值信息損失以及模式信息損失兩部分，屬性 值信息損失由於屬性值泛化而產生，模式信息損失是指原始時間序列的模式與根據模式特 徵重建的模式之間的差異，在(k，P)匿名模型約束下，證明在最壞情況下的隱私洩露概率 為 1/P。本發明具有的有益效果是本發明充分利用了傳統表數據領域的隱私保護模型以及現有的時間序列模式特 徵提取技術，將兩者進行融合，為時間序列構建出一個新的隱私保護模型，(k，p)匿名模型。 該模型將時間序列的各個屬性區間以及整條序列的模式特徵分別作為獨立的形式發布，能 夠在充分保證數據隱私的基礎上，將時間序列的模式信息最小化，充分保證了數據的可用 性。
圖1是本發明實施步驟流程圖。圖2是(k，P)匿名模型構造示意圖。
具體實施例方式下面結合附圖和具體實施對本發明的技術方案作進一步說明。1、如圖1與圖2所示，本發明具體實施過程和工作原理如下1)建立一個廣義的時間序列模式定義模型，根據這個模型以及實際應用的模式挖 掘任務需求，選擇合適的模式定義函數集(即符合實際應用需求的模式定義函數集)；
2)根據步驟1)中提出的模式定義函數集，確定模式映射函數。時間序列的屬性分 為標識屬性，QI屬性(即聯合標識屬性)和敏感屬性三種。原始時間序列的模式特徵由模 式映射函數基於QI屬性來進行提取；3)根據時間序列的屬性值以及模式特徵，定義隱私攻擊類型，構建(k，P)匿名模 型以保護時間序列數據隱私；4)根據上述步驟2)中所述的模式特徵，衡量時間序列兩兩之間(即原始數據集中 任意兩條時間序列之間)的模式相似性，構建P子組(P子組的大小由參數P確定，在同一 個P子組中的時間序列都具有相同的模式特徵)，以達到模式信息損失最小化的效果；5)基於步驟4)中形成的P子組，分析任意兩個P子組之間的QI屬性值的相似性， 以自底向上的聚類方式對P子組進行聚類，形成k匿名組，使得原始數據集最終滿足(k，P) 匿名模型的要求；6)定義(k，P)匿名模型的信息損失衡量策略，並分析其隱私洩露概率，完成對(k， P)匿名模型的可用性評估。同時根據分組結果，對時間序列數據進行屬性值的泛化，完成數 據發布。步驟1)中選用的模式定義模型，可以兼容已有文獻中所有的模式定義方式。對於 一條具體的時間序列r，其模式定義函數集可形式化為ρ (r) = ，m為系統變 量。其中，^(1 ^m)為任意兩個或兩個以上屬性的相關性函數。步驟2)中的模式特徵應滿足以下兩個條件a)由原始時間序列經過特定的模式 映射函數得出；b)可根據該模式特徵對原始時間序列的模式進行重建。模式特徵從QI屬 性中提取，並作為一種獨立的形式發布。要求模式映射函數能夠使得重建後的模式與原始 時間序列模式的差異最小。鑑於模式信息的重要性，現有文獻中有大量廣為人知的模式特 徵提取技術，包括SAX，PAA，PLA和APCA等。步驟1)中定義的模式定義模型可以完全兼容 這些模式特徵提取技術。由於SAX的直觀性和易操作性，以下幾個步驟的具體實施方式
將 在SAX的基礎上進行闡述。SAX技術將時間序列的屬性值進行離散化，最終將其模式特徵表 示為一條字符串，其參數level用於控制模式特徵的精確程度，即與原始時間序列模式的 匹配程度。level值越大，模式信息損失越小。步驟3)中，根據時間序列的屬性值以及模式特徵，分析攻擊者的背景知識，定義 隱私攻擊類型。由於最終發布的數據中包含最大化保留的模式信息，所以攻擊者的背景知 識可以分為兩大類，一類是關於時間序列屬性值的背景知識，定義為Kv，另一類是關於模式 信息的背景知識，定義為κρ。相應的，攻擊者的隱私攻擊類型可以劃分為三大類a)基於Kv 的隱私攻擊；b)基於Kp的隱私攻擊；c)基於Kv U Kp的隱私攻擊。(k，P)匿名模型基於上 述定義的三種隱私攻擊類型進行構建，能夠有效的抵禦隱私攻擊，從而保證用戶隱私。(k，P)匿名模型將時間序列的各個屬性區間，以及整條序列的模式特徵分別作為 獨立的形式發布，力求達到模式信息損失最小化的效果。(k，P)匿名模型是一個雙層隱私 保護模型，其具體含義如下a)在第一層約束中，整個時間序列原始數據集被要求在QI屬性上滿足k匿名的條 件，在數據發布時發布每個k匿名組各個屬性的泛化區間；b)在第二層約束中，在每一個k匿名組內，要求每一條時間序列的模式特徵都至 少與其他P-I條時間序列相同，在數據發布時發布每條時間序列的模式特徵。(k，P)匿名模型的構造示例如圖2所示，在圖2中，我們根據一個包含8條時間序列的原始數據集來構 建(k，P)匿名模型，首先可將其分為2個k匿名組(k匿名組1和k匿名組2)，每個k匿名 組中包含四條時間序列，發布每個k匿名組的各個屬性的泛化區間，然後，將每個k匿名組 各進一步劃分為兩個P子組，發布各個P子組的模式特徵。步驟4)中提到的模式特徵的相似性衡量方式嚴重依賴於模式映射函數以及攻擊 者的背景知識，需具體問題具體分析，不可一概而論。對於SAX而言，我們將模式特徵的相 似性定義為兩條模式特徵字符串之間的歐式距離。在進行分組以滿足(k，P)匿名模型約束 時，首先根據模式特徵的相似性，在整個原始數據集中以一種自頂向下的方式來構造P子 組，進一步保證模式信息損失最小化的需求。步驟5)中，基於步驟4)中形成的P子組，分析任意兩個P子組之間的QI屬性值 的相似性，以自底向上的聚類方式對P子組進行聚類，形成k匿名組，使得原始數據集最終 滿足(k，p)匿名模型的要求。步驟6)中提到的信息損失，包括屬性值信息損失以及模式信息損失兩部分。屬性 值信息損失由於屬性值泛化而產生。對於一條有η個屬性的時間序列r而言，其屬性區間 上限可表示為<，<，...,<，屬性區間下限表示為〈,『2_，...,(。基於上述定義，r的屬性值信息 損失可形式化為 模式信息損失是指原始時間序列的模式與根據模式特徵重建的模式之間的差異。 在(k，p)匿名模型約束下，能夠證明在最壞情況下的隱私洩露概率為1/P。
權利要求
一種模式信息損失最小化的序列類數據隱私保護方法，其特徵在於該方法的步驟如下1)建立一個廣義的時間序列模式定義模型，根據這個模型以及實際應用的模式挖掘任務需求，選擇符合實際應用需求的模式定義函數集；2)根據步驟1)中提出的模式定義函數集，確定模式映射函數，時間序列的屬性分為標識屬性，QI屬性和敏感屬性三種，時間序列的模式特徵由模式映射函數基於QI屬性來進行提取；3)根據時間序列的屬性值以及時間序列的模式特徵，定義隱私攻擊類型，構建(k，P)匿名模型以保護時間序列數據隱私；4)根據上述步驟2)中所述的時間序列的模式特徵，衡量整個原始數據集中任意兩條時間序列之間的模式相似性，構建P子組，以達到模式信息損失最小化的效果；5)基於步驟4)中形成的P子組，分析任意兩個P子組之間的QI屬性值的相似性，以自底向上的聚類方式對P子組進行聚類，形成k匿名組，使得原始數據集最終滿足(k，P)匿名模型的要求；6)定義(k，P)匿名模型的信息損失衡量策略，並分析其隱私洩露概率，完成對(k，P)匿名模型的可用性評估，同時根據分組結果，對時間序列數據進行屬性值的泛化，完成數據發布。
2.根據權利要求1所述的一種模式信息損失最小化的序列類數據隱私保護方法，其特 徵在於步驟1)中選用的模式定義模型，兼容已有文獻中所有的模式定義方式，對於一條 具體的時間序列r，其模式定義函數集形式化為ρ (r) = ，m為系統變量，其 中，fi(l彡i彡m)為任意兩個或兩個以上屬性的相關性函數。
3.根據權利要求1所述的一種模式信息損失最小化的序列類數據隱私保護方法，其特 徵在於步驟2)中的模式特徵應滿足以下兩個條件a)由原始時間序列經過特定的模式映 射函數得出；b)可根據該模式特徵對原始時間序列的模式進行重建。模式特徵從QI屬性 中提取，並作為一種獨立的形式發布。要求模式映射函數能夠使得重建後的模式與原始時 間序列模式的差異最小。
4.根據權利要求1所述的一種模式信息損失最小化的序列類數據隱私保護方法，其特 徵在於步驟3)中構建的(k，P)匿名模型是一個雙層隱私保護模型，其具體含義如下a)在第一層約束中，整個原始數據集被要求在QI屬性上滿足k匿名的條件；b)在第二層約束中，在每一個k匿名組內，要求每一條時間序列的模式特徵都至少與 其他P-I條時間序列相同。
5.根據權利要求1所述的一種模式信息損失最小化的序列類數據隱私保護方法，其特 徵在於步驟4)中提到的模式特徵的相似性衡量方式嚴重依賴於模式映射函數以及攻擊 者的背景知識。
6.根據權利要求1所述的一種模式信息損失最小化的序列類數據隱私保護方法，其特 徵在於步驟6)中提到的信息損失，包括屬性值信息損失以及模式信息損失兩部分，屬性 值信息損失由於屬性值泛化而產生，模式信息損失是指原始時間序列的模式與根據模式特 徵重建的模式之間的差異，在(k，P)匿名模型約束下，證明在最壞情況下的隱私洩露概率 為 1/P。
全文摘要
本發明公開了一種模式信息損失最小化的序列類數據隱私保護方法。基於一個廣義的模式定義模型以及實際應用需求來確定模式定義函數集，在此基礎上選擇能夠實現模式信息損失最小化的模式映射函數以提取模式特徵。同時基於攻擊者的背景知識來確定隱私攻擊類型，基於k匿名技術，對時間序列的QI屬性值和模式特徵施加(k，P)匿名模型，該模型將時間序列的屬性泛化區間以及模式特徵分別作為獨立的形式發布，在保證數據隱私的基礎上，將時間序列的模式信息最小化，保證數據的可用性。(k，P)匿名模型能夠兼容各種模式定義方式並擁有一套完整的可用性評估機制，其完善性和有效性使得(k，P)匿名模型能夠在最大程度上博得信賴，獲得廣泛應用。
文檔編號G06F17/30GK101964034SQ201010298698
公開日2011年2月2日 申請日期2010年9月30日 優先權日2010年9月30日
發明者壽黎但, 尚璇, 胡天磊, 陳剛, 陳珂 申請人:浙江大學