1、利用合并搜索发现结构交易摘要 在金融领域的数据挖掘应用中，一个重要的数据预处理步骤就是合并在一段时间内频繁发生的、小额的交易，这类交易被称作“结构”交易。为有效解决该类问题，本文提出一种基于合并搜索策略的增量方法，处理一条新增交易的时间耗费为常量；同时，该方法还支持对已合并交易的撤销处理。 关键词 数据预处理；结构交易；合并搜索；增量式 中图分类号：F8 文献标识码：A 文章编号： 分类号 在金融领域的交易数据库中，存在一种被称作“结构”（structuring）的特殊交易，即对于某个特定的交易主体，在一段时间内频繁发生的多笔小额交易看作是一个“结构”交易1。通常，分析人员需要将“结构”交易看
2、成一笔交易，因此，在利用数据仓库、数据挖掘等应用对交易数据分析前，必须通过预处理过程将这些在时间维上高频度发生的小额交易合并成一笔数额较大的交易。为方便描述，本文就用“结构”交易这一概念指代时间维上高频度发生的交易。 从实际应用出发，数据预处理面对的数据集具有以下特征：1）数据集不按时间顺序更新。由于金融管理机构的数据采集机制基于分散存放、集中上报，再加上业务原因，往往当前要处理的新增交易，其发生日期存在于已经经过合并处理的“结构”记录中；2）要求对交易撤销进行处理。交易撤销指用户取消某一条或多条已提交给银行的交易。尽管与正常交易相比，交易撤销发生的比率非常少，但是从数据准确性出发，在方法设计
3、时必须考虑这一需求；3）数据量大，同时对数据更新频度的要求较高。 综上所述，要求交易合并方法必须满足： 1）支持增量式处理；2）较高的数据处理能力；3）支持对撤销记录的处理。本文提出的交易合并方法达到了以上要求，支持对新增记录或撤销记录的处理，同时，合并一条新增交易的时间复杂度为常量级。 问题描述 根据上文对问题的描述，这里给出形式化的定义。给定交易数据集D，该数据集由 N 条交易（T1, T2, , TN）组成，其中交易 Ti（i = 1, 2, , N）用（ UID, Date, Amount）表示， Ti.UID 代表交易 i 的交易主体标识符，Ti.Date 代表发生时间，而 Ti.A
4、mount 为交易发生额。用UID 对 D 分组，得到不同交易主体发生的所有交易列表，取其中任一列表记作 d，令 d = T1, T2, , Tn，有 interval(Ti, Tj)（i,j = 1, 2, , n)表示交易 Ti 和 Tj 发生日期之间的间隔天数。假定用户自定义参数 min-interval 表示最小间隔，那么当 interval(Ti, Tj) = min-interval 时，Ti 和 Tj 被认为是同一个“结构”交易的子交易，在这里，需要考虑传递性，即如果同时有 interval(Tk, Ti) = min-interval，则 Tk 和 Tj 也被认为是同一个“结构
5、”交易的子交易。本文所提出方法的任务就是要从 D 中找到各交易主体的“结构”交易，并将构成“结构”交易的子交易合并成为一笔交易，称作“合并后的结构交易” ，形式如（BeginDate, EndDate, AmountSum） ，BeginDate 和 EndDate 表示该交易的起始和终止日期，AmountSum 表示交易总额，这些“合并后的结构交易”的集合记作 StrukTrans， 。 解决该问题的一般方法是：1）用 UID 分组、Date 作为关键字对各组排序；2）从各组第一条交易开始，依次计算相邻两笔交易的 interval，直到 interval（Ti+1, Ti）大于 min_in
6、terval 为止；3）将 T1, T2, , Ti 按上文形式合并，然后从 Ti+1 开始继续步骤 2）直到该组的所有交易访问完毕。对于新增交易的处理，有两种情况，一种是新增交易按时间顺序加入，则只需与 StrukTrans 最后一笔交易的终止日期比较，新增一条交易的时间耗费为常量；另一种是新增交易没有按时间顺序加入，这时就需要从 StrukTrans 中查找该交易所属的“结构” ，那么新增这样一条交易的最少时间耗费为 O(logk)，其中 k 为 StrukTrans 中包含的交易数量。对于撤销交易的处理，考虑下面一种情况，存在这样一个 Ti，使得 interval(Ti, Ti-1)=
7、interval(Ti+1, Ti)= min-interval，经过上述步骤的处理，Ti-1、Ti 和 Ti+1 合并在一起，这时如果需要撤销交易Ti，则 Ti-1 和 Ti+1 应当分属不同的“结构”交易，但由于 StrukTrans中没有记录子交易的发生时间，因此无法增量处理这种“结构”分裂的情况。 针对上述问题，本文提出一种基于合并搜索策略的增量方法，处理一条任意情况的新增交易的时间复杂度为常量级；同时，该方法还支持对已合并交易的撤销处理。 合并及撤销 将交易看成一个集合，那么合并同属一个“结构”的子交易就是不相交集合的合并操作，判定新增交易应属哪个“结构”也就是搜索该交易所属集合的操
8、作，因此，本文提出的方法将基于树结构的合并搜索策略，用该策略实现一系列集合的合并搜索操作接近线性时间2。 为方便表述，这里只描述对某一个特定交易主体的发生交易集合 d的处理。给定数据集 d = T1, T2, , Tn，令 d 的时间跨度（天数）为 span ，即 d 中起始日期和终止日期的间隔数，这里使用一个长度为span 的数组 S，S 中的一个元素代表处于时间跨度中的一天，该数组记录集合的树形表示，其中每个元素都是一个三元组（Parent, TNum, Amount） ，如果该元素为根节点，则 Parent 为一负整数，Parent 的绝对值表示该集合的时间跨度（天数） ，知道初始日期和
9、时间跨度就能表示“结构”记录的起始和终止日期；TNum 表示当日的总交易数（注意不是集合的交易总数） ，Amount 为该集合的交易总金额；如果该元素为非根节点，则 Parent 代表该节点的父亲节点在数组 S 中所处的位置，TNum 为当日发生的总交易数，Amount 则为当日发生的交易总金额。 按照以上描述，在首次处理交易集合时，S 中每个元素的三元组形式为：（0, null, null） ，读入交易 Ti，首先找到该交易在 S 中的位置 j = interval(Ti, T1) + 1，然后判断 Sj.Parent 是否为 0，如果是则令Sj的三元组为（-1, 1, Ti.Amount）
10、 ，并判断在下标 j - min-interval和 j 之间有没有 Parent 不为 0 的元素，有则修改 Sj的 Parent，使其指向这些元素的父亲节点，完成集合的合并，并修改合并后代表新集合的根节点的 Amount 值，接下来还需要对下标在 j 和 j + min-interval之间的元素做同样操作。为方便对撤销交易的处理，这里合并操作需要遵循一个准则：保证合并后的树是一棵有序树，即树的节点按照从上至下、从左至右的顺序在数组中进行排列；如果 Sj.Parent 不为 0，那么处理相对简单，不需要合并操作，只需要将 Sj.TNum 增加 1，Sj.Amount 累加新交易的金额 Ti
11、.Amount，同时修改 Sj所在集合的根节点的 Amount；至此，对交易 Ti 的处理完毕。例：假设 min-interval = 1，读入第一条交易 T1，则 S1 = (-1, 1, T1.Amount)，这是读入交易T2，如果 T2 与 T1 发生在同一天，则数组 S 为：S1 = (-1, 2, Amount + T2.Amount)；如果 T2 发生在 T1 的第二天，则数组 S 为：S1 = (-2, 1, Amount + T2.Amount)，S2 = (1, 1, T2.Amount)；如果 T2 与 T1的时间间隔大于一天，则 S1不变，Sinterval(T2, T1
12、) + 1 = (-1, 1, T2.Amount)。 由以上描述可以看到，对于新交易的处理，无论形成一个新集合还是并入一个已有的集合，都能用常量时间完成。文本接着描述对撤销交易的处理。假设给定一个已经由上述合并方法处理过的交易 F，F.Date和 F.Amount 分别代表该交易的发生日期和金额，撤销该交易会产生以下两种操作：1）当日交易的笔数大于 0；或者当日交易的笔数等于 0，同时 F.Date 的左右两个最近且不为空的元素之间的间隔要小于等于min_interval；这时的操作是修改当日三元组，将 TNum 减 1，并减少当日的交易额度，以及修改该日所在集合的总金额数；2）当日交易的笔
13、数等于 0，同时 F.Date 的左右两个最近且不为空的元素之间的间隔要大于min_interval；这时需要将代表该日期的元组置空，并将该集合一分为二，也就是将代表该集合的一棵树分裂为两棵，分裂方法如下：根据上文，由合并方法得到的树是一棵有序树，分裂只需从这棵有序树中删除日期为 F.Date 的节点，形成两棵新树，一棵由该集合中数组下标小于被删除节点的元素组成，另一棵是大于被删除节点的元素，前者的树形式保留原状，但后者需要指定根节点，以后面集合的第一个元素作为根节点即可。撤销交易的处理需要重新计算子树的交易额，但除此之外，没有比该操作更耗时的计算了，即使是重构一个子树，也只是为出现在与被删除
14、节点同层，且处于其右节点后的所有节点的 Parent 指向新的根节点的位置，而这些需要重新定向的节点数量是有限的。 算法描述 根据本文第 2 节描述的方法，这里给出形式化的算法，由主过程合并 Merge 及撤销 Back 两个算法组成。d 代表已根据日期排序的某交易主体的交易集合，S 为代表集合的主要数据结构，min_interal 为用户自定义阈值，而 TBegin 代表 d 的起始日期和终止日期。FrequentMerge 中Initial(S)对数组 S 初始化；ReadRecord()则从 d 中读入记录，并将指针指向下一条；Interval()如前所述，求得两个日期之间的间隔日；Le
15、xist(i)和 Rexist(i)分别返回 Si的左右 min_interval 之间 Parent不为 0 的最近元素。而 Modify(s)则表示修改树的根节点 s 的三元组，主要为累加或减少交易跨度和交易总金额。Back 中 LNeighbor(i)/ RNeighbor(i)返回离 Si最近的左边/右边同时 parent 不为 0 的节点，RNeighbors(s)则指在树形结构中居于节点 s 右边的所有兄弟。 从算法描述可以看出，处理一条新交易的时间复杂度为常量级，而处理撤销交易耗费的时间则和变量 m 成正比，m 最多为撤销交易所在集合的交易数量。 实验及总结 数据源来自国家外汇管
16、理局提供的明细交易数据，从中截取了某交易主体的一段连续交易数据，分别为 200 条、400 条和 800 条，用C#.net 在 P4/1.4G/256M 的 PC 上运行，所耗时间分别为0.5007s、1.0014s 和 2.0030s，算法运行时间为线性，表明同分析吻合；撤销交易处理，处理的交易数为 200 条，为 17.4251s，耗时较多，不过在实际应用中，撤销处理次数少且集中。 本文给出了一种将合并搜索策略这一高效的集合操作的方法用于金融交易数据库，有效解决了现实应用中的交易合并问题，算法基于增量式方法，处理一条新增交易的时间复杂度为常量级；同时，该方法还支持对已合并交易的撤销处理，
17、对撤销交易的处理所耗费的时间则和撤销交易所在集合的交易数量成正比。 参 考 文 献 U.S. Congress, Office of Technology Assessment, Information Technologies for Control of Money Laundering, OTA-ITC-630 Washington, DC: U.S. Government Printing Office, September 1995 余祥宣, 崔国华, 邹海明. 计算机算法基础（第二版）. 华中科技大学出版社, 2000 Finding Structuring Transaction
18、s by Using Union-Find HUBEI WUHAN ELECTRIC POWER SUPPLY COMPANY MAO XIN ABSTRACT In the study of applying Data Mining to financial data analysis, an important field is to finding and merging “structuring” transactions ? a series of transactions with small amount happening frequently. This paper proposes an incremental method using Union-Find. The running time of dealing with a new transaction is a positive constant. The method also supports dealing with repealing transactions. Key words data pre-processing；structuring transaction；Union-Find；incremental
