面向用户多数据场景的频繁字符串的挖掘方法

1.本发明属于计算机技术领域，特别是一种面向用户多数据场景的频繁字符串的挖掘方法。


背景技术：

2.现在大多数智能手机都依赖软件键盘作为文本输入手段，为了便于用户使用，移动操作系统通常会给用户提供一些常用词语。为了提供准确的词汇建议，需要建立一个词典，包含用户大概率会使用的词汇；而构建这样的词典，需要从用户端挖掘频繁字符串。理想情况下，移动操作系统可以从用户那里收集字符串使用的频数信息，并将其提交给收集者；然后收集者筛选出用户最常使用的前k个字符串，将其包含在移动键盘词典中，并将更新推送到用户的设备上。显然，这样直接收集字符串使用数据会侵犯用户的隐私。
3.在没有可信第三方的前提下，本地差分隐私技术(local differential privacy,ldp)已被建立为收集用户敏感信息的一个强有力的隐私标准。ldp模型中每个用户首先在本地扰动自身数据，再将处理后的数据发送给收集者，收集者对采集到的数据进行统计分析，既能得到有效的分析结果，也保证个体的隐私信息不被泄露。本频繁字符串挖掘技术就是通过ldp模型保护用户隐私的。
4.正常情况下，用户所拥有的字符串往往不止一个。目前，对于符合ldp的频繁字符串挖掘技术，已有包括ibsl、privtrie等算法。但受加噪方法的限制，对于用户有多个字符串的场景，这些算法往往是从每一个用户拥有的字符串中随机抽取出一个进行分析，而这种随机抽取的方式必然存在一定误差，造成准确率下降。
5.另外在现实生活中，一个用户所拥有的字符串往往会重复，且不同的字符串也可能拥有相同的前缀，而privtrie挖掘过程中每一轮挖掘又是对用户字符串的频繁前缀进行收集，因此会导致用户的数据出现重复。如果一个前缀或字符串重复得比较多，则其频数应该更多。


技术实现要素：

6.本发明的目的是针对现有的技术存在上述问题，提出了一种采用轮子机制代替优化随机应答机制作为加噪方法，使服务端在数据域中得出无偏分布，进而提升准确率的面向用户多数据场景的频繁字符串的挖掘方法。
7.本发明的目的可通过下列技术方案来实现：面向用户多数据场景的频繁字符串的挖掘方法，包括以下步骤：
8.1)、对用户进行划分：将用户根据截断比划分为两个部分，一部分用于自适应前缀树的构建，另一部分用于加强结点支持值的一致性；将第一部分用户随机划分为若干个大小相等的组，用于每一轮自适应前缀树的构建；
9.2)、初始化根节点，自顶向下构建自适应前缀树：
10.(1)用户端：
11.a、设前缀树中所有未被访问的非叶子结点的数量为d，并将这些结点从0开始进行编号；从根结点的子结点到这些结点中的每一结点所经过的路径构成一个前缀，由此上述结点所对应前缀的数量也为d；
12.b、为每一个用户建立一个空数组用于存放其数据；遍历该用户所拥有的所有字符串，若其中某字符串的前缀恰是上述d个前缀之一，则将该前缀对应结点的编号加入为该用户建立的数据数组中；
13.c、利用轮子机制的randomizer对用户的数据进行加噪，randomizer会随机抽取一个或多个样本作为输出；
14.d、用户将randomizer输出结果提交给服务端；
15.(2)服务端：
16.服务端统计在一组用户的输出中所有元素被抽取作为样本的次数；通过轮子机制的decoder根据统计数据得出对整个数据域的频数估计，即这些前缀的频数分布，以便于后续的剪枝和下一轮构建；
17.3)、若值不为
‘
&’(字符串结束符)且其对应前缀的频数估计c
′
(v)≥θ，其中则标记该结点未被访问且非叶结点，并扩展该结点；
18.4)、循环上述操作，当第一部分所有组用户均参与构建或没有需要扩展的结点之后，前缀树构建结束；将所有的值为
‘
&’的叶结点所对应的字符串加入备选集；
19.5)、将第二部分未参与前缀树构建的用户数据应用轮子机制，得到备选集中每一个字符串的频数估计：
20.(1)用户端：
21.a、设备选集中字符串的数量为d，将其中的字符串从0开始编号；
22.b、为每一个用户建立一个数据数组；遍历该用户拥有的每一个字符串，如果某字符串恰为备选集中的字符串，则将该字符串在备选集中的编号加入该用户的数据中；
23.c、将该用户数据利用轮子机制的randomizer进行加噪，randomizer会随机抽取一个或多个样本作为输出；
24.d、用户将randomizer输出结果提交给服务端；
25.(2)服务端：
26.服务端统计在这部分用户的输出中所有元素被抽取作为样本的次数；通过轮子机制的decoder根据统计数据得出对整个数据域的频数估计，即对应于备选集中每个字符串的频数分布；
27.6)、通过计算得出更为准确的备选集字符串的频数估计，根据频数估计对字符串进行排序，最终选出最频繁的前k个字符串。
28.在上述的面向用户多数据场景的频繁字符串的挖掘方法中，加噪过程借助于轮子机制的随机函数f完成，f满足ε-ldp，当且仅当对于任意两个输入值t1和t2，任意输出值t
*
满足约束pr[f(t1)＝t
*
]≤e
ε
·
pr[f(t2)＝t
*
]；
[0029]
其中，ε为隐私预算，代表隐私保护的强度，ε-ldp能保证对于加噪后的元组t
*
，数据收集者不能以高于e
ε
的概率推断出原始元组是t1还是t2；这意味着，ε越小，隐私保护程度越强。
[0030]
轮子机制将数据映射到循环轮的一个或多个点上，并且基于这些点设计一个满足ε-ldp的校准概率分布；根据得出的概率分布，从轮上取样一个数字值作为输出数据。这个机制只需要o(log2(e
ε
+1))的的通信成本，由于映射过程是通过用户特定的哈希函数完成，因此计算开销为o(m)，其中，m为每个用户拥有字符串的数量。通过设计扰动机制，服务端能够在优化误差范围内得出无偏估计。
[0031]
在上述的面向用户多数据场景的频繁字符串的挖掘方法中，在步骤2)、(1)的c中，所述randomizer的结果是一个长度为d的数组，若i被抽取为样本，则数组的第i个元素为1，反之为0。
[0032]
在上述的面向用户多数据场景的频繁字符串的挖掘方法中，在步骤4)、(1)的c中，所述randomizer的结果是一个长度为d的数组，若i被抽取为样本，则数组的第i个元素为1，反之为0。
[0033]
在上述的面向用户多数据场景的频繁字符串的挖掘方法中，在步骤4)、(2)中，对于每个字符串的估计频数c(v)，作如下计算得到最终的频数c
′
(v)：
[0034]
其中λ为用户的截断比。
[0035]
在上述的面向用户多数据场景的频繁字符串的挖掘方法中，构建对于重复数据的编码策略：
[0036]
(1)用户端：
[0037]
对于一组用户数据，根据其单个用户的数据最大重复次数进行编码，将出现多次的相同数据分别看作是不同的数据；设单个数据的最大重复次数为μ，原数据域c的大小为d，新数据域为c
′
；在c
′
中，令i，j从0开始计数，第(i
·
μ+j)个数据代表c中第i个数据第i次出现；因此，c
′
的大小为d
·
μ；对于用户的每一个数据，若第i个数据在该用户的数据中第j次出现，则将此数据由i变为(i
·
μ+j)；编码后的用户数据用轮子机制的randomizer进行处理，并将结果提交给服务端；
[0038]
(2)服务端：
[0039]
将轮子机制decoder得出的频数估计还原回针对原数据域的频数估计；设由decoder得出的频数估计为c
′
(v)，对于原数据域的i数据的频数估计c(vi)，有
[0040][0041]
由此可得原数据域的频数估计，再进行下一步操作即可。
[0042]
与现有技术相比，本面向用户多数据场景的频繁字符串的挖掘方法具有以下有益效果：
[0043]
1、在privtrie频繁字符串挖掘技术的基础上，将优化随机应答机制替换为轮子机制，并且去掉基于优化随机应答机制的一致性实施。以轮子机制为加噪方法的privtrie便可完成用户有多个字符串场景的频繁字符串挖掘，并有较高准确度。
[0044]
2、轮子机制的通信成本和计算开销均很小，且通过设计扰动机制，无论用户的数据是集值数据还是分类数据，服务端均能够在优化误差范围内得出无偏估计，适合用户拥
有多个字符串的场景。
[0045]
3、设计了对于重复数据的编码策略，该策略解决了用户所拥有的字符串发生重复的问题，该策略在构建自适应前缀树过程和估计备选集中字符串的频数过程均适用。
附图说明
[0046]
图1是本发明基于轮子机制的privtrie流程图。
[0047]
图2是本发明中前缀树构造过程中的用户端流程图。
[0048]
图3是本发明中前缀树构造过程中的服务端流程图。
[0049]
图4是本发明中估计备选集字符串频数过程用户端流程图。
[0050]
图5是本发明中估计备选集字符串频数过程服务端流程图。
[0051]
图6是本发明中单个用户的数据实施编码策略的实例表。
[0052]
图7是本发明中还原回原数据域的频数估计的实例表。
具体实施方式
[0053]
下面结合附图和具体实施例对本发明的具体实施方式做进一步说明：
[0054]
如图1所示，本发明引入轮子机制(wheel mechanism)作为加噪方法。轮子机制将数据映射到轮上的一个或多个点，然后根据这些点设计一个满足ε-ldp的校准概率分布。之后，它根据概率分布从轮上取样一个或多个数值作为输出。通过这种仔细设计的随机分布，服务端可以在数据域中得出无偏分布。由上述信息可知，对于用户拥有多个数据的场景，轮子机制依然可使服务端得到无偏估计。
[0055]
本面向用户多数据场景的频繁字符串的挖掘方法，包括以下步骤：
[0056]
1)、对用户进行划分：将用户根据截断比划分为两个部分，一部分用于自适应前缀树的构建，另一部分用于加强结点支持值的一致性；将第一部分用户随机划分为若干个大小相等的组，用于每一轮自适应前缀树的构建；
[0057]
2)、初始化根节点，自顶向下构建自适应前缀树：
[0058]
(1)用户端：
[0059]
a、设前缀树中所有未被访问的非叶子结点的数量为d，并将这些结点从0开始进行编号；从根结点的子结点到这些结点中的每一结点所经过的路径构成一个前缀，由此上述结点所对应前缀的数量也为d；
[0060]
b、为每一个用户建立一个空数组用于存放其数据；遍历该用户所拥有的所有字符串，若其中某字符串的前缀恰是上述d个前缀之一，则将该前缀对应结点的编号加入为该用户建立的数据数组中；
[0061]
c、利用轮子机制的randomizer对用户的数据进行加噪，randomizer会随机抽取一个或多个样本作为输出；randomizer的结果是一个长度为d的数组，若i被抽取为样本，则数组的第i个元素为1，反之为0。
[0062]
d、用户将randomizer输出结果提交给服务端；
[0063]
(2)服务端：
[0064]
服务端统计在一组用户的输出中所有元素被抽取作为样本的次数；通过轮子机制的decoder根据统计数据得出对整个数据域的频数估计，即这些前缀的频数分布，以便于后
续的剪枝和下一轮构建；
[0065]
3)、若值不为
‘
&’(字符串结束符)且其对应前缀的频数估计c
′
(v)≥θ，其中则标记该结点未被访问且非叶结点，并扩展这些结点；
[0066]
4)、循环上述操作，当第一部分所有组用户均参与构建或没有需要扩展的结点之后，前缀树构建结束；将所有的值为
‘
&’的叶结点所对应的字符串加入备选集；
[0067]
5)、将第二部分未参与前缀树构建的用户数据应用轮子机制，得到备选集中每一个字符串的频数估计：
[0068]
(1)用户端：
[0069]
a、设备选集中字符串的数量为d，将其中的字符串从0开始编号；
[0070]
b、为每一个用户建立一个数据数组；遍历该用户拥有的每一个字符串，如果某字符串恰为备选集中的字符串，则将该字符串在备选集中的编号加入该用户的数据中；
[0071]
c、将该用户数据利用轮子机制的randomizer进行加噪，randomizer会随机抽取一个或多个样本作为输出；randomizer的结果是一个长度为d的数组，若i被抽取为样本，则数组的第i个元素为1，反之为0。
[0072]
d、用户将randomizer输出结果提交给服务端；
[0073]
(2)服务端：
[0074]
服务端统计在这部分用户的输出中所有元素被抽取作为样本的次数；通过轮子机制的decoder根据统计数据得出对整个数据域的频数估计，即对应于备选集中每个字符串的频数分布；
[0075]
对于每个字符串的估计频数c(v)，作如下计算得出更为准确的备选集字符串的频数估计：
[0076]
其中λ为用户的截断比。
[0077]
6)、根据频数估计对字符串进行排序，最终选出最频繁的前k个字符串。
[0078]
加噪过程借助于轮子机制的随机函数f完成，f满足ε-ldp，当且仅当对于任意两个输入值t1和t2，任意输出值t
*
满足约束pr[f(t1)＝t*]≤e
ε
·
pr[f(t2)＝t
*
]；
[0079]
其中，ε为隐私预算，代表隐私保护的强度，ε-ldp能保证对于加噪后的元组t
*
，数据收集者不能以高于e
ε
的概率推断出原始元组是t1还是t2；这意味着，ε越小，隐私保护程度越强。
[0080]
轮子机制将数据映射到循环轮的一个或多个点上，并且基于这些点设计一个满足ε-ldp的校准概率分布；根据得出的概率分布，从轮上取样一个数字值作为输出数据。这个机制只需要o(log2(e
ε
+1))的通信成本，由于映射过程是通过用户特定的哈希函数完成，因此计算开销为o(m)，其中，m为每个用户拥有字符串的数量。通过设计扰动机制，服务端能够在优化误差范围内得出无偏估计。
[0081]
轮子机制针对的是分类数据或集值数据，其结果不能体现出重复数据的频数优势。故采用对于重复数据的编码策略：
[0082]
(1)用户端：
[0083]
对于一组用户数据，根据其单个用户的数据最大重复次数进行编码，将出现多次
的相同数据分别看作是不同的数据；设单个数据的最大重复次数为μ，原数据域c的大小为d，新数据域为c
′
；在c
′
中，令i，j从0开始计数，第(i
·
μ+j)个数据代表c中第i个数据第j次出现；因此，c
′
的大小为d
·
μ；对于用户的每一个数据，若第i个数据在该用户的数据中第j次出现，则将此数据由i变为(i
·
μ+j)；编码后的用户数据用轮子机制的randomizer进行处理，并将结果提交给服务端。
[0084]
如图6所示实例为，设原数据域大小d为4，最大重复次数μ为6，该用户的数据为为{1，1，2，2，2，2，3，3},用ij表示数据i的第j次出现，则编码后该用户的数据可表示为{10，11，20，21，22，23，30，31}，即可编码为{6，7，12，13，14，15，18，19}。
[0085]
(2)服务端：
[0086]
将轮子机制decoder得出的频数估计还原回针对原数据域的频数估计；设由decoder得出的频数估计为c
′
(v)，对于原数据域的i数据的频数估计c(vi)，有
[0087][0088]
由此可得原数据域的频数估计，再进行下一步操作即可。
[0089]
如图7所示实例为，将decoder得出的频数估计还原回针对原数据域的频数估计的实例。设μ＝3，d＝5，由decoder得出的频数估计为{55.8611，13.8547，5.4535，-2.94781，5.45346，22.256，22.256，39.0585
[0090]
，13.8547，13.8547，30.6573，-2.94781，-2.94781，-2.94781，-2.94781}。根据上述公式的计算，可得原数据域的频数估计为{75.1693，24.76165，75.1692，41.56419，-8.84343}。
[0091]
与现有技术相比，本面向用户多数据场景的频繁字符串的挖掘方法具有以下有益效果：
[0092]
1、在privtrie频繁字符串挖掘技术的基础上，将优化随机应答机制替换为轮子机制，并且去掉基于优化随机应答机制的一致性实施。以轮子机制为加噪方法的privtrie便可完成用户有多个字符串场景的频繁字符串挖掘，并有较高准确度。
[0093]
2、轮子机制的通信成本和计算开销均很小，且通过设计扰动机制，无论用户的数据是集值数据还是分类数据，服务端均能够在优化误差范围内得出无偏估计，适合用户拥有多个字符串的场景。
[0094]
3、设计了对于重复数据的编码策略，该策略解决了用户所拥有的字符串发生重复的问题，该策略在构建自适应前缀树过程和估计备选集中字符串的频数过程均适用。
[0095]
当然，上述说明并非是对本发明的限制，本发明也并不仅限于上述举例，本技术领域的技术人员在本发明的实质范围内所做出的变化、改型、添加或替换，也应属于本发明的保护范围。

技术特征：
1.面向用户多数据场景的频繁字符串的挖掘方法，其特征在于，包括以下步骤：1)、对用户进行划分：将用户根据截断比划分为两个部分，一部分用于自适应前缀树的构建，另一部分用于加强结点支持值的一致性；再将第一部分用户随机划分为若干个大小相等的组，用于每一轮自适应前缀树的构建；2)、初始化根节点，自顶向下构建自适应前缀树，构建前缀树的每一轮过程如下：(1)用户端：a、设前缀树中所有未被访问的非叶子结点的数量为d，并将这些结点从0开始进行编号；从根结点的子结点到这些结点中的每一结点所经过的路径构成一个前缀，由此上述结点所对应前缀的数量也为d；b、为每一个用户建立一个空数组用于存放其数据；遍历该用户所拥有的所有字符串，若其中某字符串的前缀恰是上述d个前缀之一，则将该前缀对应结点的编号加入为该用户建立的数据数组中；c、利用轮子机制的randomizer对用户的数据进行加噪，randomizer会随机抽取一个或多个样本作为输出；d、用户将randomizer输出结果提交给服务端；(2)服务端：服务端统计在一组用户的输出中所有元素被抽取作为样本的次数；通过轮子机制的decoder根据统计数据得出对整个数据域的频数估计，即这些前缀的频数分布。若值不为
‘
&’且其对应前缀的频数估计c
′
(v)≥θ，其中则标记该结点未被访问且非叶结点，并扩展这些结点；3)、循环2)中操作，当第一部分所有组用户均参与构建或没有需要扩展的结点之后，前缀树构建结束，将所有的值为
‘
&’的叶结点所对应的字符串加入备选集；4)、将第二部分未参与前缀树构建的用户数据应用轮子机制，得到备选集中每一个字符串的频数估计：(1)用户端：a、设备选集中字符串的数量为d，将其中的字符串从0开始编号；b、为每一个用户建立一个数据数组；遍历该用户拥有的每一个字符串，如果某字符串恰为备选集中的字符串，则将该字符串在备选集中的编号加入该用户的数据中；c、将该用户数据利用轮子机制的randomizer进行加噪，randomizer会随机抽取一个或多个样本作为输出；d、用户将randomizer输出结果提交给服务端；(2)服务端：服务端统计在这部分用户的输出中所有元素被抽取作为样本的次数；通过轮子机制的decoder根据统计数据得出对整个数据域的频数估计，即对应于备选集中每个字符串的频数分布；5)、对于每个字符串的估计频数c(v)，作如下计算得到最终的备选集字符串的频数估计c
′
(v)：
其中λ为用户的截断比。6)、根据频数估计对字符串进行排序，最终选出最频繁的前k个字符串。2.如权利要求1所述的面向用户多数据场景的频繁字符串的挖掘方法，其特征在于，其满足本地化差分隐私模型(local differential privacy，ldp)，该模型的加噪过程借助于随机函数f完成，f满足ε-ldp，当且仅当对于任意两个输入值t1和t2，任意输出值t
*
满足约束pr[f(t1)＝t
*
]≤e
ε
·
pr[f(t2)＝t
*
]；其中，ε为隐私预算，代表隐私保护的强度，ε-ldp能保证对于加噪后的元组t
*
，数据收集者不能以高于e
ε
的概率推断出原始元组是t1还是t2；其使用轮子机制，该机制将数据映射到循环轮的一个或多个点上，并且基于这些点设计一个满足ε-ldp的校准概率分布；根据得出的概率分布，从轮上取样一个数字值作为输出数据。3.如权利要求1所述的面向用户多数据场景的频繁字符串的挖掘方法，其特征在于，在步骤2)、(1)的c中，所述randomizer的结果是一个长度为d的数组，若i被抽取为样本，则数组的第i个元素为1，反之为0。4.如权利要求1所述的面向用户多数据场景的频繁字符串的挖掘方法，其特征在于，在步骤4)、(1)的c中，所述randomizer的结果是一个长度为d的数组，若i被抽取为样本，则数组的第i个元素为1，反之为0。5.如权利要求1所述的面向用户多数据场景的频繁字符串的挖掘方法，其特征在于，在步骤4)、(2)中，对于每个字符串的估计频数频数c(v)，作如下计算得到最终的频数c
′
(v)：其中λ为为用户的截断比。6.如权利要求1所述的面向用户多数据场景的频繁字符串的挖掘方法，其特征在于，构建对于重复数据的编码策略：(1)用户端：对于一组用户数据，根据其单个用户的数据最大重复次数进行编码，将出现多次的相同数据分别看作是不同的数据；设单个数据的最大重复次数为μ，，原数据域域c的的大小为d，新数据域为c
′
；在c
′
中，令i，j从0开始计数，第(i
·
μ+j)个数据代表c中第i个个数据第j次出现；因此，c
′
的大小为d
·
μ；对于用户的每一个数据，若第i个数据在该用户的数据中第j次出现，则将此数据由由i变为变为(i
·
μ+j)；编码后的用户数据用轮子机制的randomizer进行处理，并将结果提交给服务端；(2)服务端：将轮子机制decoder得出的频数估计还原回针对原数据域的频数估计；设由decoder得出的频数估计为c(v
′
)，对于原数据域的i数据的频数估计c(v
i
)，有由此可得原数据域的频数估计，再进行下一步操作即可。

技术总结
本发明提供一种面向用户多数据场景的频繁字符串的挖掘方法，包括：1)、对用户进行划分：将用户根据截断比划分为两个部分，一部分用于自适应前缀树的构建，另一部分用于加强结点支持值的一致性；2)、初始化根节点，自顶向下构建自适应前缀树，应用轮子机制扰动数据并估计值不为


技术研发人员：刘晓琳 王宁 石恬 石佳鹭
受保护的技术使用者：中国海洋大学
技术研发日：2021.12.07
技术公布日：2022/3/8