二分搜索算法在全局频繁项目集求解中的应用

曾俊义

（惠州城市职业学院民生学院，惠州516025）

0 引言

目前主流的全局频繁项目集求解方法主要包括，基于快速挖掘的全局频繁项目集求解方法，以及基于Apriori 算法的全局频繁项目集求解方法两种，但由于两种算法的全局项目求解侧重点不同，导致在全局频繁项目求解中，存在求解准确率与求解速率较低的不足[1]，为此提出了二分搜索算法在全局频繁项目集求解中的应用。依托全局频繁项目集的确定，利用频繁项目k 和全局隶属度函数x 的计算，实现了候选项目集的生成，优化了全局频繁项目集求解体系；根据数据的动态求解，实现了全局频繁项目集的更新计算，完成了二分搜索算法在全局频繁项目集求解中的应用，为保证提出的求解方法的有效性，进行仿真实验，实验数据表明，提出的全局频繁项目集求解方法具有较高的有效性。

1 优化求解的体系

与传统全局频繁项目集求解方法不同，利用二分搜索算法通过优化求解体系，利用全局频繁项目集的更新计算，实现频繁项目集的求解，在优化求解体系过程中，利用二分搜索算法，首先确定全局频繁项目集对象，然后根据频繁项目集的确定，生成候选项目集，对候选项目集进行计算，优化传统全局频繁项目集求解逐条过程，针对候选项集进行分析，通过全局频繁项目集的更新计算，实现频繁项目集的求解。

1.1 确定全局频繁项目集

设数据库项目D1，D2，D3，…，Dn属于同一类别项目，那么根据同一项目建立一个数据集和D，D={D1，D2，D3，…，Dn}，D 又称作项目集[2]。在数据库调取项目集的过程中，例如D1、D3、D5被多次重复调去，那么在项目集D 的范围内，构建一个P 的集合，P∈D，P={D1，D3，D5}，那么由D1、D3、D5组成的集合P 称作为频繁项目集，又因为数据库中包含多个D 类集合，同时包含频繁项目集P，多个频繁项目集的集合，称作为全局频繁项目集[3]。

确定全局频繁项目集，首先要确定某个项目的数据集合D，再通过项目集合D 确定频繁项目D1，D3，D5，…，Dn，构建该项目的频繁项目集，是通过往复的构建，将所有的频繁项目集进行组合，构成了全局频繁项目集。确定过程是通过全局规则库，利用全局控制模块、规则管理模块对数据库信息进行筛选，基于网络，在用户端逐渐显示局部频繁集项目，局部频繁项目集的显示是根据局部规则库、局部数据库或其他数据库接口，依托关联规则挖掘模块、数据库管理模块、局部控制模块进行显示，利用外部设备人机交互功能显示在工作人员面前，其全局频繁项目集的确定过程，如图1 所示[4]。

图1 全局频繁项目集确定过程示意图

1.2 候选项目集的生成

候选项目集的生成是依托全局频繁项目集的确定，根据二分搜索算法，对确定的全局频繁项目集进行二分搜索计算，确定频繁项目k，以及全局隶属度函数x，生成候选项目集。

频繁项目k 是根据单个集合D 扫描数据库，进行迭代计算，通过全局站点分析，其得出的频繁项目k 可用公式（1）表示[5]：

式中，PD 代表项目集成系数，是形容项目集成度的系数，项目集成度越高则PD 值越大；a 代表数据库集合相关指数，若该数据库中，存在大量相似数据集合，那么次数据集合占整个数据库的比例，即为数据库相关指数；R 代表计算求解数据量，单位GB；IL 代表数据离散程度，H 代表数据极限。

根据公式（1）确定了频繁项目k，依托k 值得确定，对全局隶属度函x 进行求解，其全局隶属度函x 可用公式（2）表示[6]：

式中，UL 代表当前数据状态；P 代表数据库类型。依托频繁项目k，全局隶属度函数x 的确定，完成了候选项目集的生成，基于全局频繁项目集的确定，优化了全局频繁项目求解体系。

2 全局频繁项目集的更新计算

二分搜索算法是一种基于数学计算的系统数据求解方法，在进行全局频繁项目集的计算中，优化传统，求解体系，针对静态数据、动态数据能够实现实时更新计算，对于数据进行自动获取，自我识别，生成候选项目集，进行求解。

在更新计算过程中，与传统计算不同首先要确定全局频繁项目的计算节点，根据动态节点，利用计算机模拟计算技术，对节点的运动进行模拟计算，并用真实值与模拟值做差，将差值控制在0.04%以内，则说明模拟计算值接近于真实值[7]。可用于动态数据节点的计算，应用于全局频繁，项目集的更新计算中。设动态节点方程可用公式（3）表示[8]：

基于动态节点方程的确定，以及平均更新计算表达式σ的求解，实现了全局频繁项目集的更新计算，基于二分搜索算法优化求解体系，实现了二分搜索算法在全局频繁项目集求解中的应用。

3 实例分析

为了保证提出的二分搜索算法的全局频繁项目集求解方法有准确性，以及速率，进行实例分析，分析过程中，采用快速挖掘的全局频繁项目集求解方法、Apriori 算法的全局频繁项目集求解方法作为实验对比对象，进行全局频繁项目集求解验证。

3.1 实验准备

实验中利用已过往的全局频繁项目作为实验对象，进行仿真实验，采用已过往的全局频繁项目作为实验对象，是因为在相同环境下进行求解可以精准地对比出求解的准确率以及求解速率，选取5 个已过往的全局频繁项目，对全局频繁项目进行全局频繁项目集求解的准确率以及求解速率进行验证。

由于全局频繁项目存在偶然性，以及相似性，为此选择5 个已过往的全局频繁项目，对全局频繁项目集求解的准确率以及求解速率进行分析验证。

3.2 实验过程

由于本次实验采用的是，根据不同全局频繁项目集求解，对已过往的全局频繁项目进行求解，用参数对比方法的验证准确率以及求解速率，为此需构建过去实验环境，让快速挖掘的全局频繁项目集求解方法、Apriori 算法的全局频繁项目集求解方法、二分搜索算法的全局频繁项目集求解方法，不接触原有求解数据结果的同时进行求解数据分析。结论与事实进行对比，分析其求解准确率以及求解速率。

实验过程中，首先建立还原实验场景，采用相同环境下相同时间节点对全局频繁项目集求解，例如在编号1 的全局频繁项目集中，载入需要进行实验的快速挖掘的全局频繁项目集求解方法，对全局频繁项目集求解，再利用其他两种全局频繁项目集求解方法对该项目进行求解，当三种方法求解完成后，记录求解值以及求解速率。以此类推，进行五组试验，当五组试验全部求解完成，并于该全局频繁项目集真实结果进行对比，并进行求解准确率记录。用以设定的标准的时间值和试验中全局频繁项目集求解时间进行对比，并记录相应求解速率。将所有记录的数值，形成实验结果图表进行对比参考。

3.3 实验结果分析

根据时间过程，得出快速挖掘的全局频繁项目集求解方法、Apriori 算法的全局频繁项目集求解方法、二分搜索算法的全局频繁项目集求解方法，在不同时间段的态势预测情况，根据记录的数据，形成全局频繁项目集求解准确率试验结果，如表1 所示。

表1 实验结果对比表

同理，形成全局频繁项目集求解速率，如表2所示。

表2 实验结果对比表

根据实验结果可以得出，在求解准确率和求解速率方面，二分搜索算法的全局频繁项目集求解方法，具有较高的准确率以及速率，但从整体上看，快速挖掘的全局频繁项目集求解方法，求解的速率相对比较快，但随着全局频繁项目集求解越多，准确率有所下降，失误点较多。Apriori 算法的全局频繁项目集求解方法，具有较高的准确率，但整体求解速率，略低于提出的二分搜索算法的全局频繁项目集求解方法。

通过实验数据的统计计算得出，二分搜索算法的全局频繁项目集求解方法准确率为61.56%，快速挖掘的全局频繁项目集求解方法准确率为55.96%，Apriori算法的全局频繁项目集求解方法准确率为45.17%。提出的二分搜索算法的全局频繁项目集求解方法，较快速挖掘的全局频繁项目集求解方法和Apriori 算法的全局频繁项目集求解方法具有更高的准确率。

4 结语

本文提出了二分搜索算法在全局频繁项目集求解中的应用。依托全局频繁项目集的确定，候选项目集的生成，优化了全局频繁项目集求解体系；根据全局频繁项目集的更新计算，完成了二分搜索算法在全局频繁项目集求解中的应用，实验数据表明，提出的全局频繁项目集求解方法具有较高的有效性，希望本文的研究能够为全局频繁项目集求解方法提供理论支撑。