【正文】 ce(oledb) 它們負(fù)責(zé)包含進(jìn)庫(kù)文件 ””和 ””,這兩個(gè)文件包含的類和函數(shù)使的 ADO的訪問(wèn)方式成為可能 . 跟數(shù)據(jù)庫(kù)打交道的只有三個(gè)函數(shù) : (f1)_ConnectionPtr GetConnection()。 if(ttid!=tid){ tid=ttid。這個(gè)新表有 3 個(gè)屬性 (PID long not null,IID text(50) not null,SUP integer not null),分別代表模式編號(hào) ,項(xiàng)編號(hào) ,和該模式的支持度 . (f4) void Algorithm1(DB* db,Node*amp。(*dbit))。transit!=pTransend()。 for(fit=pSetbegin()。 fit++。 while(tit!=dbitend()amp。 FreqSet_Iter fit。amp。tit!=ditend()。 node=temp2。 } } 關(guān)于該函數(shù)的情況 ,請(qǐng)看程序清單 中的注釋。//產(chǎn)生頻繁集 }else{ Table_Iter tit。 Node* node。 } 函數(shù) (f9)基本對(duì)應(yīng)于算法描述中的算法二 .它接受一棵由 (f4) 產(chǎn)生的 FPtree,node,相應(yīng)頭表 pTable,一個(gè)存放找到的頻繁集的數(shù)據(jù)庫(kù)結(jié)構(gòu) pDB,和存放中間模式的 pSet. Trans 類和 DB 類本來(lái)是用來(lái)存放交易和交易數(shù)據(jù)庫(kù)的 ,這里又用它來(lái)存放頻繁集和頻繁集數(shù)據(jù)庫(kù) .頻繁集和交易的數(shù)據(jù)結(jié)構(gòu)在算法描述的時(shí)候是不太一樣的 . 交易和頻繁集都需要記錄項(xiàng) .但是交易需要對(duì)每個(gè)項(xiàng)都記錄相應(yīng)的支持度 ,一個(gè)頻繁集卻只需要一個(gè)支持度 .為了方便對(duì)它們采用了相同的數(shù)據(jù)結(jié)構(gòu) .但是頻繁集中每個(gè)項(xiàng)的支持度都是相同的 . 在該函數(shù) 中使用了函數(shù) (f10)(f). (f10) bool HasNoBranch(Node* tree){ NVector_Iter nit。 set2,DB* pDB,Transamp。 tit。tit!=()。 retcount=0。 node=nodenode_link。 while(node2name!=){ (Item(node2name,count))。tit++) (Item(titname,count))。bit++){//產(chǎn)生頻繁集 { Trans trans。 int count。//得到第二個(gè)子節(jié)點(diǎn) if(nit!=treepChildrenend())//若第二個(gè)子節(jié)點(diǎn)存在 return false。 (Item(titname,count))。 tit。 while(true){//把 tree 的唯一路徑上面的所有節(jié)點(diǎn)都放入 set2 中 if(treename!=) (Item(treename,treecount))。 } fit=pSetfind(nodename)。 temp2name=titname。 這是 Algorithm1(...)中最關(guān)鍵的一個(gè)函數(shù) .它通過(guò)上面幾步建立頻繁項(xiàng)集合 pSet,頭表pTable,每個(gè)交易都已經(jīng)排序好的數(shù)據(jù)庫(kù) pDB 得到一棵 FPtree. 該函數(shù)的主要清單如下 : for(dit=pDBbegin()。 else rcount=fit。 } } 一個(gè)不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實(shí)現(xiàn) １６ 這個(gè)函數(shù)是根據(jù) pSet中的項(xiàng)對(duì) pDB 中的每個(gè)交易進(jìn)行排序 .在算法描述中我們只是說(shuō)根據(jù)頭表對(duì)交易進(jìn)行排序 .但是直接利用頭表對(duì)每一個(gè)交易中的項(xiàng)進(jìn)行排序 ,需要進(jìn)行大量的比較，因此 不太合適 .其實(shí)原先的算法只要求頭表中的項(xiàng)按照支持度遞降排序就可以了 ,并不在乎相同支持度的項(xiàng)的相對(duì)位置 .因此每個(gè)交易為了與頭表保持一致 ,都必須在排序中時(shí)刻查詢頭表 ,以決定每個(gè)項(xiàng)的相對(duì)位置 .在這里 ,我們定義頭表中的項(xiàng)不僅要按照支持度遞降排序 ,而且支持度相同的項(xiàng)按照字典序排列 .(參見(jiàn)數(shù)據(jù)結(jié)構(gòu)部分對(duì) Table 類的說(shuō)明 )這時(shí) ,對(duì)交易的排序就不需要比較頭表中的每個(gè)項(xiàng)了 ,它只需要知道每個(gè)項(xiàng)的支持度就可以排出與頭表中項(xiàng)相同的相對(duì)順序 .這個(gè)支持度可以通過(guò)項(xiàng)的名字 ()在頻繁項(xiàng)集合 (pSet)中查找 . std::sort(dbitbegin(),dbitend(),Compare(pSet))。dbit!=pDBend()。 continue。)就可以了 . 從這里我們可以看出在數(shù)據(jù)結(jié)構(gòu)里把使用 map 而不使用 set 或 multiset 模板定義 FreqSet的另外一個(gè)原因。 tree=root。 pTable=(Table*) new Table。 (*pDBbegin()).push_back(Item(name,count))。 函數(shù) (f1)的作用是彈出一個(gè)數(shù)據(jù)源選擇對(duì)話框 ,當(dāng)使用者選定數(shù)據(jù)源之后 ,我們就得到一個(gè)連接字符串 (connection string).把這個(gè)字符串傳給 ADO 中的連接對(duì)象 (_ConnectionPtr)的Open 函數(shù) ,就得到了一個(gè)連接對(duì)象 .最后把這個(gè)連接對(duì)象返回 .注意 ,在被打開(kāi)的 數(shù)據(jù)庫(kù)中必須有一個(gè)名為 TRANSDB 的表 ,并且表結(jié)構(gòu)為 (TID long not null,IID text(50) not null,COUNT long not null).3 個(gè)屬性分別代表交易編號(hào) ,項(xiàng)編號(hào) ,項(xiàng)計(jì)數(shù)值 . 函數(shù) (f2)利用 (f1)得到的連接對(duì)象掃描數(shù)據(jù)庫(kù) ,將其中的交易放如一個(gè)動(dòng)態(tài)分配的 DB 對(duì)象中 ,然后返回它 .為了方便，我們假定數(shù)據(jù)庫(kù)中的交易都按照交易編號(hào)進(jìn)行了排序 .下面的程序清單是這個(gè)函數(shù)的主要部分 .(pRs 是數(shù)據(jù)庫(kù)對(duì)象 ) DB* pDB=(DB*) new DB。 一個(gè)不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實(shí)現(xiàn) １３ typedef std::multisetEntry,Compare2 Table。 item)。其中 pChildren 指針指向子節(jié)點(diǎn) ,由于一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的數(shù)目是不定的，所以用了一個(gè) NodeVector 類來(lái)管理子節(jié)點(diǎn) .因?yàn)槲覀円? Node 類的構(gòu)造函數(shù)中給 pChildren 分配空間 ,所以需要在定義 Node 之前定義 NodeVector. NodeVector是一個(gè)以 Node*為元素的向量類 .所以我們?cè)诙x它之前聲明了 Node類 .雖然我們?cè)诤竺娴乃惴ㄖ行枰鶕?jù)名字在 pChildren 中查找子節(jié)點(diǎn) ,我們并沒(méi)有使用 hash 表或者平衡樹(shù)這樣復(fù)雜但高效的數(shù)據(jù)結(jié)構(gòu) ,是因?yàn)樽庸?jié)點(diǎn)的數(shù)目一般都不是很多 ,使用復(fù)雜的這樣復(fù)雜的數(shù)據(jù)結(jié)構(gòu)對(duì)于少量的數(shù)據(jù)來(lái)說(shuō)時(shí)間并沒(méi)有縮短多少 ,空間卻要浪費(fèi)一些 .因此使用了一個(gè)向量類 ,查找的時(shí)候使用簡(jiǎn)單的遍歷算法 . 成員變量 name 和 count 的意義很清楚 ,它們分別是節(jié)點(diǎn)的名字和計(jì)數(shù)值 . pParent 指向父節(jié)點(diǎn) ,定義這樣一個(gè)變量的作用在函數(shù) DB* Generate2(Node* node,intamp。 Node(){ pChildren=(NodeVector*) new NodeVector。 FreqSet跟我們要得到的頻繁集并不是一回事 ,它只是一個(gè)中間的數(shù)據(jù)結(jié)構(gòu) .我們?cè)趻呙钄?shù)據(jù)庫(kù)的時(shí)候需要計(jì)算每個(gè)項(xiàng)的記數(shù)值 ,因此需要建立一個(gè)項(xiàng)的集合類 ,其中有所有的項(xiàng) ,每次在數(shù)據(jù)庫(kù)中掃描到一個(gè)項(xiàng)就增加其中相應(yīng)的項(xiàng)的記數(shù)值 .它相當(dāng)于算法描述中的頻繁項(xiàng)集合 . 為了使得查找相應(yīng)項(xiàng)的速度加快 ,用 map 模板來(lái)定義 FreqSet. STL 在實(shí)現(xiàn) map 的時(shí)候 ,實(shí)際上在其內(nèi)部維持了一個(gè)平衡樹(shù) , 因此其插入，查找 ,刪除的速度是 O(ln).map 模板使用第一個(gè)類型參數(shù)作為比較的鍵值 類型 ,第二個(gè)類型參數(shù)做為節(jié)點(diǎn)內(nèi)部值 .在這里 ,鍵值類型為 CString,節(jié)點(diǎn)內(nèi)部值類型為 Item的成員變量 name為鍵值 .就可以根據(jù) Item的名字來(lái)尋找它在 FreqSet中的位置 ,在 O(ln)時(shí)間內(nèi)完成對(duì)相應(yīng)項(xiàng)的操作 . 使用 map 模板的另外一個(gè)原因參見(jiàn)后面的算法實(shí)現(xiàn)細(xì)節(jié)部分對(duì)函數(shù) (f5)的說(shuō)明 . Node class Node。 bool operator(const Transamp。 }。 ~Item()。 在選擇數(shù)據(jù)庫(kù)訪問(wèn)方式的時(shí)候 ,用了最近比較流行的 ADO 方式 ,它比 ODBC 更加靈活 ,速度也有 改善 .對(duì)網(wǎng)絡(luò)數(shù)據(jù)庫(kù)的支持也很好 . 下面首先對(duì)要實(shí)現(xiàn)的算法做一個(gè)描述 ,然后針對(duì)數(shù)據(jù)結(jié)構(gòu)和算法兩方面對(duì)程序的實(shí)現(xiàn)進(jìn)行詳細(xì)說(shuō)明 . 算法描述 本文所實(shí)現(xiàn)的頻繁集產(chǎn)生算法建立在兩個(gè)基本的函數(shù)之上 . 在具體描述這兩個(gè)算法之前 ,還要介紹一些建立它們所需要的知識(shí) . FPtree 論文 [1]對(duì) FPtree 的定義如下 : 1,它有一個(gè)標(biāo)記為 ”null”的根節(jié)點(diǎn) ,它的子節(jié)點(diǎn)為一個(gè) 項(xiàng)前綴子樹(shù) (item prefix subtree)的集合 ,還有一個(gè) 頻繁項(xiàng) (frequent item)組成的 頭表 (header table). 2,每個(gè)項(xiàng)前綴子樹(shù)的節(jié)點(diǎn)有三個(gè)域 :itemname,count, 記錄了該節(jié)點(diǎn)所代表的項(xiàng)的名字 .count 記錄了所在路徑代表的交易 (transaction)中達(dá)到此節(jié)點(diǎn)的交易個(gè)數(shù) .node_link 指向下一個(gè)具有同樣的 itemname 域的節(jié)點(diǎn) ,要是沒(méi)有這樣一個(gè)節(jié)點(diǎn) ,就為 null. 3, 頻繁項(xiàng)頭表 (frequent item header table) 的每個(gè)表項(xiàng) (entry) 由兩個(gè)域組成 :(1)itemname.(2) FPtree中具有與該表項(xiàng)相同 itemname域的第一個(gè)節(jié)點(diǎn) . 第一個(gè)算法的就是根據(jù)一個(gè)數(shù)據(jù)庫(kù)建立這樣一棵 FPtree. 下面是一個(gè)比較形式化的描述 . Algorithm1 輸入 :一個(gè)交易數(shù)據(jù)庫(kù) DB 和一個(gè)最小支持度 threshold. 輸出 :它的 FPtree. 步驟 : 1,掃描數(shù)據(jù)庫(kù) DB一遍 .得到頻繁項(xiàng)的集合 F和每個(gè)頻繁項(xiàng)的支持度 .把 F按支持度遞降排序 ,結(jié)果記為 L. 2,創(chuàng)建 FPtree 的根節(jié)點(diǎn) ,記為 T,并且標(biāo)記為 ?null?.然后對(duì) DB 中的每個(gè)交易 Trans 做如下的步驟 . 根據(jù) L中的順序 ,選出并排序 Trans中的頻繁項(xiàng) .把 Trans中排好序的頻繁項(xiàng)列表記為 [p|P],其中 p 是第一個(gè)元素 ,P 是列表的剩余部分 .調(diào)用 insert_tree([p|P],T). 函數(shù) insert_tree([p|P],T)的運(yùn)行如下 . 如果 T 有一個(gè)子結(jié)點(diǎn) N,其中 =,則將 N 的 count 域值增加 1。 for(fit=pSetbegin()。 數(shù)據(jù)采掘 即對(duì)經(jīng)過(guò)預(yù)處理的數(shù)據(jù)進(jìn)行采掘，可分為兩個(gè)模塊： （ 1）數(shù)據(jù)采掘數(shù)據(jù)庫(kù) 在進(jìn)行數(shù)據(jù)采掘分析模型的操作之前，要建立一個(gè)數(shù)據(jù)采掘的數(shù)據(jù)庫(kù) (DMDB)，放置此次要進(jìn)行操作的數(shù)據(jù)，可預(yù)先進(jìn)行一些諸如變量最大、最小、平均、標(biāo)準(zhǔn)差等處理，為數(shù)據(jù)一個(gè)不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實(shí)現(xiàn) ５ 采掘建立一個(gè)良好的工作環(huán)境。還沒(méi)有其他數(shù)據(jù)來(lái)驗(yàn)證得到的規(guī)則的正確性 . 除了支持度和可信度還有其他的關(guān)聯(lián)規(guī)則評(píng)價(jià)標(biāo)準(zhǔn)如改善度 (lift)和興趣度 (interest). 本文的實(shí)現(xiàn)當(dāng)中 ,對(duì)支持度的定義和上述不同 ,參見(jiàn)第 5 部分 . 一個(gè)不需要產(chǎn)生候選集的頻繁集產(chǎn)生算法的分析與實(shí)現(xiàn) ４ 4．?dāng)?shù)據(jù)采掘工具的研制及其應(yīng)用 “數(shù)據(jù)采掘工具的研制及其應(yīng)用”（ 8633060205）是國(guó)家 863項(xiàng)目，是前一階段 863項(xiàng)目研究的繼續(xù)，由復(fù)旦大 學(xué)計(jì)算機(jī)系數(shù)據(jù)庫(kù)組承擔(dān)。 關(guān)聯(lián)規(guī)則是關(guān)聯(lián)分析中的一種常用技術(shù)（另一種是序列模式）。在這種需求牽引下，匯聚了不同領(lǐng)域的研究者，尤其是數(shù)據(jù)庫(kù)技術(shù)、人工智能技術(shù)、數(shù) 理統(tǒng)計(jì)、可視化技