C实现的关联规则算法

C语言实现的Apriori关联规则算法 using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Text; using System.Windows.Forms; using System.Collections; namespace Apriori { //事务 struct trans { public string tID; public ArrayList items; } //项集和支持度计数 struct itemAndSup { public ArrayList items; public int sup; } public partial class Form1 : Form { private ArrayList tData = new ArrayList(); //事务数据 private int minSup = 2; //最小支持度计数阀值 private ArrayList C0 = new ArrayList(); //L的超集 private ArrayList L0 = new ArrayList(); //频繁k项集 private int step; //已完成步骤数 private bool finish; //算法是否完成 public Form1() { InitializeComponent(); } private void Form1_Load(object sender, EventArgs e) { Reset(); //test1(); } private void Reset() { tData.Clear(); C0.Clear(); L0.Clear(); this.TDataView.Items.Clear(); this.CResultView.Items.Clear(); this.LResultView.Items.Clear(); this.TDataView.Items.Add("TID\t商品ID的列表\n"); this.MinSupTextBox.Text = minSup.ToString(); step = 0; finish = false; } private void AddItem_Click(object sender, EventArgs e) { Trans addTrans = new Trans(); if (addTrans.ShowDialog() == DialogResult.OK) { trans t = new trans(); t.tID = addTrans.GetTID(); t.items = addTrans.GetItemList(); AddItemToDataView(t); tData.Add(t); } } private void DeleteItem_Click(object sender, EventArgs e) { if (this.TDataView.SelectedIndex == 0) return; tData.RemoveAt(this.TDataView.SelectedIndex - 1); this.TDataView.Items.RemoveAt(this.TDataView.SelectedIndex); } private void Next_Click(object sender, EventArgs e) { if (finish == true) { this.Next.Text = "计算下一步"; Reset(); return; } ArrayList OldL = new ArrayList(L0); //增加步骤计数，用来决定计算Ｃ或者是Ｌ。 step++; //计算L if (step % 2 == 1) { //找出频繁1项集L1 if (step == 1) { for (int i = 0; i < tData.Count; i++) { trans t = (trans)tData[i]; for (int j = 0; j < t.items.Count; j++) { bool flag = true; for (int k = 0; k < L0.Count; k++) { if (((itemAndSup)L0[k]).items[0] == t.items[j]) { flag = false; break; } } if (flag == false) continue; ArrayList items = new ArrayList(); items.Add(t.items[j]); int sup = FindItemSup(items); if (sup >= minSup) { itemAndSup temp = new itemAndSup(); temp.sup = sup; temp.items = items; L0.Add(temp); } } } } //通过Ck来确定Lk else { L0.Clear(); for (int i = 0; i < C0.Count; i++) { itemAndSup temp = (itemAndSup)C0[i]; if (temp.sup >= minSup) L0.Add(temp); } } //对L0排序 { } //更新L的视图 { if (L0.Count != 0) { this.LResultView.Items.Clear(); this.LResultView.Items.Add("项集\t支持度计数\n"); for (int i = 0; i < L0.Count; i++) { ArrayList items = ((itemAndSup)L0[i]).items; int sup = ((itemAndSup)L0[i]).sup; string LResultLine = ""; for (int j = 0; j < items.Count; j++) { LResultLine = LResultLine + items[j].ToString() + ","; } LResultLine = LResultLine + "\t" + sup + "\n"; this.LResultView.Items.Add(LResultLine); } } else { this.LResultView.Items.Clear(); this.LResultView.Items.Add("项集\t支持度计数\n"); for (int i = 0; i < OldL.Count; i++) { ArrayList items = ((itemAndSup)OldL[i]).items; int sup = ((itemAndSup)OldL[i]).sup; string LResultLine = ""; for (int j = 0; j < items.Count; j++) { LResultLine = LResultLine + items[j].ToString() + ","; } LResultLine = LResultLine + "\t" + sup + "\n"; this.LResultView.Items.Add(LResultLine); } } } //更新说明 { if (L0.Count != 0) this.Msg.Text = "比较候选支持度计数与最小支持度计数"; else { this.Msg.Text = "由于L为空，算法终止"; this.Next.Text = "完成（重新开始）"; finish = true; } } } //计算C else { //通过将Lk-1与自身连接产生Ck C0.Clear(); for (int i = 0; i < L0.Count; i++) { ArrayList items0 = ((itemAndSup)L0[i]).items; ArrayList addItem = new ArrayList(); for (int j = 0; j < L0.Count; j++) { if (j == i) continue; ArrayList items1 = ((itemAndSup)L0[j]).items; for (int k = 0; k < items1.Count; k++) { /* if (items0.Contains(items1[k])) continue; */ //改进 if (((string)items1[k]).CompareTo((string)items0[items0.Count - 1]) <= 0) continue; if (addItem.Contains(items1[k])) continue; //对items0+items1[k]进行子集测试 if (ItemTest(items0, items1[k]))//测试通过 { ArrayList items = new ArrayList(items0); items.Add(items1[k]); items.Sort(); int sup = FindItemSup(items); itemAndSup temp = new itemAndSup(); temp.items = items; temp.sup = sup; C0.Add(temp); addItem.Add(items1[k]); } } } } //更新C的视图 { this.CResultView.Items.Clear(); this.CResultView.Items.Add("项集\t支持度计数\n"); for (int i = 0; i < C0.Count; i++) { ArrayList items = ((itemAndSup)C0[i]).items; int sup = ((itemAndSup)C0[i]).sup; string CResultLine = ""; for (int j = 0; j < items.Count; j++) { CResultLine = CResultLine + items[j].ToString() + ","; } CResultLine = CResultLine + "\t" + sup + "\n"; this.CResultView.Items.Add(CResultLine); } } //更新说明 { if (C0.Count != 0) this.Msg.Text = "由L产生C，并扫描D，对每个候选计数"; else { this.Msg.Text = "由于C为空，算法终止"; this.Next.Text = "完成（重新开始）"; finish = true; } } } } //把事务添加到视图 private void AddItemToDataView(trans t) { string transLine = ""; //添加TID transLine = transLine + t.tID + "\t"; //添加商品ID列表 for (int i = 0; i < t.items.Count; i++) { transLine = transLine + t.items[i].ToString() + ","; } transLine = transLine + "\n"; this.TDataView.Items.Add(transLine); } //计算项集的Sup private int FindItemSup(ArrayList item) { int count = 0; for (int i = 0; i < tData.Count; i++) { trans t = (trans)tData[i]; bool flag = true; for (int j = 0; j < item.Count; j++) { if (!(t.items.Contains(item[j]))) { flag = false; break; } } if (flag == true) count++; } return count; } //对items0+items1[k]进行子集测试 private bool ItemTest(ArrayList items, object addItem) { for (int i = 0; i < items.Count; i++) { ArrayList newItems = new ArrayList(items); newItems.RemoveAt(i); newItems.Add(addItem); newItems.Sort(); bool flag1 = false, flag2; for (int j = 0; j < L0.Count; j++) { ArrayList tempItems = ((itemAndSup)L0[j]).items; flag2 = true; for (int k = 0; k < tempItems.Count; k++) { if (tempItems[k] != newItems[k]) { flag2 = false; break; } } if (flag2 == true) { flag1 = true; break; } } if (flag1 == false) return false; } return true; } //test1 private void test1() { trans t1 = new trans(); t1.tID = "T100"; t1.items = new ArrayList(); t1.items.Add("I1"); t1.items.Add("I2"); t1.items.Add("I5"); AddItemToDataView(t1); tData.Add(t1); trans t2 = new trans(); t2.tID = "T200"; t2.items = new ArrayList(); t2.items.Add("I2"); t2.items.Add("I4"); AddItemToDataView(t2); tData.Add(t2); trans t3 = new trans(); t3.tID = "T300"; t3.items = new ArrayList(); t3.items.Add("I2"); t3.items.Add("I3"); AddItemToDataView(t3); tData.Add(t3); trans t4 = new trans(); t4.tID = "T400"; t4.items = new ArrayList(); t4.items.Add("I1"); t4.items.Add("I2"); t4.items.Add("I4"); AddItemToDataView(t4); tData.Add(t4); trans t5 = new trans(); t5.tID = "T500"; t5.items = new ArrayList(); t5.items.Add("I1"); t5.items.Add("I3"); AddItemToDataView(t5); tData.Add(t5); trans t6 = new trans(); t6.tID = "T600"; t6.items = new ArrayList(); t6.items.Add("I2"); t6.items.Add("I3"); AddItemToDataView(t6); tData.Add(t6); trans t7 = new trans(); t7.tID = "T700"; t7.items = new ArrayList(); t7.items.Add("I1"); t7.items.Add("I3"); AddItemToDataView(t7); tData.Add(t7); trans t8 = new trans(); t8.tID = "T800"; t8.items = new ArrayList(); t8.items.Add("I1"); t8.items.Add("I2"); t8.items.Add("I3"); t8.items.Add("I5"); AddItemToDataView(t8); tData.Add(t8); trans t9 = new trans(); t9.tID = "T900"; t9.items = new ArrayList(); t9.items.Add("I1"); t9.items.Add("I2"); t9.items.Add("I3"); AddItemToDataView(t9); tData.Add(t9); } private void Example_Click(object sender, EventArgs e) { test1(); } private void MinSupTextBox_TextChanged(object sender, EventArgs e) { try { minSup = int.Parse(this.MinSupTextBox.Text); } catch { MessageBox.Show("非法输入！"); this.MinSupTextBox.Text = minSup.ToString(); } } } }