基于序列格的隐私时序模式挖掘方法

Private Time Series Pattern Mining with Sequential Lattice

基于差分隐私的时间序列模式挖掘方法中,序列的最大长度以及添加拉普拉斯噪声的多少直接制约着挖掘结果的可用性.针对现有时间序列模式挖掘方法全局敏感度过高、挖掘结果可用性较低的不足问题,提出了一种基于序列格的差分隐私下时间序列模式挖掘方法PrivTSM(Differentially Private Time Series Pattern Mining).该方法首先利用最长路径的策略对原始数据库进行截断处理;在此基础上,采用表连接操作生成满足差分隐私的序列格;结合序列格结构本身的特性,合理分配隐私预算,提高输出模式的可用性.理论分析表明PrivTSM方法满足ε-差分隐私,基于真实数据库上实验结果表明,PrivTSM方法的准确率TPR(True Postive Rate)和平均相对误差ARE(Average Relative Error)明显优于N-gram和Prefix-Hybrid方法.

Many methods of differentailly private time series pattern mining have been proposed,while in those methods,the length of sequence pattern and Laplace noise directly constrain the utility of the mining results.To address the questions caused by the global query sensitivity and lower utility of the existing works,an efficient method,called PrivTSM(differentially Private Time Series Pattern Mining) is proposed,which is based on sequence lattice for mining time series pattern with differential privacy.This method relies on the longest path strategy to truncate the original database;based on the truncated database,this method uses the table join operation to construct a differentially private sequence lattice.Furthermore,this method uses the property of the sequence lattice structure itself to allocate privacy budget reasonably and boost the accuracy of the noisy counts.PrivTSM satisfies ε-differential privacy through theoretical analysis.The experimental results on real datasets show that the accuracy(TPR) and average relative error(ARE) of the PrivTSM are better than those of the N-gram and Prefix-Hybrid algorithms.