[發明專利]一種基于空間序列數據分析的用戶軌跡隱私保護方法

有效

• 申請號: 201610028542.9
• 申請日: 2016-01-15
• 公開（公告）號: CN105701418B
• 公開（公告）日: 2018-08-14
• 發明（設計）人: 桂小林;冀亞麗;楊廣知;張晨;張開元;李敬;代兆勝
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06F17/30
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 徐文權

1.一種基于空間序列數據分析的用戶軌跡隱私保護方法，其特征在于，包括以下步驟：

A.提取個人興趣點：對每個移動用戶的空間序列數據進行聚類分析；

B.構建公共興趣區：對全體用戶的興趣點按時間分區進行聚類分析；

C.在公共興趣區內交換位置：對同一個興趣區內的用戶位置進行隨機交換；

步驟A具體包括以下步驟：

A1：對于每個移動用戶一天內所有的采樣位置，使用基于密度的聚類方法對其進行聚類，并根據聚類結果生成聚類索引；

A2：根據指定的時間閾值和漂移點個數閾值，使用基于時間序列的方法對每個移動用戶的聚類索引進行分析，修改不能形成興趣區的采樣點的聚類索引、漂移點的聚類索引，生成每個用戶的個人興趣區索引；

A3：將個人興趣區索引中數值相同的采樣點按照指定的方式生成個人興趣點；

步驟A1具體包括以下步驟：

設置位置矩陣M_OS表示某一天所有用戶的所有采樣位置，其中行向量代表一個用戶，列向量代表某一采樣時刻；設采樣時間間隔為t，t的計量單位為秒；用戶總數為N_OS；矩陣M_OS中元素為mos_i,j，其中i＝1,2,…,n_OS；j＝1,2,…,m_OS，行數n_OS＝N_OS，列數m_OS為：

設給定的時間閾值為T_s，給定的聚類半徑為R_SP，采用DBSCAN進行聚類時設置Eps＝R_SP；聚類區域中所包含的點數的最小值MinPts為：

根據DBSCAN聚類結果生成的聚類索引矩陣I_CR；I_CR的元素為icr_i,j，I_CR大小與M_OS相同；

步驟A2具體包括以下步驟：

根據指定的時間閾值和漂移點個數閾值，使用基于時間序列的方法對每個移動用戶的聚類索引進行分析，修改不能形成興趣區的采樣點的聚類索引、漂移點的聚類索引，生成每個用戶的個人興趣區索引；

對于需要修改的聚類索引，通過矩陣約簡的過程發現并修改；矩陣約簡的具體方法如下：構造以T_s為時間間隔的矩陣I_DR和與I_DR大小相同的矩陣T_DR1和T_DR2，矩陣I_DR的行數與I_CR的行數相同，即n_DR＝n_CR＝n_OS＝N_OS，矩陣I_DR的列數m_DR為:

I_DR中元素為idr_i,j，其中i＝1,2,…,n_DR，j＝1,2,…,m_DR，使得：

其中k是與j*T_s最接近的采樣時刻；

在形成I_DR的過程中，對每一個j*T_s到(j+1)*T_s時間段內的T_s/t列采樣數據，僅保留了2列，其中j＝1,2,…,m_DR-1；引入與I_DR相應大小的矩陣T_DR1和T_DR2來記錄idr_i,j在j*T_s到(j+1)*T_s內的結束時刻和idr_i,j+1在j*T_s到(j+1)*T_s內的開始時刻；

在形成T_DR1和T_DR2的過程中，發現漂移點和一部分不能構成興趣區的采樣點；在形成T_DR1和T_DR2后，通過計算tdr1_i,j+1與tdr2_i,j的差值，發現其他的不能構成興趣區的采樣點；

對于漂移點，將其聚類索引值修改為鄰近采樣點的聚類索引值，對于不能構成興趣區的采樣點，將其聚類索引值修改為噪聲點的索引值；修改聚類索引后生成的索引矩陣I_IA表示對應用戶的個人興趣區索引；索引矩陣I_IA的元素為iia_i,j，大小與I_CR相同；

步驟A3具體包括以下步驟：

索引矩陣I_IA的每一行對應一個用戶的個人興趣區索引，個人興趣區索引值相同的采樣點構成了此用戶的一個個人興趣區；個人興趣區中所有采樣點的位置數據反映在二維坐標平面上可形成一個區域，個人興趣點通過指定方式對區域中的采樣點進行處理得到；

根據個人興趣區索引I_IA將M_OS中的采樣點位置變成相應的個人興趣點位置，即設置與矩陣M_OS大小相同的矩陣M_IP，M_IP的行數n_IP＝n_OS＝N_OS，列數m_IP＝m_OS，M_IP中元素為mip_i,j，其中i＝1,2,…,n_OS，j＝1,2,…,m_OS，使得:

其中(x,y)_i表示M_OS中第i行的某個興趣點位置，A(x,y)_i表示此興趣點對應的興趣區，P_i表示第i行所有興趣點位置的集合；

步驟B具體包括以下步驟：

B1：對指定時間范圍內所有用戶的個人興趣點，使用基于密度的聚類方法對其進行聚類，根據聚類結果生成指定時間范圍內每個采樣時刻的公共興趣區索引；

B2：將指定時間范圍內的公共興趣區索引中數值相同的個人興趣點按照指定的方式生成公共興趣點；

步驟B1具體包括以下步驟：

設SIP_i(t_b,t_e)表示M_IP中指定時間范圍內第i行所有興趣點的集合；其中i＝1,2,…,n_OS，指定時間范圍為t_b采樣時刻至t_e采樣時刻，SIP_i(t_b,t_e)中無重復元素；SPA(t_b,t_e)表示所有SIP_i的并集，即：

SPA(t_b,t_e)＝∪SIP_i(t_b,t_e) (6)

對SPA(t_b,t_e)的n_spa個元素采用DBSCAN進行聚類，設置Eps＝R_SP和MinPts＝k，得到SPA(t_b,t_e)中所有元素spa_u(t_b,t_e)分別對應的聚類索引值ispa_u(t_b,t_e)；其中u＝1,2,…,n_spa；根據SPA(t_b,t_e)的聚類索引，生成t_b采樣時刻至t_e采樣時刻內每個采樣時刻的公共興趣區索引即的元素為ipa(t_b,t_e)_i,j其中i＝1,2,…,n_os，j＝b,b+1,…,e-1,e，使得:

步驟B2具體包括以下步驟：

索引矩陣中公共興趣區索引值相同的個人興趣點構成了此時間范圍內的一個公共興趣區。