添加到百度搜藏
添加到雅虎收藏
作者：ChakMan Kwan
联系邮件：jingle_guan(at)163.com
最后修改时间：2008-4-29
写在前面：Fp增长算法的关键是建立一棵Fp树，和对Fp树的挖掘。下面就是介绍在.Net平台上Fp增长算法的具体实现。而这一份作品的科学依据是《数据挖掘概念与技术》，（加）JiaweiHan，Micheline Kamber著中5.2.4节的FP增长算法。
效果图
整个项目最重要的三个类是FormFPTree，FPTree和FPGrowthFacade，FormFPTree是一个窗体类型的类，它主要是将用户的要求传达到程序，而FPTree就是FP树的抽象，如果你手头上有《数据挖掘概念与技术》，（加）JiaweiHan，Micheline Kamber著，FPTree真表达的对象就是5.2.4的图5-7，“存放压缩的频繁模式信息的FP树”。而FPGrowthFacade类就是FP树的挖掘类，它需要传入一个FP树。除这三个主要的类外，还有好几个类，它们是用来表达一个个的事实，程序上面说就是实体。
FormFPTree是一个以窗体形式展示的界面，通过ReadFile方法读取项目下面的数据文件而取得事务的集合，数据文件中，第一行是一份事务数据，如I1,I4,I5，它表示这三个项目会同时发生。FormFPTree窗体要求先进行预处理，也就是分析事务的数量，这样，可以一下子计算出最小支持度计数的大小，于是在下面的代码中就出来了_count > MinSupCount – 1的判断，意思是，如果项集的计数大于最小支持度计数，就应该被放入到频繁一项集中。下面是对FP树的建立，但最主要是频繁一项集的建立。最后FP树的成型是通过调用_fpTree.InitializeFPTree();实现的。
sLineString = sr.ReadLine();
//提取当前行的数组
_arrItemName = sLineString.Split(new Char[] { ' ' },
StringSplitOptions.RemoveEmptyEntries);
//将数组放到内存中
//_arrStrList.Add(_arrItemName);
List _listItemName = new List();
//将频繁项集合放到Hashtable中
for (int i = _start; i < _arrItemName.Length; i++)
{
_itemName = _arrItemName[i];
_listItemName.Add(
new ItemInfo(_itemName,0));
int _count = 1;
if (_hashTable.ContainsKey(_itemName))
{
_count = Convert.ToInt32(_hashTable[_itemName]) + 1;
_hashTable[_itemName] = _count;
}
else
_hashTable.Add(_itemName, _count);
//频繁
if (_count > MinSupCount - 1)
{
_fpTree.BuildFrequentItemList(_itemName, _count);
}
}
_listStrList.Add(_listItemName); //对FPTree传参
FPTree类的InitializeFPTree方法
这一个方法是在事务都加载完成之后使用的，加载完成的意思是数据已经从文本中读到内存中，并且已经选出了频繁一项集。
方法主要是建立了一棵树。
/// 建立FPTree
///
public void InitializeFPTree()
{
// 每个频繁项,按频繁项集列表(L)次序排序
//生成FPTree
//将事务数据库压缩到树中
BuildFPTree(_listStrList, _hashFrequentItemLinkTable, _indexToId);
}
FPTree类的另一个重要的功能就是建立条件FP树，条件FP树与FP树略有不同，它是在挖掘FP树的时候临时使用的FP树，但它的主要特性还是普通的FP树。在这里，笔者的处理是增加一个方法，
/// 建立条件FPTree
///
private void BuildConditionFPTree(List> _listStrList, Hashtable _hashFrequentItemLinkTable, Hashtable _indexToId)
{
//冒泡排序,排列频繁项集列表
int count = _hashFrequentItemTable.Count;
for (int bubble = 0; bubble < count; bubble++)
{
for (int lookup = bubble + 1; lookup < count; lookup++)
{
//小的计数往下排
if ((int)_hashFrequentItemTable[_indexToId[bubble]] <
(int)_hashFrequentItemTable[_indexToId[lookup]])
{
object temp = _indexToId[bubble];
_indexToId[bubble] = _indexToId[lookup];
_indexToId[lookup] = temp;
temp = _idToIndex[_indexToId[bubble]];
_idToIndex[_indexToId[bubble]] = _idToIndex[_indexToId[lookup]];
_idToIndex[_indexToId[lookup]] = temp;
}
}
}
......
}
FPGrowthFacade类
这个类的作用主要是调用挖掘方法对FP树进行挖掘。FPGrowth就是这个方法，初始化时，α传入的参数是null。
要了解这个挖掘的过程，难免要了解一下原始的实现过程的描述。
标准的实现过程
Procedure FP_growth(Tree, α)
(1) if Tree 含单个路径P then
(2) for each路径P中节点的每个组合（记作β）
(3) 产生模式β∪α，其支持度度数support_count等于β中节点的最小支持度计数，
(4) else for Tree的头表中的每个αi{
(5) 产生模式β=αi∪α，其支持度计数support_count =αi.support_count;
(6) 构造β的条件模式基，然后构造β的条件FP树Treeβ;
(7) if Treeβ ≠⊙ then
(8) 调用FP_growth(Treeβ, β);}
代码的实现
///
/// 在频繁一项集表中,从后到前遍历
/// 生成条件FPTree
///
///
public void FPGrowth(FPTree _fpTree, List _itemSet)
{
if (_fpTree.SinglePath)
{
//返回所有组合,用_itemSetList保存
List _itemSetList = new List();
CombineNodes(_fpTree, _itemSetList);
//产生模式 β∪α,_itemSetList是β的集合
AddPattern(_itemSet, _itemSetList);
_itemSet.Clear();
}
else
{
for (int i = _fpTree.FrequentItemCount - 1; i > -1; i--)
{
//头表中的每个a(i)
TreeNodeItem _treeNodeItem = _fpTree.GetLinkNode(i);
//产生模式β = a(i)∪α
List _itemSetConbine = new List();
if (_treeNodeItem != null)
{
if (_itemSet == null)
_itemSet = new List();
TreeNodeItem[] _arrTreeNodeItem = new TreeNodeItem[_itemSet.Count];
_itemSet.CopyTo(_arrTreeNodeItem);
_itemSetConbine.AddRange(_arrTreeNodeItem);
_itemSetConbine.Insert(0,_treeNodeItem);
}
//构造条件FPTree(1)
FPTree _conditionFPTree = new FPTree();
_conditionFPTree.MinSupCount = _fpTree.MinSupCount;
List> _listStrList = new List>();
Hashtable _hashTable = new Hashtable();
bool _doLoop = (_treeNodeItem != null);
while (_doLoop)
{
//构造条件模式基,支持度计数由小到大放入List
List _treeNodeItemList = new List();
GetParentPath(_treeNodeItem.CloneNode(), _treeNodeItemList, _hashTable, _conditionFPTree);
//如果模式已经产生并且不是频繁一项集
if (_treeNodeItemList.Count == 0 && _itemSetConbine.Count >1)
//产生模式
AddPattern(_itemSetConbine,_fpTree);
//构造条件FPTree(2)
if(_treeNodeItemList.Count>0)
_listStrList.Add(_treeNodeItemList);
//多个条件模式基
if (_treeNodeItem.NextNode != null)
_treeNodeItem = _treeNodeItem.NextNode;
else
_doLoop = false;
}
//构造条件FPTree(3)
if(_listStrList.Count >0)
_conditionFPTree.InitializeConditionFPTree(_listStrList);
//检查树是否为空
if (_conditionFPTree.TopNode.Nodes.Count > 0)
FPGrowth(_conditionFPTree, _itemSetConbine);
else
_itemSetConbine = _itemSet;
}
}
}
项目源代码下载
注意:当前源代码是由笔者经过50个小时的奋斗而完成的,虽然这说明了笔者资质一般,水平不高外,也说明了作品是经过努力才完成的.暂时不授权任何人对源代码进行转载或修改.只授权查看.
由于笔者没有充分准备,而这篇文章又极其重要,于是匆匆发布.
出处:小作坊网ChakMan原创
备案号: