水平分布數據隱私保護支持向量機算法

摘 要：本文介紹了水平分布數據隱私保護支持向量機的幾種算法，著重介紹了利用基于一致性的分布式支持向量機的基本原理，為水平分布數據設計了相應的求解算法，該算法可以保證數據的隱私性，并通過數值試驗驗證了該算法的有效性。

關鍵詞：隱私保護，數據挖掘，數據水平分布，支持向量機

中圖分類號：TP311.13；TP309 文獻標識碼：A 文章編號：1674-7712 （2014） 10-0000-01

數據水平分布的主要原因是多個機構或組織對于不同的個體（行）收集了相同的屬性（列）信息，即數據按記錄分布在不同的站點。水平分布數據常見于同行業的不同實體間，如在金融業中，有多家銀行，也就是本文所說的節點，搜集了一些客戶信息，其中一些客戶有不良貸款記錄，同時也記錄了部分客戶的收入、支出的個人信息，這些銀行為了減少不良貸款，降低自身的放貸風險，需要在不泄露客戶隱私的條件下，進行數據挖掘，以更好地識別不良客戶，減少自身的經濟風險。還有在醫學中，為了分析某種病的發病率，幾家醫院可能將自己擁有的數據綜合起來進行分析，但是這可能涉及病人的隱私或者因為某種原因而不愿意共享數據。設此時共有J個參與方擁有數據，這J個參與方為P1，P2，…PJ。分別擁有數據 。其中m1+m2+…mJ=m，則這J個參與方所有的數據可表示為A=[A1T，A2T，…，AJT]T∈Rm×n。數據A=[A1T，A2T，…，AJT]T∈Rm×n的每一行在支持向量機中代表了一個輸入數據，第i個輸入或矩陣A的第i行向量其模式或類別用Yii∈﹛+1，-1﹜，或yi∈﹛+1，-1﹜表示，則用對角陣Y=diag（y1，y2，…，ym）表示模式構成的矩陣，稱為模式矩陣。各方由于商業機密等原因不愿泄露或共享各自所擁有的數據，但又都想利用其他人的信息來建立更好的模型以便得到良好的商業價值或其他利益，以達到各方共贏的目的

2006年，Hwanjo Yu等人在文獻[1]中研究了水平分布數據的隱私保護支持向量機問題。具體方法是先把向量問題轉化成集合問題，再利用hash函數引入計算集合交的勢，求得兩個布爾向量的內積，即可在不泄露信息前提下，最后得到利用所有數據所建立的隱私保護支持向量機模型。該算法的缺點是只能處理布爾型數據。

2007年，Olvi L.Mangasarian等人在文獻[2]中研究了水平分布數據的隱私保護支持向量機問題。利用簡約支持向量機[3，4]（RSVM）原理，方法是讓所有的站點都產生一個相同的隨機矩陣，每個站點分別利用這個隨機矩陣求得自己的核矩陣，從而得到簡約核矩陣，最后應用簡約支持向量機模型進行求解得到所要的隱私保護支持向量機模型。、

2009年，鄧乃揚、田英杰兩人在科學出版社共同出版了專著《支持向量機——理論、算法與拓展》，該書對支持向量機進行了全面完整地介紹和論述。該書講的是基于集中式的支持向量機，那么集中式和分布式有什么區別呢？

分布式結構是相對于集中式結構而言的。從數據處理的角度來說， 典型的集中式結構是數據集中存放和處理，用戶通過遠程終端或通過網絡連接來共享集中存放的數據。分布式結構則是將數據及其處理分散在不同場地，各場地各自管理一部分數據，同時又通過網絡系統相互連接。

所謂分布式計算是一門計算機科學，它研究如何把一個需要非常巨大的計算能力才能解決的問題分成許多小的部分，然后把這些部分分配給許多計算機進行處理，最后把這些計算結果綜合起來得到最終的結果。

在基于一致性分布式支持向量機中用到了一個被稱為交替方向乘子法（Alternating Direction Method of Multipliers，ADMoM）[6]的分布式優化算法。

利用基于一致性分布式支持向量機得出的數據水平分布的隱私保護算法[5]，即使有參與方互相串通，也不會泄露其他參與方的數據，所以，本算法的保密性很強。與別的算法不同，這個算法內部節點通信的代價是固定的，而且只依賴于網絡拓撲不依賴每個節點上可用訓練集的大小。相對于以往的隱私保護支持向量機算法，該算法在運算過程中不必關心數據的存儲格式，初始化可用的訓練集節點和獲得的訓練集節點整合在一起即可尋找最大線性間隔分類器。另外，刪除訓練集中的樣本或者更新訓練集中的樣本不需要重啟算法。另外，該算法對隱私保護問題具有魯棒性。

這種算法可以用如下數值試驗驗證：從UCI數據庫中選擇三個數據集：Gisette，Abalone，Covertype，按規模等分為幾部分，每部分所擁有的個體的數量或屬性個數大致相同。對于多分類的數據集，取其中的一類組成負類，其余的類為正類。為了更加準確地測試分類器的效果，對于上述三個數據集，分別任意的選取其中的70%作為訓練集，剩余的30%作為測試集。數據集的描述如下表：

由于Gauss徑向基核對于任意情況的兩類數據，都能夠在適當的參數下把數據集有效的分開，所以在模型的建立和預測過程中選取了高斯徑向基核： ，這里我們取σ=1，L=300，η=10。

實驗結果顯示，用本文給出的算法進行分類所得的正確率與所有原始數據集中時進行分類的正確率比較接近，并且利用所有參與方數據進行分類的正確率比只利用一方數據的正確率高。隨著L取值的增大，用本文算法的收斂速度下降，這時可以用η進行調節算法的收斂速度。

參考文獻：

[1]Yu H，Jiang X Q，Vaidya J.Privacy-preserving SVM using nonlinear kernels on horizontally partitioned data[C].Proceedings of the 2006 ACM Symposium on Applied Computing.New York，USA：ACM New York，2006：603-610.

[2]Mangasarian O L，Wild E W.Privacy-preserving classification of horizontally partitioned data via random kernels[C].Proceedings of the 2008 International Conference on Data Mining DMIN08，Las Vegas，July 2008（02）：473-479.

[3]Lee Y J，Mangasarian O L.RSVM：reduced support vector machines [C].Proceedings of the First SIAM International Conference on Data Mining，Chicago，April 5-7，SIAM，Philadelphia，CD-ROM Proceeding，2001：57-64.

[作者簡介]張成學（1976-），男，山東臨沂人，研究方向：向量機、模型與算法。