文摘

本文处理的事务类。类代表了不同的数据收集的条件。本文重新定义两种支持:特征和可能的支持。前一个是基于特定的类分配给特定的模式。后者是基于最小类的类。提出了一种新的有效方法,发现模式的特性支持大于或等于最低支持通过使用预定义的可能的支持。同时,本文通过数值实验验证方法的影响的基础上,在UCI机器学习数据注册库和RFID(无线射频识别)收集的数据来自两个服装商店。

1。介绍

由于计算机的发展环境和网络环境,我们可以很容易地收集大量的数据和廉价商店。我们相信数据包括有用的知识,可以帮助我们的决策。许多研究人员解决发现的知识从1990年代中期以来的数据。研究各种发现任务来处理各种各样的数据。

频繁模式的发现任务组成的物品从事务的任务。每个事务由一组项目。在零售领域,收据和销售项对应一个事务和一个项目,分别。在最初的研究中,1)提出了一个方法,高效地生成候选模式,发现频繁模式通过使用先天属性。这里,属性显示模式单调减少的频率增加项目组合模式。文献[2)提出了一个位图索引,3)提出了一种垂直ID列表,4)提出了频繁模式树(FP-tree)为了有效地迅速访问事务和计算模式的频率。有可能这些改进迅速发现频繁模式。

然而,发现频繁模式并不总是对分析师的吸引力。的发现模式尝试用不同的特性。例如,[5]试图发现模式的订单基础上的频率高于预定义的秩序。文献[6代表很多频繁模式)并关闭模式。文献[7)长模式包括许多项目。文献[8]模式反映了重量的物品。文献[9]模式反映物品之间的层次关系。预计更有吸引力的模式是由这些研究发现的。

另一方面,从不同的数据模式的发现是尝试。例如,[10]试图处理结构化数据表格。在这里,每个项目由一个属性和一个属性值。它提出了一个有效方法,发现频繁模式从数据通过使用属性和属性值之间的关系。在数据的情况下,缺少的值通常是包括在内。为了处理的值,10- - - - - -12)提出新的评价标准的模式。

从交易模式的发现任务是扩大研究领域越来越多。本文侧重于不同的数据收集的条件作为一个扩展字段。这是因为我们想要发现模式往往是忽略了由于不同。例如,我们试图发现的模式从连锁零售商店销售商品。如果我们从许多商店收集的数据,我们无法预计,每个商店出售相同的商品。有限的商店可以卖特定的项目,如新项目和地区项目。很难发现模式相关的项目在有限的商店出售。这是因为他们的销量往往远小于所有商店出售的物品。此外,我们不能预测,每天每个商店出售相同的商品。它可以销售经验丰富的项目。 Patterns related to the seasoned items tend to be overlooked. In addition, we cannot anticipate that each store sells items based on the same sales method. Customers may be able to buy items through the trial of items in a store. Patterns related to the trial tend to be buried in patterns unrelated to the one. We can easily find difference of conditions in the data collection. It is anticipated that more attractive patterns are discovered, if we reflect the difference in the discovery of patterns.

因此,本文认为条件的差异数据收集类。它提出了一个有效方法,发现模式反映了类。另外,本文的方法适用于在UCI机器学习数据注册库(13)和RFID(无线射频识别)收集的数据从服装商店14]。它比较模式发现方法与模式发现的现有的发现方法,验证模式发现了该方法的有效性,并显示该方法的效果。

2。发现的特征模式

2.1。交易与他们的类

本文作为一个类的项目集一个事务。也就是说,交易由公式(定义1)。在这个公式,是一组的所有项目,是一组类,是物品的数量包括在交易。是的一个子集和由类的项目可以包括在内。这个定义表明,该事务没有多个相同的物品。介绍了约束由原发现任务(1不处理类。它指出一个项目是否出售或不是。另外,这个定义表明,每一项是包含在类

这里,我们注意的例子是由四类:“春”、“夏”、“秋”,和“冬季”,和三个项目:“苹果”、“西瓜”,和“香蕉”。表1显示类,其中的每个项目销售。相对应的组类一个项目被称为一个项目类以后。表2和3分别显示合法和非法的例子。

在表2,是一个事务的类,因为“冬季”包括在项目类的“苹果”和“香蕉”。同时,是一个事务的类,因为“夏天”是包含在项目类的“西瓜”和“香蕉”。在表3,和它的类不是一个交易,因为两个“苹果”是包含在吗。同时,和它的类不是一个事务,因为“苹果”不包括项目类的“春天”。有些读者可能会认为这个限制太严格了。然而,它并不总是严格。这是因为我们可以添加条目类的“春天”如果我们需要把“苹果”作为一个事务类。另一方面,如果一个有效的项目类分配给每个项目,我们能想到的两种可能。一个是类事务中是错误的,和另一个是错误的项目都包含在项目集,我们可以认为一些错误发生在数据收集。

2.2。标准

本节考虑一种方法处理事务类。此外,它认为这种方法发现重要的模式由交易商品的原因。这里,我们注意到事务与特定类的数据并不总是相等的。即交易的数量对应于一个类可以大,和一个对应于另一个类可以很小。因此,物品的数量对应于前阶级倾向于频繁,和模式组成的项目往往是频繁。

例如,事务和项目类,如表所示4给出了。同时,他们有三个模式由两个项目:(,),(,)和(,)。他们的频率4、2和1,分别。(,)是最常见的模式三种模式。这里,我们注意频率的比值的事务可以包含的模式。(,)可以包含在所有事务()。这是因为这两个项目类的的一个是和相对应的类集(,)是。的比率(,)是0.50 (= 4/8)。另一方面,(,)可以包含在三个事务()。这是因为项目类的是。的比率(,)是0.67 (= 2/3)。同样的,(,)可以包含在三个事务()。的比率(,)是0.33 (= 1/3)。因此,(,)是最大的模式比,它是最重要的模式三种模式。

我们预料的重要模式基于比率比频繁模式更有效,因为后者往往是一个著名的模式,不给分析师产生重大影响。需要定义一个新的标准对应比例。公式(2)显示了定义。它是基于一个想法类似于支持结构化数据表格中的遗漏值(10,11]。标准被称为支持以下特点

在公式(2),是一个项目组成的模式。是交易的数量包括。是这样一个组合类集,所有项目可以包括在内。是交易的数量的类都包含在吗。和被称为一个模式类和一个总事务数从今以后。我们注意到,可以。然而,如果,是0。没有必要计算特性的支持。因此,没有必要在乎这种可能性。同时,我们注意到,支持的特征。这是因为小于或等于。

我们可以预见,如果发现方法提取模式的特性支持大于或等于一个预定义的阈值,可以反映类分布的模式交易。然而,模式可能不小心从一个非常小的事务子集。我们不能总是相信模式特点。因此,本文介绍了其他标准保证的最低频率模式。标准等于representativity引入的(12]。

本文试图发现模式满足两个条件:最低支持和最低频率。如果支持的模式特点是大于或等于最低的支持和他们的频率大于或等于最低频率的模式中提取的特征模式。在交易的情况下没有他们的类,这些条件是相等的。这是因为如果一个模式的支持总是比另一个模式吗在后一种情况下,的频率比一个大的。是足够的交易没有他们的课程评估的条件之一。

接下来,我们注意特性支持的性质和频率。如果两个模式和满足的关系的频率,很明显大于或等于之一吗。频率单调降低的增长模式。然而,单调性并不总是满足支持的特征。例如,我们注意事务和项目类,如表所示5。

表5显示的频率是3的总事务数是5。这是因为包含在三个项目类,,。的特性支持0.60 (= 3/5)。另外,表5显示的频率(,2)和总事务数(,)是3。这是因为一个模式类的(,)是。特征的支持(,)是0.67 (= 2/3)。这个例子表明,单调性不满足。

的单调性是非常重要的发现方法的模式以有效地发现它们。可以避免多余的评价方法通过使用属性。因此,很难支持高效地发现模式特征。当然,我们可以试着发现模式基于频率的单调性。然而,频率是一个有限的标准。最低频率往往是设置为一个较小的值。我们不能预料到足够的效率所获得的频率。

因此,本文介绍了另一个标准。标准是基于一个想法类似于提出的可能的支持(10]。反映了表格结构化数据的缺失值的支持。本文重新定义了可能的支持为了处理事务类。公式(3)显示了定义。在公式(3),是交易的数量分配类。被称为“最低交易数量以后 重新定义了可能的支持大于或等于0,可以大于或等于1。这是因为可以比。此外,重新定义了可能的满足单调性的支持。原因如下所示。首先,我们注意公式的分子。分子是一个模式的频率和单调减少。另一方面,如果两个模式和有关系的关系,显然是满意的。因此,。即分母单调增加的增长模式。因此,可能支持单调减少的模式生长。

接下来,我们注意之间的关系特征和可能的支持。这些支持的公式表明,分子是相等的。同时,他们显示的关系满足在任何模式。因此,公式(描述的关系4)总是满意

公式(4)表明,可能支持模式给出了上界特性支持的任何超级模式()。因此,如果可能的支持小于最小支持,晚餐的特性支持模式是小于最小支持。晚餐模式不能特征模式。因此,发现方法保持模式的可能支持大于或等于最低的支持和频率大于或等于最低频率以种植它们。以后的模式被称为可能的模式。同时,发现方法提取模式的特性支持大于或等于最低的支持可能的模式。发现方法基于two-stepwise评价方法能够有效地发现所有的特征模式。

2.3。发现方法

本文提出一种方法,发现所有特征模式从事务类。该方法是基于FP树和提出的FP增长4]。这里,FP树与树的数据结构存储交易格式。FP增长方法发现所有利用FP频繁模式树。FP增长生成FP树从事务子集并生成新的事务子集生成的FP树。递归两种生成步骤重复。本文提出了精制FP树和FP增长以处理事务类。

原来的FP树是由节点分配一个项目名称及其频率,链接将项目名称相同的节点,一个头表存储项目,和链接将与节点表中项目包括项目名称。FP树的根节点是一个特殊的节点和分配“零”。精制FP树基本上等于原来的一个。但是,提炼一个分配一个模式类和识别标志头表中的每一项。这里的标志显示相对应的模式是否头表中的每一项都包含在一个特征模式。精制FP树是由一个算法如表所示6与他们交易类、项目类和条件项集。第一代的精制FP树,条件项目集。一代除了第一个,这至少是可能的模式。在这个算法中,最小支持((0,1)和最低频率(≥1)是预定义的。表6描述了原代方法的差异与大胆的风格。

在接下来,我们将展示一个例子生成精制FP树从事务和项目类,如表所示7。

在这种情况下,项目集。最低支持0.5和最低频率是1。的事务表7显示的频率 6、3、3、4、3、2、1,1,1,分别。表的项目类7显示的总事务数,,,,7日的吗和3,的和是4。同时,它表明最低交易数量,,,,,,3,的和是4。可能的支持2.00 (=),1.00 (=),1.00 (=),1.33 (=),1.00 (=),0.50 (=),0.25 (=),0.33 (=),0.33 (=),分别。因此,可以选择生成方法,,,,,尽可能的物品。项目降序排列的频率特性支持,和可能的支持。该方法生成弗利斯特雨如列表。但是,索引项作为第四键,如果三个标准是相等的。

接下来,该方法可能拿起商品的交易和安排的项目顺序弗利斯特雨。它会生成一个选择和排序事务子集,如表所示8。使用子集以生成精制FP树。

如果被选中的子集,该方法生成一个精制FP-tree如图的一部分1(一)。另外,如果被选中的子集,它生成一个精致的FP树的一部分,如图1 (b)。即方法添加新节点或更新现有的节点的频率从根节点。最后,提炼FP树如图2是生成的。

在本小节的剩余部分,我们解释了精制FP增长。最初的FP增长检测一个前缀路径。路径是一个路径从根有关。每个节点包含在路径只有一个孩子。如果FP树单前缀路径,原来的FP增长将FP-tree划分为单前缀路径和剩余的部分。剩下的部分是添加了一个新的根节点和FP树生成。最初的FP增长分别发现频繁模式从单一新FP-tree和前缀路径。此外,它结合了基于树的模式和基于路径的模式。频繁模式的结合模式。最初的FP增长可以发现所有基于频繁模式的组合。

另一方面,在精制FP增长的情况下,我们不知道是否支持增加模式生长特征。即使特征模式基础上给出一个前缀路径和特征模式基于一种新的精制FP树,他们并不总是特征模式组合。有必要检查组合是通过计算特征模式是否支持他们的特征。的检测单前缀路径不给足够的优点。因此,精制FP增长试图发现没有检测一个前缀路径特征模式。在下面,我们解释了FP增长没有检测。

精制FP增长拿起一个项目从后方的弗利斯特雨精制FP树。它生成的交易条件。也就是说,精制提取节点包括FP增长从精制FP树和提取提取路径上节点的节点到根节点。事务从每个路径生成和分配频率的频率等于节点包括。精制FP增长生成一个新的FP树的交易条件。被添加到项目集的条件。在这里,分配给前面的精制FP树,是吗在第一个精制FP增长的过程。精制FP增长递归重复精制FP树的生成和条件交易。

另一方面,精制FP增长需求模式类为了计算特征支持和可能的支持。生成的模式类可以指两项包含在模式及其项目类。然而,如果一代总是从头开始,它是多余的。我们可以更有效地生成模式类通过使用一个模式类之间的关系。也就是说,如果一个模式是由一个模式的组合吗和一个新的项目,一个模式类()等于该产品集()基于模式类()和一个条目类()。因此,头表保持模式类。

根据上述讨论,提炼FP增长描述如表所示9。表9描述之间的差异原来的FP增长和精制与大胆的风格。精制FP树和其输入精制FP增长。

最后,模式发现方法的特征是描述如表所示10。适当的方法调用算法如表所示6和9。它可以生成所有特征模式与他们交易类、项目类,最小支持度,最低频率。

3所示。数值实验

3.1。数据

本文使用UCI数据集在UCI机器学习库中注册的数值实验。同时,它使用RFID数据集收集从两个服装商店。在UCI数据集的情况下,三个数据集“车”、“海斯”,选择“托儿所”。这是因为每个数据集的数据集分类任务,由离散值。这些数据集是结构化数据表格。每个例子的数据集是由属性值和一个类和被认为是一个事务。然后,一个属性和一个属性值被认为是一个项目。一个类的一个例子被认为是一类事务。检查生成的项目类属性值和类的组合。表11显示生成特性的交易来自UCI数据集。

RFID数据集的数据集收集为了分析销量之间的关系和操作客户的商店。RFID阅读器将试衣间,货架,收银机,RFID标签分配给销售物品。我们可以掌握顾客追逐的行为在某种程度上的条目。在这个实验中,我们认为合适的项目,没有配件项目的区别为类。这是因为配件项目的一个重要客户的行为,但其频率并不高。表12显示类的分布事务。我们可以确认合适的项的数量远远小于没有合适的项目之一。

3.2。方法

我们提出的方法与现有的方法比较4),但一个前缀路径不是合并的过程。现有的方法是一个频繁模式发现方法。它不处理类。此外,它忽略了类分配给事务和项目类对应于每一项。该方法旨在发现最多数百模式。最低支持和最低频率调整。

在UCI数据集的情况下,该方法发现特征模式通过改变最小频率。最低支持是固定的。此外,该方法输出可能的模式为了评估研究模式。另一方面,现有的方法发现频繁模式通过改变最小频率。最低支持直接计算指的频率。频率取决于最低支持和该方法的最低频率。这个实验评估发现之间的关系模式,最低支持,和最小频率。

在RFID数据集的情况下,这个实验侧重于特征模式的差异和频繁模式。该方法和现有方法发现模式通过改变最低支持。该方法的最低频率是固定的。这个实验评估发现模式的有效性。

3.3。实验结果

数据3,4,5实验结果显示在UCI数据集的情况下:“汽车”,“海”,和“托儿所”。图图(a)和(b)显示模式和频繁模式的差异特征。图(一个)显示模式的总数。在这个图中,我们不关心的物品包括模式。称为长度以下数量。

图(b)显示特征模式的差异和频繁模式在特定长度的情况下。长度的“汽车”,“海斯”和“托儿所”,2、2和3分别。只在每个图中,“阶级”的数量显示模式只有通过该方法发现的。“阶级共同”显示了数据发现的方法和现有的方法。“不”类只显示数字只发现现有的方法。但是,在该方法中,最小0.100支持是固定的。同时,最低频率的“汽车”9日,18日,52岁,87年和173年。的“海耶斯”1,2,5,8,16岁。的“托儿所”是65,130,389,649,1297。他们对应的最小支持现有的方法:0.005,0.010,0.030,0.050和0.100。 In the case of the existing method, the minimum frequency for the data sets: “car”, “hayes”, and “nursery” are fixed and they are 173, 16, and 1297, respectively. They correspond to the minimum support 0.100.

图(c)显示了可能的模式和频繁模式的区别。该方法中的阈值等于图中图(a)和(b),最低支持现有的方法改变了根据该方法的频率。在每个图中,“类”节目的总数可能的模式和“无阶级”显示的总数频繁模式。

图(d)显示了该方法的计算时间和现有的方法。但是,现有的方法的计算时间估计通过修改程序代码的方法。即计算的特点和可能的支持,和评估基于摆脱的程序代码。另一方面,其他额外的过程因为他们计算成本相对较小。修改后的程序代码是用来评估现有方法的计算时间。在实验中,计算时间是衡量使用DOS命令与毫秒单位“时间”。实验使用的计算机环境,如Windows 7家庭高级版Service Pack 1和东芝dynabook卫星PXW / 59千瓦加载英特尔酷睿2双核CPU (TM)(电子邮件保护)兆赫和4.00 GB RAM内存。程序代码是由C语言描述和MinGW-5.1.6.exe由gcc编译命令。在该方法中,最小的支持是固定的0.100,最低频率改变。使用的频率是评估现有的方法。

在这些图中,水平轴的最小支持,除了图和垂直轴(d)的模式。在图(d),垂直轴的计算时间,和他们的计算单位是毫秒。

图6实验结果显示在RFID数据集。在这个实验中,该方法的最低频率是2。最低支持从0.001改为0.005每0.001提出的方法与现有的方法。图图(a)和(b)显示模式的总数店,店,分别。只在这些图中,“类”、“阶级共同的”,“不”类,轴对应的UCI数据集的情况下。另一方面,表13和14显示模式发现只有通过该方法从每个商店。在这些表,最小支持0.001,长度大于或等于2。

3.4。讨论

本节讨论该方法的效果由于七个观点:“发现模式的差异”,“发现模式的有效性”,“项目”的频率,计算时间,精制FP树的“复杂性”、“预处理法”、“普遍性”。

3.4.1。发现模式的区别

图图(a)和(b)显示,有许多模式只有通过该方法发现的。特别是,当该方法的最低频率很小,模式是大的数量。我们可以预期,分析师感兴趣的模式,因为比率包含在一组特定的类是比较高的。另一方面,现有的方法很难发现的模式。如果现有的方法试图发现他们,有必要设置较小的最低频率。然而,较小的最低频率往往会发现许多频繁模式。现有的方法可能忽略重要的模式,因为模式隐藏在很多频繁模式。为了避免忽视,我们也许能够执行two-stepwise方法。方法结合了现有方法的后处理方法。即第一步发现频繁模式运用现有的规模较小的最低频率的方法。 The second step extracts characteristic patterns from the discovered patterns by evaluating their characteristic supports. However, Graph (c) shows that the number of possible patterns is smaller than the number of frequent patterns. The former numbers are 0.376 times, 0.461 times, and 0.404 times as small as the latter numbers in the case of “car", “hayes”, and “nursery”, respectively. The proposed method can discover all characteristic patterns by investigating possible patterns whose number is less than half as small as the numbers based on the existing method. The proposed method is more efficient method with calculation cost.

3.4.2。发现模式的有效性

表13和14表明,该方法发现许多模式由上穿,下穿。如果客户感兴趣的只有穿顶部,顶部穿不是通常安装在试衣间。然而,如果客户感兴趣的结合上穿和底部穿,客户倾向于适合的组合。发现的模式显示组合。另一方面,客户的配件是一个麻烦的行为。没有合适的销量远远大于的拟合。现有的方法很难发现模式相关的配件。我们可以认为,该方法比现有的方法发现更有效的模式。在未来的工作中,我们将尝试显示模式在服装商店和零售商详细验证模式的有效性。

3.4.3。频率的物品

的“汽车”和“托儿所”,特征模式的长度是1完全对应于频繁模式的长度是1。特征模式的长度大于等于2包括模式现有方法不能发现。这是因为特性支持增加类包含在模式类的数量减少。该方法发现的相关特征模式结合特定的类。我们认为该方法的特点是实验证实。

3.4.4。计算时间

结果在图3- - - - - -5显示图形的形状(c)类似的图(d),也就是说,计算时间取决于数量的模式。它几乎不依赖于额外的计算成本与该方法有关。额外的该方法的计算成本并不是那么大。我们可以预测,该方法迅速发现的模式,因为它调查小组合项目。

3.4.5。精制FP-Tree的复杂性

精制FP-tree已经头表中的类和ID标记模式。它需要额外的内存。然而,节点组合精制FP-tree占领更大的记忆的一部分。这是因为交易的数量和项目的一个更大的类的数量。我们认为额外的内存并不是一个大问题。

3.4.6。预处理的方法

即使现有的方法不能直接处理类,结合现有的方法和预处理方法可以处理它们。即预处理方法可以将事务划分为一些事务指的子集的类。现有的方法可以发现频繁模式划分事务子集。组合方法可以发现所有的特征模式。但是,如果类的数量很大,类的组合指数增加。此外,我们通常不有用的组合类的知识。有必要发现不同交易模式的子集。结合的方法需要大量的计算成本。另一方面,该方法可以发现特征模式而不需要额外的知识。因此,该方法是更有效的比相结合的方法。

3.4.7。普遍性

我们可以把各种条件为类。零售领域,例如,在一个销售周期的差别,商店,和销售人员被视为类。在传感器网络领域,地区的差异,数据收集时间间隔和数据探测范围被认为是类。因此,我们认为,该方法具有较高的通用性。该方法可以分析各种观点的数据使用的类。

根据讨论,我们认为,该方法可以为交易进行更有效的分析。

4所示。总结和未来工作

提出了一种方法,发现特征模式从事务类。该方法作为条件的差异数据收集类。本文重新定义了可能的支持和特征支持为了有效地发现模式。最后,通过数值实验验证了该方法的效果基于三个数据集在UCI机器学习库和注册两个数据集收集的RFID阅读器和射频识别标签在服装商店。

在未来的工作中,我们试图提高计算速度的方法与观点。例如,我们考虑一个小方法,计算可能的支持,以减少可能的模式。具体地说,我们试图使用的增长模式及其之间的关系模式类。我们相信可以估计的关系可能支持为较小的值。同时,我们尽量考虑使用单前缀路径。在这篇文章中,我们忽略的道路因为特征模式不能只是从单一的组合发现前缀路径和剩下的FP树。然而,对于快速发现类似的组合可能会有用。有必要详细调查的功能组合。此外,我们将考虑使用精制FP树节点的类信息。使用可能导致更有效的发现模式。 On the other hand, it leads to a more complex FP tree with high calculation cost. It is important to clarify the relationships between the validity of patterns and the complexity of the FP tree. Lastly, we will try to apply the proposed method to many data sets in order to verify its effect in detail.

交易没有类的发现任务是扩大研究领域越来越多。扩张可能有用的发现任务事务类。我们尝试将该方法的扩张。