英语原文共 42 页,剩余内容已隐藏,支付完成后下载完整资料
基于行为的聚类分析和对的兴趣度量的关联规则挖掘
C. Tew · C. Giraud-Carrier · K. Tanner ·S. Burton
摘要:对关联规则挖掘的兴趣测度的性质和行为进行了研究,提出了一些研究、理论、经验或两者的研究。虽然每个人都有自己的价值,但大多数都是有限的,或者更重要的是,忽略了感兴趣措施的目的,也就是发现关联规则的最终排名。因此,本文重点分析了在110个不同数据集所生成的规则中,对61个著名的跨性测试行为的规则排名行为进行了分析。通过对排名行为的聚类,我们强调并正式证明,在兴趣测量中,以前未报告的相等。我们还发现,似乎存在着不同的兴趣度量集群,但集群之间仍然存在差异,这就证明了对于特定任务和业务目标选择适当的兴趣度量是至关重要的。
关键词:兴趣度量,聚类,行为分析,关联规则挖掘
1介绍
关联规则挖掘已经在研究人员和数据分析师的工具箱中加入了其他分析技术的行列。主要来源于原始Apriori算法(Agrawal 等人在1993年提出; Agrawal and Srikant在1994提出),关联规则挖掘算法将数据记录视为属性值对或项目的集合,并提取项集之间的关联规则 形式A→B.这种规则的含义是,只要A中的项目存在于数据记录中,则B中的项目可能存在于同一记录中。通常计算两个简单的统计量来指导关联规则的提取:支持度,即数据记录包含A和B两者的信息的可能性;置信度,这是数据记录包含包含A的同时包含B的概率。
通常,用户指定最小可接受的支持水平,并且关联规则挖掘算法分两个阶段进行。在第一阶段,产生频繁项集(即支持超过用户指定的最小支持阈值的项目集),利用支持的向下关闭属性,即项目集的支持总是小于其任何子集。在第二阶段,所有由频繁项集中项目的二分组成的规则都是根据质量或兴趣的一般衡量标准来排列的。还可以在感兴趣度量的值上设置一个阈值,以便只保留超过该阈值的规则。信心通常被用作默认的兴趣度量。然而,有明显的其他有用的兴趣观念,多年来,研究人员设计了(客观的)趣味性措施,尝试匹配不同用户和应用领域期望的“趣味性”的不同概念(例如Lan等人在2006年提出)。
最近对McGarry(2005)以及耿和汉密尔顿(2006)进行了许多有趣的措施的调查。还进行了一些理论研究,经验论研究或两者研究,以提供对这些措施的性质和行为的了解,以及如何在给定的应用中选择它们。不幸的是,大多数这些研究的范围是有限的,或者忽略了意图措施的目的。特别是,对于从业者来说,最重要的是一个有趣的措施是如何排列规则的,所以她可以从她的数据中获得最有趣的规则。因此,如果两个趣味性措施产生相同的排名,就最终目标而言,它们在根本上是一样的,并且讨论可以被区分的其他属性主要是理论和哲学的练习。换句话说,如果排名相同,就无法区分所制定的规则,所以根据其他标准优先选择一个有趣的度量似乎没有实际价值。我们在这里跟随这个想法,并通过考虑排名来调查趣味性措施之间的相似之处。特别是,我们报告了一个广泛的理论和经验分析,重点是大量有趣的措施对大量任务的行为。我们用一系列规则来表征一个有趣度量的行为。然后,根据他们的排名之间的协议水平比较有趣的措施,我们可以产生一个基于行为的聚类,这增加了我们对这些措施的理解。
我们在一开始就注意到,对于一些有趣的措施,存在一个有趣的悖论,因为“给出一些使规则有意义的一些措施,发现的符合该措施的规则应该是有趣的。然而,一些发现的规则实际上是不感兴趣的,因为他们预计会持有给定一些被发现的其他规则和简单的分配假设“(Padmanabhan 2004)。例如,如果选择电梯有趣的度量,如果A→B被认为是有趣的,那么所有的规则独立于A和B,也将被列为有趣的。然而,这些额外的规则没有增加真正的兴趣。帮助减少一组规则的方法可能是有趣的,包括优化规则发现(Li 2006),规则生成过程中的筛选(Webb 2010),假发现避免(Webb 2006),以及生成后的集群和汇总的规则(Sahar 2002)。
最近,一些研究人员将注意力转移到采用模式集而不是个人关联规则的思想,作为处理规则之间冗余的另一种手段,并使用背景知识来排序模式(Jaroszewicz和Simovici 2004; Gallo et al。2007; De Bie et al。2010; Tatti and Mampaey 2010; Mampaey et al。2011; Webb 2010,2011; Spyropoulou和De Bie 2011)。有趣的是,与模式集挖掘方法相反,衡量个体规则的好处是人们知道什么时候一个特定的规则是“足够好的”,而在模式集中,往往存在复杂的统计依赖关系,它们决定是否包含模式。然而,我们忽略这些问题,因为我们不旨在解决“有趣的”和“什么是多余的”问题,而是更直接和更实际的问题是“所有这些有趣的措施如何在行动上有所不同?”
论文的其余部分是按如下方式组织的。在第2节中,我们讨论了相关的工作,包括先前关于兴趣测量的研究,以及在数据挖掘的其他领域中使用集群来进行行为分析。在第3节中,我们描述了基于其排名行为的集群感兴趣度量方法。在第4节中,我们讨论了我们的结果,证明了几组有趣的方法的不可识别性,并指出了一些关于相对船之间的有见解的发现。最后,第5节总结了这篇论文。
2相关工作
在关于规则挖掘的兴趣度量的设计,使用和评估方面,在数据挖掘方面做了大量工作。 在高水平上,McGarry(2005)和Sahar(2010)都明确区分了客观和主观的趣味性。 客观的措施量化了前提与规则之间的关系。 主观措施需要用户输入,根据数据和用户信念和期望的规则的兴趣。 在本文中,我们专注于客观的措施。 我们在这里简要介绍最相关的工作。 在整篇论文中都有更详细的比较和讨论。
Vaillant等人(2004)和Lenca等人(2007年,2008年),在设计一个多标准的决策系统来选择感兴趣的方法时,基于理论属性和经验结果的20个指标,使用了前序比较矩阵。他们发现了五个群集,它们与我们在相同的兴趣措施上是一致的。考虑到的20项措施都在减少。记录中包含条目的数量,而不是B中的项),这反映了作者的偏见,反例的数量越少,有趣的就越高。作者还指出,他们根据所考虑的数据集观察不同的情况。我们通过考虑大量的有趣的、没有预先选择的有趣的度量,以及大量不同的数据集来解决这两个问题。有趣的是,作者指出,一些“保证”是“单调递增的信心的转换,而另一些是单调递增的提升”和“单调递增的变化的度量”继承了这些其他度量的属性,因此“这样的度量将按照相同的顺序排列规则”。“这也是我们在更大范围内提出并正式证明的。”
Huynh等人(2005年,2006年,2007年)是第一个提出基于排名行为的有趣的措施。然而,尽管他们确实考虑了35个有趣的度量方法,但是他们基于最多2个数据集进行集群。他们小心地选择具有非常不同属性的数据集,但是样本很小,这让人怀疑他们的结果的健壮性和有效性。在某种程度上,他们的工作实际上是用来探索、分析和可视化一个数据集(在他们的工具ARQAT中),而不是真正地比较有趣的度量。特别地,他们不考虑公式和代数关系,除了Yule的Y,Yule的Q,和概率比,而且只有通过。我们的分析更进一步,建立了观察到的“功能依赖关系”和“霸权特性”。另一方面,我们从他们那里借鉴了建立高相关性(CG )和高反相关性(CG0)图的有趣想法,我们通过对所有数据集进行平均,而不是只在那些只有最小关联阈值的数据集上进行调整。我们的工作还有另外两个显著的不同。一方面,他们使用皮尔逊的相关性,而我们使用Spearman的等级关系;另一方面,它们用1表示距离,而我们用1/2。我们相信排名相关性是相对行为的更好代表,因为它是最重要的,而不是原始的价值。我们同样相信,不混淆完美的相关性和完美的反相关性是有价值的。我们的许多发现提供了额外的支持证据。第二种观点与他们的观点一致,从而证实了他们的有效性,而另一些则扩展了他们的观点(例如。在现有的集群中包含了新的有趣的措施,并发现了新的有趣度量集群。
Ohsaki等人(2003年,2004年)审查了38个有趣的措施,重点是如何在(1)实际应用(在医疗领域),以及(2)反对专家判断(这里是医学专家)执行它们。他们的前提是,趣味性测量“主要用于消除无意义的规则,而不是为人类用户发现真正有趣的规则,因为它们不包括领域知识。”因此,他们认为的措施不能相互比较,而是根据使用C5.0(Ohsaki等人2002)的分类挖掘(而不是关联规则挖掘)获得的一组特定规则,对人类黄金标准进行了衡量。然后,他们可以显示一些趣味性措施如何符合专家评估(例如,召回),而其他人则不会(例如流行率)。有趣的是,他们将Yule的Q和Yule的Y定义为Odds Ratio的函数,但是他们没有进一步得出结论,所有这三个给出相同的排名,导致他们之间的冗余。
姚和忠(1999)描述了一个非常好的理论框架,它使用集合理论和概率观点来分析兴趣度量。 他们的工作只涉及16项措施,根据它们在单向支持和双向支持之间的差异进行分类。 他们还在措施之间建立各种代数关系,例如双向支持=支持times;log2电梯(在我们的命名惯例中),但是虽然他们意识到“不同的名称已被用于基本上相同的措施,或者是正单调变换 相同的措施(称为订单保存转型),“他们仍然是理论性的,不排除他们的措施在排名方面的行为。
吴等人(2010)仅分析了五个有趣的措施,因为他们反对一些趣味性措施对零交易的敏感性(即既不包含A也不包含B的交易)。 他们认为,这种敏感性在涉及到趣味性方面给出了不好的结果,并进一步断言,他们选择的五项措施是他们所知道的唯一不变的。 非常优雅的结果是,他们可以用数学泛化的平均值和适当的指数来重写它们,然后能够在它们之间建立一个总的顺序。 虽然本身没有对行为本身的分析,但是本文还简要讨论了Coherence,Cosine和Kulczynski对一个数据集和八个规则,使用Kendall的tau;秩相关性来获得的排名。 有趣的是,本文还展示了基于排名的等价性的理解,因为作者证明了M1(ri)le;M1(r j)lArr;rArr;M2(ri)le;M2(rj)的形式的陈述。
Kannan和Bhaskaran(2009)在设计修剪关联规则的方法时考虑了38个有趣的措施。 特别地,它们显示了每个关注度测量在不良规则被删除后与覆盖所有规则时的覆盖范围。 不幸的是,很难从这些结果中推测出趣味性度量之间的相对相似性或相关性。
贾拉利-赫维和Zaiuml;ane(2010)讨论了49种不同的有趣的措施,这是目前研究中最大的数字。他们的分析发生在关联分类器的上下文中,这是关联规则矿商的一个子集(即:他们只计算那些带有目标值的规则作为结果)。他们的重点是在每个阶段中选择感兴趣的措施的影响:规则的生成/修剪和规则选择(确定每个阶段的最佳度量)。然而,它们确实会聚集它们所选择的兴趣度量,但是它们的结果似乎是偶然的,并且在本文中并没有深入探讨。此外,集群是基于16个人类编码的二进制属性。目前的研究是直接互补的,因为我们基于它们的行为,而不是预先定义的属性,聚集了大量的度量。
Abe和Tsumoto(2008)关于超过32个数据集的39个有趣测量的行为在原理上类似于我们的分类。实际上,它们使用PART而不是与Apriori的关联规则应用分类规则。另外,我们尝试去除尽可能多的偏倚,并且在使用秩相关性时使用原始相关性,它们被增益比(PART)所使用。最后,他们有一个非常不同的方法,它们首先对一组规则(即每个数据集一个)平均有趣度值,然后计算相关性,同时我们先计算等级相关性,然后计算下一个数据集的平均值。毫不奇怪,他们的结果与我们非常不同。跨规则的平均化可能会失去关于行为的一些信息。行为应在规则层面而不是在全球层面进行衡量。关于分类器输出差异与分类学习的准确性也有类似的论据(Peterson和Martinez 2005; Lee和Giraud-Carrier 2011)。
在早期的工作中,Tan和Kumar(2000)从统计关系理想的前提出发,分析了一些关于他们与相关概念的匹配程度的趣味性措施,并介绍了自己的有趣度量。 后来,Tan等 (2002年,2004年)通过基于20个客观措施的属性进行比较研究,增加了他们的工作。他们的目的是说明是否有可能使用一小部分精心分离的意外事故表找出最合适的措施,这相当于使用整个数据集找到最佳的措施。它们提供了一些关键属性,可帮助分析人员为特定应用程序选择正确的度量。 他们的结果表明,在某些条件下,许多措施开始相互一致。我们的一些结果证实了这一发现,并将其扩展到更广泛的措施。
Lallich等(2007)从理论观点分析了15个兴趣度量。他们指出了一些与我们所研究的措施之间关系的引理和定理相同的结果。但是,从纯粹的理论视角来看,他们并没有把这些措施的排名摆在同等水平上,这样他们就可以把这15个措施减少到一组11个等同的措施。而Lavra˘c等人(1999)将注意力集中在分类和归纳逻辑编程上,他们还描述了一些理性框架来推理一些有趣的措施。他们甚至提供了一个关于人类专家之间的秩相关性的小的实证分析和一组10个规则的4个措施。再次,我们将这些反思观点与对更多数量的趣味性措施的排名行为进行了彻底的实证研究,从而证实和扩展了这些结果。
最后,我们注意到,我们从数据挖掘中的其他应用中借鉴了基于行为的聚类的思想,在数据挖掘中被用来获取洞察力并帮助选择分类学习算法(Lee和Giraud-Carrier 2011)。 虽然方法不同,但是在关联规则挖掘的上下文中,我们对趣味性度量之间的等价性的动机,分析和结果也可以被认为类似于Meil˘a(2012)关于聚类背景下距离的逻辑等价性的工作 ,以及Fuuml;rnkranz和Flach(2005)在涵盖算法的背景下的搜索
全文共5756字,剩余内容已隐藏,支付完成后下载完整资料
资料编号:[144051],资料为PDF文档或Word文档,PDF文档可免费转换为Word
以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。