利用合并搜索发现结构交易利用合并搜索发现结构交易 摘要 在金融领域的数据挖掘应用中，一个重要的数据预处理步骤就是合并在一段时间内频繁发生的、小额的交易，这类交易被称作“结构”交易。为有效解决该类问题，本文提出一种基于合并搜索策略的增量方法，处理一条新增交易的时间耗费为常量；同时，该方法还支持对已合并交易的撤销处理。 关键词 数据预处理；结构交易；合并搜索；增量式 中图分类号：F8 文献标识码：A 文章编号： 分类号 在金融领域的交易数据库中，存在一种被称作“结构”（structuring）的特别交易，即对于某个特定的交易主体，在一段时间内频繁发生的多笔小额交易看作是一个“结构”交易[1]。通常，分析人员需要将“结构”交易看成一笔交易，因此，在利用数据仓库、数据挖掘等应用对交易数据分析前，必须通过预处理过程将这些在时间维上高频度发生的小额交易合并成一笔数额较大的交易。为方便描述，本文就用“结构”交易这一概念指代时间维上高频度发生的交易。 从实际应用出发，数据预处理面对的数据集具有以下特征：1）数据集不按时间顺序更新。由于金融管理机构的数据采集机制基于分散存放、集中上报，再加上业务原因，往往当前要处理的新增交易，其发生日期存在于已经经过合并处理的“结构”记录中；2）要求对交易撤销进行处理。交易撤销指用户取消某一条或多条已提交给银行的交易。尽管与正常交易相比，交易撤销发生的比率非常少，但是从数据准确性出发，在方法设计时必须考虑这一需求；3）数据量大，同时对数据更新频度的要求较高。 综上所述，要求交易合并方法必须满足： 1）支持增量式处理；2）较高的数据处理能力；3）支持对撤销记录的处理。本文提出的交易合并方法达到了以上要求，支持对新增记录或撤销记录的处理，同时，合并一条新增交易的时间复杂度为常量级。 问题描述 根据上文对问题的描述，这里给出形式化的定义。给定交易数据集 D，该数据集由 N 条交易（T1, T2, …, TN）组成，其中交易Ti（i = 1, 2, …, N）用（UID, Date, Amount）表示， Ti.UID代表交易 i 的交易主体标识符，Ti.Date 代表发生时间，而Ti.Amount 为交易发生额。用 UID 对 D 分组，得到不同交易主体发生的所有交易列表，取其中任一列表记作 d，令 d = { T1, T2, …, Tn}，有 interval(Ti, Tj)（i,j = 1, 2, …, n)表示交易 Ti 和 Tj发生日期之间的间隔天数。假定用户自定义参数 m...
