有趣项集获取方法和装置的制造方法
有趣项集获取方法和装置的制造方法
【技术领域】
[0001] 本发明涉及数据挖掘领域，特别涉及一种有趣项集获取方法和装置。
【背景技术】
[0002] 关联规则挖掘是数据挖掘技术中研究的热点之一。通过对大型事务集进行关联规 则挖掘，可以挖掘出隐藏在该大型事务集中不同项之间的关联规则，这些关联规则可以应 用于电子商务推荐、购物篮分析等多种领域。
[0003] 关联规则挖掘算法中一般使用"支持度-置信度"框架，挖掘出支持度不小于支持 度阈值的候选项集，再基于这些候选项集，挖掘出置信度不小于置信度阈值的关联规则。但 是，这种方法容易产生没有实际应用价值的"干扰性"的关联规则，具有一定的局限性。例 如，对于"茶"和"咖啡"两个项来说，通过对事务集进行挖掘后，得到关联规则"不买茶，则 不买咖啡"，该否定式的关联规则没有实际应用价值。
[0004] 为了弥补"支持度-置信度"框架的不足，引入了兴趣度，以修剪具有"干扰性"的 关联规则。该兴趣度用于在挖掘出关联规则之后，对关联规则进行评价和过滤。但是，对于 被过滤掉的项集来说，在挖掘关联规则的过程中仍然需要计算该项集的支持度和置信度， 增加了冗余的计算量，极大地降低了效率。
【发明内容】
[0005] 为了解决现有技术的问题，本发明实施例提供了一种有趣项集获取方法和装置。 所述技术方案如下：
[0006] 第一方面，提供了一种有趣项集获取方法，所述方法包括：
[0007] 扫描待分析的事务集，得到所述事务集中的每个项目，并计算每个项目的支持度， 所述事务集包括多个事务，每个事务包括至少一个项目；
[0008] 基于每个项目的支持度，得到多个候选项集；
[0009] 对于每个候选项集，计算所述候选项集的支持度和余弦相似度；
[0010] 判断所述候选项集的余弦相似度是否大于第一预设阈值，并判断所述候选项集的 支持度是否大于第二预设阈值；
[0011] 当所述候选项集的余弦相似度大于所述第一预设阈值，且所述候选项集的支持度 大于所述第二预设阈值时，将所述候选项集作为有趣项集。
[0012] 第二方面，提供了一种有趣项集获取装置，所述装置包括：
[0013] 扫描模块，用于扫描待分析的事务集，得到所述事务集中的每个项目，并计算每个 项目的支持度，所述事务集包括多个事务，每个事务包括至少一个项目；
[0014] 候选项集获取模块，用于基于每个项目的支持度，得到多个候选项集；
[0015] 计算模块，用于对于每个候选项集，计算所述候选项集的支持度和余弦相似度；
[0016] 判断模块，用于判断所述候选项集的余弦相似度是否大于第一预设阈值，并判断 所述候选项集的支持度是否大于第二预设阈值；
[0017] 有趣项集获取模块，用于当所述候选项集的余弦相似度大于所述第一预设阈值， 且所述候选项集的支持度大于所述第二预设阈值时，将所述候选项集作为有趣项集。
[0018] 本发明实施例提供的技术方案带来的有益效果是：
[0019] 本发明实施例提供的方法和装置，通过定义项集的余弦相似度，在获取有趣项集 的过程中，计算候选项集的支持度和余弦相似度，通过判断该候选项集的余弦相似度是否 大于第一预设阈值，并判断该候选项集的支持度是否大于第二预设阈值，对候选项集进行 过滤。与使用"支持度-置信度"框架挖掘出关联规则再使用兴趣度进行过滤相比，应用余 弦相似度这一客观兴趣度和支持度，能够在挖掘有趣项集的同时，对候选项集进行评价和 过滤，以修剪"干扰性"的候选项集，无需计算出所有候选项集的支持度和置信度后再进行 过滤，降低了计算量，提高了挖掘效率。
【附图说明】
[0020] 为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使 用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于 本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他 的附图。
[0021] 图1是本发明实施例提供的一种有趣项集获取方法的流程图；
[0022] 图2是本发明实施例提供的一种有趣项集获取方法的流程图；
[0023] 图3是本发明实施例提供的项集枚举树形图；
[0024] 图4是本发明实施例提供的一种有趣项集获取装置结构示意图。
【具体实施方式】
[0025] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完 整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发 明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施 例，都属于本发明保护的范围。
[0026] 图1是本发明实施例提供的一种有趣项集获取方法的流程图，参见图1，所述方法 包括：
[0027] 101、扫描待分析的事务集，得到该事务集中的每个项目，并计算每个项目的支持度。
[0028] 102、基于每个项目的支持度，得到多个候选项集。
[0029] 103、对于每个候选项集，计算该候选项集的支持度和余弦相似度。
[0030] 104、判断该候选项集的余弦相似度是否大于第一预设阈值，并判断该候选项集的 支持度是否大于第二预设阈值。
[0031] 105、当该候选项集的余弦相似度大于该第一预设阈值，且该候选项集的支持度大 于该第二预设阈值时，将该候选项集作为有趣项集。
[0032] 本发明实施例提供的方法，通过定义项集的余弦相似度，在获取有趣项集的过程中，计 算候选项集的支持度和余弦相似度，通过判断该候选项集的余弦相似度是否大于第一预设阈值， 并判断该候选项集的支持度是否大于第二预设阈值，对候选项集进行过滤。与使用"支持度-置 信度"框架挖掘出关联规则再使用兴趣度进行过滤相比，应用余弦相似度这一客观兴趣度和支持 度，能够在挖掘有趣项集的同时，对候选项集进行评价和过滤，以修剪"干扰性"的候选项集，无需 计算出所有候选项集的支持度和置信度后再进行过滤，降低了计算量，提高了挖掘效率。
[0033] 可选地，计算该候选项集的支持度和余弦相似度包括：
[0034] 获取该事务集包含的事务数目，并获取该候选项集中的每个项目在该事务集中同 时出现的次数；
[0035] 根据该事务数目以及该候选项集中每个项目在该事务集中同时出现的次数，计算 该候选项集的支持度；
[0036] 根据该候选项集的支持度以及该候选项集中每个项目的支持度，应用以下公式计 算该候选项集的余弦相似度：
[0038] 其中，X为该候选项集，XHii，i2, . . .，iK}，K为该候选项集的宽度，K彡2， k=l，2，...K，cos(X)为该候选项集的余弦相似度，supp(X)为该候选项集的支持度， supp({ik})为该候选项集中项目ik的支持度。
[0039] 可选地，基于每个项目的支持度，得到多个候选项集包括：
[0040] 将每个项目所构成的项集分别作为候选项集。
[0041] 可选地，该方法还包括：
[0042] 当该第一候选项集的余弦相似度大于该第一预设阈值，且该第一候选项集的支持 度大于该第二预设阈值时，将该第一候选项集的直接超集作为该第二候选项集，继续执行 计算该第二候选项集的支持度和余弦相似度的步骤；
[0043] 其中，在该第一候选项集的直接超集与该第一候选项集的差集中，每个项目的支 持度均大于该第一候选项集中每个项目的支持度。
[0044] 可选地，将该第一候选项集的直接超集作为该第二候选项集包括：
[0045] 从不属于该第一候选项集的项目中选取第一项目，该第一项目的支持度大于该第 一候选项集中每个项目的支持度；
[0046] 将该第一候选项集与该第一项目合并后的项集作为该第二候选项集。
[0047] 可选地，判断该候选项集的余弦相似度是否大于第一预设阈值，并判断该候选项 集的支持度是否大于第二预设阈值之后，该方法还包括：
[0048] 当该候选项集的余弦相似度不大于该第一预设阈值时，过滤该候选项集的直接超 集和该候选项集；
[0049] 当该候选项集的支持度不大于该第二预设阈值时，过滤该候选项集的超集和该候 选项集；
[0050] 其中，在该候选项集的直接超集与该候选项集的差集中，每个项目的支持度均大 于该候选项集中每个项目的支持度。
[0051] 可选地，余弦相似度具有如下的条件反单调性：
[0052] 对于任意的项集X和Y，满足.
，当 8即卩（{；[})〈8即卩（{；['})时，（30800>(308(￥);
[0053] 其中，i为项集X中的任一项，i'为项集Y与项集X的差集中的任一项，supp({i}) 为i的支持度，supp(U'})为i'的支持度，cos(X)为项集X的余弦相似度，cos(Y)为项集Y的余弦相似度。
[0054] 上述所有可选技术方案，可以采用任意结合形成本发明的可选实施例，在此不再 --赘述。
[0055] 图2是本发明实施例提供的一种有趣项集获取方法的流程图，参见图2,所述方法 包括：
[0056] 201、扫描待分析的事务集，得到该事务集中的每个项目。
[0057] 其中，该事务集包括多个事务，每个事务包括至少一个项目，则一个事务可以看作 一个项集。例如，该事务集可以根据用户选择物品的行为生成，一个用户一次可以选择多种 物品，用户的一次选择行为构成一个事务，此次用户所选择的至少一种物品即为该事务包 括的至少一个项目。
[0058] 该事务集用于挖掘隐藏在该至少一个项目中的关联规则，通过对该事务集进行分 析，可以确定每个项目的出现频率 、两个项目同时出现的频率、一个项目出现而另一个项目 不出现的频率、在一个项目出现的条件下另一个项目出现的频率等等，根据获取到的各种 频率，能够挖掘出隐藏在该至少一个项目中的关联规则。在本发明实施例中，可以选取多个 目标用户作为样本，对于每个目标用户，在该目标用户执行操作行为的过程中，统计该目标 用户本次操作行为的至少一个操作对象，该目标用户本次的操作行为构成一个事务，该至 少一个操作对象即为该事务中的至少一个项目，该事务包括该至少一个项目，则可以认为 在该事务中该至少一个项目同时出现。通过统计多个目标用户执行的操作行为，得到多个 事务，该多个事务构成该事务集。
[0059] 仍以用户选择物品的行为为例，对于每个目标用户，在目标用户选择物品完成时， 统计该目标用户本次选择的至少一个物品，构成一个事务，该事务包括该至少一个物品。通 过不断地对多个目标用户的选择物品的行为进行统计，可以得到多个事务，将该多个事务 构成该事务集，通过对该事务集进行分析，可以挖掘出隐藏在该至少一个物品中的关联规 贝U，确定具有关联关系的物品。那么，物品提供商即可将具有关联关系的物品放置在同一位 置或者相邻位置，以主动为用户推荐具有关联关系的物品，节省用户选择物品的时间。
[0060] 为了区分不同的事务，为每个事务设置一个事务标识TID，当两个事务的TID相同 时，表明两个事务相同。例如，该事务集可以如下表1所示。
[0061] 表 1
[0063] 该事务集中包括5个事务"134"、"235"、"1235"、"25"，扫描该事务集，可以确定该 事务集中的项目为" 1"、" 2 "、" 3 "、" 4 "、" 5 "。
[0064] 202、获取该事务集包含的事务数目以及每个项目在该事务集中出现的次数。
[0065] 具体地，计算该事务集中每个事务的出现次数，计算每个事务的出现次数之和，作 为该事务集包含的事务数目。对于每个项目，获取包括该项目的每个事务的出现次数，将包 括该项目的每个事务的出现次数之和作为每个项目在该事务集中出现的次数。
[0066] 参见表1，假设在该事务集中这4个事务的出现次数均为1，则该事务集包含的事 务数目为4,对于每个项目，包括该项目的每个事务标识TID以及该项目在该事务集中出现 的次数如下表2所示。
[0067]表 2
[0069] 203、将每个项目所构成的项集分别作为第一候选项集，对于每个第一候选项集， 执行步骤204。
[0070] 参见表1，5个项目"1"、"2"、"3"、"4"、"5"所构成的项集分别为{1}、{2}、{3}、 ⑷、{5}。
[0071] 204、根据该事务数目和每个项目在该事务集中出现的次数，计算支持度和余弦相 似度。
[0072] 在本发明实施例中，将每个项目所构成的项集分别作为第一候选项集，从该第一 候选项集中获取有趣项集。实际上，还可以根据该第一候选项集进行迭代，每次迭代过程 中，将当前候选项集的直接超集或者超集作为下一次迭代时的候选项集，通过迭代的方式 从当前候选项集中获取多个有趣项集。而在每次迭代过程中，需要计算当前候选项集的支 持度和余弦相似度，具体包括以下步骤（1)和（2 ):
[0073] (1)获取该事务集包含的事务数目，并获取该候选项集中的每个项目在该事务集 中同时出现的次数，根据该事务数目以及该候选项集中每个项目在该事务集中同时出现的 次数，计算该候选项集的支持度。
[0074] 本发明实施例以将每个项目所构成的项集作为第一候选项集为例，则根据该事务 数目以及每个项目在该事务集中出现的次数，计算每个项目的支持度，即为该第一候选项 集的支持度。具体地，计算每个项目在该事务集中出现的次数与该事务数目之间的商，作为 每个项目所构成的第一候选项集的支持度。参见表1和表2,每个项目的支持度如下表3所 /_J、1 o
[0075]表 3
[0077]^而对于在第一候选项集之后得到的、包括至少两个项目的候选项集来说，当任一 事务中包括该候选项集中的所有项目时，确定该候选项集中每个项目在该事务集中同时出 现一次，则对于每个事务，判断该事务是否包括该候选项集中的所有项目，如果是，将该事 务作为该候选项集对应的事务，以统计该候选项集对应的事务的出现次数之和，作为该候 选项集中每个项目在该事务集中同时出现的次数，并计算该候选项集中每个项目在该事务 集中同时出现的次数与该事务数目之间的商，作为该候选项集的支持度。
[0078] 参见表1和表3,假设基于该第一候选项集得到{1，2}、{1，3}、{1，4}、{1，5}四个 第二候选项集，则四个第二候选项集的支持度如下表4所示。
[0079] 表 4
[0081] 进一步地，本发明实施例以将该候选项集中每个项目在该事务集中同时出现的次 数与该事务数目的比例作为该候选项集的支持度为例，也即是计算该候选项集的"相对支 持度"，而实际上，还可以将该候选项集中每个项目在该事务集中同时出现的次数直接作为 该候选项集的支持度，也即是计算该候选项集的"绝对支持度"，本发明实施例对此不做限 定。
[0082] (2)根据该候选项集的支持度以及该候选项集中每个项目的支持度，计算该候选 项集的余弦相似度。
[0083] 可选地，根据该候选项集的支持度以及该候选项集中每个项目的支持度，应用以 下公式计算该候选项集的余弦相似度：
[0085] 其中，X为该候选项集，XHii，i2, . . .，iK}，K为该候选项集的宽度，K彡2， k=l，2，...K，cos(X)为该候选项集的余弦相似度，supp(X)为该候选项集的支持度， supp({ik})为该候选项集中项目ik的支持度。
[0086] 对于一个项集X=Ui，i2, . . .，ik}，X关于项ik的条件支持度为：
[0087]
，该条件支持度与条件概率的定义类似。结合该条件支持 度和该余弦相似度，可以得出：
表明项集X的余弦相似度可以 看作项集X在项集X的每个项目的条件下的支持度的几何平均值，因此，在关联规则挖掘过 程中，余弦相似度可以用于衡量项集X的"紧密程度"。
[0088]参见表3和表4,以X={{1}，⑵}为例，
[0090] 应用该余弦相似度的公式可以得出上述第一候选项集和第二候选项集的余弦相 似度，如下表5所示。
[0091]表 5
[0093] 205、判断该第一候选项集的余弦相似度是否大于第一预设阈值，并判断该第一候 选项集的支持度是否大于第二预设阈值，执行步骤206、208、209或210。
[0094] 其中，该第一预设阈值和该第二预设阈值可以预先根据该事务集的事务数目设 定，还可以在更新该事务集时对该第一预设阈值和该第二预设阈值进行调整，本发明实施 例对此不做限定。
[0095] 在本发明实施例中，当该第一候选项集的余弦相似度大于该第一预设阈值时，可 以认为该第一候选项集"紧密"，当该第一候选项集的支持度大于该第二预设阈值时，可以 认为该第一候选项集"频繁"。通过应用该第一预设阈值和该第二预设阈值，对该第一候选 项集进行过滤，可以获取到"频繁"且"紧密"的项集。在本发明实施例中，可以认为"频繁" 且"紧密"的项集的每个项目之间具有关联关系，且该关联关系具有实际的应用价值。
[0096] 206、当该第一候选项集的余弦相似度大于该第一预设阈值，且该第一候选项集的 支持度大于该第二预设阈值时，将该第一候选项集作为有趣项集。
[0097] 在本发明实施例中，以D指代该待分析的事务集，以min_cos指代该第一预设阈 值，以min_supp指代该第二预设阈值，则D中关于min_cos和min_supp的有趣模式集合被 定义为：
[0098]F(D，min_supp，min_cos) ={XGI/supp(X) ^min_supp,cos(X) >min_cos}〇
[0099] 相应的，集合F(D,min_supp，min_cos)中的元素就是有趣项集。基于有趣项集的 定义，当该第一候选项集的余弦相似度大于该第一预设阈值，且该第一候选项集的支持度 大于该第二预设阈值时，将该第一候选项集作为有趣项集。
[0100] 参见表3和表5,当该第一预设阈值为0. 7,该第二预设阈值为0. 4时，可以确定第 一候选项集{1}、12}、{3}、{5}的余弦相似度大于该0. 7且支持度大于0. 4,将第一候选项 集{1}、{2}、{3}、{5}作为有趣项集。而第一候选项集{4}的支持度小于0.4,则过滤该第 一候选项集{4}。
[0101] 207、将该第一候选项集的直接超集作为该第二候选项集，对于每个第二候选项 集，执行步骤204。
[0102] 在本发明实施例中，支持度具有如下的反单调性：对于任意的项集X和Y，满足 XgY，贝Usupp(X)彡supp(Y);其中，supp(X)为项集X的支持度，supp(Y)为项集Y的支 持度，在此不再证明。
[0103] 余弦相似度具有如下的条件反单调性：
[0104] 对于任意的项集X和Y，满足
，当 8即卩（{；[})〈8即卩（{；['})时，（30800>(308(￥);
[0105] 其中，i为项集X中的任一项，i'为项集Y与项集X的差集中的任一项，supp({i}) 为i的支持度，supp(U'})为i'的支持度，cos(X)为项集X的余弦相似度，cos(Y)为项集 Y的余弦相似度。
[0106] 以下将证明余弦相似度具有条件反单调性。
[0107] 假设项集XHii，i2, . . .，iK}，该项集X的宽度为K，K彡1，该项集的超集 Y=XU{iK+1，iK+2，…，iK+J，项集Y的宽度为K+L(L彡 0)，且VlSlSL，lSkSK,均 有 supp({ik+1})彡supp({ik})，则当L=0 时，X=Y,贝ljcos〇()=cos〇〇。当L尹 0 时，Y\X#0S 由于支持度具有反单调性，则suppQii,i2,…，iK})彡suppQii,i2,…，iK+Ij)，则
[0109]因为，
，均有supp({ik+1})彡supp({ik})，所以，supp({ik}) (1彡k彡K+L)的几何平均值一定不小于supp({ik}) (1彡k彡K)的几何平均值，即
，则
则cos(X) >cos(Y)，得证。
[0111] 由于余弦相似度具有条件反单调性，当按照支持度从小到大的顺序遍历项集时， 余弦相似度可以作为中评价度量。
[0112] 基于支持度的反单调性和余弦相似度的条件反单调性，将该第一候选项集的直接 超集作为该第二候选项集，这是由于：
[0113] 在该第一候选项集的直接超集与该第一候选项集的差集中，每个项目的支持度均 大于该第一候选项集中每个项目的支持度，则基于支持度的反单调性和余弦相似度的条件 反单调性，可以得出，该第一候选项集的支持度大于该第一候选项集的直接超集的支持度， 且该第一候选项集的余弦相似度大于该第一候选项集的直接超集的余弦相似度。由于该第 一候选项集的余弦相似度大于该第一预设阈值，且该第一候选项集的支持度大于该第二预 设阈值，则该第一候选项集的直接超集的余弦相似度可能大于该第一预设阈值，该第一候 选项集的直接超集的支持度可能大于该第二预设阈值，因此，将该第一候选项集的直接超 集作为第二候选项集，以便后续通过判断该第二候选项集的余弦相似度是否大于第一预设 阈值，并判断该第二候选项集的支持度是否大于第二预设阈值，从多个第二候选项集中获 取有趣项集。
[0114] 该步骤207具体可以包括：从不属于该第一候选项集的项目中选取第一项目，该 第一项目的支持度大于该第一候选项集中每个项目的支持度；将该第一候选项集与该第一 项目合并后的项集作为该第二候选项集。参见表3,项集{2}、{3}、{5}的支持度均大于项 集{1}的支持度，则对于第一候选项集{1}来说，项集{1，2}、{1，3}、{1，5}均为该第一候选 项集{1}的直接超集。
[0115] 优选地，按照支持度从小到大的顺序，对每个项目进行排序，对于每个项目，将该 项目与排在该项目之后的每个项目分别合并，得到多个第二候选项集，也即是，将支持度大 于该项目的支持度的每个项目分别与该项目合并，得到多个第二候选项集。
[0116] 同理地，对于包括至少两个项目的候选项集来说，获取该候选项集中支持度最大 的项目，将排在该支持度最大的项目之后的每个项目与该候选项集合并，得到该候选项集 的多个直接超集。参见表3,项集{2}的支持度大于项集{1}和{4}的支持度，则项集{1， 2,4}为项集{1，4}的直接超集。
[0117] 208、当该第一候选项集的余弦相似度不大于该第一预设阈值，且该第一候选项集 的支持度大于该第二预设阈值时，过滤该第一候选项集的直接超集和该第一候选项集。
[0118] 对于该第一候选项集来说，由于该第一候选项集的余弦相似度不大于该第一预设 阈值，则过滤该第一候选项集。
[0119] 而对于该第一候选项集的直接超集来说，基于余弦相似度的条件反单调性，当该 第一候选项集的余弦相似度不大于该第一预设阈值时，由于该第一候选项集的余弦相似度 大于该第一候选项集的直接超集的余弦相似度，则可以确定，该第一候选项集的直接超集 的余弦相似度也不大于该第一预设阈值，因此，该第一候选项集的直接超集不可能是有趣 项集，无需计算该第一候选项集的直接超集的余弦相似度，直接将该第一候选项集的直接 超集过滤即可。
[0120] 需要说明的是，由于余弦相似度的计算公式复杂，因此可以简化公式，计算该第一 候选项集的余弦相似度上界，当该第一候选项集的余弦相似度上界不大于该第一预设阈值 时，表明该第一候选项集的余弦相似度也不大于该第一预设阈值，此时可以直接过滤该第 一候选项集的直接超集和该第一候选项集。
[0121] 209、当该第一候选项集的余弦相似度大于该第一预设阈值，但该第一候选项集的 支持度不大于该第二预设阈值时，过滤该第一候选项集的超集和该第一候选项集。
[0122] 对于该第一候选项集来说，由于该第一候选项集的支持度不大于该第一预设阈 值，则过滤该第一候选项集。
[0123] 而对于该第一候选项集的超集来说，基于支持度的反单调性，当该第一候选项集 的支持度不大于该第二预设阈值时，由于该第一候选项集的支持度大于该第一候选项集的 超集的支持度，则可以确定，该第一候选项集的超集的支持度也不大于该第二预设阈值，因 此，该第一候选项集的超集不可能是有趣项集，无需计算该第一候选项集的超集的支持度， 直接将该第一候选项集的超集过滤即可。
[0124] 210、当该第一候选项集的余弦相似度不大于该第一预设阈值，且该第一候选项集 的支持度不大于该第二预设阈值时，过滤该第一候选项集的超集和该第一候选项集。
[0125]在本发明实施例中，在对该第一候选项集的余弦相似度和支持度进行判断之后， 通过执行步骤206-207、208、209和210,获取到有趣项集以及第二候选项集，对于每个第 二候选项集，继续对该第二候选项集的余弦相似度和支持度进行判断，再次通过执行步骤 206-207、208、209和210,获取到有趣项集以及第三候选项集……，直至已过滤当前候选项 集的所有超集，没有获取到新的有趣项集时结束，或者直至当前候选项集不存在超集时结 束。例如，当前候选项集为包括该事务集中的所有项目的总候选项集时，对该总候选项集的 余弦相似度和支持度进行判断，当该总候选项集的余弦相似度大于该第一预设阈值，且该 总候选项集的支持度大于该第二预设阈值时，将该总候选项集作为有趣项集，否则，过滤该 总候选项集，此时，该总候选项集不存在超集，迭代过程结束。
[0126]在获取到多个有趣项集之后，该方法还包括：基于获取到的多个有趣项集和用户 当前选择的项目进行推荐。
[0127]在本发明实施例中，可以认为有趣项集中的每个项目之间具有关联关系，则当用 户选择了一个或多个项目时，可以基于获取到的多个有趣项集，找出该一个或多个项目所 属的有趣项集，将该有趣项集中用户未选择的项目推荐给该用户。考虑到了每个用户选择 项目的需求，自动为用户推荐关联的项目，实现了个性化推荐。
[0128] 本发明实施例提供的方法，通过定义项集的余弦相似度，在获取有趣项集的过程 中，计算候选项集的支持度和余弦相似度，通过判断该候选项集的余弦相似度是否大于第 一预设阈值，并判断该候选项集的支持度是否大于第二预设阈值，对候选项集进行过滤。与 使用"支持度-置信度"框架挖掘出关联规则再使用兴趣度进行过滤相比，应用余弦相似度 这一客观兴趣度和支持度，能够在挖掘有趣项集的同时，对候选项集进行评价和过滤，以修 剪"干扰性"的候选项集，无需计算出所有候选项集的支持度和置信度后再进行过滤，降低 了计算量，提高了挖掘效率。
[0129] 进一步地，在每次迭代过程中，使用产生-测试的方法发现有趣项集，在产生候选 项集阶段，以余弦相似度表示项集的"紧密程度"，并采用宽度优先的策略遍历所有的候选 项集，基于余弦相似度的条件反单调性和已获取的候选项集，生成新的候选项集。而在测试 候选项集阶段，当该候选项集的余弦相似度不大于该第一预设阈值时，过滤该候选项集的 直接超集和该候选项集，而当该候选项集的支持度不大于该第二预设阈值时，过滤该候选 项集的超集和该候选项集。尽可能少地产生候选项集，且无需计算被过滤项集的支持度和 余弦相似度，进一步降低了计算量，提高了挖掘效率。
[0130]图3是本发明实施例提供的项集枚举树形图。假设该事务集包括5个项目"A"、 "B"、"C"、"D"、"E"，则参见图3,该方法包括：
[0131] 301、扫描待分析的事务集，得到该事务集中的每个项目1"、1"、"(："、"0"、1"，获 取该事务集包含的事务数目以及每个项目在该事务集中出现的次数。
[0132] 302、将每个项目所构成的项集{A}、{B}、{C}、{D}、{E}分别作为第一候选项集，根 据该事务数目和每个项目在该事务集中出现的次数，计算第一候选项集{A}、{B}、{C}、{D}、 {E}的支持度和余弦相似度，对于每个第一候选项集，判断该第一候选项集的余弦相似度是 否大于第一预设阈值，并判断该第一候选项集的支持度是否大于第二预设阈值。
[0133] 以supp({A})指代项集{A}的支持度，假设supp({A})〈supp({B})〈supp({C})〈sup p({D})〈supp({E})，贝U按照支持度从小至IJ大的顺序，对每个项目进行排列，得到按照顺序排 列的第一候选项集{A}、{B}、{C}、{D}、{E}。
[0134] 303、当确定第一候选项集{A}、{B}、{C}、{D}、{E}的余弦相似度均大于该第一预 设阈值，且支持度均大于该第二预设阈值时，将第一候选项集{A}、{B}、{C}、{D}、{E}作为 有趣项集，将第一候选项集{A}、{B}、{C}、{D}、{E}的直接超集作为第二候选项集。
[0135] 如图3所示，对于每个项目，将该项目与排在该项目之后的每个项目分别合并，得 到多个第二候选项集，则第一候选项集{A}的直接超集为项集{AB}、{AC}、{AD}和{AE}，第 一候选项集{B}的直接超集为项集{BC}、{BD}和{BE}，第一候选项集{C}的直接超集为项 集{CD}和{CE}，第一候选项集{D}的直接超集为项集{DE}，第一候选项集{E}不存在直接 超集。
[0136] 304、对于每个第二候选项集，计算该第二候选项集的支持度和余弦相似度，并判 断该第二候选项集的余弦相似度是否大于第一预设阈值，判断该第二候选项集的 支持度是 否大于第二预设阈值。
[0137] 305、当确定第二候选项集{AC}的余弦相似度不大于该第一预设阈值、支持度大 于该第二预设阈值，而除第二候选项集{AC}以外的其他的第二候选项集的余弦相似度均 大于该第一预设阈值、支持度均大于该第二预设阈值时，过滤第二候选项集{AC}的直接超 集{ACD}和{ACE}以及第二候选项集{AC}，将其他的第二候选项集作为有趣项集，将其他的 第二候选项集的直接超集作为第三候选项集。
[0138] 图3中以斜线阴影表示项集的余弦相似度不大于该第一预设阈值，或者支持度不 大于该第二预设阈值，以网格阴影表示项集直接被过滤，而没有计算余弦相似度和支持度。 第二候选项集{AC}的余弦相似度不大于该第一预设阈值时，表明该第二候选项集{AC}的 直接超集{ACD}和{ACE}的余弦相似度也不大于该第一预设阈值，则无需再计算项集{ACD} 和{ACE}的余弦相似度，直接过滤项集{ACD}和{ACE}即可。而项集{ABC}是第二候选项 集{AB}的直接超集，不是第二候选项集{AC}的直接超集，因此并不过滤项集{ABC}，而是将 项集{ABC}作为第三候选项集。
[0139] 306、对于每个第三候选项集，计算该第三候选项集的支持度和余弦相似度，并判 断该第三候选项集的余弦相似度是否大于第一预设阈值，判断该第三候选项集的支持度是 否大于第二预设阈值。
[0140] 由于已过滤项集认⑶}和{ACE}，因此，如图3所示，基于第二候选项集，得到了除 项集{ACD}和{ACE}以外的8个第三候选项集，对这8个第三候选项集分别进行判断。
[0141] 307、当确定第三候选项集{BCD}的余弦相似度不大于该第一预设阈值、支持度大 于该第二预设阈值，而除第三选项集{BCD}以外的其他的第三候选项集的余弦相似度均大 于该第一预设阈值、支持度均大于该第二预设阈值时，过滤第三候选项集{BCD}的直接超 集{BCDE}和第三候选项集{BCD}，将其他的第二候选项集作为有趣项集，将其他的第三候 选项集的直接超集作为第四候选项集，即{ABCD}、{ABCE}和{ABDE}。
[0142] 第三候选项集{BCD}的余弦相似度不大于该第一预设阈值时，表明该第三候选项 集{BCD}的直接超集{BCDE}的余弦相似度也不大于该第一预设阈值，则无需再计算项集 {BCDE}的余弦相似度，直接过滤项集{BCDE}即可。
[0143] 308、对于每个第四候选项集，计算该第四候选项集的支持度和余弦相似度，并判 断该第四候选项集的余弦相似度是否大于第一预设阈值，判断该第四候选项集的支持度是 否大于第二预设阈值。
[0144] 由于已过滤项集{A⑶}、{ACE}以及{B⑶E}，因此，如图3所示，基于第三候选项集， 得到了 3个第四候选项集，对这3个第四候选项集分别进行判断。
[0145] 309、当确定第四候选项集{ABCD}、{ABCE}和{ABDE}的余弦相似度均大于该第一 预设阈值，且支持度大于该第二预设阈值时，将第四候选项集{ABCD}、{ABCE}和{ABDE}作 为有趣项集，将第四候选项集{ABCD}的直接超集{ABCDE}作为第五候选项集。
[0146] 310、计算该第五候选项集{ABCDE}的支持度和余弦相似度，并判断该第五候选项 集{ABCDE}的余弦相似度是否大于第一预设阈值，判断该第五候选项集{ABCDE}的支持度 是否大于第二预设阈值。
[0147] 311、当确定该第五候选项集{AB⑶E}的余弦相似度不大于该第一预设阈值，且支 持度不大于该第二预设阈值时，过滤该第五候选项集{ABCDE}，结束。
[0148] 312、基于获取到的多个有趣项集和用户当前选择的项目进行推荐。
[0149] 例如，项集{ABCE}为有趣项集，则当用户选择了A和B两个项目时，可以为该用户 推荐项目C和项目E。而项集{ACDE}不是有趣项集，当用户选择了A、C和D三个项目时， 无需为该用户推荐项目E。
[0150] 为了实现本发明实施例提供的方法，提供伪代码如下：
[0151] "输入：
[0152] D:事务集；
[0153] min_cosmin_cos :第一预设阈值；
[0154] min_suppmin_supp :第二预设阈值。
[0155]输出：FFD, min_supp, min_coss
[0156] 1一次性扫描D并得到频繁项的集合I;
[0157] 2重新编码并对每个事务中的项按照支持度从小到大排序；
[0158]
[0159] 伪代码的第1-2行用于准备构造支持度升序项集枚举树，在第2行中按照项目的 支持度的大小进行排序(用《表示这个顺序)。第4行用于生成有趣1-项集F:F1，且Fk用于 表不下一次迭代时生成的k+1项候选项集。
[0160] 第5-26行用于描述获取所有的有趣项集的迭代过程，每次迭代包括两个阶段。其 中，第7-17行为第一个阶段，用于生成候选项集，第18-25行为第二个阶段，用于对生成的 候选项集进行测试，首先扫描一次事务集，确定候选项集的支持度和余弦相似度，并分别与 该第二预设阈值和第一预设阈值进行比较。最终在27行将所有的有趣项集合并为一个项 集返回。
[0161] 与Brute-force方法和FkXFi的方法相比，Apriori算法使用FkXFk的方法产生 k+1项的候选项集，能够在保证完整性的前提下，尽可能少地产生候选项集。但是，FkXFk的 方法并不适用于本发明实施例提供的方法，原因在于，余弦相似度仅具有条件反单调性，而 不具有反单调性。参见图3,项集{ABC}是项集{AB}的直接超集，而不是项集{AC}的直接 超集，如果使用FkXFk的方法，则可能会由于项集{AC}不是有趣项集而过滤掉项集{ABC}。
[0162] 因此，在第7-8行中提出了FkX(FkUJk)的方法，生成候选项集。在第9行中检 测了该候选项集的所有直接子集的支持度，以便在该候选项集的任一直接子集的支持度不 大于该第二预设阈值时，过滤该候选项集。然而，由于余弦相似度的剪枝作用，在上一次迭 代过程中，可能已经过滤了一个或多个该候选项集的直接子集，即无法得到该候选项集的 所有直接子集的支持度，因此，实际上可能仅检测了部分直接子集的支持度。第15行中，Jk 用来存储所有由于余弦相似度的剪枝而被过滤的项集。虽然检测了每一个候选项集的余弦 相似度，实际上，可以计算余弦相似度上界降低计算成本。
[0163] 图4是本发明实施例提供的一种有趣项集获取装置结构示意图，参见图4,该装置 包括：
[0164] 扫描模块401，用于扫描待分析的事务集，得到该事务集中的每个项目，并计算每 个项目的支持度，该事务集包括多个事务，每个事务包括至少一个项目；
[0165] 候选项集获取模块402与扫描模块401连接，用于基于每个项目的支持度，得到多 个候选项集；
[0166] 计算模块403与扫描模块401和候选项集获取模块402分别连接，用于对于每个 候选项集，计算该候选项集的支持度和余弦相似度；
[0167] 判断模块404与计算模块403连接，用于判断该候选项集的余弦相似度是否大于 第一预设阈值，并判断该候选项集的支持度是否大于第二预设阈值；
[0168] 有趣项集获取模块405与判断模块404连接，用于当该候选项集的余弦相似度大 于该第一预设阈值，且该候选项集的支持度大于该第二预设阈值时，将该候选项集作为有 趣项集。
[0169] 可选地，该计算模块403包括：
[0170] 数目获取单元，用于获取该事务集包含的事务数目，并获取该候选项集中的每个 项目在该事务集中同时出现的次数；
[0171] 支持度计算单元，用于根据该事务数目以及该候选项集中每个项目在该事务集中 同时出现的次数，计算该候选项集的支持度；
[0172] 余弦相似度计算单元，用于根据该候选项集的支持度以及该候选项集中每个项目 的支持度，应用以下公式计算该候选项集的余弦相似度：
[0174] 其中，X为该候选项集，XzUi，、，...，、}，K为该候选项集的宽度，K彡2， k=l，2，...K，cos(X)为该候选项集的余弦相似度，supp(X)为该候选项集的支持度， supp({ik})为该候选项集中项目ik的支持度。
[0175] 可选地，该候选项集获取模块402用于将每个项目所构成的项集分别作为候选项 集。
[0176] 可选地，该装置还包括：
[0177] 第二候选项集获取模块，用于当第一候选项集的余弦相似度大于该第一预设阈 值，且该第一候选项集的支持度大于该第二预设阈值时，将该第一候选项集的直接超集作 为该第二候选项集，继续执行计算该第二候选项集的支持度和余弦相似度的步骤；
[0178] 其中，在该第一候选项集的直接超集与该第一候选项集的差集中，每个项目的支 持度均大于该第一候选项集中每个项目的支持度。
[0179] 可选地，该第二候选项集获取模块用于从不属于该第一候选项集的项目中选取第 一项目，该第一项目的支持度大于该第一候选项集中每个项目的支持度；将该第一候选项 集与该第一项目合并后的项集作为该第二候选项集。
[0180] 可选地，该装置还包括：
[0181] 第一过滤模块，用于当该候选项集的余弦相似度不大于该第一预设阈值时，过滤 该候选项集的直接超集和该候选项集；
[0182] 第二过滤模块，用于当该候选项集的支持度不大于该第二预设阈值时，过滤该候 选项集的超集和该候选项集；
[0183] 其中，在该候选项集的直接超集与该候选项集的差集中，每个项目的支持度均大 于该候选项集中每个项目的支持度。
[0184] 可选地，其特征在于，余弦相似 度具有如下的条件反单调性：
[0185]对于任意的项集X和Y，满足
，当 8即卩（{；[})〈8即卩（{；['})时，（30800>(308(￥);
[0186] 其中，i为项集X中的任一项，i'为项集Y与项集X的差集中的任一项，supp({i}) 为i的支持度，supp(U'})为i'的支持度，cos(X)为项集X的余弦相似度，cos(Y)为项集 Y的余弦相似度。
[0187] 本发明实施例提供的装置，通过定义项集的余弦相似度，在获取有趣项集的过程 中，计算候选项集的支持度和余弦相似度，通过判断该候选项集的余弦相似度是否大于第 一预设阈值，并判断该候选项集的支持度是否大于第二预设阈值，对候选项集进行过滤。与 使用"支持度-置信度"框架挖掘出关联规则再使用兴趣度进行过滤相比，应用余弦相似度 这一客观兴趣度和支持度，能够在挖掘有趣项集的同时，对候选项集进行评价和过滤，以修 剪"干扰性"的候选项集，无需计算出所有候选项集的支持度和置信度后再进行过滤，降低 了计算量，提高了挖掘效率。
[0188] 需要说明的是：上述实施例提供的有趣项集获取装置在获取有趣项集时，仅以上 述各功能模块的划分进行举例说明，实际应用中，可以根据需要而将上述功能分配由不同 的功能模块完成，即将设备的内部结构划分成不同的功能模块，以完成以上描述的全部或 者部分功能。另外，上述实施例提供的有趣项集获取装置与有趣项集获取方法实施例属于 同一构思，其具体实现过程详见方法实施例，这里不再赘述。
[0189] 本领域普通技术人员可以理解实现上述实施例的全部或部分步骤可以通过硬件 来完成，也可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读 存储介质中，上述提到的存储介质可以是只读存储器，磁盘或光盘等。
[0190] 以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和 原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
【主权项】
1. 一种有趣项集获取方法，其特征在于，所述方法包括： 扫描待分析的事务集，得到所述事务集中的每个项目，并计算每个项目的支持度，所述 事务集包括多个事务，每个事务包括至少一个项目； 基于每个项目的支持度，得到多个候选项集； 对于每个候选项集，计算所述候选项集的支持度和余弦相似度； 判断所述候选项集的余弦相似度是否大于第一预设阈值，并判断所述候选项集的支持 度是否大于第二预设阈值； 当所述候选项集的余弦相似度大于所述第一预设阈值，且所述候选项集的支持度大于 所述第二预设阈值时，将所述候选项集作为有趣项集。2. 根据权利要求1所述的方法，其特征在于，计算所述候选项集的支持度和余弦相似 度包括： 获取所述事务集包含的事务数目，并获取所述候选项集中的每个项目在所述事务集中 同时出现的次数； 根据所述事务数目以及所述候选项集中每个项目在所述事务集中同时出现的次数，计 算所述候选项集的支持度； 根据所述候选项集的支持度以及所述候选项集中每个项目的支持度，应用以下公式计 算所述候选项集的余弦相似度：其中，X为所述候选项集，K为所述候选项集的宽度，K彡2， k=l, 2，... K，cos(X)为所述候选项集的余弦相似度，supp(X)为所述候选项集的支持度， Supp(UJ)为所述候选项集中项目ik的支持度。3. 根据权利要求1所述的方法，其特征在于，基于每个项目的支持度，得到多个候选项 集包括： 将每个项目所构成的项集分别作为候选项集。4. 根据权利要求1所述的方法，其特征在于，所述方法还包括： 当所述第一候选项集的余弦相似度大于所述第一预设阈值，且所述第一候选项集的支 持度大于所述第二预设阈值时，将所述第一候选项集的直接超集作为所述第二候选项集， 继续执行计算所述第二候选项集的支持度和余弦相似度的步骤； 其中，在所述第一候选项集的直接超集与所述第一候选项集的差集中，每个项目的支 持度均大于所述第一候选项集中每个项目的支持度。5. 根据权利要求4所述的方法，其特征在于，将所述第一候选项集的直接超集作为所 述第二候选项集包括： 从不属于所述第一候选项集的项目中选取第一项目，所述第一项目的支持度大于所述 第一候选项集中每个项目的支持度； 将所述第一候选项集与所述第一项目合并后的项集作为所述第二候选项集。6. 根据权利要求1所述的方法，其特征在于，判断所述候选项集的余弦相似度是否大 于第一预设阈值，并判断所述候选项集的支持度是否大于第二预设阈值之后，所述方法还 包括： 当所述候选项集的余弦相似度不大于所述第一预设阈值时，过滤所述候选项集的直接 超集和所述候选项集； 当所述候选项集的支持度不大于所述第二预设阈值时，过滤所述候选项集的超集和所 述候选项集； 其中，在所述候选项集的直接超集与所述候选项集的差集中，每个项目的支持度均大 于所述候选项集中每个项目的支持度。7. 根据权利要求1-6任一项所述的方法，其特征在于，余弦相似度具有如下的条件反 单调性： 对于任意的项集X和Y，满足Χ(Ξ Y且Y\X其0，则VieX，i'eY\X 5当 supp ({i})〈supp({i，})时，cos 〇() Scos(Y); 其中，i为项集X中的任一项，i'为项集Y与项集X的差集中的任一项，supp ({i})为 i的支持度，supp (U'})为i'的支持度，cos (X)为项集X的余弦相似度，cos (Y)为项集Y 的余弦相似度。8. -种有趣项集获取装置，其特征在于，所述装置包括： 扫描模块，用于扫描待分析的事务集，得到所述事务集中的每个项目，并计算每个项目 的支持度，所述事务集包括多个事务，每个事务包括至少一个项目； 候选项集获取模块，用于基于每个项目的支持度，得到多个候选项集； 计算模块，用于对于每个候选项集，计算所述候选项集的支持度和余弦相似度； 判断模块，用于判断所述候选项集的余弦相似度是否大于第一预设阈值，并判断所述 候选项集的支持度是否大于第二预设阈值； 有趣项集获取模块，用于当所述候选项集的余弦相似度大于所述第一预设阈值，且所 述候选项集的支持度大于所述第二预设阈值时，将所述候选项集作为有趣项集。9. 根据权利要求8所述的装置，其特征在于，所述计算模块包括： 数目获取单元，用于获取所述事务集包含的事务数目，并获取所述候选项集中的每个 项目在所述事务集中同时出现的次数； 支持度计算单元，用于根据所述事务数目以及所述候选项集中每个项目在所述事务集 中同时出现的次数，计算所述候选项集的支持度； 余弦相似度计算单元，用于根据所述候选项集的支持度以及所述候选项集中每个项目 的支持度，应用以下公式计算所述候选项集的余弦相似度：其中，X为所述候选项集，K为所述候选项集的宽度，K彡2， k=l, 2，... K，cos(X)为所述候选项集的余弦相似度，supp(X)为所述候选项集的支持度， Supp(UJ)为所述候选项集中项目ik的支持度。10. 根据权利要求8所述的装置，其特征在于，所述候选项集获取模块用于将每个项目 所构成的项集分别作为候选项集。11. 根据权利要求8所述的装置，其特征在于，所述装置还包括： 第二候选项集获取模块，用于当第一候选项集的余弦相似度大于所述第一预设阈值， 且所述第一候选项集的支持度大于所述第二预设阈值时，将所述第一候选项集的直接超集 作为所述第二候选项集，继续执行计算所述第二候选项集的支持度和余弦相似度的步骤； 其中，在所述第一候选项集的直接超集与所述第一候选项集的差集中，每个项目的支 持度均大于所述第一候选项集中每个项目的支持度。12. 根据权利要求11所述的装置，其特征在于，所述第二候选项集获取模块用于从不 属于所述第一候选项集的项目中选取第一项目，所述第一项目的支持度大于所述第一候选 项集中每个项目的支持度；将所述第一候选项集与所述第一项目合并后的项集作为所述第 二候选项集。13. 根据权利要求8所述的装置，其特征在于，所述装置还包括： 第一过滤模块，用于当所述候选项集的余弦相似度不大于所述第一预设阈值时，过滤 所述候选项集的直接超集和所述候选项集； 第二过滤模块，用于当所述候选项集的支持度不大于所述第二预设阈值时，过滤所述 候选项集的超集和所述候选项集； 其中，在所述候选项集的直接超集与所述候选项集的差集中，每个项目的支持度均大 于所述候选项集中每个项目的支持度。14. 根据权利要求8-13任一项所述的方法，其特征在于，余弦相似度具有如下的条件 反单调性： 对于任意的项集X和Y，满足XeY且Υ\χ#0 ,则Vie5C/eY\X，当 supp ({i})〈supp({i，})时，cos 〇() Scos(Y); 其中，i为项集X中的任一项，i'为项集Y与项集X的差集中的任一项，supp ({i})为 i的支持度，supp (U'})为i'的支持度，cos (X)为项集X的余弦相似度，cos (Y)为项集Y 的余弦相似度。
【专利摘要】本发明公开了一种有趣项集获取方法和装置，属于数据挖掘领域。该方法包括：扫描事务集，得到事务集中的每个项目，并计算每个项目的支持度，得到多个候选项集；对于每个候选项集，计算候选项集的支持度和余弦相似度；判断余弦相似度是否大于第一预设阈值，并判断支持度是否大于第二预设阈值；当余弦相似度大于第一预设阈值，且支持度大于第二预设阈值时，将候选项集作为有趣项集。本发明通过定义余弦相似度，在获取有趣项集时，计算候选项集的支持度和余弦相似度，并进行过滤，应用余弦相似度这一客观兴趣度，能够在挖掘有趣项集的同时，对候选项集进行评价和过滤，无需计算出所有候选项集的支持度和置信度，降低了计算量，提高了挖掘效率。
【IPC分类】G06F19/00
【公开号】CN104899408
【申请号】CN201410078745
【发明人】祝世伟, 李雪峰, 王天梅, 张巍, 涂艳
【申请人】孙宝文, 祝世伟
【公开日】2015年9月9日
【申请日】2014年3月5日
【技术领域】
[0001] 本发明涉及数据挖掘领域，特别涉及一种有趣项集获取方法和装置。
【背景技术】
[0002] 关联规则挖掘是数据挖掘技术中研究的热点之一。通过对大型事务集进行关联规 则挖掘，可以挖掘出隐藏在该大型事务集中不同项之间的关联规则，这些关联规则可以应 用于电子商务推荐、购物篮分析等多种领域。
[0003] 关联规则挖掘算法中一般使用"支持度-置信度"框架，挖掘出支持度不小于支持 度阈值的候选项集，再基于这些候选项集，挖掘出置信度不小于置信度阈值的关联规则。但 是，这种方法容易产生没有实际应用价值的"干扰性"的关联规则，具有一定的局限性。例 如，对于"茶"和"咖啡"两个项来说，通过对事务集进行挖掘后，得到关联规则"不买茶，则 不买咖啡"，该否定式的关联规则没有实际应用价值。
[0004] 为了弥补"支持度-置信度"框架的不足，引入了兴趣度，以修剪具有"干扰性"的 关联规则。该兴趣度用于在挖掘出关联规则之后，对关联规则进行评价和过滤。但是，对于 被过滤掉的项集来说，在挖掘关联规则的过程中仍然需要计算该项集的支持度和置信度， 增加了冗余的计算量，极大地降低了效率。
【发明内容】
[0005] 为了解决现有技术的问题，本发明实施例提供了一种有趣项集获取方法和装置。 所述技术方案如下：
[0006] 第一方面，提供了一种有趣项集获取方法，所述方法包括：
[0007] 扫描待分析的事务集，得到所述事务集中的每个项目，并计算每个项目的支持度， 所述事务集包括多个事务，每个事务包括至少一个项目；
[0008] 基于每个项目的支持度，得到多个候选项集；
[0009] 对于每个候选项集，计算所述候选项集的支持度和余弦相似度；
[0010] 判断所述候选项集的余弦相似度是否大于第一预设阈值，并判断所述候选项集的 支持度是否大于第二预设阈值；
[0011] 当所述候选项集的余弦相似度大于所述第一预设阈值，且所述候选项集的支持度 大于所述第二预设阈值时，将所述候选项集作为有趣项集。
[0012] 第二方面，提供了一种有趣项集获取装置，所述装置包括：
[0013] 扫描模块，用于扫描待分析的事务集，得到所述事务集中的每个项目，并计算每个 项目的支持度，所述事务集包括多个事务，每个事务包括至少一个项目；
[0014] 候选项集获取模块，用于基于每个项目的支持度，得到多个候选项集；
[0015] 计算模块，用于对于每个候选项集，计算所述候选项集的支持度和余弦相似度；
[0016] 判断模块，用于判断所述候选项集的余弦相似度是否大于第一预设阈值，并判断 所述候选项集的支持度是否大于第二预设阈值；
[0017] 有趣项集获取模块，用于当所述候选项集的余弦相似度大于所述第一预设阈值， 且所述候选项集的支持度大于所述第二预设阈值时，将所述候选项集作为有趣项集。
[0018] 本发明实施例提供的技术方案带来的有益效果是：
[0019] 本发明实施例提供的方法和装置，通过定义项集的余弦相似度，在获取有趣项集 的过程中，计算候选项集的支持度和余弦相似度，通过判断该候选项集的余弦相似度是否 大于第一预设阈值，并判断该候选项集的支持度是否大于第二预设阈值，对候选项集进行 过滤。与使用"支持度-置信度"框架挖掘出关联规则再使用兴趣度进行过滤相比，应用余 弦相似度这一客观兴趣度和支持度，能够在挖掘有趣项集的同时，对候选项集进行评价和 过滤，以修剪"干扰性"的候选项集，无需计算出所有候选项集的支持度和置信度后再进行 过滤，降低了计算量，提高了挖掘效率。
【附图说明】
[0020] 为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使 用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于 本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他 的附图。
[0021] 图1是本发明实施例提供的一种有趣项集获取方法的流程图；
[0022] 图2是本发明实施例提供的一种有趣项集获取方法的流程图；
[0023] 图3是本发明实施例提供的项集枚举树形图；
[0024] 图4是本发明实施例提供的一种有趣项集获取装置结构示意图。
【具体实施方式】
[0025] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完 整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发 明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施 例，都属于本发明保护的范围。
[0026] 图1是本发明实施例提供的一种有趣项集获取方法的流程图，参见图1，所述方法 包括：
[0027] 101、扫描待分析的事务集，得到该事务集中的每个项目，并计算每个项目的支持度。
[0028] 102、基于每个项目的支持度，得到多个候选项集。
[0029] 103、对于每个候选项集，计算该候选项集的支持度和余弦相似度。
[0030] 104、判断该候选项集的余弦相似度是否大于第一预设阈值，并判断该候选项集的 支持度是否大于第二预设阈值。
[0031] 105、当该候选项集的余弦相似度大于该第一预设阈值，且该候选项集的支持度大 于该第二预设阈值时，将该候选项集作为有趣项集。
[0032] 本发明实施例提供的方法，通过定义项集的余弦相似度，在获取有趣项集的过程中，计 算候选项集的支持度和余弦相似度，通过判断该候选项集的余弦相似度是否大于第一预设阈值， 并判断该候选项集的支持度是否大于第二预设阈值，对候选项集进行过滤。与使用"支持度-置 信度"框架挖掘出关联规则再使用兴趣度进行过滤相比，应用余弦相似度这一客观兴趣度和支持 度，能够在挖掘有趣项集的同时，对候选项集进行评价和过滤，以修剪"干扰性"的候选项集，无需 计算出所有候选项集的支持度和置信度后再进行过滤，降低了计算量，提高了挖掘效率。
[0033] 可选地，计算该候选项集的支持度和余弦相似度包括：
[0034] 获取该事务集包含的事务数目，并获取该候选项集中的每个项目在该事务集中同 时出现的次数；
[0035] 根据该事务数目以及该候选项集中每个项目在该事务集中同时出现的次数，计算 该候选项集的支持度；
[0036] 根据该候选项集的支持度以及该候选项集中每个项目的支持度，应用以下公式计 算该候选项集的余弦相似度：
[0038] 其中，X为该候选项集，XHii，i2, . . .，iK}，K为该候选项集的宽度，K彡2， k=l，2，...K，cos(X)为该候选项集的余弦相似度，supp(X)为该候选项集的支持度， supp({ik})为该候选项集中项目ik的支持度。
[0039] 可选地，基于每个项目的支持度，得到多个候选项集包括：
[0040] 将每个项目所构成的项集分别作为候选项集。
[0041] 可选地，该方法还包括：
[0042] 当该第一候选项集的余弦相似度大于该第一预设阈值，且该第一候选项集的支持 度大于该第二预设阈值时，将该第一候选项集的直接超集作为该第二候选项集，继续执行 计算该第二候选项集的支持度和余弦相似度的步骤；
[0043] 其中，在该第一候选项集的直接超集与该第一候选项集的差集中，每个项目的支 持度均大于该第一候选项集中每个项目的支持度。
[0044] 可选地，将该第一候选项集的直接超集作为该第二候选项集包括：
[0045] 从不属于该第一候选项集的项目中选取第一项目，该第一项目的支持度大于该第 一候选项集中每个项目的支持度；
[0046] 将该第一候选项集与该第一项目合并后的项集作为该第二候选项集。
[0047] 可选地，判断该候选项集的余弦相似度是否大于第一预设阈值，并判断该候选项 集的支持度是否大于第二预设阈值之后，该方法还包括：
[0048] 当该候选项集的余弦相似度不大于该第一预设阈值时，过滤该候选项集的直接超 集和该候选项集；
[0049] 当该候选项集的支持度不大于该第二预设阈值时，过滤该候选项集的超集和该候 选项集；
[0050] 其中，在该候选项集的直接超集与该候选项集的差集中，每个项目的支持度均大 于该候选项集中每个项目的支持度。
[0051] 可选地，余弦相似度具有如下的条件反单调性：
[0052] 对于任意的项集X和Y，满足.
，当 8即卩（{；[})〈8即卩（{；['})时，（30800>(308(￥);
[0053] 其中，i为项集X中的任一项，i'为项集Y与项集X的差集中的任一项，supp({i}) 为i的支持度，supp(U'})为i'的支持度，cos(X)为项集X的余弦相似度，cos(Y)为项集Y的余弦相似度。
[0054] 上述所有可选技术方案，可以采用任意结合形成本发明的可选实施例，在此不再 --赘述。
[0055] 图2是本发明实施例提供的一种有趣项集获取方法的流程图，参见图2,所述方法 包括：
[0056] 201、扫描待分析的事务集，得到该事务集中的每个项目。
[0057] 其中，该事务集包括多个事务，每个事务包括至少一个项目，则一个事务可以看作 一个项集。例如，该事务集可以根据用户选择物品的行为生成，一个用户一次可以选择多种 物品，用户的一次选择行为构成一个事务，此次用户所选择的至少一种物品即为该事务包 括的至少一个项目。
[0058] 该事务集用于挖掘隐藏在该至少一个项目中的关联规则，通过对该事务集进行分 析，可以确定每个项目的出现频率 、两个项目同时出现的频率、一个项目出现而另一个项目 不出现的频率、在一个项目出现的条件下另一个项目出现的频率等等，根据获取到的各种 频率，能够挖掘出隐藏在该至少一个项目中的关联规则。在本发明实施例中，可以选取多个 目标用户作为样本，对于每个目标用户，在该目标用户执行操作行为的过程中，统计该目标 用户本次操作行为的至少一个操作对象，该目标用户本次的操作行为构成一个事务，该至 少一个操作对象即为该事务中的至少一个项目，该事务包括该至少一个项目，则可以认为 在该事务中该至少一个项目同时出现。通过统计多个目标用户执行的操作行为，得到多个 事务，该多个事务构成该事务集。
[0059] 仍以用户选择物品的行为为例，对于每个目标用户，在目标用户选择物品完成时， 统计该目标用户本次选择的至少一个物品，构成一个事务，该事务包括该至少一个物品。通 过不断地对多个目标用户的选择物品的行为进行统计，可以得到多个事务，将该多个事务 构成该事务集，通过对该事务集进行分析，可以挖掘出隐藏在该至少一个物品中的关联规 贝U，确定具有关联关系的物品。那么，物品提供商即可将具有关联关系的物品放置在同一位 置或者相邻位置，以主动为用户推荐具有关联关系的物品，节省用户选择物品的时间。
[0060] 为了区分不同的事务，为每个事务设置一个事务标识TID，当两个事务的TID相同 时，表明两个事务相同。例如，该事务集可以如下表1所示。
[0061] 表 1
[0063] 该事务集中包括5个事务"134"、"235"、"1235"、"25"，扫描该事务集，可以确定该 事务集中的项目为" 1"、" 2 "、" 3 "、" 4 "、" 5 "。
[0064] 202、获取该事务集包含的事务数目以及每个项目在该事务集中出现的次数。
[0065] 具体地，计算该事务集中每个事务的出现次数，计算每个事务的出现次数之和，作 为该事务集包含的事务数目。对于每个项目，获取包括该项目的每个事务的出现次数，将包 括该项目的每个事务的出现次数之和作为每个项目在该事务集中出现的次数。
[0066] 参见表1，假设在该事务集中这4个事务的出现次数均为1，则该事务集包含的事 务数目为4,对于每个项目，包括该项目的每个事务标识TID以及该项目在该事务集中出现 的次数如下表2所示。
[0067]表 2
[0069] 203、将每个项目所构成的项集分别作为第一候选项集，对于每个第一候选项集， 执行步骤204。
[0070] 参见表1，5个项目"1"、"2"、"3"、"4"、"5"所构成的项集分别为{1}、{2}、{3}、 ⑷、{5}。
[0071] 204、根据该事务数目和每个项目在该事务集中出现的次数，计算支持度和余弦相 似度。
[0072] 在本发明实施例中，将每个项目所构成的项集分别作为第一候选项集，从该第一 候选项集中获取有趣项集。实际上，还可以根据该第一候选项集进行迭代，每次迭代过程 中，将当前候选项集的直接超集或者超集作为下一次迭代时的候选项集，通过迭代的方式 从当前候选项集中获取多个有趣项集。而在每次迭代过程中，需要计算当前候选项集的支 持度和余弦相似度，具体包括以下步骤（1)和（2 ):
[0073] (1)获取该事务集包含的事务数目，并获取该候选项集中的每个项目在该事务集 中同时出现的次数，根据该事务数目以及该候选项集中每个项目在该事务集中同时出现的 次数，计算该候选项集的支持度。
[0074] 本发明实施例以将每个项目所构成的项集作为第一候选项集为例，则根据该事务 数目以及每个项目在该事务集中出现的次数，计算每个项目的支持度，即为该第一候选项 集的支持度。具体地，计算每个项目在该事务集中出现的次数与该事务数目之间的商，作为 每个项目所构成的第一候选项集的支持度。参见表1和表2,每个项目的支持度如下表3所 /_J、1 o
[0075]表 3
[0077]^而对于在第一候选项集之后得到的、包括至少两个项目的候选项集来说，当任一 事务中包括该候选项集中的所有项目时，确定该候选项集中每个项目在该事务集中同时出 现一次，则对于每个事务，判断该事务是否包括该候选项集中的所有项目，如果是，将该事 务作为该候选项集对应的事务，以统计该候选项集对应的事务的出现次数之和，作为该候 选项集中每个项目在该事务集中同时出现的次数，并计算该候选项集中每个项目在该事务 集中同时出现的次数与该事务数目之间的商，作为该候选项集的支持度。
[0078] 参见表1和表3,假设基于该第一候选项集得到{1，2}、{1，3}、{1，4}、{1，5}四个 第二候选项集，则四个第二候选项集的支持度如下表4所示。
[0079] 表 4
[0081] 进一步地，本发明实施例以将该候选项集中每个项目在该事务集中同时出现的次 数与该事务数目的比例作为该候选项集的支持度为例，也即是计算该候选项集的"相对支 持度"，而实际上，还可以将该候选项集中每个项目在该事务集中同时出现的次数直接作为 该候选项集的支持度，也即是计算该候选项集的"绝对支持度"，本发明实施例对此不做限 定。
[0082] (2)根据该候选项集的支持度以及该候选项集中每个项目的支持度，计算该候选 项集的余弦相似度。
[0083] 可选地，根据该候选项集的支持度以及该候选项集中每个项目的支持度，应用以 下公式计算该候选项集的余弦相似度：
[0085] 其中，X为该候选项集，XHii，i2, . . .，iK}，K为该候选项集的宽度，K彡2， k=l，2，...K，cos(X)为该候选项集的余弦相似度，supp(X)为该候选项集的支持度， supp({ik})为该候选项集中项目ik的支持度。
[0086] 对于一个项集X=Ui，i2, . . .，ik}，X关于项ik的条件支持度为：
[0087]
，该条件支持度与条件概率的定义类似。结合该条件支持 度和该余弦相似度，可以得出：
表明项集X的余弦相似度可以 看作项集X在项集X的每个项目的条件下的支持度的几何平均值，因此，在关联规则挖掘过 程中，余弦相似度可以用于衡量项集X的"紧密程度"。
[0088]参见表3和表4,以X={{1}，⑵}为例，
[0090] 应用该余弦相似度的公式可以得出上述第一候选项集和第二候选项集的余弦相 似度，如下表5所示。
[0091]表 5
[0093] 205、判断该第一候选项集的余弦相似度是否大于第一预设阈值，并判断该第一候 选项集的支持度是否大于第二预设阈值，执行步骤206、208、209或210。
[0094] 其中，该第一预设阈值和该第二预设阈值可以预先根据该事务集的事务数目设 定，还可以在更新该事务集时对该第一预设阈值和该第二预设阈值进行调整，本发明实施 例对此不做限定。
[0095] 在本发明实施例中，当该第一候选项集的余弦相似度大于该第一预设阈值时，可 以认为该第一候选项集"紧密"，当该第一候选项集的支持度大于该第二预设阈值时，可以 认为该第一候选项集"频繁"。通过应用该第一预设阈值和该第二预设阈值，对该第一候选 项集进行过滤，可以获取到"频繁"且"紧密"的项集。在本发明实施例中，可以认为"频繁" 且"紧密"的项集的每个项目之间具有关联关系，且该关联关系具有实际的应用价值。
[0096] 206、当该第一候选项集的余弦相似度大于该第一预设阈值，且该第一候选项集的 支持度大于该第二预设阈值时，将该第一候选项集作为有趣项集。
[0097] 在本发明实施例中，以D指代该待分析的事务集，以min_cos指代该第一预设阈 值，以min_supp指代该第二预设阈值，则D中关于min_cos和min_supp的有趣模式集合被 定义为：
[0098]F(D，min_supp，min_cos) ={XGI/supp(X) ^min_supp,cos(X) >min_cos}〇
[0099] 相应的，集合F(D,min_supp，min_cos)中的元素就是有趣项集。基于有趣项集的 定义，当该第一候选项集的余弦相似度大于该第一预设阈值，且该第一候选项集的支持度 大于该第二预设阈值时，将该第一候选项集作为有趣项集。
[0100] 参见表3和表5,当该第一预设阈值为0. 7,该第二预设阈值为0. 4时，可以确定第 一候选项集{1}、12}、{3}、{5}的余弦相似度大于该0. 7且支持度大于0. 4,将第一候选项 集{1}、{2}、{3}、{5}作为有趣项集。而第一候选项集{4}的支持度小于0.4,则过滤该第 一候选项集{4}。
[0101] 207、将该第一候选项集的直接超集作为该第二候选项集，对于每个第二候选项 集，执行步骤204。
[0102] 在本发明实施例中，支持度具有如下的反单调性：对于任意的项集X和Y，满足 XgY，贝Usupp(X)彡supp(Y);其中，supp(X)为项集X的支持度，supp(Y)为项集Y的支 持度，在此不再证明。
[0103] 余弦相似度具有如下的条件反单调性：
[0104] 对于任意的项集X和Y，满足
，当 8即卩（{；[})〈8即卩（{；['})时，（30800>(308(￥);
[0105] 其中，i为项集X中的任一项，i'为项集Y与项集X的差集中的任一项，supp({i}) 为i的支持度，supp(U'})为i'的支持度，cos(X)为项集X的余弦相似度，cos(Y)为项集 Y的余弦相似度。
[0106] 以下将证明余弦相似度具有条件反单调性。
[0107] 假设项集XHii，i2, . . .，iK}，该项集X的宽度为K，K彡1，该项集的超集 Y=XU{iK+1，iK+2，…，iK+J，项集Y的宽度为K+L(L彡 0)，且VlSlSL，lSkSK,均 有 supp({ik+1})彡supp({ik})，则当L=0 时，X=Y,贝ljcos〇()=cos〇〇。当L尹 0 时，Y\X#0S 由于支持度具有反单调性，则suppQii,i2,…，iK})彡suppQii,i2,…，iK+Ij)，则
[0109]因为，
，均有supp({ik+1})彡supp({ik})，所以，supp({ik}) (1彡k彡K+L)的几何平均值一定不小于supp({ik}) (1彡k彡K)的几何平均值，即
，则
则cos(X) >cos(Y)，得证。
[0111] 由于余弦相似度具有条件反单调性，当按照支持度从小到大的顺序遍历项集时， 余弦相似度可以作为中评价度量。
[0112] 基于支持度的反单调性和余弦相似度的条件反单调性，将该第一候选项集的直接 超集作为该第二候选项集，这是由于：
[0113] 在该第一候选项集的直接超集与该第一候选项集的差集中，每个项目的支持度均 大于该第一候选项集中每个项目的支持度，则基于支持度的反单调性和余弦相似度的条件 反单调性，可以得出，该第一候选项集的支持度大于该第一候选项集的直接超集的支持度， 且该第一候选项集的余弦相似度大于该第一候选项集的直接超集的余弦相似度。由于该第 一候选项集的余弦相似度大于该第一预设阈值，且该第一候选项集的支持度大于该第二预 设阈值，则该第一候选项集的直接超集的余弦相似度可能大于该第一预设阈值，该第一候 选项集的直接超集的支持度可能大于该第二预设阈值，因此，将该第一候选项集的直接超 集作为第二候选项集，以便后续通过判断该第二候选项集的余弦相似度是否大于第一预设 阈值，并判断该第二候选项集的支持度是否大于第二预设阈值，从多个第二候选项集中获 取有趣项集。
[0114] 该步骤207具体可以包括：从不属于该第一候选项集的项目中选取第一项目，该 第一项目的支持度大于该第一候选项集中每个项目的支持度；将该第一候选项集与该第一 项目合并后的项集作为该第二候选项集。参见表3,项集{2}、{3}、{5}的支持度均大于项 集{1}的支持度，则对于第一候选项集{1}来说，项集{1，2}、{1，3}、{1，5}均为该第一候选 项集{1}的直接超集。
[0115] 优选地，按照支持度从小到大的顺序，对每个项目进行排序，对于每个项目，将该 项目与排在该项目之后的每个项目分别合并，得到多个第二候选项集，也即是，将支持度大 于该项目的支持度的每个项目分别与该项目合并，得到多个第二候选项集。
[0116] 同理地，对于包括至少两个项目的候选项集来说，获取该候选项集中支持度最大 的项目，将排在该支持度最大的项目之后的每个项目与该候选项集合并，得到该候选项集 的多个直接超集。参见表3,项集{2}的支持度大于项集{1}和{4}的支持度，则项集{1， 2,4}为项集{1，4}的直接超集。
[0117] 208、当该第一候选项集的余弦相似度不大于该第一预设阈值，且该第一候选项集 的支持度大于该第二预设阈值时，过滤该第一候选项集的直接超集和该第一候选项集。
[0118] 对于该第一候选项集来说，由于该第一候选项集的余弦相似度不大于该第一预设 阈值，则过滤该第一候选项集。
[0119] 而对于该第一候选项集的直接超集来说，基于余弦相似度的条件反单调性，当该 第一候选项集的余弦相似度不大于该第一预设阈值时，由于该第一候选项集的余弦相似度 大于该第一候选项集的直接超集的余弦相似度，则可以确定，该第一候选项集的直接超集 的余弦相似度也不大于该第一预设阈值，因此，该第一候选项集的直接超集不可能是有趣 项集，无需计算该第一候选项集的直接超集的余弦相似度，直接将该第一候选项集的直接 超集过滤即可。
[0120] 需要说明的是，由于余弦相似度的计算公式复杂，因此可以简化公式，计算该第一 候选项集的余弦相似度上界，当该第一候选项集的余弦相似度上界不大于该第一预设阈值 时，表明该第一候选项集的余弦相似度也不大于该第一预设阈值，此时可以直接过滤该第 一候选项集的直接超集和该第一候选项集。
[0121] 209、当该第一候选项集的余弦相似度大于该第一预设阈值，但该第一候选项集的 支持度不大于该第二预设阈值时，过滤该第一候选项集的超集和该第一候选项集。
[0122] 对于该第一候选项集来说，由于该第一候选项集的支持度不大于该第一预设阈 值，则过滤该第一候选项集。
[0123] 而对于该第一候选项集的超集来说，基于支持度的反单调性，当该第一候选项集 的支持度不大于该第二预设阈值时，由于该第一候选项集的支持度大于该第一候选项集的 超集的支持度，则可以确定，该第一候选项集的超集的支持度也不大于该第二预设阈值，因 此，该第一候选项集的超集不可能是有趣项集，无需计算该第一候选项集的超集的支持度， 直接将该第一候选项集的超集过滤即可。
[0124] 210、当该第一候选项集的余弦相似度不大于该第一预设阈值，且该第一候选项集 的支持度不大于该第二预设阈值时，过滤该第一候选项集的超集和该第一候选项集。
[0125]在本发明实施例中，在对该第一候选项集的余弦相似度和支持度进行判断之后， 通过执行步骤206-207、208、209和210,获取到有趣项集以及第二候选项集，对于每个第 二候选项集，继续对该第二候选项集的余弦相似度和支持度进行判断，再次通过执行步骤 206-207、208、209和210,获取到有趣项集以及第三候选项集……，直至已过滤当前候选项 集的所有超集，没有获取到新的有趣项集时结束，或者直至当前候选项集不存在超集时结 束。例如，当前候选项集为包括该事务集中的所有项目的总候选项集时，对该总候选项集的 余弦相似度和支持度进行判断，当该总候选项集的余弦相似度大于该第一预设阈值，且该 总候选项集的支持度大于该第二预设阈值时，将该总候选项集作为有趣项集，否则，过滤该 总候选项集，此时，该总候选项集不存在超集，迭代过程结束。
[0126]在获取到多个有趣项集之后，该方法还包括：基于获取到的多个有趣项集和用户 当前选择的项目进行推荐。
[0127]在本发明实施例中，可以认为有趣项集中的每个项目之间具有关联关系，则当用 户选择了一个或多个项目时，可以基于获取到的多个有趣项集，找出该一个或多个项目所 属的有趣项集，将该有趣项集中用户未选择的项目推荐给该用户。考虑到了每个用户选择 项目的需求，自动为用户推荐关联的项目，实现了个性化推荐。
[0128] 本发明实施例提供的方法，通过定义项集的余弦相似度，在获取有趣项集的过程 中，计算候选项集的支持度和余弦相似度，通过判断该候选项集的余弦相似度是否大于第 一预设阈值，并判断该候选项集的支持度是否大于第二预设阈值，对候选项集进行过滤。与 使用"支持度-置信度"框架挖掘出关联规则再使用兴趣度进行过滤相比，应用余弦相似度 这一客观兴趣度和支持度，能够在挖掘有趣项集的同时，对候选项集进行评价和过滤，以修 剪"干扰性"的候选项集，无需计算出所有候选项集的支持度和置信度后再进行过滤，降低 了计算量，提高了挖掘效率。
[0129] 进一步地，在每次迭代过程中，使用产生-测试的方法发现有趣项集，在产生候选 项集阶段，以余弦相似度表示项集的"紧密程度"，并采用宽度优先的策略遍历所有的候选 项集，基于余弦相似度的条件反单调性和已获取的候选项集，生成新的候选项集。而在测试 候选项集阶段，当该候选项集的余弦相似度不大于该第一预设阈值时，过滤该候选项集的 直接超集和该候选项集，而当该候选项集的支持度不大于该第二预设阈值时，过滤该候选 项集的超集和该候选项集。尽可能少地产生候选项集，且无需计算被过滤项集的支持度和 余弦相似度，进一步降低了计算量，提高了挖掘效率。
[0130]图3是本发明实施例提供的项集枚举树形图。假设该事务集包括5个项目"A"、 "B"、"C"、"D"、"E"，则参见图3,该方法包括：
[0131] 301、扫描待分析的事务集，得到该事务集中的每个项目1"、1"、"(："、"0"、1"，获 取该事务集包含的事务数目以及每个项目在该事务集中出现的次数。
[0132] 302、将每个项目所构成的项集{A}、{B}、{C}、{D}、{E}分别作为第一候选项集，根 据该事务数目和每个项目在该事务集中出现的次数，计算第一候选项集{A}、{B}、{C}、{D}、 {E}的支持度和余弦相似度，对于每个第一候选项集，判断该第一候选项集的余弦相似度是 否大于第一预设阈值，并判断该第一候选项集的支持度是否大于第二预设阈值。
[0133] 以supp({A})指代项集{A}的支持度，假设supp({A})〈supp({B})〈supp({C})〈sup p({D})〈supp({E})，贝U按照支持度从小至IJ大的顺序，对每个项目进行排列，得到按照顺序排 列的第一候选项集{A}、{B}、{C}、{D}、{E}。
[0134] 303、当确定第一候选项集{A}、{B}、{C}、{D}、{E}的余弦相似度均大于该第一预 设阈值，且支持度均大于该第二预设阈值时，将第一候选项集{A}、{B}、{C}、{D}、{E}作为 有趣项集，将第一候选项集{A}、{B}、{C}、{D}、{E}的直接超集作为第二候选项集。
[0135] 如图3所示，对于每个项目，将该项目与排在该项目之后的每个项目分别合并，得 到多个第二候选项集，则第一候选项集{A}的直接超集为项集{AB}、{AC}、{AD}和{AE}，第 一候选项集{B}的直接超集为项集{BC}、{BD}和{BE}，第一候选项集{C}的直接超集为项 集{CD}和{CE}，第一候选项集{D}的直接超集为项集{DE}，第一候选项集{E}不存在直接 超集。
[0136] 304、对于每个第二候选项集，计算该第二候选项集的支持度和余弦相似度，并判 断该第二候选项集的余弦相似度是否大于第一预设阈值，判断该第二候选项集的 支持度是 否大于第二预设阈值。
[0137] 305、当确定第二候选项集{AC}的余弦相似度不大于该第一预设阈值、支持度大 于该第二预设阈值，而除第二候选项集{AC}以外的其他的第二候选项集的余弦相似度均 大于该第一预设阈值、支持度均大于该第二预设阈值时，过滤第二候选项集{AC}的直接超 集{ACD}和{ACE}以及第二候选项集{AC}，将其他的第二候选项集作为有趣项集，将其他的 第二候选项集的直接超集作为第三候选项集。
[0138] 图3中以斜线阴影表示项集的余弦相似度不大于该第一预设阈值，或者支持度不 大于该第二预设阈值，以网格阴影表示项集直接被过滤，而没有计算余弦相似度和支持度。 第二候选项集{AC}的余弦相似度不大于该第一预设阈值时，表明该第二候选项集{AC}的 直接超集{ACD}和{ACE}的余弦相似度也不大于该第一预设阈值，则无需再计算项集{ACD} 和{ACE}的余弦相似度，直接过滤项集{ACD}和{ACE}即可。而项集{ABC}是第二候选项 集{AB}的直接超集，不是第二候选项集{AC}的直接超集，因此并不过滤项集{ABC}，而是将 项集{ABC}作为第三候选项集。
[0139] 306、对于每个第三候选项集，计算该第三候选项集的支持度和余弦相似度，并判 断该第三候选项集的余弦相似度是否大于第一预设阈值，判断该第三候选项集的支持度是 否大于第二预设阈值。
[0140] 由于已过滤项集认⑶}和{ACE}，因此，如图3所示，基于第二候选项集，得到了除 项集{ACD}和{ACE}以外的8个第三候选项集，对这8个第三候选项集分别进行判断。
[0141] 307、当确定第三候选项集{BCD}的余弦相似度不大于该第一预设阈值、支持度大 于该第二预设阈值，而除第三选项集{BCD}以外的其他的第三候选项集的余弦相似度均大 于该第一预设阈值、支持度均大于该第二预设阈值时，过滤第三候选项集{BCD}的直接超 集{BCDE}和第三候选项集{BCD}，将其他的第二候选项集作为有趣项集，将其他的第三候 选项集的直接超集作为第四候选项集，即{ABCD}、{ABCE}和{ABDE}。
[0142] 第三候选项集{BCD}的余弦相似度不大于该第一预设阈值时，表明该第三候选项 集{BCD}的直接超集{BCDE}的余弦相似度也不大于该第一预设阈值，则无需再计算项集 {BCDE}的余弦相似度，直接过滤项集{BCDE}即可。
[0143] 308、对于每个第四候选项集，计算该第四候选项集的支持度和余弦相似度，并判 断该第四候选项集的余弦相似度是否大于第一预设阈值，判断该第四候选项集的支持度是 否大于第二预设阈值。
[0144] 由于已过滤项集{A⑶}、{ACE}以及{B⑶E}，因此，如图3所示，基于第三候选项集， 得到了 3个第四候选项集，对这3个第四候选项集分别进行判断。
[0145] 309、当确定第四候选项集{ABCD}、{ABCE}和{ABDE}的余弦相似度均大于该第一 预设阈值，且支持度大于该第二预设阈值时，将第四候选项集{ABCD}、{ABCE}和{ABDE}作 为有趣项集，将第四候选项集{ABCD}的直接超集{ABCDE}作为第五候选项集。
[0146] 310、计算该第五候选项集{ABCDE}的支持度和余弦相似度，并判断该第五候选项 集{ABCDE}的余弦相似度是否大于第一预设阈值，判断该第五候选项集{ABCDE}的支持度 是否大于第二预设阈值。
[0147] 311、当确定该第五候选项集{AB⑶E}的余弦相似度不大于该第一预设阈值，且支 持度不大于该第二预设阈值时，过滤该第五候选项集{ABCDE}，结束。
[0148] 312、基于获取到的多个有趣项集和用户当前选择的项目进行推荐。
[0149] 例如，项集{ABCE}为有趣项集，则当用户选择了A和B两个项目时，可以为该用户 推荐项目C和项目E。而项集{ACDE}不是有趣项集，当用户选择了A、C和D三个项目时， 无需为该用户推荐项目E。
[0150] 为了实现本发明实施例提供的方法，提供伪代码如下：
[0151] "输入：
[0152] D:事务集；
[0153] min_cosmin_cos :第一预设阈值；
[0154] min_suppmin_supp :第二预设阈值。
[0155]输出：FFD, min_supp, min_coss
[0156] 1一次性扫描D并得到频繁项的集合I;
[0157] 2重新编码并对每个事务中的项按照支持度从小到大排序；
[0158]
[0159] 伪代码的第1-2行用于准备构造支持度升序项集枚举树，在第2行中按照项目的 支持度的大小进行排序(用《表示这个顺序)。第4行用于生成有趣1-项集F:F1，且Fk用于 表不下一次迭代时生成的k+1项候选项集。
[0160] 第5-26行用于描述获取所有的有趣项集的迭代过程，每次迭代包括两个阶段。其 中，第7-17行为第一个阶段，用于生成候选项集，第18-25行为第二个阶段，用于对生成的 候选项集进行测试，首先扫描一次事务集，确定候选项集的支持度和余弦相似度，并分别与 该第二预设阈值和第一预设阈值进行比较。最终在27行将所有的有趣项集合并为一个项 集返回。
[0161] 与Brute-force方法和FkXFi的方法相比，Apriori算法使用FkXFk的方法产生 k+1项的候选项集，能够在保证完整性的前提下，尽可能少地产生候选项集。但是，FkXFk的 方法并不适用于本发明实施例提供的方法，原因在于，余弦相似度仅具有条件反单调性，而 不具有反单调性。参见图3,项集{ABC}是项集{AB}的直接超集，而不是项集{AC}的直接 超集，如果使用FkXFk的方法，则可能会由于项集{AC}不是有趣项集而过滤掉项集{ABC}。
[0162] 因此，在第7-8行中提出了FkX(FkUJk)的方法，生成候选项集。在第9行中检 测了该候选项集的所有直接子集的支持度，以便在该候选项集的任一直接子集的支持度不 大于该第二预设阈值时，过滤该候选项集。然而，由于余弦相似度的剪枝作用，在上一次迭 代过程中，可能已经过滤了一个或多个该候选项集的直接子集，即无法得到该候选项集的 所有直接子集的支持度，因此，实际上可能仅检测了部分直接子集的支持度。第15行中，Jk 用来存储所有由于余弦相似度的剪枝而被过滤的项集。虽然检测了每一个候选项集的余弦 相似度，实际上，可以计算余弦相似度上界降低计算成本。
[0163] 图4是本发明实施例提供的一种有趣项集获取装置结构示意图，参见图4,该装置 包括：
[0164] 扫描模块401，用于扫描待分析的事务集，得到该事务集中的每个项目，并计算每 个项目的支持度，该事务集包括多个事务，每个事务包括至少一个项目；
[0165] 候选项集获取模块402与扫描模块401连接，用于基于每个项目的支持度，得到多 个候选项集；
[0166] 计算模块403与扫描模块401和候选项集获取模块402分别连接，用于对于每个 候选项集，计算该候选项集的支持度和余弦相似度；
[0167] 判断模块404与计算模块403连接，用于判断该候选项集的余弦相似度是否大于 第一预设阈值，并判断该候选项集的支持度是否大于第二预设阈值；
[0168] 有趣项集获取模块405与判断模块404连接，用于当该候选项集的余弦相似度大 于该第一预设阈值，且该候选项集的支持度大于该第二预设阈值时，将该候选项集作为有 趣项集。
[0169] 可选地，该计算模块403包括：
[0170] 数目获取单元，用于获取该事务集包含的事务数目，并获取该候选项集中的每个 项目在该事务集中同时出现的次数；
[0171] 支持度计算单元，用于根据该事务数目以及该候选项集中每个项目在该事务集中 同时出现的次数，计算该候选项集的支持度；
[0172] 余弦相似度计算单元，用于根据该候选项集的支持度以及该候选项集中每个项目 的支持度，应用以下公式计算该候选项集的余弦相似度：
[0174] 其中，X为该候选项集，XzUi，、，...，、}，K为该候选项集的宽度，K彡2， k=l，2，...K，cos(X)为该候选项集的余弦相似度，supp(X)为该候选项集的支持度， supp({ik})为该候选项集中项目ik的支持度。
[0175] 可选地，该候选项集获取模块402用于将每个项目所构成的项集分别作为候选项 集。
[0176] 可选地，该装置还包括：
[0177] 第二候选项集获取模块，用于当第一候选项集的余弦相似度大于该第一预设阈 值，且该第一候选项集的支持度大于该第二预设阈值时，将该第一候选项集的直接超集作 为该第二候选项集，继续执行计算该第二候选项集的支持度和余弦相似度的步骤；
[0178] 其中，在该第一候选项集的直接超集与该第一候选项集的差集中，每个项目的支 持度均大于该第一候选项集中每个项目的支持度。
[0179] 可选地，该第二候选项集获取模块用于从不属于该第一候选项集的项目中选取第 一项目，该第一项目的支持度大于该第一候选项集中每个项目的支持度；将该第一候选项 集与该第一项目合并后的项集作为该第二候选项集。
[0180] 可选地，该装置还包括：
[0181] 第一过滤模块，用于当该候选项集的余弦相似度不大于该第一预设阈值时，过滤 该候选项集的直接超集和该候选项集；
[0182] 第二过滤模块，用于当该候选项集的支持度不大于该第二预设阈值时，过滤该候 选项集的超集和该候选项集；
[0183] 其中，在该候选项集的直接超集与该候选项集的差集中，每个项目的支持度均大 于该候选项集中每个项目的支持度。
[0184] 可选地，其特征在于，余弦相似 度具有如下的条件反单调性：
[0185]对于任意的项集X和Y，满足
，当 8即卩（{；[})〈8即卩（{；['})时，（30800>(308(￥);
[0186] 其中，i为项集X中的任一项，i'为项集Y与项集X的差集中的任一项，supp({i}) 为i的支持度，supp(U'})为i'的支持度，cos(X)为项集X的余弦相似度，cos(Y)为项集 Y的余弦相似度。
[0187] 本发明实施例提供的装置，通过定义项集的余弦相似度，在获取有趣项集的过程 中，计算候选项集的支持度和余弦相似度，通过判断该候选项集的余弦相似度是否大于第 一预设阈值，并判断该候选项集的支持度是否大于第二预设阈值，对候选项集进行过滤。与 使用"支持度-置信度"框架挖掘出关联规则再使用兴趣度进行过滤相比，应用余弦相似度 这一客观兴趣度和支持度，能够在挖掘有趣项集的同时，对候选项集进行评价和过滤，以修 剪"干扰性"的候选项集，无需计算出所有候选项集的支持度和置信度后再进行过滤，降低 了计算量，提高了挖掘效率。
[0188] 需要说明的是：上述实施例提供的有趣项集获取装置在获取有趣项集时，仅以上 述各功能模块的划分进行举例说明，实际应用中，可以根据需要而将上述功能分配由不同 的功能模块完成，即将设备的内部结构划分成不同的功能模块，以完成以上描述的全部或 者部分功能。另外，上述实施例提供的有趣项集获取装置与有趣项集获取方法实施例属于 同一构思，其具体实现过程详见方法实施例，这里不再赘述。
[0189] 本领域普通技术人员可以理解实现上述实施例的全部或部分步骤可以通过硬件 来完成，也可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读 存储介质中，上述提到的存储介质可以是只读存储器，磁盘或光盘等。
[0190] 以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和 原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
【主权项】
1. 一种有趣项集获取方法，其特征在于，所述方法包括： 扫描待分析的事务集，得到所述事务集中的每个项目，并计算每个项目的支持度，所述 事务集包括多个事务，每个事务包括至少一个项目； 基于每个项目的支持度，得到多个候选项集； 对于每个候选项集，计算所述候选项集的支持度和余弦相似度； 判断所述候选项集的余弦相似度是否大于第一预设阈值，并判断所述候选项集的支持 度是否大于第二预设阈值； 当所述候选项集的余弦相似度大于所述第一预设阈值，且所述候选项集的支持度大于 所述第二预设阈值时，将所述候选项集作为有趣项集。2. 根据权利要求1所述的方法，其特征在于，计算所述候选项集的支持度和余弦相似 度包括： 获取所述事务集包含的事务数目，并获取所述候选项集中的每个项目在所述事务集中 同时出现的次数； 根据所述事务数目以及所述候选项集中每个项目在所述事务集中同时出现的次数，计 算所述候选项集的支持度； 根据所述候选项集的支持度以及所述候选项集中每个项目的支持度，应用以下公式计 算所述候选项集的余弦相似度：其中，X为所述候选项集，K为所述候选项集的宽度，K彡2， k=l, 2，... K，cos(X)为所述候选项集的余弦相似度，supp(X)为所述候选项集的支持度， Supp(UJ)为所述候选项集中项目ik的支持度。3. 根据权利要求1所述的方法，其特征在于，基于每个项目的支持度，得到多个候选项 集包括： 将每个项目所构成的项集分别作为候选项集。4. 根据权利要求1所述的方法，其特征在于，所述方法还包括： 当所述第一候选项集的余弦相似度大于所述第一预设阈值，且所述第一候选项集的支 持度大于所述第二预设阈值时，将所述第一候选项集的直接超集作为所述第二候选项集， 继续执行计算所述第二候选项集的支持度和余弦相似度的步骤； 其中，在所述第一候选项集的直接超集与所述第一候选项集的差集中，每个项目的支 持度均大于所述第一候选项集中每个项目的支持度。5. 根据权利要求4所述的方法，其特征在于，将所述第一候选项集的直接超集作为所 述第二候选项集包括： 从不属于所述第一候选项集的项目中选取第一项目，所述第一项目的支持度大于所述 第一候选项集中每个项目的支持度； 将所述第一候选项集与所述第一项目合并后的项集作为所述第二候选项集。6. 根据权利要求1所述的方法，其特征在于，判断所述候选项集的余弦相似度是否大 于第一预设阈值，并判断所述候选项集的支持度是否大于第二预设阈值之后，所述方法还 包括： 当所述候选项集的余弦相似度不大于所述第一预设阈值时，过滤所述候选项集的直接 超集和所述候选项集； 当所述候选项集的支持度不大于所述第二预设阈值时，过滤所述候选项集的超集和所 述候选项集； 其中，在所述候选项集的直接超集与所述候选项集的差集中，每个项目的支持度均大 于所述候选项集中每个项目的支持度。7. 根据权利要求1-6任一项所述的方法，其特征在于，余弦相似度具有如下的条件反 单调性： 对于任意的项集X和Y，满足Χ(Ξ Y且Y\X其0，则VieX，i'eY\X 5当 supp ({i})〈supp({i，})时，cos 〇() Scos(Y); 其中，i为项集X中的任一项，i'为项集Y与项集X的差集中的任一项，supp ({i})为 i的支持度，supp (U'})为i'的支持度，cos (X)为项集X的余弦相似度，cos (Y)为项集Y 的余弦相似度。8. -种有趣项集获取装置，其特征在于，所述装置包括： 扫描模块，用于扫描待分析的事务集，得到所述事务集中的每个项目，并计算每个项目 的支持度，所述事务集包括多个事务，每个事务包括至少一个项目； 候选项集获取模块，用于基于每个项目的支持度，得到多个候选项集； 计算模块，用于对于每个候选项集，计算所述候选项集的支持度和余弦相似度； 判断模块，用于判断所述候选项集的余弦相似度是否大于第一预设阈值，并判断所述 候选项集的支持度是否大于第二预设阈值； 有趣项集获取模块，用于当所述候选项集的余弦相似度大于所述第一预设阈值，且所 述候选项集的支持度大于所述第二预设阈值时，将所述候选项集作为有趣项集。9. 根据权利要求8所述的装置，其特征在于，所述计算模块包括： 数目获取单元，用于获取所述事务集包含的事务数目，并获取所述候选项集中的每个 项目在所述事务集中同时出现的次数； 支持度计算单元，用于根据所述事务数目以及所述候选项集中每个项目在所述事务集 中同时出现的次数，计算所述候选项集的支持度； 余弦相似度计算单元，用于根据所述候选项集的支持度以及所述候选项集中每个项目 的支持度，应用以下公式计算所述候选项集的余弦相似度：其中，X为所述候选项集，K为所述候选项集的宽度，K彡2， k=l, 2，... K，cos(X)为所述候选项集的余弦相似度，supp(X)为所述候选项集的支持度， Supp(UJ)为所述候选项集中项目ik的支持度。10. 根据权利要求8所述的装置，其特征在于，所述候选项集获取模块用于将每个项目 所构成的项集分别作为候选项集。11. 根据权利要求8所述的装置，其特征在于，所述装置还包括： 第二候选项集获取模块，用于当第一候选项集的余弦相似度大于所述第一预设阈值， 且所述第一候选项集的支持度大于所述第二预设阈值时，将所述第一候选项集的直接超集 作为所述第二候选项集，继续执行计算所述第二候选项集的支持度和余弦相似度的步骤； 其中，在所述第一候选项集的直接超集与所述第一候选项集的差集中，每个项目的支 持度均大于所述第一候选项集中每个项目的支持度。12. 根据权利要求11所述的装置，其特征在于，所述第二候选项集获取模块用于从不 属于所述第一候选项集的项目中选取第一项目，所述第一项目的支持度大于所述第一候选 项集中每个项目的支持度；将所述第一候选项集与所述第一项目合并后的项集作为所述第 二候选项集。13. 根据权利要求8所述的装置，其特征在于，所述装置还包括： 第一过滤模块，用于当所述候选项集的余弦相似度不大于所述第一预设阈值时，过滤 所述候选项集的直接超集和所述候选项集； 第二过滤模块，用于当所述候选项集的支持度不大于所述第二预设阈值时，过滤所述 候选项集的超集和所述候选项集； 其中，在所述候选项集的直接超集与所述候选项集的差集中，每个项目的支持度均大 于所述候选项集中每个项目的支持度。14. 根据权利要求8-13任一项所述的方法，其特征在于，余弦相似度具有如下的条件 反单调性： 对于任意的项集X和Y，满足XeY且Υ\χ#0 ,则Vie5C/eY\X，当 supp ({i})〈supp({i，})时，cos 〇() Scos(Y); 其中，i为项集X中的任一项，i'为项集Y与项集X的差集中的任一项，supp ({i})为 i的支持度，supp (U'})为i'的支持度，cos (X)为项集X的余弦相似度，cos (Y)为项集Y 的余弦相似度。
【专利摘要】本发明公开了一种有趣项集获取方法和装置，属于数据挖掘领域。该方法包括：扫描事务集，得到事务集中的每个项目，并计算每个项目的支持度，得到多个候选项集；对于每个候选项集，计算候选项集的支持度和余弦相似度；判断余弦相似度是否大于第一预设阈值，并判断支持度是否大于第二预设阈值；当余弦相似度大于第一预设阈值，且支持度大于第二预设阈值时，将候选项集作为有趣项集。本发明通过定义余弦相似度，在获取有趣项集时，计算候选项集的支持度和余弦相似度，并进行过滤，应用余弦相似度这一客观兴趣度，能够在挖掘有趣项集的同时，对候选项集进行评价和过滤，无需计算出所有候选项集的支持度和置信度，降低了计算量，提高了挖掘效率。
【IPC分类】G06F19/00
【公开号】CN104899408
【申请号】CN201410078745
【发明人】祝世伟, 李雪峰, 王天梅, 张巍, 涂艳
【申请人】孙宝文, 祝世伟
【公开日】2015年9月9日
【申请日】2014年3月5日
最新回复(0)