FP增长算法实验报告

FP增长算法实验报告实验人：王虓学号：20101174实验目的了解关联规则在数据挖掘中的应用，理解和掌握关联挖掘的经典算法FP增长算法的基本原理和执行过程并完成程序设计。实验内容对给定数据集用FP增长算法进行挖掘，找出其中的频繁集并生成关联规则。对下面数据集进行挖掘：实验步骤首先数据库第一次扫描，导出频繁项集（1项集）的集合和支持度计数。频繁项的集合按支持度计数的递减序排序，记为L，同时对事物数据库的每条记录也进行排序。构造FP树，建FP-tree的根节点，记为T,并且标记为"null"。然后对数据库D中的每个事务t,把t中排好序的事务项列表进行建树，为方便树的遍历创建一个项头表。FP-树挖掘处理：由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基。然后，构造它的（条件）FP-树，并递归地在该树上进行挖掘。模式增长通过后缀模式与由条件FP-树产生的频繁模式连接实现。实验过程主要代码：usingSystem;usingSystem.Collections;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Text;usingSystem.Windows.Forms;usingSystem.10;namespaceFPTree{///<summary>///FPTree获取频繁模式///</summary>publicpartialclassFormFPTree:Form{///<summary>///最小支持度计数///</summary>staticintMinSupCount=2;///<summary>///最小支持度///</summary>staticintMinSupPercent=22;///<summary>///事务数据库中的所有事务总数///</summary>staticintTotalItems=0;///<summary>///测试集的文件名///</summary>staticstring_testSet="";#region测试数据集路径staticstringTestData1=Application.StartupPath+"\\testdata1_for_FP.dat";staticstringTestData2=Application.StartupPath+"\\testdata2_for_FP.dat";staticstringTestData3=Application.StartupPath+"\\testdata3_for_FP.dat";#endregionpublicFormFPTree(){InitializeComponent();cbMinSupPercent.SelectedIndex=0;}///<summary>///分析数据///</summary>///<paramname="_dataSetFileName"></param>privatevoidDoAnalysis(string_dataSetFileName){//FPTreeFPTree_fpTree=newFPTree();//FPTree挖掘FPGrowthFacade_fpGrowthFacade=newFPGrowthFacade();DateTime_dateTimeStart=DateTime.Now;//读取数据集,并遍历取得频繁一项集ReadFile(_dataSetFileName,_fpTree);_fpTree.InitializeFPTree();_fpGrowthFacade.FPGrowth(_fpTree,null);_content.Text="";if(_fpGrowthFacade.FrequentPattern.Count>0){DateTime_dateTimeEnd=DateTime.Now;TimeSpan_span=(_dateTimeEnd-_dateTimeStart);_content.Text+="程序分析总时间:"+_span.TotalSeconds.ToString()+"\r\n"+"支持度阀值设置:计数"+MinSupCount+", 支持度"+Math.Round((float)MinSupCount/TotalItems,3)*100+"%\r\n\r\n";foreach(DictionaryEntry_entryin_fpGrowthFacade.FrequentPattern){List<ItemSet>_tmpItemSetList=(List<ItemSet>)_fpGrowthFacade.FrequentPattern[_entry.Key];_content.Text+="频繁"+_entry.Key+"项集"_tmpltemSetList.Count+"个\r\n";foreach(ItemSet_itemSetin_tmpItemSetList){string[]_contents=newstring[_itemSet.Content.Count];_itemSet.Content.CopyTo(_contents);_content.Text+=ShowlnOrder(_fpTree,_contents)+"(计数"+_itemSet.Count+",支持度"+}}Math.Round((float)_itemSet.Count/TotalItems,3)*100+"%)\r\n";}}_content.Text+=" 频繁一项集"+_fpTree.FrequentItemCount+"个:\r\n";foreach(DictionaryEntry_entryin_fpTree.HashFrequentItemTable){_content.Text+=_entry.Key+"( 计数"+_entry.Value.ToString()+", 支持度"+Math.Round((float)Convert.ToInt32(_entry.Value)/TotalItems,3)*100+"%)\r\n";}}_fpTree.DisposeAll();_fpGrowthFacade.DisposeAll();}///<summary>///按顺序显示字符///</summary>///<paramname="_fpTree"></param>///<paramname="_contents"></param>///<returns></returns>privatestringShowInOrder(FPTree_fpTree,string[]_contents){int[]_indexs=newint[_contents.Length];for(inti=0;i<_indexs.Length;i++){_indexs[i]=_fpTree.GetSupCountByID(_contents[i]);}intcount=_indexs.Length;for(intbubble=0;bubble<count;bubble++){for(intlookup=bubble+1;lookup<count;lookup++){//小的计数往下排if(_indexs[bubble]<_indexs[lookup]){stringtemp=_contents[bubble];_contents[bubble]=_contents[lookup];_contents[lookup]=temp;}}string_tmpContents="";for(inti=0;i<_contents.Length;i++){_tmpContents+=_contents[i]+"";}return_tmpContents;}#region系统方法privatevoidbutton1_Click(objectsender,EventArgse){if(TotalItems==0){MessageBox.Show("请先预处理数据,以计算事务总数","系统提示");return;}SetFilePath();SetMinSupPercent();if(_testSet!="")DoAnalysis(_testSet);flowLayoutPanel1.Enabled=true;TotalItems=0;}privatevoidtoolStripButton2_Click(objectsender,EventArgse){Close();}privatevoidtoolStripButton3_Click(objectsender,EventArgse){SetFilePath();//预处理,计算事务总项数flowLayoutPanel1.Enabled=false;StreamReadersr=newStreamReader(_testSet,System.Text.Encoding.Default);while(sr.Peek()>=0){//读取当前行sr.ReadLine();TotalItems++;}sr.Close();}///<summary>///设置数据所在位置///</summary>privatevoidSetFilePath(){if(smallSet.Checked)_testSet=TestData1;if(bigSet.Checked)_testSet=TestData2;if(standardSet.Checked)_testSet=TestData3;}///<summary>///设计支持度///</summary>privatevoidSetMinSupPercent(){MinSupPercent=Convert.ToInt32(cbMinSupPercent.SelectedItem.ToString().Replace("%",""));}#endregion#region 读取数据集,并遍历取得频繁一项集publicvoidReadFile(stringstrFileName,FPTree_fpTree){//设置支持度计数TotalItems/MinSupCount=Convert.ToInt32(MinSupPercent)TotalItems/StreamReadersr=newStreamReader(strFileName,System.Text.Encoding.Default);stringsLineString="";string[]_arrItemName=null;string_itemName=null;//设置测试数据集开始位置int_start=0;if(_testSet==TestData1)_start=1;// 用Hashtable来保存一项集Hashtable_hashTable=newHashtable();List<List<ItemInfo>>_listStrList=newList<List<ItemInfo>>();while(sr.Peek()>=0){// 读取当前行sLineString=sr.ReadLine();// 提取当前行的数组_arrItemName=sLineString.Split(newChar[]{''},StringSplitOptions.RemoveEmptyEntries);//将数组放到内存中//_arrStrList.Add(_arrItemName);List<ItemInfo>_listItemName=newList<ItemInfo>();//将频繁项集合放到Hashtable中for(inti=_start;i<_arrItemName.Length;i++