数据和知识工程外文翻译资料

 2022-12-25 12:30:16

英语原文共 24 页，剩余内容已隐藏，支付完成后下载完整资料

数据和知识工程

摘要

近年来，许多应用领域对计算余弦相似性的兴趣越来越大。大多数先前的研究需要指定最小相似度阈值来执行余弦相似度计算。但是，用户通常很难在实践中提供适当的阈值。相反，在本文中，我们建议搜索由余弦相似度测量的顶K强相关物体对。具体而言，我们首先确定余弦测度上界的单调性质，并利用对角遍历策略来开发TOP-DATA算法。另外，我们观察到，对角遍历策略通常会导致更多的I / O成本。因此，我们制定了最大优先遍历策略并提出了TOP-MATA算法。理论分析表明，TOP-MATA具有节省假阳性项目对计算的优点，并且可以显着降低I / O成本。最后，实验结果证明了TOP-DATA和TOP-MATA算法的计算效率。此外，我们还表明，TOP-MATA特别适用于具有大量项目的大规模数据集。

1.介绍

给定一系列关于共生项目的项目（对象）和观察数据，关联分析涉及确定强烈相关的项目子集。关联分析已经成为数据挖掘领域的核心问题之一，在许多应用领域如市场篮子分析[2]，气候研究[30]，公共健康[10]和生物信息学[23 ，37]。例如，在市场篮子研究中，关联分析可以找到对促销，货架管理和库存管理有用的模式。另外，在医学信息学中，关联分析可以用于发现药物相互作用。

虽然已经开发了多种可扩展方法来挖掘关联分析中的频繁模式，但传统的支持与置信框架在找到有趣的关系方面显示出其局限性[13,14,33]。为了应对这一关键挑战，统计相关性或相似性度量已经被用于挖掘关联模式[32]，如lift，chi;2[7]，连贯性和余弦相似性。然而，由于缺乏对计算友好的财产，大多数这些措施仅用于后期评估。

本文中，我们专注于开发用于查找由余弦相似度测量的顶K强关联项对的高效算法，该算法已被广泛用作文本挖掘中高维数据的流行相似度度量[31,43]，信息检索[5,29]和生物信息学[20]。事实上，搜索顶级K强相关项目对在许多真实世界的应用程序中都有很大的用处。一个很好的例子是根据这些查询的搜索结果的相似性找到顶级K类似的查询来提出替代查询公式[28]。另一个例子是通过在大量项目中搜索具有类似用户偏好的前K商品来推荐替代商品。

事实上，余弦相似性是少数几个保持对称性，三角不等式，零不变性[25]和交叉支持性质[39]的有趣度度量之一。然而，支持和提升等许多措施并不能满足这些特性。而且，余弦相似性非常简单，并且具有真正的意义;即测量两个矢量的角度差。这使得余弦相似度对于测量高维空间中的接近度特别有用。

为此，我们首先提出一种名为TOP-DATA的对角遍历算法来搜索顶K强关联对。 TOP-DATA可以利用余弦上界的单调性质来有效地修剪项目对，而无需计算其精确的余弦值。通过使用边界向量，我们进一步降低了O（N2）空间复杂度，以将检查状态保存为O（N）。然后，我们提出一种新颖的TOP-MATA算法，该算法采用最大优先遍历策略来搜索top-K对。理论分析表明，TOP-MATA具有降低I / O成本的能力，并节省了假阳性项目对的余弦相似度计算。

最后，我们对各种实际数据集进行了实验。结果显示，与蛮力方法相比，TOP-DATA和TOP-MATA算法对于找到顶K项目对显示出显着的计算优势。特别是，TOP-MATA在大量数据集上拥有比TOP-DATA更好的性能。我们还将TOP-MATA与TKCP [16]进行了比较，TKCP是一种使用FP-tree [15]查找top-K对的完善算法。结果表明，当K小于所有对的数量时，由于最大优先遍历策略的高效剪枝效应，TOP-MATA具有更好的性能。

1.1 大纲

本文的其余部分安排如下。第2节介绍相关工作。在第3节中，我们介绍一些预备并定义问题。第4节提出了TOP-DATA算法。在第5节中，我们给出TOP-MATA算法并提供理论分析。第6节显示了实验结果。最后，我们在第7部分结束这项工作。

2.相关工作

2.1有趣的措施

在文献中，从大规模的基于项目的数据集中挖掘有趣模式有许多有趣的措施。例如，Piatetski-Shapiro提出规则的统计独立性作为一种有趣的度量[26]。 Brin等人[7]提出升力和chi;2作为相关性措施，并开发出一种有效的采矿方法。 Blanchard等人[6]设计了一个基于信息论的规则感兴趣度量，定向信息比率。 Hilderman和Hamilton [17]和Tan等人。 [32]分别为有趣的措施提供了组织良好的比较研究。

在可用的有趣度测量中，余弦相似性获得了特别的兴趣。例如，Omiecinski [25]和Lee等人[24]揭示了余弦是零不变的，因此是在交易数据库中挖掘有趣关系的好方法。事实上，余弦相似性是少数几个有对称性，三角不等式，零不变性[32]和交叉支持性质[39]的有趣度量度之一。在[34]中，吴等人。扩展了包含多项集余项的余弦相似度在内的一些度量，进一步显示了关联分析余弦相似度的值。本文的工作重点是计算高维空间中项目对的余弦相似度。

2.2挖掘有趣的模式

使用上述有趣性度量的一个关键挑战是缺乏计算友好的属性，如反单调属性[1]，可用于高效计算。因此，很难将这些措施直接纳入挖掘算法。事实上，由于上​​述原因，大多数现有的措施，如余弦和phi;系数常常被用作后评估措施[32]。

为了迎接这一挑战，熊等人。引入了phi;系数的上界，并提出了TAPER算法来有效计算全强对相关[38]。沿着同样的路线，伊利亚斯等人。 [18]也提出了一种有效识别相关对的方法，该方法应用了抽样技术。由于抽样的性质，这种方法无法避免发现假阳性和假阴性的相关性。 Zhang和Feigenbaum [42]也提出了一种简单的随机算法，其假阴性概率可以忽略不计。 Zhou和Xiong [44]提出了CHECK-POINT算法，通过设置检查点来建立计算缓冲区，从而有效地计算流数据集的全强对关联。然而，这些方法需要一个有趣的阈值，这在实践中往往很难找到。

为了解决上述问题，熊等人[36,40]提出TOP-COP算法来有效地计算top-K相关对，这是首次使用对角遍历策略的研究。我们在这项研究中的TOP-DATA算法对余弦相似性也采用了类似的对角线遍历策略，但是我们通过使用边界向量将其改进为TOP-DATA-R。更重要的是，我们开发了最大优先遍历策略并提出了TOP-MATA算法。理论和实验研究表明TOP-MATA比TOP-DATA-R在节省计算成本和I / O成本方面的优势。他等人。 [16]还提出了一种称为TKCP的算法，通过使用FP-tree [15]来找到顶K相关对。但是，TKCP需要遍历所有对，而TOP-MATA使用最大优先遍历方法避免假阳性对。因此，当K不是很大时，TOP-MATA具有显着的修剪效果，并且比TKCP显示出更好的性能。详细信息见实验部分。

寻找感兴趣的对的问题与信息检索社区中的所有对相似性搜索问题有着密切的关系，已经在许多应用领域中使用[21,22,27]。该领域的早期研究密切关注使用各种近似技术[11,12,19]来解决这个问题，但最近的趋势是计算相似性并准确找到所有的对。有三种主要的方法分别是基于索引的方法[5,8]，基于前缀过滤的方法[5,9,35]和基于签名的方法[3]。上述研究集中在找出二进制或非二进制对以及某些给定阈值以上的某些特定相似性度量。最近，Awekar等人。 [4]研究了增量搜索候选对以改变相似度阈值的问题。肖等人。 [35]研究了用于近似重复检测的top-K集合相似度连接问题，该算法按照递减顺序列举了所有“必要”相似阈值，直到找到top-K集合。从这个角度来看，它也可以被看作是使用不同的相似性阈值的增量算法。相比之下，本研究的工作目标是找到有趣的配对与顶部K余弦相似度值，而不设置任何兴趣度阈值。而且，TOP-MATA可以避免使用新颖的最大优先遍历策略计算假阳性对。

3.初步和问题定义

余弦相似度是两个高维向量之间相似度的量度。 实质上，它是两个向量之间角度的余弦值。 也就是说，给定两个向量X和Y，

其中“lt;gt;”表示两个向量的内积，“‖”表示向量的L2范数。对于具有非负元素的矢量，余弦相似度值始终位于[0，1]的范围内，其中1表示两个向量完美匹配，而0表示完全相反。

在实际应用中，矢量通常由二元属性值（0或1）组成。例如，商品的购买记录是典型的二元矢量，其中“1”表示在某些交易中购买此商品，而“ 0“表示在另一个事务中的省略。又例如，在文档数据集中，一个词可以用二进制向量来表示，其中每个维度表示该词是否出现在特定文档中。对于一对二进制向量，我们可以将二进制信息提取到双向表中，如表1所示。在表中，nij（i，jisin;{0,1}）表示维数的属性值对于X和Y分别是i和j。最后，ni = ni0 ni1，n j = n0j n1j，N =Sigma;i，jnij。

根据表1，等式（1）可以等价地转换成

从频繁集合采用的支持度量的角度来看，我们有supp（XY）= n11 / N，supp（X）= n1 / N，supp（Y）= n等价地转换为：

现在，假设在市场购物篮数据集中有n个不同的商品，每个商品都以二元向量为特征。 然后我们制定我们的问题如下：

问题定义. 给定项集I = {X1，X2，...，Xn}，其中每个项由二进制向量表示，找到其余弦相似度值在最高K值之间的K对项。

显然，解决这个问题的一种方法是以蛮力的方式计算n（n-1）/ 2对的所有余弦相似值，然后选择top-K。 但是，计算所有2项支持的成本通常非常高。 如果n变得非常大，这可能会更糟 - 太大而无法加载到主存储器中 - 事实上，这是市场购物篮数据集的常见情况。 而且我们也应该考虑到余弦值排序的高成本。 因此，我们应该找到一个更有效的方法来计算top-K对。

表一

X和Y的双向表格。

4.找到top-K余弦相似度：对角线遍历算法

在本节中，我们研究如何使用对角遍历策略找到顶点K余弦相似度。 我们首先给出一个简单的余弦相似性的上界如下。

4.1. 余弦相似度的上界

对于两个项目X和Y，不失一般性，我们假设supp（X）ge;supp（Y）。 根据支持的定义，我们有

Sup(XY) le;supp(Y).

因此，

因此，我们得到了cos（X，Y）的上界，表示为

接下来，我们制定上限的属性。

属性1单调性. 给定supp（X）给定两个项目X和Y，其中supp（X）ge;supp（Y），upper（cos（X，Y））单调递增（递减） supp（Y））是固定的。

备注. 由于属性1的证明很简单，我们在此省略。 upper（cos（X，Y））的优点在于两个方面。 首先，为避免supp（X，Y）的计算，上界的计算比原始余弦相似性更有效。 当物品数量非常大时，这是非常重要的，例如超过1,000,000。 其次，上限具有单调性质，这对于有效搜索top-K二进制对是至关重要的。 我们在下面详细说明。

4.2.对角遍历算法

在这里，我们引入一个对角遍历过程来找到具有顶K余弦相似度值的二进制对（为简单起见，我们称它们为“顶K对”）。该算法的关键点在于使用余弦相似度的上界及其单调性。

4.2.1.上界的过滤效果

假设我们有n个项目。直观地说，我们可以在计算所有n（n-1）/ 2对的余弦相似度值期间构建和维护top-K对列表。 top-K列表的更新规则如下：1）计算新二进制对的余弦值; 2）如果此值大于当前top-K对中的最小值，则新对应替换最小值对。但是，直接计算2项支持supp（XY）的成本非常高。所以第一点是过滤具有小余弦上限的项目对。令minCos表示当前top-K列表中对的最小余弦值，我们有一个简单的引理如下。

引理1.一个新对{X，Y}只有在以下情况下才能进入顶K列表

上部(cos(X,Y))ge;minCos：

备注.由于这个引理的证明很简单，我们在这里省略它。根据这个引理，我们可以使用上界作为一个过滤器来过滤掉不能进入顶K列表而不计算它们的精确余弦相似值的二进制对。也就是说，对于任何新的对{X，Y}，我们首先计算upper（cos（X，Y））。如果upper（cos（X，Y））ge;minCos，我们进一步计算cos（X，Y）来检查cos（X，Y）ge;minCos。否则，我们只需跳过这一对而不计算cos（X，Y）。我们在此称之为上界的“过滤效应”。显然，如果我们可以在整个计算过程的初始阶段找到一个具有较高minCos的顶K列表，那么过滤效果将非常显着。

4.2.2. 上限的剪枝效应

接下来的任务是通过设计一个高效的修剪策略来进一步减少余弦相似度计算。 为此，我们应该利用上界的单调性。

4.2.2.1。排序的项目矩阵。假设我们有n项：{X1，X2，...，Xn}。我们首先按支持降序排序项目。这会导致排序的项目序列

其中supp（X [i]）ge;supp（X [j]）如果if ilt;j。根据排序的项目序列，我们可以建立一个二维排序的项目矩阵M =Sotimes;S，如图1（n = 6）所示。请注意，由于余弦相似性是对称的，我们只需要考虑上三角矩阵UM。

4.2.2.2.对角遍历程序。这里我们通过排序的项目矩阵来说明对角线遍历过程。假设我们需要从1

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[24664]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章