一種隱私保護的序列數據馬爾可夫分類方案

李宗峰，黃劉生，沈 瑤，許 楊，聶熠文，楊 威

1(中國科學技術大學 計算機科學與技術學院，合肥 230027) 2(中國科學技術大學 蘇州研究院，江蘇 蘇州 215123)

1 引 言

序列數據分為時間序列數據、DNA序列數據、語音數據、自然語言數據等.序列數據分類是目前數據挖掘領域的一個研究熱點.本文將主要研究使用馬爾可夫模型對序列數據進行分類時的隱私保護.

數據挖掘是在大型數據存儲庫中，自動地發現有用信息的過程[4].數據挖掘主要有分類、聚類和關聯分析等研究方向.分類就是確定對象屬于哪個預定義的目標類[4].分類任務一般分為兩步，第一步根據輸入數據建立分類模型，第二步利用分類模型對待分類數據進行分類.常見的分類模型主要有決策樹模型、神經網絡模型、基于規則的模型、支持向量機模型、貝葉斯模型等.

序列分類是分類算法的一個類別，其輸入是序列數據，輸出是對這個序列的某個離散標記.針對序列數據，常見的分類方案有如下幾種：一是借助于序列數據的領域知識或者特點進行分類，這種方法存在通用性差、特點難以發現等特點；二是使用傳統的特征分類算法進行分類，使用這種方法需要找到有效的特征查找方法，但很多序列數據難以找到有效的特征；第三種是使用概率模型對數據進行分類，該方案在序列數據分類中比較常見，針對序列數據，有較完善的數學基礎；同時具有效率與準確性較高，通用性強的優勢.

馬爾可夫模型是一個描述隨機過程的概率模型.作為一種分類方法，馬爾科夫模型的準確度和參與訓練的具有代表性的數據量密切相關.因此如何獲得足夠多的具有代表性的數據成為一個關鍵問題.

某機構或個人獲得的序列數據往往是相同類型，會導致數據的代表性比較差，無法訓練出有效的模型.此時比較好的方案是與多個機構合作進行訓練，這就可以獲得足夠多有代表性的數據，所以多個機構或個人合作訓練模型是一種解決問題的有效辦法.

多個機構或個人合作訓練模型能夠獲得比較好的模型，但并不是所有的機構或個人都同意直接共享數據.例如某機構持有購買的金融市場的金融產品價格數據或持有某些具有基因缺陷的人類基因信息.如果直接共享數據，會造成這些機構或個人在法律或者隱私等方面的擔憂，例如遺傳病的基因標記[3].這種情況下，如何保證每個合作的機構或個人的數據隱私是一個非常重要的考慮.

基于上述實際場景的需求，本文主要介紹了在多方參與者擁有序列數據并且保護各方隱私的情況下，共同訓練馬爾科夫模型的方案.本文提出的方案不僅可以訓練出傳統的一階馬爾可夫模型，還可以訓練k階馬爾可夫模型，k階馬爾可夫模型可以提高模型的分類準確度[5].此方案還能夠對隨著時間變化的數據做到有效的處理，此外，此方案的各項開銷(計算、通信等開銷)比[2]中介紹的同態加密方案低，是一種高效可行的方案.

2 預備知識

本文主要針對馬爾可夫模型的隱私保護進行討論.在這一節將首先對馬爾可夫模型進行簡要概述，接著對隱私保護方法進行簡要說明.本文采用的方案與目前已有的同態加密方案[2]相比，具有簡單、高效以及能夠更好的處理隨時間變化的數據等特點.

2.1 馬爾可夫模型

馬爾可夫模型是一種廣泛使用的統計模型，目前已經成功應用在語音識別、輸入法等領域.

馬爾可夫鏈分為連續時間馬爾可夫鏈與離散時間馬爾可夫鏈，本文中使用的馬爾可夫模型為離散時間馬爾可夫鏈.下面分別介紹一階與K階馬爾可夫模型.

馬爾科夫鏈是一系列狀態的集合，集合中每一個狀態發生的概率只與前一個狀態有關，與集合中其他狀態無關.這里為方便表示，將狀態集合表示為∑.例如，如果用S表示一個長度為n的序列，這個序列的第i個狀態表示為Si，這個狀態的值表示為si.這樣第i個狀態發生的概率可以如下表示

P(Si=si|Si-1=si-1,Si-2=si-2，…S1=s1)

=P(Si=si|Si-1=si-1)

即任何一個狀態發生的概率只與前一個狀態有關，與前面其他狀態無關.可以計算出序列S的概率

P(S)=P(Sn=sn|Sn-1=sn-1)P(Sn-1=sn-1|Sn-2=sn-2)…

簡化為：

P(S) =P(sn|sn-1)P(sn-1|sn-2)…P(s1)

上式的主要參數為每個狀態的先驗概率和狀態之間的轉移概率.對于任意狀態Si，其先驗概率為：

上式中num(si)表示狀態Si出現的次數，∑sj∈∑count(sj)表示所有狀態出現的次數總和.

馬爾科夫模型對序列數據分類就是首先根據訓練數據對每個類計算以下參數：類中每個狀態發生的先驗概率，類中狀態之間的轉移概率.經過訓練之后每個類都有一個先驗概率向量和一個轉移概率矩陣.使用馬爾科夫模型的方法如下：對于任意一個新的序列數據S，分別使用每個類訓練的參數計算S發生的概率，然后將所有計算所得的概率求最大值，概率最大值對應的類就是S的類標.

K階馬爾科夫模型相對于一階馬爾科夫模型，每個狀態發生的概率不僅僅與前一個狀態有關，而且與緊鄰的前k個狀態有關，并且也只與前k個狀態有關.這種情況下，每種狀態的發生概率變為：

P(Si=s|Si-1=si-1,Si-2=si-2,…S1=s1)

=P(Si=si|Si-1=si-1,…,Si-k=si-k)

對于時間序列S其發生的概率為

K階馬爾可夫模型下，任何一個狀態的先驗概率為：

上式中num(s1,s2,…,sk-1,sk)表示序列s1,s2,…,sk-1,sk在訓練數據集中出現的次數，num(所有k長度序列)表示所有長度為k的序列在訓練數據集中出現的次數總和.

對于任意狀態si與序列s1,s2,…,sk-1,sk的轉移概率為：

上式中num(s1,s2,…,sk-1,sk,si)是序列s1,s2,…,sk-1,sk,si出現的次數.num(s1,s2,…,sk-1,sk)是序列s1,s2,…,sk-1,sk出現的次數.

K階馬爾科夫模型與一階馬爾科夫模型類似.首先使用訓練數據針對每個類計算出每個狀態的先驗概率以及狀態轉移矩陣.對于任意序列S，使用每個類的先驗概率和狀態轉移矩陣計算其發生的概率，概率最大的類標即為序列S的類標.

2.2 隱私保護技術

隱私包括很多方面，例如數據隱私、模型參數隱私等.本文中隱私主要是指數據內容隱私以及數據統計特征的隱私.本文中隱私為每個參與方所持有的數據內容以及統計特征，所有參與方數據總體的統計特征并不是隱私.一直以來隱私保護問題依賴于數據分析方法[1].很多數據挖掘和機器學習算法通過擴展能夠做到保護隱私，這類拓展大多分為兩類.第一類是對數據加擾動，例如隨機化、旋轉或多重采樣[2，7-9，12，14].這類方法會造成一定的數據損失.第二類是在計算過程中使用密碼學方法對數據進行保護[2，10，11，13，15，16].這類方法理論上不會造成數據損失.本文方案屬于第二類.本文主要使用了群，哈希函數，冪乘等來實現隱私保護.

目前已經有馬爾可夫模型的隱私保護方案，[2]中提出的方案主要借助同態加密技術實現隱私保護，同態加密具有復雜、效率低等特點.本文提出的方案比較簡單，效率較高，能夠更好的處理隨時間變化的數據.

本文提出的方案使用的隱私保護技術主要參考[1]，要點包括可信第三方確定一個群，以及n+1(參與方數目為n)個密鑰s0，s1,s2…，sn，其中所有密鑰之和為0，其中群是公開的，G是一個p階循環群，p是素數，g為生成元，G滿足decisional Diffie-Hellman(DDH)assumption.每個參與方獲得一個密鑰，剩下的一個密鑰分給最終模型訓練者.對于任意參與者i，在t時刻加密其參數x，此時計算

Ci=gxH(t)Ki

其中，H(t)為公開的哈希函數.Ki為參與者i的密鑰.每個參與者都計算Ci，并將Ci發送給最終模型訓練者，最終模型訓練者計算

化簡可得

本文的隱私保護主要借助于密碼學技術，包括群運算以及哈希函數等.本方案使用的密碼學技術已經在[1]中進行了證明.

3 一種基于隱私保護的馬爾可夫序列分類方法

本方案為在保護各參與方隱私的前提下合作訓練馬爾科夫模型.簡化起見，假設參與方有A與B，其中A為最終的模型訓練者，A與B分別掌握一定數量的序列數據，A與B希望合作訓練馬爾可夫模型，下面將針對一階與k階馬爾科夫模型進行說明.

3.1 一階馬爾可夫模型

訓練馬爾可夫模型的核心為：對每一類序列數據，計算每一個狀態的先驗概率和狀態之間的轉移概率.

此處使用C表示訓練集合中序列數據所有類的集合，對于第i個類使用ci作為類標.

對任意狀態s，其在類ci中的先驗概率為

上式中num(s,ci)表示類ci中狀態s出現的次數，num(ci)表示類ci中所有狀態出現的次數的總和.

當數據分布在A和B兩方時，類ci中狀態s的先驗概率為

上式中，numA(s,ci)表示A的數據上，類ci中狀態s出現的次數，numB(s,ci)表示B的數據上，類ci中狀態s出現的次數，numA(ci)表示A的數據上，類ci中所有狀態出現的次數的總和，numB(ci)表示B的數據上，類ci中所有狀態出現的次數的總和.

訓練模型，就是計算numA(s,ci)+numB(s,ci)和numA(ci)+numB(ci)的值。此處借鑒了參考文獻[1]中一種處理方法。此方法的正確性已經在文獻中進行了證明.

除A、B外，還需有一個可信第三方T，T首先生成群G以及三個密鑰keyA、keyB、keyC，群G生成元為g，階為p，keyA+keyB+keyC=0.T分發keyA給A，分發keyB給B，并將訓練最終模型的密鑰keyC給A.A與B分別在各自本地數據上進行訓練，計算每個類中各個狀態的先驗概率，不同狀態之間的轉移概率等參數.A、B針對每一個參數計算對應的加密參數，例如A計算的某個參數值為parA，B計算的對應的參數值為parB，則A計算加密參數為basekeyA*gparA，B計算結果為basekeyB*gparB，，其中base為A與B共享的哈希函數H(t):Z→G，t為當前時間.A、B將各自計算所得的結果發給最終模型訓練者A，A將各個參與方的計算結果與basekeyC相乘得到V=basekeyC*basekeyA*gparA*basekeyB*gparB=gparA+parB，V與g已知，可計算得到parA+parB.將模型所有參數用上述流程計算可得到最終的模型.算法總結如算法1所示

算法1.隱私保護的一階馬爾可夫序列分類

輸入：A有數據集DA，B有數據集DB，T為可信第三方

輸出：保護DA與DB隱私前提下A、B每隔PT時刻合作訓練馬爾可夫模型

1 在時刻t，T向A與B分發密鑰以及g等參數.

2 每隔PT時刻(每一輪)：

3 for 每個類cido

4 A在DA上計算類ci中每個狀態出現的次數.

5 B在DB上計算類ci中每個狀態出現的次數.

6 for每個狀態sado：

7 A在DA上計算類ci中sa出現的次數

numA(Sa,ci)

8 B在DB上計算類ci中sa出現的次數

numB(Sa,ci)

9 for每個狀態sbdo：

10 A在DA上計算類ci中sasb出現的次數

numB(aa,sb,ci)

11 B在DB上計算類ci中sasb出現的次數

numB(sa,sb,ci)

12 endfor

13 endfor

14 endfor

15 A、B各自計算上面計算的所有次數對應的加密參數，B將計算的參數發送給A，A利用B的參數計算獲得最終模型.

3.2 K階馬爾可夫模型

K階馬爾可夫模型與一階馬爾科夫模型類似，但需將每個狀態的關聯狀態向前進行了拓展，所以K階馬爾可夫模型的需要計算更多的參數.

對于每一個K長度的序列：s1,s2,…,sk，對于每一個類ci，先驗概率為：

上式中num(s1,s2,…,sk,ci)表示類ci中串s1,s2,…,sk出現的次數，num(所有K長度序列)表示串ci中所有K長度序列的數量.

對于任何一個狀態si以及k長度串：s1,s2,…,sk，狀態si到s1,s2,…,sk的轉移概率為：

K階馬爾可夫對應的訓練方案與一階馬爾可夫模型的訓練方案基本一致，不同點為需要計算的模型參數數目會根據K變化，需要計算更多的先驗概率和轉移概率.

4 試驗及結果分析

4.1 實驗環境及相關說明

使用單核CPU主頻為2.4GHz，內存為512M，運行Ubuntu 16.04系統的主機.使用C++進行編程，借助Crypto++庫和Linux Socket.

實驗數據為人和老鼠的基因數據，數據由1提供的鏈接下載，數據為真實數據.根據數據的特點，為方便實驗，對數據進行了預處理.對缺失數值采取刪除處理，并去除一些無用信息后將數據整理成每行最多20個，最少18個.根據對實驗的相關參數的分析，將數據組織成20、100、200、1000行四個訓練數據集，標記為D1、D2、D3、D4.

為綜合評估本方案，從方案的誤差、時間效率以及與類似方案的對比進行分析.

4.2 誤差分析

此處誤差是指多方合作訓練馬爾科夫模型與單獨在數據集上訓練馬爾科夫模型所獲得的兩個模型的誤差.

由理論分析可知，使用此方案訓練的馬爾科夫模型沒有誤差.但是實際實驗中仍然可能產生誤差.對過程分析可知需要計算H(t)k這個參數，其中所有K相加為0，故存在K為負數，此時H(t)k為實數，實數運算中就會產生誤差.為了避免此類誤差，有兩種解決方法，一種是對所有K加一常數，使其為非負數，另一種方法是將K當成其絕對值，然后標記計算結果，改進計算方式.本實驗使用第二種方法.經過實驗驗證，本方案在所選的數據集上合作訓練馬爾科夫模型與單獨訓練馬爾科夫模型相比無誤差.

4.3 時間效率

方案的時間效率主要考慮整體時間開銷，以及模型訓練各階段的時間開銷.

表1 一階運行時間實驗結果Table 1 Experimental result of running time with order 1

對方案的時間效率進行分析，設計兩組實驗.第一組實驗主要測試不同參數以及不同數據集上實驗的時間開銷.參數主要有群的階的位數、可信第三方分發的密鑰位數以及馬爾科夫模型階數，實驗只訓練一輪.實驗結果如表1表2所示，實驗結果中時間單位為秒.

表2 二階運行時間實驗結果Table 2 Experimental result of running time with order 2

從表1表2可以看到，在其它參數相同的條件下，馬爾科夫模型階數、群的階的位數、密鑰的位數、數據集的規模分別增長時，訓練模型的時間開銷都會增長.此實驗只進行一輪，可以看出只有一輪的情況下，有些參數情況時時間開銷較小，實際使用的可行性較高.

第二組實驗主要探索模型訓練各階段時間開銷，將模型訓練過程分為三階段：可信第三方生成及分發密鑰等參數、各方本地訓練并發送數據給最終模型訓練者、最終模型訓練者計算模型，三階段依次記為T1、T2、T3.群G的階為2048位，密鑰長度為8位.實驗結果如表3所示，實驗結果中時間單位為秒.

表3 各階段時間實驗結果Table 3 Experimental result of time cost in every period

從表3可看到T1階段的時間開銷最大，其他兩個階段時間開銷比較小.如果是多輪訓練，則只會增加T2和T3階段，時間開銷增長較少，所以隨著輪數增加，本方案優勢較高.需要指出的是本實驗中群的階為2048位，當群的階為1024位時，則T1會有較大幅度的較少，同理，如果將群的階設置為4096位，在本實驗環境中花費六分鐘以上仍未完成T1階段.從本實驗結果可以看出，雖然T1時間較長，但是T2、T3比較小，實際使用有較高的可行性.

4.4 比較與分析

目前隱私保護的馬爾科夫模型訓練方案還有同態加密方案[2].其主要借助于secure logsum協議，其實驗中使用ElGamal加密系統作為同態加密工具.本實驗數據集D1與同態加密方案測試的第一個數據集的數量相比近似相同，此處將使用其實驗數據與本文方案做比較.實驗結果如圖1所示，柱狀體的高度表示時間開銷，單位為秒.

圖1 兩種方案時間開銷Fig.1 Time cost of two method

從圖中可以看出，隨著輪數增加，本文方案具有較小的增長，同態加密方案則是增加一個固定的數值.通過對兩個方案進行比較可以知道，兩個方案使用了類似的技術，而從分層的角度看，同態加密方案有兩層，而本文方案只有一層，本文方案對本問題具有更強的針對性，同態加密方案有較高的通用性.

4.5 實驗總結與改進

本實驗模擬了在保護各參與方數據隱私的前提下合作訓練馬爾可夫模型的方案.誤差分析說明了方案的正確性，時間效率實驗指出本方案具有較高的可行性，與已有方案的比較試驗證明了本方案具有較高的時間效率優勢.

通過對方案分析和對實驗結果進行探究可以對本方案進行加強和改進，例如在程序流程上可以探索各方合作時如何針對不同的數據集調整訓練流程，減小訓練時間.另外在某些數據量比較大的時候可以考慮把單個參與方虛擬為多個參與方，將數據均分到虛擬參與方，減少單個參與方在計算大數時的較高開銷.

5 工作展望

本文首先介紹了用于序列數據分類的馬爾科夫模型，然后介紹了隱私保護的馬爾科夫模型，進而提出了一個在隱私保護情況下訓練馬爾科夫模型的方案，并針對提出的方案進行實驗. 實驗結果顯示此方案具有比較好的準確度和相對較小的開銷.后面將會探索對實驗方案進行改進，在可信第三方發放密鑰之后，將研究密鑰隨著時間變化，每個參與方的密鑰將會有一個以初始密鑰作為輸入的函數產生，所有參與方的密鑰都會隨著時間變化，但是仍然保持所有參與方密鑰之和為零的特性.還將探索如何利用現代計算機特性，提高運算效率.

[1] Shi E，Chan H T H，Rieffel E，et al.Privacy-preserving aggregation of time-series data[C].Annual Network & Distributed System Security Symposium(NDSS)，Internet Society，2011.

[2] Guo S，Zhong S，Zhang A.A privacy preserving Markov model for sequence classification[C].Proceedings of the International Conference on Bioinformatics，Computational Biology and Biomedical Informatics，ACM，2013：561.

[3] Jha S，Kruger L，Shmatikov V.Towards practical privacy for genomic computation[C].Security and Privacy，SP 2008，IEEE Symposium on.IEEE，2008：216-230.

[4] Tan Pang-ning，Michael Steinbach，Vipin Kumar.Introduction to data mining[M].Beijing：Beijing Posts and Telecom Press，2011.

[5] Andorf C，Silvescu A，Dobbs D，et al.Learning classifiers for assigning protein sequences to gene ontology functional families[J].Structural Induction：Towards Automatic Ontology Elicitation，2008：39.

[6] Chen K，Liu L.Privacy preserving data classification with rotation perturbation[C].Data Mining，Fifth IEEE International Conference on.IEEE，2005：589-592.

[7] Agrawal R，Srikant R.Privacy-preserving data mining[C].ACM Sigmod Record，ACM，2000，29(2)：439-450.

[8] Huang Z，Du W，Chen B.Deriving private information from randomized data[C].Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data，ACM，2005：37-48.

[9] Du W，Zhan Z.Building decision tree classifier on private data[C].Proceedings of the IEEE International Conference on Privacy，Security and Data Mining-Volume 14，Australian Computer Society，Inc.，2002：1-8.

[10] Lindell Y，Pinkas B.Privacy preserving data mining[C].Annual International Cryptology Conference，Springer Berlin Heidelberg，2000：36-54.

[11] Yan Cai-rong，Zhu Ming，Shi You-qun.Mining sequential patterns based on privacy preserving [J].Journal of Chinese Computer Systems，2008，29(7)：1241-1244.

[12] Lu Cheng-lang，Liu Ming-yong，Wu Zong-da，et al.Personal privacy protection scheme for network information systems[J].Journal of Chinese Computer Systems，2015，36(6)：1291-1295.

[13] Lin Shao-cong，Ye A-yong，Xu Li.K-anonymity location privacy protection method with coordinate transformation[J].Journal of Chinese Computer Systems，2016，37(1)：119-123.

[14] Qian Ping，Wu Meng，Liu Zhen.A method on homomorphic encryption privacy preserving for cloud computing[J].Journal of Chinese Computer Systems，2015，36(4)：840-844.

[15]Xu Wei-jiang，Huang Liu-sheng，Luo Yong-long，et al.Privacy-preserving range searching [J].Journal of Chinese Computer Systems，2009，30(10)：1972-1979.

附中文參考文獻：

[4] Tan Pang-ning，Michael Steinbach，Vipin Kumar.數據挖掘導論[M].北京：人民郵電出版社，2011.

[11] 燕彩蓉，朱 明，史有群.基于隱私保護的序列模式挖掘[J].小型微型計算機系統，2008，29(7)：1241-1244.

[12] 盧成浪，劉明雍，吳宗大，等.針對網絡信息系統的個人隱私保護方案[J].小型微型計算機系統，2015，36(6)：1291-1295.

[13] 林少聰，葉阿勇，許 力.基于坐標變換的k匿名位置隱私保護方法[J].小型微型計算機系統，2016，37(1)：119-123.

[14] 錢 萍，吳 蒙，劉 鎮.面向云計算的同態加密隱私保護方法[J].小型微型計算機系統，2015，36(4)：840-844.

[15] 徐維江，黃劉生，羅永龍，等.保護私有信息的范圍搜索算法[J].小型微型計算機系統，2009，30(10)：1972-1979.