本发明涉及top-k高效用项集数据挖掘，具体是一种基于数据缓冲池的top-k高效用项集挖掘方法。
背景技术：
：：在零售行业中，根据商品被购买次数的多寡，向决策制定者提供制定决策的数据依据是普遍现象。在现实生活中，每个商品的成本、售价、利润、重量、风险均不相同，那么仅考虑商品在交易数据库的被购买的次数并不能反映真实的情况。高效用项集挖掘(high-utilityitemsetsmining，简称huim)算法不仅考虑到交易中商品出现的次数，还考虑到商品的单位利润(效用)，高效用项集挖掘算法的目标是在交易数据库中发现为零售商带来可观利润的项目和项集，被发掘的项集称作高效用项集。近年来，高效用项集挖掘算法的效率方面取得了一定成果，但由于实际应用中，最小阈值的设定不但影响着算法挖掘高效用项集的数量，而且影响着算法运行时的效率。最小阈值设定过高，使得挖掘出的结果集过少无法满足用户需求；设定过低，则产生大量结果集使得算法运行时间过长，占用大量的内存空间甚至内存溢出导致算法运行失败。用户为了确定合适的最小阈值，往往需要经验和反复测试，但每当数据集中数据的变更很有可能使之前设定的最小阈值失去意义。top-k高效用项集挖掘算法采用挖掘前k个效用值最大的项集的方式，将设定最小阈值的问题，转变为设定所需结果集数量的问题。top-k高效用项集挖掘算法主要分为以tko(miningtop-kutilityitemsetsinonephase)算法为代表的一阶段算法和以tku(top-kutilityitemsetsmining)算法为代表的二阶段算法。先前算法在优化挖掘高效用项集时，主要关注点在改进存储效用信息数据结构。例如tku算法通过树结构up-tree两次扫描数据库进行挖掘，而tko采用效用链表结构在算法第一次扫描数据库时，将关键信息存入效用链表，之后只需扫描效用链表上的信息，通过大量连接操作和递归效用链表，构建过程挖掘高效用项集。随着数据库中项的增长，项集的增加，存储效用信息的数据结构中数据量也随之增长，挖掘过程中所需要的信息和已不再需要的信息大量影响着执行速度和内存消耗。技术实现要素：本发明的目的是针对现有技术的不足，而提供一种基于数据缓冲池的top-k高效用项集挖掘方法。实现本发明目的的技术方案是：一种基于数据缓冲池的top-k高效用项集挖掘方法，具体包括如下步骤：(1)数据挖掘运行参数初始化：设置需要被挖掘的数据库d，指定结果集数量k和利润表ptable；(2)扫描数据库d：初次扫描事务数据库d并计算单一项的加权事务效用值，将最小阈值minutil初始化为0并创建初始化链表i*；(3)将单一项的加权事务效用值存入初始化链表i*并按加权事务效用值升序排列；(4)再次扫描数据库d，建立数据缓冲池dbp、索引链表indexlist和评估效用共现结构eucs，创建高效用项集队列；(5)调用搜索子程序search，将初始化链表i*、评估效用共现结构eucs、数据缓冲池dbp和索引链表indexlist传入子程序search；(6)输出效用最高的前k个高效用项集，完成数据挖掘。步骤(5)所述的调用搜索子程序search，包括如下步骤：(5.1)在搜索子程序search中，对于项集p的一个分支项集px，如果索引链表indexlist(px)中存储的项集px效用之和sumiutil不小于最小阈值minutil，那么将项集px加入到高效用项集队列；在项集px加入之前，判断队列长度是否大于结果集数量k值，若小于k值，直接将项集px插入队列；若队列长度大于k值，则比较项集px的效用值和高效用队列中的最小值，如果项集px的效用值小于高效用队列中的最小值，则不插入队列；如果项集px的效用值大于高效用队列中的最小值，则删除最小值的项集，插入项集px并将minutil更新为高效用项集最新的最小值；(5.2)如果项集px的索引链表indexlist(px)中的效用之和sumiutil与剩余效用之和sumrutil相加不小于最小阈值minutil，那么项集px的分支项集则可能是高效用项集；(5.3)对于项集p的另一个分支项集py，py与项集px合并使得y＞x并且twu({x,y})≥minutil，形成新的分支项集pxy继续执行；(5.4)将项集p，px，py，数据缓冲池dbp，索引链表indexlist作为参数调用数据缓冲池构建过程。步骤(5.4)所述的数据缓冲池构建过程，包括如下步骤：(5.4.1)在数据缓冲池构建过程中，设指针ppnt，pxpnt，pypnt分别为索引链表indexlist(p)，indexlist(px)，indexlist(py)的起始位置，指针指向数据缓冲池dbp中的元组；(5.4.2)如果指针pxpnt指向的元组中tids小于pypnt指向的元组中tids，那么将指针pxpnt向右移动一位；(5.4.3)如果指针pxpnt指向的元组中tids大于pypnt指向的元组中tids，那么将指针pypnt向右移动一位；(5.4.4)如果pxpnt指向的元组中tids等于pypnt指向的元组中tids，并且索引链表indexlist(p)不为空，那么ppnt的指针连续向右移动，直到ppnt移动到indexlist(p)的末位或者ppnt指向元组中的tids和pxpnt指向元组中的tids相同为止；(5.4.5)数据缓冲池dbp的末位添加一个新元组，令tids为pxpnt的tids，iutils为pxpnt的iutils加pypnt的iutils减去ppnt的iutils，rutils为pypnt的rutils；(5.4.6)pxpnt和pypnt同时右移一位；(5.4.7)当指针pxpnt没有指向索引链表indexlist(px)的末位置endpos，并且指针pypnt没有指向索引链表indexlist(py)的末位置endpos时，重复执行数据缓冲池构建过程；(5.4.8)更新索引链表indexlist(pxy)和数据缓冲池dbp，结束数据缓冲池构建过程；完成数据缓冲池构建后，若索引链表indexlist(pxy)不为空，pxy及其分支项集将被搜索进程search继续挖掘，不断递归此程序直到没有分支项集。本发明挖掘方法具有以下优点：(1)数据缓冲池统一分配和回收内存空间，当发现搜索过程不再需要项集的效用链表时，将数据缓冲池中分配给项集的临时内存空间回收，并重新分配给其他需要存储的效用链表，通过内存复用的方式降低内存消耗。(2)将项集的效用链表数据临时插入到数据缓冲池中，位置信息存储在索引链表中，通过读取位置信息可以直接访问所需要的项集，避免查找项集过程中大量比较操作，降低算法运行时间。本发明挖掘方法主要应用于零售业，电子商务等交易系统后台事务数据库中的数据挖掘。本发明方法通过数据缓冲池的方式，对效用链表的构建过程精细管理，高效的存储和检索缓冲池内的数据。对已使用的数据空间进行回收，提高内存的复用率，降低高效用项集挖掘的运行时间和内存消耗。附图说明图1为实施例中数据库缓冲池中的数据段结构示意图；图2为实施例中tkbph方法总体流程示意图；图3为实施例中搜索子程序search流程示意图；图4为实施例中数据缓冲池构建过程流程示意图；图5为实施例中tkbph方法与tko、tku方法运行时间效果对比示意图；图6为实施例中tkbph方法与tko、tku方法内存消耗效果对比示意图。具体实施方式下面结合附图和实施例，对本发明的内容作进一步的阐述，但不是对本发明的限定。实施例：一种基于数据缓冲池的top-k高效用项集挖掘方法，该方法提出数据缓冲池(databufferpool，简称dbp)结构，令i为数据库d中所有项的集合，tidd为数据库中所有事务标识符的集合，iutil为项集效用之和，rutil为项集剩余效用之和，dbp采用缓冲池的方式存储效用链表中的项集，元组的形式为这些元组称为数据段。为了快速访问存储在数据缓冲池中的信息，将数据缓冲池中的位置信息和效用信息存储在索引链表。项集x效用链表的索引链表为indexlist(x)，令startpos和endpos元素分别表示效用链表中数据段开始位置和结束位置。sumiutil元素存储项集x效用链表中iutil之和。sumrutil元素存储项集x效用链表中rutil之和。indexlist(x)存储的元组形式为(x,startpos,endpos,sumiutil,sumrutil)。如图1所示，项为g，链表中起始位置为0，末位置为1，g效用之和为8，g的剩余效用之和为29。当搜索空间中项集x的分支项集可能是一个潜在的高效用项集，通过将项集x的效用链表数据临时插入到数据缓冲池中位置从startpos到endpos的数据段。当需要查找项集x时，此方法可以直接访问数据缓冲池中startpos和endpos的位置读取相关数据。当发现搜索过程不再需要项集x的效用链表时，此方法将数据缓冲池中分配给项集x的临时内存空间回收并重新分配给其他需要存储的效用链表。参照图2-4，基于数据缓冲池的top-k高效用项集挖掘方法，具体包括如下步骤：(1)数据挖掘运行参数初始化：设置需要被挖掘的数据库d，指定结果集数量k和利润表ptable；(2)扫描数据库d：初次扫描事务数据库d并计算单一项的加权事务效用值，将最小阈值minutil初始化为0并创建初始化链表i*；(3)将单一项的加权事务效用值存入初始化链表i*并按加权事务效用值升序排列；(4)再次扫描数据库d，建立数据缓冲池dbp、索引链表indexlist和评估效用共现结构eucs，创建高效用项集队列；(5)调用搜索子程序search，将初始化链表i*、评估效用共现结构eucs、数据缓冲池dbp和索引链表indexlist传入子程序search；(5.1)在搜索子程序search中，对于项集p的一个分支项集px，如果索引链表indexlist(px)中存储的项集px效用之和sumiutil不小于最小阈值minutil，那么将项集px加入到高效用项集队列；在项集px加入之前，判断队列长度是否大于结果集数量k值，若小于k值，直接将项集px插入队列；若队列长度大于k值，则比较项集px的效用值和高效用队列中的最小值，如果项集px的效用值小于高效用队列中的最小值，则不插入队列；如果项集px的效用值大于高效用队列中的最小值，则删除最小值的项集，插入项集px并将minutil更新为高效用项集最新的最小值；(5.2)如果项集px的索引链表indexlist(px)中的效用之和sumiutil与剩余效用之和sumrutil相加不小于最小阈值minutil，那么项集px的分支项集则可能是高效用项集；(5.3)对于项集p的另一个分支项集py，py与项集px合并使得y＞x并且twu({x,y})≥minutil，形成新的分支项集pxy继续执行；(5.4)将项集p，px，py，数据缓冲池dbp，索引链表indexlist作为参数调用数据缓冲池构建过程；(5.4.1)在数据缓冲池构建过程中，设指针ppnt，pxpnt，pypnt分别为索引链表indexlist(p)，indexlist(px)，indexlist(py)的起始位置，指针指向数据缓冲池dbp中的元组；(5.4.2)如果指针pxpnt指向的元组中tids小于pypnt指向的元组中tids，那么将指针pxpnt向右移动一位；(5.4.3)如果指针pxpnt指向的元组中tids大于pypnt指向的元组中tids，那么将指针pypnt向右移动一位；(5.4.4)如果pxpnt指向的元组中tids等于pypnt指向的元组中tids，并且索引链表indexlist(p)不为空，那么ppnt的指针连续向右移动，直到ppnt移动到indexlist(p)的末位或者ppnt指向元组中的tids和pxpnt指向元组中的tids相同为止；(5.4.5)数据缓冲池dbp的末位添加一个新元组，令tids为pxpnt的tids，iutils为pxpnt的iutils加pypnt的iutils减去ppnt的iutils，rutils为pypnt的rutils；(5.4.6)pxpnt和pypnt同时右移一位；(5.4.7)当指针pxpnt没有指向索引链表indexlist(px)的末位置endpos，并且指针pypnt没有指向索引链表indexlist(py)的末位置endpos时，重复执行数据缓冲池构建过程；(5.4.8)更新索引链表indexlist(pxy)和数据缓冲池dbp，结束数据缓冲池构建过程；完成数据缓冲池构建后，若索引链表indexlist(pxy)不为空，pxy及其分支项集将被搜索进程search继续挖掘，不断递归此程序直到没有分支项集；(6)输出效用最高的前k个高效用项集，完成数据挖掘。本实施例数据挖掘方法tkbph(top-kbufferpoolhighutilityitemsetsmining，简称tkbph)，可为零售业、电商等交易系统数据仓库进行更高效的数据挖掘。通过对比，本实施例数据挖掘方法有以下优点：(1)项集挖掘运行时间短：将tko，tku算法与tkbph算法在不同数据集进行测试，运行结果如图5所示。在语义数据集t10i4d100k上，当k值等于4000时，tkbph算法仅需5.28s，而tku算法的运行时间已经高达121.47s，而tko为24.46s。在稀疏数据集retail上，tkbph算法不仅运行时间最短，而且随着k值的增长，时间效率变化非常平稳。当k值从200上升至800，tkbph算法的运行时间仅从25.76s上升至28.66s，然而tku算法已经从35.76s上升至95.88s。在稠密数据集chess和mushroom上，tkbph算法同样性能优异，对比在chess数据集上做实验的其他项集，在同等k值的情况下，仅需其他算法大约二分之一的运行时间。主要原因是单一项在链表初始化时已经插入到数据缓冲池中，当搜索子程序search挖掘分支项集时，只需把合并的项集插入到缓冲池，根据索引链表indexlist中单一项的位置信息直接访问单一项进行计算，从而避免之前算法项集合并时大量比较操作，提高算法运行时的效率。(2)挖掘过程所需内存空间小：通过将四种算法在不同数据集上运行，监测内存空间的使用量如图6。tkbph算法提出的数据缓冲池结构，将单一项的效用信息存储在数据缓冲区，将缓冲区内效用信息的位置信息存储在索引链表。挖掘新的分支项集时只需在缓冲尾部加入新的项集，当完成挖掘操作不再需要此项集时，数据缓冲池会回收此项集所占用的内存空间等待分配给其他需要的项集。数据缓冲池充当内存管理者角色，将内存中不需要的空间回收再利用，使得算法运行时内存空间的消耗大幅降低。相比其他算法，tkbph算法在实验中所需的内存仅需二分之一甚至更少。由于缓冲池结构的内存复用，在调整k值的过程中，内存消耗的波动非常平稳。在数据集t10i4d100k的实验中，tkbph算法内存从50.32mb上升至54.14mb，然而其他算法中内存消耗最小的tko算法内存消耗从286.1mb至538.38mb，内存波动最小的tku算法在551.68mb到567.76mb，内存消耗比tkbph算法多了一个数量级。当前第1页1 2 3 当前第1页1 2 3
技术特征：1.一种基于数据缓冲池的top-k高效用项集挖掘方法，其特征在于，包括如下步骤：
(1)数据挖掘运行参数初始化：设置需要被挖掘的数据库d，指定结果集数量k和利润表ptable；
(2)扫描数据库d：初次扫描事务数据库d并计算单一项的加权事务效用值，将最小阈值minutil初始化为0并创建初始化链表i*；
(3)将单一项的加权事务效用值存入初始化链表i*并按加权事务效用值升序排列；
(4)再次扫描数据库d，建立数据缓冲池dbp、索引链表indexlist和评估效用共现结构eucs，创建高效用项集队列；
(5)调用搜索子程序search，将初始化链表i*、评估效用共现结构eucs、数据缓冲池dbp和索引链表indexlist传入子程序search；
(6)输出效用最高的前k个高效用项集，完成数据挖掘。
2.根据权利要求1所述基于数据缓冲池的top-k高效用项集挖掘方法，其特征在于，
步骤(5)所述的调用搜索子程序search，包括如下步骤：
(5.1)在搜索子程序search中，对于项集p的一个分支项集px，如果索引链表indexlist(px)中存储的项集px效用之和sumiutil不小于最小阈值minutil，那么将项集px加入到高效用项集队列；
在项集px加入之前，判断队列长度是否大于结果集数量k值，若小于k值，直接将项集px插入队列；
若队列长度大于k值，则比较项集px的效用值和高效用队列中的最小值，如果项集px的效用值小于高效用队列中的最小值，则不插入队列；如果项集px的效用值大于高效用队列中的最小值，则删除最小值的项集，插入项集px并将minutil更新为高效用项集最新的最小值；
(5.2)如果项集px的索引链表indexlist(px)中的效用之和sumiutil与剩余效用之和sumrutil相加不小于最小阈值minutil，那么项集px的分支项集则可能是高效用项集；
(5.3)对于项集p的另一个分支项集py，py与项集px合并使得y＞x并且twu({x,y})≥minutil，形成新的分支项集pxy继续执行；
(5.4)将项集p，px，py，数据缓冲池dbp，索引链表indexlist作为参数调用数据缓冲池构建过程。
3.根据权利要求2所述基于数据缓冲池的top-k高效用项集挖掘方法，其特征在于，步骤(5.4)所述的数据缓冲池构建过程，包括如下步骤：
(5.4.1)在数据缓冲池构建过程中，设指针ppnt，pxpnt，pypnt分别为索引链表indexlist(p)，indexlist(px)，indexlist(py)的起始位置，指针指向数据缓冲池dbp中的元组；
(5.4.2)如果指针pxpnt指向的元组中tids小于pypnt指向的元组中tids，那么将指针pxpnt向右移动一位；
(5.4.3)如果指针pxpnt指向的元组中tids大于pypnt指向的元组中tids，那么将指针pypnt向右移动一位；
(5.4.4)如果pxpnt指向的元组中tids等于pypnt指向的元组中tids，并且索引链表indexlist(p)不为空，那么ppnt的指针连续向右移动，直到ppnt移动到indexlist(p)的末位或者ppnt指向元组中的tids和pxpnt指向元组中的tids相同为止；
(5.4.5)数据缓冲池dbp的末位添加一个新元组，令tids为pxpnt的tids，iutils为pxpnt的iutils加pypnt的iutils减去ppnt的iutils，rutils为pypnt的rutils；
(5.4.6)pxpnt和pypnt同时右移一位；
(5.4.7)当指针pxpnt没有指向索引链表indexlist(px)的末位置endpos，并且指针pypnt没有指向索引链表indexlist(py)的末位置endpos时，重复执行数据缓冲池构建过程；
(5.4.8)更新索引链表indexlist(pxy)和数据缓冲池dbp，结束数据缓冲池构建过程；
完成数据缓冲池构建后，若索引链表indexlist(pxy)不为空，pxy及其分支项集将被搜索进程search继续挖掘，不断递归此程序直到没有分支项集。
技术总结本发明公开一种基于数据缓冲池的Top‑k高效用项集挖掘方法，包括如下步骤：（1）数据挖掘运行参数初始化；（2）初次扫描事务数据库并计算单一项的加权事务效用值，将最小阈值初始化为0并创建初始化链表；（3）将单一项的加权事务效用值存入初始化链表并按加权事务效用值升序排列；（4）再次扫描数据库，创建高效用项集队列；（5）调用搜索子程序Search，将初始化链表、评估效用共现结构EUCS、数据缓冲池DBP和索引链表传入子程序Search；（6）输出效用最高的前个高效用项集，完成数据挖掘。本发明方法通过数据缓冲池的方式，对已使用的数据空间进行回收，提高内存的复用率，降低高效用项集挖掘的运行时间和内存消耗。
技术研发人员：蒋华;路昕宇;王慧娇;王鑫;韦晓虎;刘鼎立
受保护的技术使用者：桂林电子科技大学
技术研发日：2020.01.07
技术公布日：2020.06.05
