6.3.3.1　TDA并行式挖掘算法主要思想

TDA挖掘算法仍然采用了连接、剪枝、计数的方法来挖掘频繁项集，虽然采用了垂直数据布局数据库的方法使得计数的方法由扫描数据库对项集计数变为采用项集中所有项的支持事务列表求并集进行计数，大大提升了其中最耗时的计数步骤的效率，进而大大提升了效率，然而在数据量较大时，该算法仍然比较耗时，我们需要进一步提升其效率。根据上面的描述，我们知道，TDA挖掘算法实际上是首先通过（k－）－项集的集合（我们称其为X）中可两两进行连接的2项子集项，生成k项集的集合（我们称其为集合Y），然后利用频繁子集定理，即k－项频繁项集的（k－1）－项子集仍是频繁项集的，通过检查集合X对集合Y进行剪枝，生成候选项集Ck，然后再对候选项集Ck进行计数，产生频繁项集Lk。在这种步骤中，我们发现，这种操作的步骤是先连接产生一个k－项集集合，对该集合中项集一个个进行剪枝，产生一个候选项集合，在对该候选项集合中的项集一个一个地进行计数，连接所产生的项集集合中各项集之间剪枝、计数操作是无关的，我们称其为无关联性。因此我们可以采用首先连接得到一个项集，对该项集进行剪枝，进行计数，然后再连接得到一个项集，再对其进行剪枝，进行计数，以此操作下去的方法，依然可以得到正确的结果。如果另一台计算机拥有剪枝程序且拥有（k－1）－项项集的集合，只要对其进行输入k－项集，该计算机就可以对该k－项集进行剪枝，输出该k－项集的剪枝结果，我们称这种拥有剪枝能力的计算机为剪枝结点。而一台计算机只要拥有一个垂直数据库，对其输入k－项集，则该计算机就可以对该k－项集进行计数，我们将其称之为计数结点。由于剪枝和计数所花费的时间在TDA挖掘算法中较长，故我们可以设计一个并行性挖掘算法，将剪枝和计数分别放在不同的计算机上，如果需进一步提高算法效率，可将剪枝和计数分别放在多台计算机上，形成多个剪枝和计数结点。但这样做，有一点必须注意，连接输出项集后，需要带上一个序号，在剪枝和计数后如确定了频繁项集，最终生成的k－项频繁项集集合，仍需按照这个序号进行排序，以便用于（k＋1）－项集的生成。

6.3.3.2　TDA并行挖掘算法描述

在TDA并行式挖掘算法中，用于产生垂直数据库及用于连接的计算机称为连接节点或主节点，用于剪枝的计算机称为剪枝结点，用于计数的计算机称为计数结点。其中每个节点都含有三个线程，分别称为发送线程、处理线程及接收线程，其节点示意图如图6.2所示。

图6.2　TDA并行挖掘算法节点示意图

下面具体描述TDA并行式挖掘算法的步骤：

（1）由主节点对数据库进行扫描生成垂直数据库，并根据垂直事务数据库得到1－项频繁项集L1，并将项集按照支持事务列表计数降序排列，对垂直事务数据库进行删剪，将1－项非频繁项集及其支持事务列表删除。

（2）将垂直事务数据库拷贝到计数结点。(www.daowen.com)

（3）由主节点连接对L1进行连接，将连接得到的2－项集交给主节点的发送线程，发送线程每次得到N个2项集对其按顺序进行编号，并将这N个2－项集发送给剪枝节点，剪枝节点将其传送给计数结点，如果连接操作执行完毕则由发送进程发送完成标致｛连接end｝。

（4）计数结点接到项集将其保存在项集队列中，并且不断扫描队列，只要队列不空，则从中取出一个项集，然后在本地的垂直事务数据库中查找项集中项的事务列表，对这些事务列表求交集，将所得到的集合用于计数，计数大于最小支持计数的频繁项集发送回主程序，当从队列中取到｛连接end｝标致时将｛计数end｝标致发送至主程序。

（5）主结点收到｛计数end｝标致时，对己收到的频繁项集按编号排序，即有序2－项频繁项集L2，并将L2，发送到剪枝结点。

（6）主结点通过Lk－1中可连接的项相连接得到k－项集，每得到N个k－项集对其进行编号，并将其发送到剪枝结点，如果连接操作执行完毕则发送完成标致｛连接end｝。

（7）剪枝结点的接受线程不断接收主节点发送过来的k－项集，将其加入队列并且由剪枝线程不断扫描队列，只要队列非空，从中取出k项集，并对其进行剪枝，对于所有（k－1）－项集都为频繁项集的k－项集，每得到N个k项集将其发送到计数节点，如果取到标致｛连接end｝，则将标致｛剪切end｝标致发送到计数结点。

（8）计数结点的接受线程不断接收剪切结点发送过来的k项集，将其加入队列，并且由计数线程不断扫描队列，只要队列非空，从中取出k项集，然后在本地的垂直事务数据库中查找项集中项的事务列表，对这些事务列表求交集，将所得到的集合用于计数，将Count（K项集）＞最小支持计数的频繁项集交由发送线程，发送线程每次收集到N个k项频繁项集就将其发送至主结点，当从队列中取到｛剪切end｝标致时将｛计数end｝标致发送至主结点。

（9）主节点的接受线程不断接受来至计数节点的k－项频繁项集，将其按编号的顺序加入Lk，直至接收到｛计数end｝标致为止。如果Lk≠φ，则重复第（6）步。

TDA并行算法的做法就是把连接、剪枝、计数分别放在不同的结点让他们同时进行，进而节约挖掘时间，提高效率。其中每个节点的发送线程、即接收线程程序基本类似，可以采用统一的接口进行统一开发。