利用合并搜索發(fā)現(xiàn)結(jié)構(gòu)交易

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

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

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

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

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