- 博客(0)
- 资源 (15)
- 收藏
- 关注
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);
//增加步骤计数,用来决定计算C或者是L。
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();
}
}
}
}
2009-07-28
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人