利索能及
我要发布
收藏
专利号: 2021105793457
申请人: 南京师范大学
专利类型:发明专利
专利状态:已下证
更新日期:2025-08-18
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种数据集频繁项集挖掘可用性评估方法,其特征在于:所述方法包括以下步骤:

步骤(1)设C={I1,I2,…,In}是项的集合,给定事务数据集D1和D2,其中每个事务T是一个非空项集,使得 对D1、D2利用Apriori算法挖掘得到最大频繁项集集合,记为FIS1、FIS2;最大频繁项集MIS表示自身频繁但其超集均不频繁的项集, FIS1、FIS2包含若干MIS及支持度信息,而l1、l2分别表示FIS1,FIS2中|MIS1|、|MIS2|的最大值;文中MIS1、MIS2表示来自FIS1,FIS2的某一项集,步骤(2)将FIS1的任一项集MIS1与FIS2的任一项集MIS2,通过项集匹配算法F进行匹配,得到配对项集表Pairs,Pairs由若干项集对组成,score1表示MIS1、MIS2的项目相似度,在匹配过程中计算得到;

步骤(3)对Pairs中所有的,计算MIS1,MIS2的支持度相似度score2,进一步计算得到MIS1,MIS2的复合相似度score,更新pair为

步骤(4)将Pairs中的每一项的复合相似度score累加,并除以Pairs中项的个数,得到D1和D2的相似度分数SCORE,且该分数的取值范围为[0,1];

步骤(2)(3)中的项目相似度score1、支持度相似度score2、复合相似度score的定义如下:项目相似度score1:项集MIS1、MIS2基于项目的相似度记为score1,计算如下:若MIS1、MIS2的组成完全相同,score1=1;

若MIS1、MIS2不相同,且均不为空集,

若MIS1、MIS2中某一项为空集,score1=0;

支持度相似度score2:已配对的项集MIS1、MIS2基于支持度的相似度记为score2.计算如下:对于Pairs中某一项,MIS1的支持度为s1,MIS2的支持度为s2,复合相似度score:项集MIS1、MIS2的复合相似度记为score,score主要基于项目相似度score1,在score1基础上,利用支持度支持度score2进行进一步细化,计算过程如下:score=score1*score2。

2.根据权利要求1所述的数据集频繁项集挖掘可用性评估方法,其特征在于:步骤(2)中项集匹配算法F说明如下:

(a)设置score1=1,将FIS1,FIS2中组成完全相同的项集以的形式加入Pairs,同时分别从FIS1和FIS2中删除匹配成功的MIS1,MIS2,设置k=1;

(b)初始化FIS1、FIS2中每一项的候选匹配集合为空集,对FIS1任意项集MIS1,FIS2的任意项集MIS2,计算MIS1、MIS2的距离dis,若dis等于k,将MIS2加入到当前MIS1的候选匹配集合中,将MIS1加入到MIS2的候选匹配集合中;

(c)对于FIS1中的任意项集MIS1,如果其候选匹配集合PList为空,直接跳过当前项集,否则在PList中根据最小影响匹配策略选择项集MIS2,计算 将加入Pairs,同时分别从FIS1和FIS2中删除MIS1、MIS2.

(d)k++,若k小于MAX(l1,l2),回到步骤(b),若k等于MAX(l1,l2),将FIS1的前n项和FIS2的前n项一一匹配,n为MIN(|FIS1|,|FIS2|),匹配过程中设置score1=0.1,同时添加到Pairs中,最后将匹配过的项集从FIS1,FIS2中删除;

(e)设置score1=0,将FIS1,FIS2中剩余项集,与空集匹配添加到Pairs中。

3.根据权利要求2所述的数据集频繁项集挖掘可用性评估方法,其特征在于:项集匹配算法F,其特征在于:步骤(b)中距离dis的定义如下:项集距离表示项集之间不重合的项的个数,记为dis,计算如下:dis=MAX(|MIS1|,|MIS2|)‑|MIS1∩MIS2|。

4.根据权利要求2所述的数据集频繁项集挖掘可用性评估方法,其特征在于:项集匹配算法F,该匹配算法采用最近原则启发式算法进行项集间的匹配,匹配规则为将距离相近的两个项集进行优先匹配,其中使用的k用于控制该启发式算法,k表示当前配对过程只考虑两个项集距离为k的进行匹配,通过k的迭代,将距离近的两个项集进行优先匹配,即在进行距离为k的匹配时,所有距离小于k的项集对已被匹配完成,通过最近匹配原则使得无序查找变成有序匹配,每次的计算过程都可被复用,无重复计算过程,且每次进行k‑距离查找时,所有距离为k‑1的项集均被排除,而k+1的项集不在本次查找范围内,有效降低搜索空间,避免每次匹配都需与其余所有项集进行匹配而产生的重复计算。

5.根据权利要求2所述的数据集频繁项集挖掘可用性评估方法,其特征在于:步骤(c)中,候选匹配集合说明如下:候选匹配集合用于存储与当前项集MIS的距离等于k的项集集合,通过将每个与当前项集MIS相距为k的项集存储起来得到候选匹配集合,能够使得在保证最近匹配原则的同时,在候选匹配集合中通过最小影响匹配策略,保证匹配结果的优越性;同时也可在每一轮迭代中,将已经匹配过的项集从候选匹配集合中删除,实时记录每个项集可匹配的项集的变化情况,避免重复匹配。

6.根据权利要求2所述的数据集频繁项集挖掘可用性评估方法,其特征在于:步骤(c)中所述最小影响匹配策略说明如下:如果当前MIS1的候选匹配集合PList有且只有一个项集MIS2,则进行配对,若有多个项集,则从PList中挑选一个项集MIS2进行配对,挑选条件是在PList中,MIS2的候选匹配集合中可匹配项目最少,从而保证每次选择的匹配项为对其他项集的匹配影响最小。