利用合并搜索發(fā)現(xiàn)結構交易

1、利用合并搜索發(fā)現(xiàn)結構交易摘要在金融領域的數(shù)據(jù)挖掘應用中，一個重要的數(shù)據(jù)預處理步驟就是合并在一段時間內(nèi)頻繁發(fā)生的、小額的交易，這類交易被稱作“結構”交易。為有效解決該類問題，本文提出一種基于合并搜索策略的增量方法，處理一條新增交易的時間耗費為常量；同時，該方法還支持對已合并交易的撤銷處理。關鍵詞數(shù)據(jù)預處理；結構交易；合并搜索；增量式中圖分類號：F8文獻標識碼：A文章編號：分類號在金融領域的交易數(shù)據(jù)庫中，存在一種被稱作“結構”（struct

2、uring）的特殊交易，即對于某個特定的交易主體，在一段時間內(nèi)頻繁發(fā)生的多筆小額交易看作是一個“結構”交易[1]。通常，分析人員需要將“結構”交易看成一筆交易，因此，在利用數(shù)據(jù)倉庫、數(shù)據(jù)挖掘等應用對交易數(shù)據(jù)分析前，必須通過預處理過程將這些在時間維上高頻度發(fā)生的小額交易合并成一筆數(shù)額較大的交易。為方便描述，本文就用“結構”交易這一概念指代時間維上高頻度發(fā)生的交易。從實際應用出發(fā)，數(shù)據(jù)預處理面對的數(shù)據(jù)集具有以下特征：1）數(shù)據(jù)集不按時間順序更

3、新。由于金融管理機構的數(shù)據(jù)采集機制基于分散存放、集中上報，再加上業(yè)務原因，往往當前要處理的新增交易，其發(fā)生日期存在于已經(jīng)經(jīng)過合并處理的“結構”記錄中；2）要求對交易撤銷進（BeginDateEndDateAmountSum），BeginDate和EndDate表示該交易的起始和終止日期，AmountSum表示交易總額，這些“合并后的結構交易”的集合記作StrukTrans，。解決該問題的一般方法是：1）用UID分組、Date作為關鍵字對

4、各組排序；2）從各組第一條交易開始，依次計算相鄰兩筆交易的interval，直到interval（Ti1Ti）大于min_interval為止；3）將T1T2…Ti按上文形式合并，然后從Ti1開始繼續(xù)步驟2）直到該組的所有交易訪問完畢。對于新增交易的處理，有兩種情況，一種是新增交易按時間順序加入，則只需與StrukTrans最后一筆交易的終止日期比較，新增一條交易的時間耗費為常量；另一種是新增交易沒有按時間順序加入，這時就需要從Stru

5、kTrans中查找該交易所屬的“結構”，那么新增這樣一條交易的最少時間耗費為O(logk)，其中k為StrukTrans中包含的交易數(shù)量。對于撤銷交易的處理，考慮下面一種情況，存在這樣一個Ti，使得interval(TiTi1)=interval(Ti1Ti)=mininterval，經(jīng)過上述步驟的處理，Ti1、Ti和Ti1合并在一起，這時如果需要撤銷交易Ti，則Ti1和Ti1應當分屬不同的“結構”交易，但由于StrukTrans中沒有