关键字 |
| 频繁模式，收缩树，可能的世界语义，不确定的数据库 |
介绍 |
| 数据挖掘是从大型数据库中提取隐藏信息的过程，这是一项强大的技术，具有巨大的潜力，可以帮助公司专注于数据仓库中最重要的信息。数据挖掘工具预测未来的趋势和行为，允许企业做出实际的、知识驱动的决策。数据挖掘提供的自动化、前瞻性分析超越了决策支持系统典型演示工具所提供的对过去事件的分析。数据挖掘工具可以回答传统上过于耗时而无法解决的业务问题。他们清理数据库中隐藏的模式，找到专家可能会错过的预测信息，因为这些信息超出了他们的预期。数据挖掘已经准备好在商业领域应用，因为它有三种技术的支持，这些技术现在已经足够成熟: |
| •海量数据收集 |
| •强大的多处理器计算机 |
| •数据挖掘算法 |
| 随着无线通信技术的飞速发展和功能强大的便携式设备的日益普及，移动用户不仅可以随时随地获取全球范围内的信息，还可以使用移动设备轻松地进行商业交易，例如通过数字钱包进行交易。同时，位置采集技术的可用性，如全球定位系统(GPS)，便于获取移动轨迹，记录用户的运动历史。因此，我们设想，在未来的移动商务(MCommerce)时代，一些移动商务服务将能够捕捉用户的移动轨迹和购买交易。以最近公布的Shop kick为例，当手机用户在商店和商品中签到时，它会为用户提供奖励和优惠。预计到一些用户可能会愿意用他们的位置和交易来换取良好的奖励和折扣，我们预计未来会出现更多的移动商务应用，无论它们是否会承担类似于Shop kick的商业模式。本项目旨在开发模式挖掘和预测技术，探索移动用户的移动行为和购买交易之间的相关性，以探索潜在的移动商务特征。由于web2.0技术的快速发展，许多商店已经把他们的商店信息，如营业时间、位置和功能，通过地图服务，如谷歌地图，在网上提供。此外，当用户移动时，支持gps的设备可以检测到用户的轨迹。当用户进入建筑物时，用户可能会失去卫星信号，直到返回室外。通过匹配用户轨迹和商店位置信息，可以提取用户在某些商店区域内的商店间移动序列。 In this proposed system we consider the mining p-FSPs using Systolic tree which accelerates the speed of processing than the existing works. Data mining, which is the exploration of knowledge from the large set of data, generated as a result of the various data processing activities. Frequent Pattern Mining is a very important task in data mining. The previous approaches applied to generate frequent set generally adopt candidate generation and pruning techniques for the satisfaction of the desired objective. Frequent pattern mining in transaction database is one of the well-studied problem in data mining. One obstacle that limits the practical usage of frequent pattern mining is the extremely large number of patterns generated. Such a large size of the output collection makes it difficult for users to understand and use in practice. Even restricting the output to the border of the frequent itemset collection does not help much in alleviating the problem. |
相关工作 |
| 在[4]中可以找到对传统数据挖掘问题的全面调查，例如在不确定数据的背景下的频繁模式挖掘。我们只详细介绍了FSP挖掘中出现的一些概念和问题。 |
| A.不确定数据的频繁序列模式挖掘 |
| 该研究基于两个不确定序列数据模型，这是许多现实生活应用的基础，他们提出了两种新的U-PrefixSpan算法[1]，从符合我们的序列级和元素级不确定序列模型的数据中挖掘p-FSPs。我们还设计了三个剪枝规则和一个早期验证方法来加快模式频率检查。这些规则能够提高采矿效率。在合成数据集和真实数据集上的实验表明，我们的两种U-PrefixSpan算法有效地避免了“可能的世界爆炸”问题，PA和NA的逼近方法非常高效和准确。该方法考虑了在不确定序列数据的背景下挖掘fsp的问题。与以往采用预期支持来度量模式频率的方法不同，我们提出基于可能的世界语义来定义模式频率。相对于正式的概率数据模型，这种方法可以更有效地挖掘高质量的模式。我们开发了两个不确定序列数据模型(序列级模型和元素级模型)，从许多涉及不确定序列数据的实际应用中抽象出来。基于这些模型，我们定义了挖掘概率频繁序列模式(或p-FSPs)的问题。由于模式增长频繁，单个基于最小支持度的应用程序会出现低支持度或高支持度的情况，因此设置罕见的关联规则来处理不可预测的项是一项困难的任务。如果将最低支持设置得很高以覆盖很少出现的道具，那么它将错过涉及稀有道具的频繁模式，因为稀有道具无法满足较高的最低支持。在文献中，努力提取具有多个最小支持度的罕见关联规则。 Some problems of the existing system are : Less performance on customer learning and Not adaptive as to customer needs. |
提出工作 |
| 随着技术特色的不断发展，面向电子商务的数据挖掘将是一个非常有前景的领域。它可以自动预测客户消费趋势，市场趋势，指导公司使用移动商务技术建立个性化的商业智能。在我们的任务中，我们没有预定义的类标签。事实上，购物车中的所有项目都成为属性，必须预测其他项目的存在/缺席。所需要的是一个可行的规则生成算法和有效的方法来使用生成的规则。对于购物车中所有缺失物品的预测，我们的算法称为收缩树方法，它通过使用项目集树(it树)来加快计算速度，然后使用DS理论概念来组合生成的规则。所提出的规则生成算法使用从训练数据集中创建的标记it树。该算法将传入项集作为输入，并返回一个图，其中定义了给定传入项集所包含的关联规则。收缩树[5]是流水线处理元素(PEs)在多维树模式中的排列。我们的体系结构的目标是模拟FP-growth算法的内部内存布局，同时实现更高的吞吐量。在FPGA硬件中映射的收缩树的作用类似于在软件中使用的fp树。 Ecommerce companies are faced with a wealth of data, lack of knowledge of discomfiture.To really take advantage of this domain, however, data mining must be integrated into the e-commerce systems with the appropriate data transformation bridges from the transaction processing system to the data warehouse and vice-versa.We proposed this work which provides solution for the best use of these rich data make the e-commerce more effective and analyzing about this data mining in order to fully understand customer preferences, buying patterns, design to meet the needs of different customer groups. Let us consider an example of Mobile Commerce where the users are allowed to use the application to extract the information that they need in considering the sales options. With the help of this application our proposed system could be exposed as shown in the Figure.1.It shows the process of pattern mining by p-FSPs that uses systolic tree approach to speedup the mining process as well as the techniques can be restricted using the pruning methods to specify only the required or relevant data regarding the specified constraints which makes mining effective in the purpose of commercial activities. |
| A.关联规则学习: |
| 在数据挖掘中，关联规则学习是一种流行且研究较好的方法，用于发现大型数据库中变量之间有趣的关系。皮亚茨基-夏皮罗描述了用不同的兴趣度度量方法分析和展示在数据库中发现的强大规则。Agrawal等人基于强规则的概念，在超市POS系统记录的大规模交易数据中引入关联规则，用于发现产品之间的规律。例如，规则{洋葱，土豆}?在超市的销售数据中发现{Burger}，这表明如果一个顾客同时购买洋葱和土豆，他或她很可能也会购买汉堡肉。此类信息可作为有关促销定价或产品植入等营销活动的决策依据。 |
| B.系统流程图 |
| 根据注册客户提出的请求，采用模式挖掘的方法处理查询可用的详细信息等功能，在系统提供的列表中进行选择。系统从数据库中引用注册数据，寻找特定领域的解决方案，采用所提出的收缩树方法处理频繁的顺序挖掘，以尽可能快地响应请求。通过GPS轨迹跟踪技术来跟踪移动环境，从而考虑了该域。通过对域数据库的预处理来延续系统流程，并从系统中挖掘出提供所需信息的模式。通过考虑预处理技术和频繁模式挖掘之间的流程，确定频繁顺序项集，建立数据库并添加请求者进一步更改的细节，保持数据库的一致性，以收集更新的信息。更新后的记录用于未来的模式识别。 |
| C.移动移动过程 |
| 管理二维(或更高)空间中移动物体的信息对于交通监控、飞行控制、移动计算等几个新兴应用来说非常重要。为了避免频繁的位置更新，数据库存储了每个对象o的运动函数o(t)，该函数返回其位置。移动商务服务将能够捕捉用户的移动轨迹和购买交易。移动轨迹预测可用于非线性模型。非线性模型利用复杂的回归函数来捕捉物体的运动。因此，它们的预测精度高于线性模型。递归运动函数(RMF)是文献中基于回归函数的最准确的预测方法。 |
| D.频繁的道具创造 |
| 在这一阶段，我们利用移动事务数据库应用收缩树算法来挖掘每个用户的频繁事务(FTransactions)。首先，为每个用户计算每个(商店、商品)对的支持。当频繁的1-事务的支持度满足用户指定的最小支持度阈值TSUP时，得到它们的模式。候选2-事务(表示在事务中同时购买两个商品)是通过连接两个频繁的1-事务(其中用户标识和存储都相同)而生成的。例如，候选2-事务是通过连接生成的，因为它们的用户标识和购买的存储分别是U1和F。因此，当它们的支持大于tup时，我们将模式保持为频繁的2-事务模式。最后，重复相同的过程，直到不再生成候选事务为止。我们使用一个项目映射表来重新标记项目集，以便为每个唯一的项目集呈现f -事务，我们使用一个符号LIi(大型项目集i)来表示它，其中i表示一个运行数。映射过程可以减少检查移动交易序列中是否包含移动商务模式所需的时间。 |
| E.收缩树过程 |
| 收缩树是流水线处理元素(pe)在多维树模式中的排列。我们的体系结构的目标是模拟收缩树算法的内部内存布局，同时实现更高的吞吐量。在FPGA硬件中映射的收缩树的作用类似于在软件中使用的U-PrefixSpan。直接将软件算法转换为硬件架构并不总是实际或有效的。我们的方法是基于最大节点度估计来构建树。当树中某一点的实际节点度超过估计节点度时，将找不到某个频繁项集。假设数据库中的条目数为n，估计的最大节点度估计为K，估计的收缩树深度为W。静态树结构中的每个节点都有K个子节点。树中的节点总数为 |
 |
| 当K很大时，每个节点的子节点数量也很大，这反过来又要求每个节点具有大量的接口。这将使每个节点的内部结构非常复杂。为了简化节点的复杂性，我们为每个节点分配了两个而不是K个接口。两个接口中的一个专用于与其第一个子接口的连接，另一个连接到其最近的兄弟接口。在我们的收缩树结构中，从任何PE到对照PE只有一条路径，因为每个PE都有唯一的父PE。听写的主要原则是，包含查询的候选项集的任何路径都将被报告给控制节点。注意，该路径可能包含比查询项集更多的项。为了阐明听写算法，我们假设每个PE中有两个门。正确的门永远是敞开的。图2为K=2, W=3时的静态收缩结构。 |
| 收缩树结构中的每个节点也被称为一个处理元素(PE)。每个PE都有自己的本地数据结构和接收外部信号时的相应操作。在这个图中有三种处理元素。根PE是上面讨论的控制节点。最右边一列的PEs是计数节点，专门用于频繁项集听写，我们将在后面讨论。第三类加工要素是一般的PEs。收缩树中的每个PE都有三种模式:WRITE模式、SCAN模式和COUNT模式。 |
| WRITE模式算法的设计原则是，给定相同的事务数据库，构建的收缩树应该具有与fp树相似的布局。软件将候选模式发送到收缩压树。经过一些时钟周期后，收缩树将候选模式的支持计数发送回软件。该软件将支持计数与支持阈值进行比较，并决定候选模式是否频繁。在软件中使用支持阈值检查所有候选模式后，进行模式挖掘。获取候选模式支持度计数的方法称为候选项集(模式)匹配。利用SCAN模式确定候选项集的听写过程。在收缩树结构中使用的方法是我们所说的候选项集听写。当我们想要检查一个给定的项目集是否频繁时，它被发送到收缩树。经过一些时钟周期后，将在收缩树的输出中获得项集的数目。 The dictation must be performed after t he systolic tree is built. When the tree is in itemset dictation phase, PEs are in SCAN mode. In our systolic tree To clarify the dictation algorithm, we seem there are two doors in each PE. The right door is always open. The bottom door is locked when no data should be sent to the children. Once all items in a candidate itemset are sent to the systolic tree, a control signal signifying the COUNT mode is broadcasted to the whole systolic tree. The architecture of the systolic tree will change accordingly with response to the COUNT mode signal. |
结论及未来工作 |
| 本文研究了不确定数据库中概率频繁序列模式(p-FSPs)的挖掘问题。我们的研究建立在两个不确定序列数据模型上，这两个模型是许多现实应用的基础。我们提出了收缩树算法来从符合我们的序列级和元素级不确定序列模型的数据中挖掘p-FSPs。我们还设计了一种验证方法来加快可限制在边界内设计的模式频率检查。所实施的规则能够提高采矿效率。基于泊松分布和正态分布，我们设计了两种近似方法来验证模式的概率频度。在合成数据集和真实数据集上的实验表明，我们的收缩树算法有效地避免了“可能的世界爆炸”问题，逼近方法PA和NA是非常高效和准确的。我们的初步实验表明，通过仔细选择收缩树的大小，与目前的软件方法相比，挖掘时间可以大大加快。未来的工作可以扩展到确定用户规范的概率，以保证质量和识别的结果。 |
|
数字一览 |
 |
 |
| 图1 |
图2 |
|
|
参考文献 |
- 周昭，阎达，Wilfred Ng，“在大型不确定数据库中挖掘概率频繁序列模式”，2014。
- M. Muzammal和R. Raman，“从概率数据库中挖掘序列模式”，第15期PAKDD，中国深圳，2011。
- 陈宏，顾文生，王宏，和孙文泰，“利用时空冗余进行RFID数据清理”，美国印第安纳波利斯，2010年。
- 李玉华，王俊杰，王俊杰，“基于不确定数据的频繁模式挖掘”，第15届计算机科学与技术会议，2009。
- 孙松，乔素泽，“具有收缩树的采矿关联规则”，2008。
- F. Giannotti, M. Nanni, F. Pinelli，和D. Pedreschi，“轨迹模式挖掘”，Proc. 13 ACM SIGKDD，圣何塞，CUSA, 2007。
- J. Pei等人，“前缀跨度:通过前缀预测模式增长有效地挖掘顺序模式”，第17届ICDE，柏林，德国，2001。
|
菜单
