本发明涉及一种基于改进遗传算法的模式数据挖掘方法，属于数据挖掘技术领域。
背景技术：
频繁项集挖掘(frequentitemsetsmining，fim)，一直都是数据挖掘领域中的重要研究方向，它指的是从数据库中挖掘出其出现频率不低于用户指定阈值的项集的过程。虽然fim能挖掘出事务数据库中那些频繁出现的项集，但是并没有考虑项集的效用值。而在挖掘项集的过程中，往往需要考虑效用值较高的项集(简称高效用项集，high-utilityitemsets，huis)。高效用项集(模式)挖掘的目的就是挖掘出事务数据库中，效用值不小于指定最小效用值的所有项集。
高效用项集挖掘(high-utilityitemsetmining,huim)问题是一个典型的组合优化问题，演化计算(evolutionarycomputation,ec)是一种有效的随机优化方法，它从自然进化过程中得到启发，利用自然进化原理寻找最优解，并应用于各种组合优化问题中。为了探索huim问题中的巨大搜索空间，基于ec的方法如遗传算法(ga)、粒子群优化(pso)、蚁群优化(aco)和和人工蜂群算法被引入用来解决这一问题。
然而，基于ec的高效用项集挖掘算法在挖掘满足最小效用阈值的所有高效用项集(huis)时通常耗费严重来。出现这个问题的原因可概括为两个方面。一方面的原因在于，高效用项集挖掘不同与传统的最优化问题，所有满足最小效用阈值的项集都应该被发现，而原始的演化计算方法总是沿着上一代最佳个体的方向搜索，这可能会在迭代过程中遗漏一些结果。另一方面的原因在于，基于ec的高效用项集挖掘算法在搜索新的huis时效率较低。
技术实现要素：
为了解决现有技术中的至少一个技术问题，本发明采用改进的遗传算法用来高效地挖掘huis，提供一种基于改进遗传算法的模式数据挖掘方法huim-iga。本发明方法提高了发现huis的效率，缩短了挖掘所有huis的总耗时。
本发明的模式数据挖掘方法，所述方法基于遗传算法(ga)进行改进，包括：
将原始数据库表示成位图的形式；
初始化种群；
对种群进行个体修复处理；
得到huis集合。
在一种实施方式中，所述数据库是任意一种可以记录交易、新闻等事务的数据库。所述数据库通常记录有至少一条事务，每条事务中包括至少一个数据项。
可选地，所述数据库为购物篮数据库。在购物篮数据中，商品的数据项对应商品的名称，一条关于交易记录的事务中可以包括若干个商品的数据项。
在一种实施方式中，所述初始化种群，包括：根据每个1-htwuis(高事务加权效用1项集，high-transaction-weightedutilization1-itemsets)的twu值(数据集中的事务加权效用值)来初始化每个个体。
所述初始化种群，具体是：每个初始个体先全部赋值为0，然后随机生成整数k作为该个体中不为0位置的个数；根据每个1-htwuis的twu值并利用轮盘赌选择算子决定哪些项将会出现在当前个体中；将生成的新的个体加入到(初始)种群中；最后返回完成初始化的种群。
在一种实施方式中，所述对种群进行个体修复处理，包括：基于1-htwuis的twu值大小进行顺序修剪；尽可能保存了个体中可能会产生效用值的项的组合。
所述个体修复处理，具体是：先判断待修复的个体是否全为0，如果待修复的个体全为0，则直接跳出该算法，否则，进入个体修复阶段；
所述个体修复阶段，包括：初始化中间变量temp为位图中twu值最大的1-htwui对应的那一列；按照twu值从大到小的顺序将temp与位图中的htwui对应的列进行与运算得到temp’，如果temp’全由0组成，则从当前个体中删除对应的项，否则，继续执行当前操作，直到待修复个体的所有位都被检查完为止。
所述个体修复处理后，计算每个个体x的适应度值f(x)(在遗传算法中，适应度是描述个体性能的主要指标，根据适应度的大小，达到评估个体优劣的目的，从而对个体进行优胜劣汰。在这里适应度值就是该个体所代表的项集的效用值，即f(x)＝utility(x))，如果适应度值不小于最小效用值(minuti)，则将x添加到huis集合。
在一种实施方式中，所述模式数据挖掘方法，还包括：
对种群中的重复huis进行邻域探索处理。
在一种实施方式中，所述对种群中的重复huis进行邻域探索处理，包括：针对基因操作之后所产生的新个体，不直接进行适应度评估，而是先检查该个体是否包含在huis集合中，如果是，则对其执行邻域变异，产生一个该hui附近的新解，来探索其邻域空间内的解，然后再对其进行适应度评估，否则，直接进行适应度评估。
所述邻域探索处理，具体是：假设当前执行完变异操作的个体是一个hui(二进制编码形式)，使用presence_indexs存放该hui中为1位置对应的下标(step1),absence_indexs存放该hui中为0位置的下标(step2)，先从presence_indexs集合中随机选择一个值m(step3)，然后再从absence_indexs集合中随机选择一个值n(step4)；最后将hui中第m个位置设置为0(step5)，hui中第n个位置设置为1(step6)。
在一种实施方式中，所述方法还包括：
进行种群多样性维持处理。
所述进行种群多样性维持处理，包括：在每一次进化过程中，都从huis集合中选择两个连续存放的hui来替换当前种群中的两个随机选择的个体。
进行精英处理。
所述进行精英处理，包括：将上一代种群pt与当代种群pt+1合并，并删除合并种群中的重复个体，然后按照utility值从大到小排序，并选择utility较大的个体构成下一代种群q。
在一种实施方式中，所述模式数据挖掘方法，基于遗传算法(ga)进行改进，包括：
首先，计算每个项对应的twu值，然后找出所有的1-htwuis，并根据twu值的大小对1-htwui进行排序，每个个体的长度由1-htwuis的个数决定(step1-4)。根据各项的twu值并利用轮盘赌选择法随机初始化种群(step6)。在进化阶段，对种群中的每个个体按照1-htwuis的twu值由大到小的顺序进行修复，如果修复后的个体属于huis集合，则探索其邻域范围内的解，然后判断是否为hui，如果是，则将其加入到huis集合(step8-18)。然后，运用种群多样性维护策略，避免由于算法陷入局部最优而导致的huis丢失(step19-27)。随后对当前种群执行选择和交叉操作(step28-29)。同步骤8-17一样，对当前种群执行修复策略(step30-38)。然后对当前种群执行变异操作(step39)。随后精英策略被执行，保留效用值较大的个体(step40-41)。最后，将挖掘出的所有二进制编码形式的hui进行解码，并返回(step43-44)。
本发明还提供一种向用户推荐产品的方法，所述方法包括利用本发明的数据挖掘方法挖掘高效用项集，根据高效用项集中挖掘的信息向用户推荐产品。
本发明还提供一种商品包装方法，所述方法包括利用本发明的数据挖掘方法挖掘购物篮数据中的高效用项集，将某一高效用项集中的若干个商品打包包装。
本发明还提供一种项集挖掘装置，所述项集挖掘装置包括：
第一计算模块，用于计算每项的twu值(事务加权效用值)；
第二计算模块，用于计算个体(即项集)的效用值；
个体修复模块，用于对1-htwuis的twu值大小进行顺序修剪，尽可能保存了个体中可能会产生效用值的项的组合；
高效用项集确定模块，用于当所述个体对应的项集的效用值≥最小效用值时，将所述项集确定为高效用项集hui。
在一种实施方式中，项集挖掘装置还包括：
邻域探索模块，用于当修复后的个体属于huis集合时，将所述个体进行邻域变异生成新的个体。
种群多样性维持模块，用于在每一次进化过程中，从huis集合中选择两个连续存放的hui来替换当前种群中的两个随机选择的个体。
种群选择和交叉模块，用于对种群执行选择和交叉。
精英模块，用于将上一代种群pt与当代种群pt+1合并，并删除合并种群中的重复个体，然后按照utility值从大到小排序，并选择效用值较大的个体构成下一代种群q。
在一种实施方式中，项集挖掘装置还包括：解码模块，用于将挖掘出的所有二进制编码形式的hui进行解码。
本发明还提供一张数据处理设备，包含本发明的项集挖掘装置。
本发明的有益效果：
(1)本发明的方法，种群初始化后，包括使用如下一种以上处理：个体修复处理，邻域探索处理，种群多样性维持处理和精英处理，来挖掘huis。
本发明的方法，在种群初始化阶段，为了更有效地挖掘huis，数据集被表示成位图的形式，并根据每个1-htwuis(高事务加权效用1项集，high-transaction-weightedutilization1-itemsets)的twu值(数据集中的事务加权效用值)来初始化个体；
进一步地，本发明方法，通过采用的基于1-htwuis的事务加权效用排序(twu)的个体修复处理，一方面可以保证修复后的个体是数据集中有效的组合方式，另一方面，避免了修复策略对优秀个体的破坏。
进一步地，本发明方法，可以通过采用的针对重复huis的邻域探索处理，通过合理利用这些重复的huis，来达到提高求解效率的目的。具体的，这些重复的huis将被其邻域搜索空间内的其他解替代，提高了算法在最优解区域的局部搜索能力，加快了算法对新huis的搜索速度和效率。
进一步地，本发明方法，还可以通过采用的新的种群多样性维持处理，有效地扩展高质量解的搜索空间，避免了由于算法过早陷入局部最优而导致的huis的遗漏问题，减少了算法在搜索过程中的huis缺失；
进一步地，本发明方法，还可以通过采用的精英处理，防止高质量项集的流失。
附图说明
图1一条染色体的编码示例；
图2针对重复huis的邻域探索处理示意图；
图3种群多样性维持处理方法示意图；
图4精英处理方法示意图；
图5邻域变异示意图；
图6多样性维持处理对收敛速度的影响的示意图；
图7精英处理对收敛速度的影响的示意图；
图8算法的收敛速度比较(chess)；
图9算法的收敛速度比较(mushroom)；
图10算法的收敛速度比较(accident_10％)；
图11算法的收敛速度比较(connect)。
具体实施方式
1、遗传算法(ga)
遗传算法是受自然选择过程启发而产生的一种元启发式优化方法。遗传算法被广泛应用于各种np难题的求解。在遗传算法中，一定数量的个体构成种群，每个个体代表了一个潜在的解决方案。遗传算法从具有潜在解的初始种群开始，然后在染色体上执行三种遗传操作(交叉、突变和选择)，来产生下一代种群。重复执行遗传算子，直到满足停止条件，然后输出最优解。遗传算法的主要进化算子如下：
(1)选择算子：选择算子用于选择种群中的合适的个体。根据预定义的规则，越优秀的个体更有可能被选中并生存下来，越差的个体被选中进入下一代的可能性就越小。
(2)交叉算子：通过选择算子选择的两个个体可以重组其基因，并通过交换部分基因形成新的个体。后代个体从两个个体(父母)那里都继承了一些特征。
(3)变异算子：变异算子在一定概率下使个体的一个或多个基因发生变化，使后代个体产生不同于父母的基因。变异算子有助于保持种群的多样性，增加实现全局优化的可能性。
2、高效用项集(huim)
huim的目的是从数据集中探索出效用值不小于用户指定阈值的项的组合，这些被探索出来的项集可以帮助诸如商场决策者或者管理人员制定合理有效的销售策略。作为fim问题的延伸，huim问题同时考虑了项的数量和权重。其形式化定义和数学模型最早由yao等人给出。liu等人在two-phase算法中首次提出了twu模型，并利用事务加权向下封闭属性(transaction-weighteddownwardclosure，twdc)，达到对搜索空间减枝的目的。two-phase算法存在在第二阶段会生成大量的候选项集的问题。为了解决这个问题，li等人提出了降低候选项集的iids策略，来减少two-phase算法中候选项集的数量。ahmed等人提出的ihup算法不需要对数据集进行多次扫描。随后，tseng等人对ihup算法进行了改进，提出了up-tree结构，up-growth和up-growth+用于发现huis。liu等人提出了hui-miners算法，将原数据库转化为列表结构，避免了候选集的产生和对数据集的重复扫描，提高了挖掘效率。
不同于传统的huim算法，基于ec的huim算法也被用来挖掘huis。kannimuthua等人首次基于遗传算法提出了hupeumu-garm算法，该算法对变异算子进行了改进，采用了基于排名的变异算子，算法会随着进化的进行来适应性的调整突变概率。lin等人基于离散pso(thediscretepso)算法，提出了huim-bpsosig算法，在该算法中粒子的长度由高事务加权效用1项集(high-transaction-weightedutilization1-itemsets，1-htwuis)的个数决定，这可以有效地减小搜索空间，提高求解效率。lin等人设计了一种or/nor-tree结构用来产生合理的项集，并提出了huim-bpso算法，减少了无效组合的产生，进一步提高了挖掘性能。最近，song等人提出了包含bio-huif-ga，bio-huif-pso等算法的huim框架，来尽可能多的挖掘huis。
3、准备工作和问题陈述
(1)准备工作
假设集合i＝{i1,i2,…,iv}由事务数据集d＝{t1,t2,…,tn}中v个互不相同的项的组成，n＝|d|是d中的总交易数量。事务数据库d中，每笔交易事务tq∈d(1≤q≤n)是集合i的子集，并由若干个项组成。并且使用唯一的标志tid来标记。交易事务tq中的每个项都有一个购买数量(内部效用)，记作q(ij,tq)(1≤j≤v,1≤q≤n)，集合i中每个项都有一个外部效用p(ij)，表示商品的利润。一个项集(或模式)x＝{i1,i2,…,ik}(1≤k≤v)是i的一个非空子集。表1定义了一个量化数据库，表2定义了数据库中不同项的利润。
表1.示例数据库.
表2.利润表.
项ij在事务tq中的效用值，记作u(ijtq)，其定义如下：
u(ij，tq)＝q(ij，tq)×p(ij)(1)
例如，在表1和表2中，
u(a，t1)＝q(a，t1)×p(a)＝1×2＝2，
u(d，t2)＝q(d，t2)×p(d)＝2×4＝8。
项集x在事务tq中的效用值，记作u(x,tq)，其定义如下：
例如，
u({b，f}，t6)＝(b，t6)+u(f，t6)＝q(b，t6)(×p(b)+q(f，t6)×p(f)＝2×7+2×5＝24，u({f，g}，t8)＝u(f，t8)+u(f，t8)+u(g，t8)＝q(f，t8)×p(f)+q(g，t8)×p(g)＝2×5+1×13＝23。
项集x在数据集d中的效用值，记作u(x)，其定义如下：
u({a，c，e})＝u({a，c，e}，t1)+u({a，c，e}，t3)＝u(a，t1)+u(c，t1)+u(e，t1)+u(a，t3)+u(c，t3)+u(e，t3)＝1×2+2×3+2×9+1×2+1×3+1×9＝40，
u({d，f})＝u({d，f}，t2)+u({d，f}，t4)+u({d，f}，t9)＝u(d，t2)+u(f，t2)+u(d，t4)+
u(f，t4)+u(d，t9)+u(f，t9)＝2×4+3×5+2×4+1×5+2×4+1×5＝49。
事务tq的效用值，记作tu(tq)，其定义如下：
tu(t2)＝u(c，t2)+u(d，t2)+u(f，t2)＝1×3+2×4+3×5＝26
tu(t7)＝u(c，t7)+u(e，t7)＝4×3+1×9＝21
项集x在数据集d中的事务加权效用值，记作twu(x)，其定义如下：
twu({e，g})＝tu(t1)+tu(t3)＝52+41＝93，twu({f})＝tu(t2)+tu(t4)+tu(t6)+tu(t8)+tu(t9)+tu(t10)＝26+34+52+25+13+32＝182。
用户根据偏好，设置最小效用阈值δ。如果项集x的效用值不小于用户预设的最小效用值，则项集x就是一个高效用项集。其中，最小效用值minuti的定义如下：
例如，假设最小效用阀值δ设置为25％，则
minuti＝(52+26+41+34+34+52+21+25+13+32)×25％＝330×25％＝82.5。
因为u({c，e})＝84＞minuti＝82.5，所以{c，e}为高效用项集；由于u({b，d，f})＝34＜minuti＝82.5，因此{b，d，f}不是高效用项集。
如果项集x满足twu(x)≥minuti，则x称为高事务加权效用项集(htwui)。例如，在表1和表2中，假设最小效用值为330×25％＝82.5，挖掘出的1-htwuis如表3所示。
表3.示例数据库在minuti＝82.5时对应的1-htwuis.
(2)问题陈述
基于以上定义，可以将huim问题定义为：对于一个给定的交易数据库d，所有项的外部效用值pt，最小效用阈值δ，huim的目的就是挖掘出数据库d中效用值不小于最小效用minuti的所有项集。
实施例1：基于改进遗传算法的模式数据挖掘方法huim-iga
本实施例的方法，种群初始化后，包括使用如下多种处理：个体修复处理，邻域探索处理，种群多样性维持处理和精英处理，来挖掘huis。
本实施例的基于改进遗传算法的模式数据挖掘方法，其使用的huim-iga算法如算法1所示。
算法1具体如下：
以下，为基于改进遗传算法的模式数据挖掘方法中，初始化种群、个体修复处理、邻域探索处理、种群多样性维持处理、精英处理等的说明。
(1)初始化种群
在本实施例的huim-iga算法中，数据集被表示成位图的形式。对于一个由n个事务和v个不同项构成的事务数据集d，其位图是一个n×v的布尔矩阵，记作b(d)。b(d)的第q行(1≤q≤n)和第j列(1≤j≤v)的值，即bq,j，通过如下方式计算：
表4给出了示例数据库的位图表示。
表4.示例数据库的位图表示
在提出的huim-iga算法中，利用事务加权效用向下封闭(twdc)属性，删除那些无法构成huis的项。可以显著减小搜索空间，提升计算速度。该算法中，染色体的长度由1-htwuis的个数决定，例如在示例数据集中假设minuti＝82.5，挖掘出的1-htwuis为{a,b,c,e,f,g}，因此染色体的长度为6。每条染色体表示一个项集，并且由0和1构成。其中，1表示对应位置的项存在；0表示对应位置的项不存在。例如，在图1中该染色体作为一个潜在的解，表示项集{a,c,e,g}。
在种群初始化阶段，根据每个1-htwuis的twu值来初始化每个个体，高twu值的1-htwuis被选中的概率较大。种群初始化的伪代码如算法2所示。在算法2中，每个初始个体先全部赋值为0，然后随机生成整数k作为该个体中不为0位置的个数(step5-6)。根据每个1-htwuis的twu值并利用轮盘赌选择算子决定哪些项将会出现在当前个体中(step7-13)。将生成的新的个体加入到种群中(step14)。最后返回完成初始化的种群(step17)。
算法2具体如下：
(2)个体修复处理
个体修复处理方法基于1-htwuis的twu值大小进行顺序修剪，尽可能保存了个体中可能会产生效用值的项的组合。其伪代码如算法3所示，在算法3中，先判断待修复的个体是否全为0(表示这个个体所对应的项集是空的，显然，空的项集对应的效用值为0，因此不需要修复)，如果待修复的个体全为0，则直接跳出该算法(step2-3)，否则，进入个体修复阶段(step4-28)。初始化中间变量temp为位图中twu值最大的1-htwui对应的那一列(step5-12)。按照twu值从大到小的顺序将temp与位图中的htwui对应的列进行与运算得到temp’，如果temp’全由0组成，则从当前个体中删除对应的item，否则，继续执行当前操作，直到待修复个体的所有位都被检查完为止(step13-28)。
算法3具体如下：
(3)针对重复huis的邻域探索处理
为了合理利用重复huis，避免重复评价适应度，采用了一种针对重复huis的邻域搜索处理方法。针对基因操作之后所产生的新个体，不直接进行适应度评估，而是先检查该个体是否包含在huis集合中，如果是，则对其执行邻域变异，产生一个该hui附近的新解，来探索其邻域空间内的解，然后再对其进行适应度评估，否则，直接进行适应度评估。
图2解释了这个邻域探索处理方法。如图2所示，深颜色的圆表示种群中重复的huis所对应的个体，浅颜色圆表示这些重复huis邻域内潜在的huis，所有适应度值低于minuti的个体在图中都被标注成了白色圆。该方法的目的就是为了利用这些重复的huis探索其邻域范围内潜在的huis，提高算法在最优解区域的局部搜索能力。
算法4描述了这种邻域变异方法。假设当前执行完变异操作的个体是一个hui(二进制编码形式)，使用presence_indexs存放该hui中为1位置对应的下标(step1),absence_indexs存放该hui中为0位置的下标(step2)，先从presence_indexs集合中随机选择一个值m(step3)，然后再从absence_indexs集合中随机选择一个值n(step4)。最后将hui中第m个位置设置为0(step5)，hui中第n个位置设置为1(step6)。
算法4具体如下：
(4)种群多样性维持处理和精英处理
高效用项集挖掘问题需要找到所有的满足最小效用值的项集，这意味着最终解的数量可能远不止一个。由于huis在解空间中的分布并不均匀，仅仅沿着上一代的最佳个体的方向进行搜索，很容易遗漏一些解。同时，随着种群多样性的迅速下降，搜索空间受到限制，算法也很容易过早的陷入局部最优。
为了保持各代群体的多样性，防止由于算法陷入局部最优而导致的huis遗漏问题，本实施例采用了一种种群多样性维持处理方法。
如图3所示，在每一次进化过程中，都从huis集合中选择两个连续存放的hui来替换当前种群中的两个随机选择的个体。这样做的目的，一方面可以使较优个体有更多机会向不同方向进化，扩大了最优解的搜索空间，另一方面，还使种群在进化过程中维持一定的多样性，一定程度上防止了由于算法过早陷入局部最优而导致的huis的遗漏问题。
同时，为了防止精英个体的流失，huim-iga算法中还引入了精英方法。如图4所示，首先将上一代种群pt与当代种群pt+1合并，并删除合并种群中的重复个体，然后按照utility值从大到小排序，并选择utility较大的个体构成下一代种群q。
实施例2：改进遗传算法的模式数据挖掘方法的应用示例
以表1所示的示例数据库和表2所示的利润表为例，简要说明所设计的改进遗传算法的模式数据挖掘方法(huim-iga)的应用过程。
假设minuti＝82.5，挖掘出的1-htwuis如表3所示，染色体长度为6(由1-htwuis的个数决定)，表4给出了示例数据库的位图表示。
由表3可知twu(d)＜minuti，因此可以将其对应的数据列删除。每个1-htwui的twu值从大到小排序结果为{c:206,f:182,a:170,g:170,b:161,e:146}。
假设通过算法2得到的初始种群中的3个个体的二进制编码分别为110111，110110和001100。对于110111按照算法3的修复过程，先初始化中间变量temp为位图中twu值最大的1-htwui对应的那一列，即temp＝bit(f)＝0101010111。然后按照1-htwui的twu值从大到小的顺序依次修复，temp∩bit(a)＝0101010111∩1010010100＝0000010100，由于结果不全为0，所以令temp＝0000010100。temp∩bit(g)＝0000010100∩1010010100＝0000010100，同时令temp＝0000010100。temp∩bit(b)＝0000010100∩0011110000＝0000010000,令temp＝0000010000。temp∩bit(e)＝0000010000∩1010001001＝0000000000，由于结果为0，所以将该个体中e所对应的位置置为0。故修复的结果为110011。类似的，修复110110后的结果为110010，修复001100后的结果保持不变仍为001100。
分别计算修复后的这三个个体对应的适应度函数值(即utility值)，可得到utility(110011)＝52
实施例3：改进遗传算法的模式数据挖掘方法的性能测试
a试验方法
表5.所用数据集的特征表
b实验结果
(1)种群多样性维护策略和精英策略对收敛速度的影响
为了说明种群多样性维持策略和精英策略对算法搜索huis效率的影响，在原算法(实施例1的的huim-iga)基础上去除种群多样性维持策略，并标记为huim-iga-dms，在原算法基础上去除精英策略，并标记为huim-iga-es，并分别在数据集上进行实验，huim-iga、huim-iga-dms和huim-iga-es各独立运行10次。
图6-图7给出了收敛曲线。从图6可以发现，
在进化初期huim-iga和huim-iga-dms的收敛速度相似，但是在算法进化的中后期huim-iga收敛速度明显快于huim-iga-dms,huim-iga仅需进行15000次适应度函数评价就基本上收敛，而不带种群多样性维持策略的huim-iga-dms直到60000次适应度函数评价结束也没有收敛。造成这一现象的原因在于，在进化初期，由于种群的多样性较高，算法很容易找到huis，因此这此阶段两者的收敛速度类似。但是随着进化的不断进行，种群多样性逐渐丧失，算法的探索能力被削弱，因此使得huim-iga-dms的收敛速度逐渐降低。而带有种群多样性维持策略的huim-iga却能始终保持对新huis的探索能力。因此进化中后期huim-iga的收敛速度会快于huim-iga-dms的收敛速度，这意味着huim-iga可以以更快的速度挖掘到huis。
从图7可以发现，不带精英策略的huim-iga-es在进化初期的收敛速度就明显慢于huim-iga，在mushroom和accident_10％数据集上需要超过30000次的评估才能收敛。这说明精英策略可以避免huis的遗漏和优秀解的丢失，因此带有精英策略的huim-iga的收敛速度要明显快于不带精英策略的huim-iga-es。
(2)收敛速度比较
为了评价各算法的收敛性能，选取各算法分别独立运行10次的平均结果。由于ihup，up-growth和up-histgrowth不是迭代算法，因此只比较了基于ec的六种算法。各算法在不同数据集上搜索到的huis随着评价次数的变化曲线如图8-图11所示。
观察图8-图11可以发现，相比于其他五个算法，实施例1提出的huim-iga算法收敛速度最快。主要原因在于种群多样性维持处理可以有效防止算法过早陷入局部最优，从而使算法始终保持对新huis的探索能力。另外，此外，精英处理和邻域探索处理有助于避免优秀个体的流失，进而加快对新huis的探索。
bio-huif-ga算法和bio-huif-pso算法的收敛速度相比实施例1的huim-iga算法较慢，一方面原因在于，相同的huis在huim-iga中只被评估一次，这有助于节省适应度评估次数，从而提高收敛速度。另一方面，由于缺乏有效的搜索策略，导致进化后期收敛速度逐渐下降。huim-bpso算法表现优于huim-bpsosig算法和hupeumu-gram算法，主要是由于算法采用了一种or/nor-tree结构，避免了演化过程中无效组合的产生，加快了算法的收敛速度。hupeumu-gram算法收敛速度最慢，主要是标准的遗传算法在求解huim问题时，缺乏有效的搜索策略，因此算法很难在有限的评估次数内收敛。
(3)比较挖掘到的huis的个数
对各算法在四个真实数据集上对挖掘出来的huis个数进行分析，并基于不同的最小效用阈值进行实验。由于ihup算法，up-growth算法和up-histgrowth算法可以从数据集中挖掘出完整的huis，因此这里被用来确定在不同数据集上的不同最小效用阈值下的真实huis个数。
表6-表7给出了各算法分别独立运行10次，挖掘出来的huis个数与各数据集在对应最小效用阈值下的真实huis个数比值的最好结果，最差结果和平均结果。
表6各算法挖掘到的huis的百分比
表7
从表6-表7可以看出，在所列举的数据集的不同最小阈值下，提出的huim-iga方法在探索出的huis完整程度上优于其他算法。huim-iga在δ较高的情况下，可以挖掘出所有的huis，但是在δ较低的情况下(比如，在connect数据集δ＝31.3％和accident_10％数据集δ＝12.1％时)，仍不能保证挖掘出所有的huis。但是即便在低最小效用阈值下，相比于其他的基于ec的算法，huim-iga挖掘到的huis的数量明显更多。相比于huim-iga，bio-huif-ga算法和bio-huif-pso算法需要在更高的δ下才能挖掘出所有的huis。这是由于最小效用阈值越小，满足条件的hui个数就越多，在缺乏有效搜索策略的情况下，使得挖掘huis变得更加的困难。bio-huif-ga算法和bio-huif-pso算法在最小效用阈值较小的情况下，并不能保证100％挖掘出所有的huis，这是由于最小效用阈值越小，满足条件的hui个数就越多，在缺乏有效搜索策略的情况下，很难挖掘出完整的huis。
由于huim-bpso算法相比于huim-bpsosig算法可以避免了无效组合的产生，加快了挖掘huis的速度，因此表现优于huim-bpsosig算法。hupeumu-gram算法在各数据集上的平均准确度基本上都低于20％，这是因为在算法迭代进化过程中，总是将上一代的优秀个体作为目标进行搜索，对于huim这种解数量较多的问题，很容易丢失解，算法很难在有限次评估次数内找到全部huis。
表9
表10
—内存溢出
表11挖掘到不同比例的huis各算法的耗时
实施例4：高效用项集挖掘装置
一种项集挖掘装置，包括：
第一计算模块、第二计算模块、邻域探索模块、种群多样性维持模块、种群选择和交叉模块、精英模块、高效用项集确定模块、解码模块。
本装置的原理如下：
第一计算模块计算事务数据库中各项的twu值，然后找出所有的1-htwuis，并根据twu值的大小对1-htwui进行排序，每个个体的长度由1-htwuis的个数决定，根据各项的twu值并利用轮盘赌选择法随机初始化种群。
个体修复模块，用于对1-htwuis的twu值大小进行顺序修剪，尽可能保存了个体中可能会产生效用值的项的组合；具体是：先判断待修复的个体是否是无效项集，如果不是，则进入个体修复阶段；所述个体修复阶段，包括：初始化中间变量temp为位图中twu值最大的1-htwui对应的那一列；按照twu值从大到小的顺序将temp与位图中的htwui对应的列进行与运算得到temp’，如果temp’全由0组成，则从当前个体中删除对应的item，否则，继续执行当前操作，直到待修复个体的所有位都被检查完为止。
邻域探索模块，用于当修复后的个体属于huis集合时，将所述个体进行邻域变异生成新的个体；具体是：假设当前执行完变异操作的个体是一个hui(二进制编码形式)，使用presence_indexs存放该hui中为1位置对应的下标，absence_indexs存放该hui中为0位置的下标，先从presence_indexs集合中随机选择一个值m，然后再从absence_indexs集合中随机选择一个值n；最后将hui中第m个位置设置为0，hui中第n个位置设置为1。
种群多样性维持模块，用于在每一次进化过程中，从huis集合中选择两个连续存放的hui来替换当前种群中的两个随机选择的个体；
种群选择和交叉模块，用于对种群执行选择和交叉；
精英模块，用于将上一代种群pt与当代种群pt+1合并，并删除合并种群中的重复个体，然后按照utility值从大到小排序，并选择效用值较大的个体构成下一代种群q；
第二计算模块，用于计算个体(即项集)的效用值；高效用项集确定模块，用于当所述个体对应的项集的效用值≥最小效用值时，将所述项集确定为高效用项集hui；解码模块，用于将挖掘出的所有二进制编码形式的hui进行解码。
可选地，所述项集挖掘装置可以实现如下算法：
以上为本发明的较佳实施例，并不构成对本发明的限定。本发明的保护范围以权利要求限定的范围为主。