FP增長算法實驗報告

FP增長算法實驗報告實驗目的了解關聯(lián)規(guī)則在數據挖掘中的應用，理解和掌握關聯(lián)挖掘的經典算法FP增長算法的基本原理和執(zhí)行過程并完成程序設計。實驗內容對給定數據集用FP增長算法進行挖掘，找出其中的頻繁集并生成關聯(lián)規(guī)則。對下面數據集進行挖掘：I1I2I5I2I4I2I3I1I2I4I1I3I2I3I1I3I1I2I3I5I1I2I3實驗步驟①首先數據庫第一次掃描，導出頻繁項集（1項集）的集合和支持度計數。頻繁項的集合按支持度計數的遞減序排序，記為L，同時對事物數據庫的每條記錄也進行排序。

②構造FP樹，建FP-tree的根節(jié)點,記為T,并且標記為"null"。然后對數據庫D中的每個事務t,把t中排好序的事務項列表進行建樹，為方便樹的遍歷創(chuàng)建一個項頭表。

③FP-樹挖掘處理：由長度為1的頻繁模式（初始后綴模式）開始，構造它的條件模式基。然后，構造它的（條件）FP-樹，并遞歸地在該樹上進行挖掘。模式增長通過后綴模式與由條件FP-樹產生的頻繁模式連接實現(xiàn)。

實驗過程主要代碼：usingSystem;usingSystem.Collections;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Text;usingSystem.Windows.Forms;usingSystem.IO;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+"項集"+_tmpItemSetList.Count+"個\r\n";foreach(ItemSet_itemSetin_tmpItemSetList){string[]_contents=newstring[_itemSet.Content.Count];_itemSet.Content.CopyTo(_contents);_content.Text+=ShowInOrder(_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系統(tǒng)方法privatevoidbutton1_Click(objectsender,EventArgse){if(TotalItems==0){MessageBox.Show("請先預處理數據,以計算事務總數","系統(tǒng)提示");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){//設置支持度計數MinSupCount=Convert.ToInt32(MinSupPercent)*TotalItems/100;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++){_itemName=_arrItemName[i];_listItemName.Add(newItemInfo(_itemName,0));int_count=1;if(_hashTable.ContainsKey(_itemName