基于关联规则满足用户隐私保护的个性化推荐方法及系统

摘要

本发明公开一种基于关联规则满足用户隐私保护的个性化推荐方法及系统。该方法应用维规约技术得到原始数据的规约表示，并采用拉普拉斯机制或者指数机制保证规约过程满足ε1-差分隐私；应用闭频繁模式挖掘技术构建规约数据对应的前缀树，并利用拉普拉斯机制扰动频繁模式对应的支持度计数，保证满足ε2-差分隐私；同时利用一致性约束后置处理保证输出结果的可用性；挖掘前缀树，获得满足ε-差分隐私的频繁模式集合及其对应的支持度计数；应用关联规则发现算法，获得满足最小支持度和最小置信度，以及ε-差分隐私的强关联规则集合。本发明有效解决了用户隐私保护和提升个性化推荐系统性能之间的矛盾，可广泛应用于电子商务、社交网络、广告等个性化推荐系统。

说明书

技术领域

本发明属于信息技术、计算机技术领域，涉及数据挖掘方法，具体涉及一种差分隐私下 的关联规则挖掘方法，并采用该方法实现个性化推荐系统，保证用户隐私的保护。

背景技术

个性化推荐系统是建立在海量数据挖掘基础上的一种高级智能平台，能够根据用户的兴 趣特点和操作行为，向用户推荐感兴趣的信息和商品。以电子商务为例，电子商务网站(如 亚马逊、淘宝等)为用户推荐商品，自动完成个性化选择商品的过程，满足用户的个性化需 求。其中，基于关联规则的个性化推荐系统，是以关联规则为基础，把已购商品作为规则头， 规则体为推荐对象。关联规则挖掘可以发现不同商品在销售过程中的相关性，在零售业已经 得到了成功的应用。然而关联规则挖掘过程中存在用户隐私泄露的风险，即关联规则本身的 内容及其支持度计数有可能泄露用户的隐私信息。因此，如何在保护用户隐私的前提下，保 证个性化推荐系统的可用性是一个值得深入研究的问题。

传统隐私保护模型下的个性化推荐系统大多基于K-匿名模型，然而当攻击者具备一定背 景知识时，K-匿名模型就存在隐患。攻击者可以利用背景知识攻击、再识别攻击等攻击方法 来确认用户隐私信息。此外，传统隐私保护模型无法定量分析其隐私保护水平。

差分隐私作为一种新的隐私保护模型，能够解决传统隐私保护模型的两大缺陷：(1)定义 了一个相当严格的攻击模型，不关心攻击者拥有多少背景知识，即使攻击者已掌握除某一条 记录之外的所有记录信息，该记录的隐私信息也无法被披露；(2)对隐私保护水平给出了严 谨的定义和量化评估方法。因此，本发明应用差分隐私保护模型实现个性化推荐系统中用户 隐私的保护。

发明内容

本发明针对已有方法的不足，提出一种差分隐私下的关联规则挖掘方法及采用该方法的 个性化推荐系统，有效解决了用户隐私保护和提升个性化推荐系统性能之间的矛盾。

为实现上述目的，本发明采用如下技术方案：

一种差分隐私下的关联规则挖掘方法，其步骤包括：

(1)应用维规约技术得到原始数据的规约表示，并采用拉普拉斯机制或者指数机制保证 规约过程满足ε₁-差分隐私；

(2)应用闭频繁模式挖掘技术构建规约数据对应的前缀树，并利用拉普拉斯机制扰动频 繁模式对应的支持度计数，保证满足ε₂-差分隐私；同时利用一致性约束后置处理保证输出结 果的可用性；

(3)挖掘前缀树，获得满足ε-差分隐私的频繁模式集合及其对应的支持度计数；

(4)应用关联规则发现算法，获得满足最小支持度和最小置信度，以及ε-差分隐私的 强关联规则集合。

一种采用上述方法的满足用户隐私保护的个性化推荐方法，其步骤包括：

(1)获得一段时间内用户的历史行为数据；

(2)将用户的历史行为数据按照关联规则挖掘的需求进行预处理(包括数据清洗、去除 噪声数据、数据格式转换等处理)；

(3)采用上述差分隐私下的关联规则挖掘方法对预处理过的数据进行挖掘，生成关联规 则集合；

(4)依据上述模块产生的关联规则数据生成推荐列表，帮助用户发现他们感兴趣的信息， 并依据推荐列表为目标用户提供个性化的推荐服务。

一种采用上述方法的满足用户隐私保护的个性化推荐系统，包括：

数据采集模块，用于获得一段时间内用户的历史行为数据；

数据准备模块，用于将用户的历史行为数据按照关联规则挖掘的需求进行预处理(包括 数据清洗、去除噪声数据、数据格式转换等处理)；

规则挖掘模块，用于采用上述差分隐私下的关联规则挖掘方法对预处理过的数据进行挖 掘，生成关联规则集合；

推荐系统模块，用于依据上述模块产生的关联规则数据生成推荐列表，帮助用户发现他 们感兴趣的信息，并依据推荐列表为目标用户提供个性化的推荐服务。

本发明的个性化推荐系统中实现的用户隐私保护方法，是基于差分隐私交互式数据保护 框架的隐私保护方法。通过综合应用差分隐私的噪音机制(例如，拉普拉斯机制和指数机制)、 数据规约技术和闭频繁序列模式挖掘技术，实现了差分隐私下的关联规则挖掘方法，有效解 决了关联规则本身的内容及其支持度计数有可能泄露用户隐私信息的问题，保证基于关联规 则的个性化推荐系统中用户隐私的保护。本发明可广泛应用于电子商务、基于位置的服务、 社交网络、音乐视频、广告等个性化推荐系统。

附图说明

图1是差分隐私保护模型下的个性化推荐系统流程图。

图2是表2某超市用户购买记录数据对应的前缀树构建过程示例图。

具体实施方式

下面通过具体示例和附图，对本发明做进一步说明。首先说明本发明所涉及的相关技术， 然后说明本发明方法的实施过程。

1.本发明所涉及的相关技术

差分隐私是基于数据失真的隐私保护技术。通过向查询或者分析结果中添加噪音使数据 失真，确保在数据集中插入或者删除某一条记录的操作不会影响任何查询的输出结果，从而 达到隐私保护的目的。差分隐私的形式化定义如下：

ε-差分隐私 对于所有差别至多为一个记录的两个相邻数据集D₁和D₂，给定隐私算法 K，Range(K)表示K取值范围。若算法K提供ε-差分隐私，则对于所有S∈Range(K)，有

Pr[K(D₁)∈S]≤exp(ε)·Pr[K(D₂)∈S]    (1)

其中，概率Pr[]表示隐私披露风险，隐私预算ε表示隐私保护水平，ε越小保护水平越 高。

噪音机制是实现差分隐私的主要技术，常用的噪音机制包括拉普拉斯机制(Laplace  Mechanism)和指数机制(Exponential Mechanism)。基于不同的噪音机制，实现差分隐私所 添加的噪音大小与全局敏感性(Global Sensitivity)密切相关。

全局敏感性 对于任意一个函数f:D→R^d，f的全局敏感性定义为：

$\mathrm{\Delta f}={\max }_{D_1,D_2}{\left|\right|f\left(D_1\right)-f\left(D_2\right)\left|\right|}_1---\left(2\right)$

其中，D₁和D₂为相邻数据集，d表示函数f的查询维度，R表示所映射的实数空间。

拉普拉斯机制 对于任一个函数f:D→R^d，若算法K的输出结果满足下列等式，则K满 足ε-差分隐私保护。

K(D)＝f(D)+<Lap₁(△f/ε),…,Lap_d(△f/ε)>    (3)

其中，Lap_i(△f/ε)(1≤i≤d)是相互独立的拉普拉斯变量，对应概率密度函数为 p(x|b)＝(1/2b)exp(-|x|/b)。噪音大小与△f成正比，与ε成反比，即全局敏感性越大，所添 加噪音越大。拉普拉斯机制主要处理一些输出结果为实数型的算法。

指数机制 给定一个打分函数u:(D×O)→R，若算法K满足下列等式,则K满足ε-差分 隐私。

$K(D,u)=\left\{r\right|\mathrm{Pr}[r\in O]\propto \exp \left(\frac{\mathrm{ϵu}(D,r)}{2\mathrm{\Delta u}}\right)\}---\left(4\right)$

其中，△u为打分函数u(D,r)的全局敏感性，r表示从输出域O中所选择的输出项。由公 式(4)可知，打分越高，被选择输出的概率越大。指数机制主要处理一些输出结果为非数值型 的算法。

关联规则 重复出现概率很高的模式或规则。规则的支持度(support)和置信度 (confidence)是规则兴趣度的两种度量，反别反映所发现规则的有用性和确定性。一般而言， 关联规则的挖掘是一个两步的过程：(1)找出所有的频繁模式；(2)由频繁模式产生强关联规 则。因此，挖掘关联规则的问题可以归结为挖掘频繁模式。

频繁模式 模式在原始数据集中的支持度计数满足预定义的最小支持度计数阈值。频繁 模式FP(Frequent Patterns)形式化定义为：

且S∈DB,使得support(s)≥min_sup}    (5)

其中，DB表示原始数据集，support(s)表示模式s对应的支持度计数，min_sup表示最小 支持度计数阈值。

闭频繁模式 模式在原始数据集中是频繁和闭的。模式是闭的，如果不存在真超模式使 得两者在原始数据集中具有相同的支持度计数。闭频繁模式CP(Closed-frequent Patterns)形 式化定义为：

CP＝{s|s∈FP且使得s∈s'且support(s)≠support(s')}    (6)

数据规约技术 用来得到大型数据集的规约表示，它小得多，但仍接近于保持原始数据 的完整性。在规约后的数据集上挖掘将更有效，仍然产生相同(或几乎相同)的分析结果。常 用的数据规约策略包括维规约、数量规约和数据压缩。本发明应用到的维规约策略是一种有 损的数据压缩技术。

2.本发明方法的实施过程

本发明的差分隐私下的关联规则挖掘方法，其详细描述如表1所示：

表1 本发明方法的详细描述

例如，采用表2所示的某超市的用户购买记录数据，对应前缀树的构建过程如图2所示， 假设最小支持度阈值min_sup＝3。

表2 某超市的用户购买记录数据

维归约：假设规约后的最大记录长度l_opt＝3，则表2所示数据会有两条记录被截断，即 第5条记录I₂→I₃→I₁→I₂→I₃表示为I₂→I₃→I₁，第8条记录I₃→I₁→I₂→I₃表示为 I₃→I₁→I₂，其他记录保持不变。

闭频繁模式挖掘：图2中以模式{I₁}为前缀的子分支和以模式{I₃→I₁}为前缀的子分支 满足闭频繁模式包含关系。故只对闭频繁模式，即以{I₁}为前缀的子分支分配隐私预算，添 加相应的拉普拉斯噪音扰动其真实支持度计数。后将{I₁}在前缀树中的所有后代直接移植给 {I₃→I₁}，或{I₃}指向{I₁}即可。

后置处理：图2中假设添加拉普拉斯噪音的支持度计数C(v₁)＝3.1,C(v₂)＝0.3, C(v₃)＝0.8,C(v₄)＝1.8,进行一致性估计得到C(v₁)＝7·3.1/(3.1+0.3+0.8+1.8)≈3, C(v₂)＝7·0.3/(3.1+0.3+0.8+1.8)≈0,C(v₃)＝7·0.8/(3.1+0.3+0.8+1.8)≈1,C(v₄)＝7·1.8/( 3.1+0.3+0.8+1.8)≈2，均满足一致性约束。

挖掘前缀树：图2中某一频繁模式{I₂→I₃→I₁：4}，其对应7个频繁子模式： {I₂：2},{I₃：4},{I₁：4},{I₂→I₃：4},{I₃→I₁：2},{I₂→I₁：4},{I₂→I₃→I₁：4}，其中有三个 频繁子序式在其他频繁模式中重复出现，且对应支持度计数均大于当前值，即 {I₂：10},{I₃：9},{I₂→I₃：7}，故需要更新取频繁子模式对应最大扰动计数值。

关联规则挖掘：例如频繁模式{I₂：10},{I₂→I₃：7}，易得关联规则对应支持度 为7/8＝87.5％，置信度为7/10＝70％。假设最小置信度阈值min_conf＝0.7，则该规则满足强 关联规则，可被放入推荐列表中用于个性化推荐。

下面提供一个个性化推荐系统具体应用示例。

以沃尔玛案例为例子，假设上述示例经过挖掘所找到的强关联规则为“尿布和啤酒”，则 支持度表示在所有的交易数据记录中，尿布与啤酒这两项商品被同时购买的比例至少有 87.5％；置信度表示所有包含尿布的交易数据记录中，同时购买啤酒的比例至少为70％。因 此，本个性化推荐系统可以指定一种推荐服务，即发现有消费者有购买尿布的行为，就向消 费者推荐啤酒。在整个个性化推荐过程中，在关联规则的挖掘满足差分隐私保护模型的前提 下，同时有效保证了个性化推荐系统的可用性。

以上实施例仅用以说明本发明的技术方案而非对其进行限制，本领域的普通技术人员可 以对本发明的技术方案进行修改或者等同替换，而不脱离本发明的精神和范围，本发明的保 护范围应以权利要求所述为准。