毕业论文一个不需要产生候选集的频繁集挖掘算法的分析与实现(编辑修改稿)

毕业论文一个不需要产生候选集的频繁集挖掘算法的分析与实现(编辑修改稿)内容摘要：

.按照从表尾到表头的顺序考察表中的每一个表项 . 从表项 p 出发 ,先可以得到一个频繁集 (p:3).然后 ,我们可以得到包含 p 的所有模式 .顺着 p表项的 node_link域 ,我们找到所有包含 p的路径 f:4,c:3,a:3,m:2,p:2和 c:1,b:1,p:1.对第一条路径 ,虽然 f 出现了 3 次 ,c 和 a 各出现了两次 ,但它们同 p 在一起只出现了 2 次 ,所以把它们 的计数改为 2,得到 f:2,c:2,a:2,m:2,p:2.第二条路径中各项的计数都已相同 ,不用修改了 .把这 2条路径中的 p项去掉 ,就得到了 p的条件模式库 ,{(f:2,c:2,a:2,m:2),(c:1,b:1)},这是下一步递归的依据 .我们把这个条件模式库看作一个数据库 ,在上面运用算法一产生一个新的 FPtree,这就是算法二中的条件树 ,这个新树只有一个节点 (c:3).这时又得到一个新的频繁集 (cp:3).包含 p项的频繁集就挖掘完了 . 接着考察 m,先还是得到 (m:3).顺着它的 node_link 得到 2 条路 径 f:4,c:3,a:3,m:2和f:4,c:3,a:3,b:1,m:1.这时 ,不需要考虑 p 项了 ,因为含有它的频繁集都已经产生完毕了 .按照上面的做法 ,得到一个条件模式库 {(f:2,c:2,a:3),(f:1,c:1,b:1,m:1)}.我们在上面构建条件树 ,得到f:3,c:3,a:3,这是一棵只有一条路径的 繁集 ,得到 {(am:3),(cm:3),(acm:3),(fm:3),(fam:3),(fcm:3),(fcam:3)}. 类似的 ,表项 b产生一个频繁集 (b:3)和 3条路径 f:4,c:3,a:3,b:1,f:4,b:1,和 c:1,b:1.同样的 ,这里也不在考虑项 p和项 m 了 .b的条件模式库 {(f:1,c:1,a:1),(f:1,b:1),(c:1,b:1)},在这个条件一个不需要产生候选集的频繁集产生算法的分析与实现 ９ 模式库上面运用算法一 ,得到一棵空树 ,对含有 b 的频繁集的挖掘到此为止 . 表 2 和图 2 显示了算法二的部分执行过程 . item conditional pattern base conditional FPtree p {(f:2,c:2,a:2,m:2),(c:1,b:1)} {(c:3)}|p m {(f:2,c:2,a:2),(f:1,c:1,a:1,b:1)} {(f:3,c:3,a:3)}|m b {(f:1,c:1,a:1),(f:1),(c:1)}  a {(f:3,c:3)} {(f:3,c:3)}|a c {(f:3)} {(f:3)}|c f   表 2 (f:2,c:2,a:2) (f::1,a::1) „m‟的条件模式库 头表 item head of node_links f c a 算法一产生的 FPtree 图 2 root f : 4 c : 1 c : 3 a : 3 m :2 p : 2 m :1 b : 1 b : 1 p : 1 b : 1 root f:3 c:3 a:3 一个不需要产生候选集的频繁集产生算法的分析与实现 １０ 数据结构 对应于算法描述中所出现的各个对象分别定义了一些数据结构 .下面予以分别介绍 .(有关代码的清单只列出重要部分，如类中的普通的构造函数之类就不予详细描述了 .) 1． Item class Item{ public: CString name。 int count。 LPVOID lpvoid。 Item()。 Item(const Itemamp。 item)。 Item(CString strName,int icount)。 ~Item()。 Itemamp。 operator=(const Itemamp。 right)。 bool operator==(const Itemamp。 right)。 bool operator(const Itemamp。 right)。 }。 Item 类对应于算法中的项 .为了操作方便其中的成员变量和成员函数都定义为 public 类型 . 成员变量 name 用来存放项的名字 . count 则是每个项的记数值 ,在最后的输出之中 ,它的意义就变成了支持度 . 还有一个变量 lpvoid,是没有在算法描述中出现过的 ,用来在使用过程中指向一个新分配的 Table_Iter 对象 .因为 Table_Iter 类还没有声明 ,所以只好用 LPVOID 类型的指针 .对它的释放在析构函 数 ~Item()中 .~Item()又调用 DeleteVoid(LPVOID),这个函数在 class Item 声明之前声明 ,但又在 class Table_Iter 定义之后定义 ,因此可以用它来删除这个对象 . 三个构造函数 Item(),Item(const Itemamp。 item)和 Item(CString strName,int icount)在实例化对象的时候起到不同的作用 .其中第二个是一个赋值构造函数 ,因为在后面定义的一些类中需要使用 class Item做为类型参数 ,根据约定 ,需要 class Item实现一个 赋值构造函数 .最后三个成员函数重载了两个运算符 ‟==‟和 ‟‟,是因为在后面的函数中我们需要对频繁的项集进行查找 ,插入，所以要对比较作出规定 . class Trans:public std::vectorItem { public: int TID。 Trans(){TID=0。 }。 Trans(int t){ TID=t。 } bool operator==(const Transamp。 right)。 bool operator(const Transamp。 right)。 一个不需要产生候选集的频繁集产生算法的分析与实现 １１ } typedef Trans::iterator Trans_Iter。 Trans 类对应于交易对象 (Transaction).对它的定义利用了 STL 中的 vector 模板 ,把它定义为一个以 Item 为元素的向量 .把它定义为向量 ,是因为后来需要对其中的元素进行排序 ,向量可以使用快速排序 . 这个 Trans 类身肩两任 ,它不仅代表交易对象 ,还在最后的结果输出中还被用来存放频繁集 . Trans_Iter 是 Trans 类的遍历子 .在以后使用 STL 容器模板定义的类都会有一个与之相对应的遍历子 ,不再赘述 . typedef std::listTrans DB。 typedef DB::iterator DB_Iter。 DB 对应于数据库对象 ,它是一个存在于内存中的 ”数据库 ”.它的定义借助于 STL 的 list 模板就非常的简明 .之所以使用 list模板而不是 vector是因为对一个数据库的操作我们通常只需要对其进行遍历 ,不需要查找 ,排序等操作 ,因此 list 最合适 ,效率因此也最高。 typedef std::mapCString,Item FreqSet。 typedef FreqSet::iterator FreqSet_Iter。 FreqSet跟我们要得到的频繁集并不是一回事 ,它只是一个中间的数据结构 .我们在扫描数据库的时候需要计算每个项的记数值 ,因此需要建立一个项的集合类 ,其中有所有的项 ,每次在数据库中扫描到一个项就增加其中相应的项的记数值 .它相当于算法描述中的频繁项集合 . 为了使得查找相应项的速度加快 ,用 map 模板来定义 FreqSet. STL 在实现 map 的时候 ,实际上在其内部维持了一个平衡树 , 因此其插入，查找 ,删除的速度是 O(ln).map 模板使用第一个类型参数作为比较的键值 类型 ,第二个类型参数做为节点内部值 .在这里 ,键值类型为 CString,节点内部值类型为 Item的成员变量 name为键值 .就可以根据 Item的名字来寻找它在 FreqSet中的位置 ,在 O(ln)时间内完成对相应项的操作 . 使用 map 模板的另外一个原因参见后面的算法实现细节部分对函数 (f5)的说明 . Node class Node。 typedef std::vectorNode* NodeVector。 typedef NodeVector::iterator NVector_Iter。 class Node{ public: CString name。 int count。 Node* node_link。 NodeVector* pChildren。 Node* pParent。 Node(){ pChildren=(NodeVector*) new NodeVector。 node_link=NULL。 一个不需要产生候选集的频繁集产生算法的分析与实现 １２ pParent=NULL。 count=0。 name=。 } ~Node(){ if(pChildren)delete pChildren。 //在析构函数中删除 } }。 class Node 是建立 FPtree的关键数据结构 ,节点。 其中 pChildren 指针指向子节点 ,由于一个节点的子节点的数目是不定的，所以用了一个 NodeVector 类来管理子节点 .因为我们要在 Node 类的构造函数中给 pChildren 分配空间 ,所以需要在定义 Node 之前定义 NodeVector. NodeVector是一个以 Node*为元素的向量类 .所以我们在定义它之前声明了 Node类 .虽然我们在后面的算法中需要根据名字在 pChildren 中查找子节点 ,我们并没有使用 hash 表或者平衡树这样复杂但高效的数据结构 ,是因为子节点的数目一般都不是很多 ,使用复杂的这样复杂的数据结构对于少量的数据来说时间并没有缩短多少 ,空间却要浪费一些 .因此使用了一个向量类 ,查找的时候使用简单的遍历算法 . 成员变量 name 和 count 的意义很清楚 ,它们分别是节点的名字和计数值 . pParent 指向父节点 ,定义这样一个变量的作用在函数 DB* Generate2(Node* node,intamp。 retcount)中可以看到 . node_link 也是一个 Node*类型 的变量 ,它用来指向下一个同名的节点 ,其作用在函数Node* SetupFP(FreqSet* pSet,Table* pTable,DB* pDB)中可以看到 . class Entry{ public: CString name。 int count。 Node* head_link。 Entry()。 Entry(const Entryamp。 entry)。 Entry(const Itemamp。 item)。 }。 Entry 类对应于头表中的表项 .因此它有一个 name 成员 ,所指 项的名字 ,还有一个 Node*类 ,head_link,用来串起同名的项 . 成员变量 count 是为了优化算法而添加的 ,它的作用可以在下面 Table 的说明看到 . class Compare2{ public: Compare2(){}。 bool operator()(const。