首页 > 代码库 > 关联规则挖掘算法

关联规则挖掘算法

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 =http://www.mamicode.com/ 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)
        {
            Init();
        }
        //初始化程序主界面
        private void Init()
        {
            this.Text = "关联规则算法";
            tData.Clear();
            C0.Clear();
            L0.Clear();
            this.TDataView.Items.Clear();
            this.CResultView.Items.Clear();
            this.LResultView.Items.Clear();
            this.ItemList.Items.Clear();
            this.TDataView.Items.Add("TID\t商品ID的列表\n");
            this.ItemList.Items.Add("I1");
            this.ItemList.Items.Add("I2");
            this.ItemList.Items.Add("I3");
            this.ItemList.Items.Add("I4");
            this.ItemList.Items.Add("I5");
            this.confList.Items.Add("I1");
            this.confList.Items.Add("I2");
            this.confList.Items.Add("I3");
            this.confList.Items.Add("I4");
            this.confList.Items.Add("I5");
            this.ListConf.Items.Add("I1");
            this.ListConf.Items.Add("I2");
            this.ListConf.Items.Add("I3");
            this.ListConf.Items.Add("I4");
            this.ListConf.Items.Add("I5");
            this.txtbMinSup.Text = minSup.ToString();
            step = 0;
            finish = false;
        }     
         
        //删除事务
        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);
        }
        //示例事务
        #region
        private void Example_Click(object sender, EventArgs e)
        {
            example();
        }
        private void example()
        {
            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);
        }
        #endregion
        //最小支持度阈值变化
        private void txtbMinSup_TextChanged(object sender, EventArgs e)
        {
            try
            {
                //获得最小支持度阈值,将其赋给minSup
                minSup = int.Parse(this.txtbMinSup.Text);
            }
            catch
            {
                MessageBox.Show("非法输入!");
                this.txtbMinSup.Text = minSup.ToString();
            }
        }
        //添加事务
        #region
        //获得事务ID号
        public string GetTID()
        {
            return this.TID.Text;
        }
        //获得事务中的项
        public ArrayList GetItemList()
        {
            ArrayList items = new ArrayList();
            for (int i = 0; i < this.SelectItemList.Items.Count; i++)
            {
                string itemID = this.SelectItemList.Items[i].ToString();
                items.Add(itemID);
            }
            items.Sort();
            return items;
        }
        //添加项到备选栏
        private void Add_Click(object sender, EventArgs e)
        {
            if (this.ItemList.SelectedIndex < 0)
                return;
            for (int i = 0; i < this.SelectItemList.Items.Count; i++)
            {
                if (this.SelectItemList.Items[i] == this.ItemList.SelectedItem)
                    return;
            }
            this.SelectItemList.Items.Add(this.ItemList.SelectedItem);
        }
        //从备选栏中删除项
        private void Delete_Click(object sender, EventArgs e)
        {
            if (this.SelectItemList.SelectedIndex < 0)
                return;
            this.SelectItemList.Items.RemoveAt(this.SelectItemList.SelectedIndex);
        }
        //确定添加事务到挖掘准备框
        private void Submit_Click(object sender, EventArgs e)
        {
            insertform();
        }
        private void insertform()
        {
            trans t = new trans();
            t.tID = GetTID();
            t.items = GetItemList();
            AddItemToDataView(t);
            tData.Add(t);
        }
         
        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);
        }     
        //取消添加事务到挖掘准备框
        private void Cancel_Click(object sender, EventArgs e)
        {
            this.SelectItemList.Items.Clear();
        }
        #endregion
        //计算下一项
        private void Next_Click(object sender, EventArgs e)
        {
            if (finish == true)
            {
                this.Next.Text = "计算下一步";
                Init();
                return;
            }
             
            ArrayList OldL = new ArrayList(L0);
            //增加步骤计数,用来决定计算C或者是L。
            step++;
            //计算L并显示L视图
            #region           
            //计算L
            if (step % 2 == 1)
            {
                //找出频繁1项集L1
                if (step == 1)
                {
                    //当前事务总数tData.Count
                    for (int i = 0; i < tData.Count; i++)
                    {
                        trans t = (trans)tData[i];
                        //当前一个事务中的项的总数t.items.Count
                        for (int j = 0; j < t.items.Count; j++)
                        {
                            bool flag = true;
                            //判断一下当前项是不是已经被计算过支持度,L0用于存放频繁K项集(items和sup)
                            for (int k = 0; k < L0.Count; k++)
                            {
                                string mda=((itemAndSup)L0[k]).items[0].ToString();
                                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);
                    }
                }
                //更新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);
                        }
                        this.resultBox.Items.Clear();
                        this.resultBox.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 ResultLine = "";
                            for (int j = 0; j < items.Count; j++)
                            {
                                ResultLine = ResultLine + items[j].ToString() + ",";
                            }
                            ResultLine = ResultLine + "\t" + sup + "\n";
                            this.resultBox.Items.Add(ResultLine);
                        }
                    }
                    else
                    {                       
                        this.resultBox.Items.Clear();
                        this.resultBox.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 ResultLine = "";
                            for (int j = 0; j < items.Count; j++)
                            {
                                ResultLine = ResultLine + items[j].ToString() + ",";
                            }
                            ResultLine = ResultLine + "\t" + sup + "\n";
                            this.resultBox.Items.Add(ResultLine);
                        }
                        OldL.Clear();
                        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);
                        }
                    }
                //更新L说明
                    if (L0.Count != 0)
                        this.Msg.Text = "比较候选支持度计数与最小支持度计数";
                    else
                    {
                        this.Msg.Text = "由于L为空,算法终止";
                        this.Next.Text = "完成(重新开始)";
                        finish = true;
                    }
            }
            #endregion
            //计算C并显示C视图
            #region          
            //计算C
            else
            {
                //通过将Lk-1与Lk-1自身连接产生Ck,Lk-1中的items项的顺序已经排好为由小到大
                C0.Clear();
                for (int i = 0; i < L0.Count; i++)
                {
                    //items0(Lk)与Lk合并
                    ArrayList items0 = ((itemAndSup)L0[i]).items;
                    //将可以合并到items0的值items[k]添加到addItem中,以防止后面重复添加
                    ArrayList addItem = new ArrayList();
                    for (int j = 0; j < L0.Count; j++)
                    {
                        //当自身与自身组合时,跳过这一步
                        if (j == i)
                            continue;
                        //Lk本身,将被合并到items0
                        ArrayList items1 = ((itemAndSup)L0[j]).items;
                        for (int k = 0; k < items1.Count; k++)
                        {
                            //当前items1[k]是否比items0中最后一个数值小,如果小的话则进行下一次循环
                            if (((string)items1[k]).CompareTo((string)items0[items0.Count - 1]) <= 0)
                                continue;
                            //如果items[1]已经合并到items0的话,则进行下一次循环
                            if (addItem.Contains(items1[k]))
                                continue;
                            //对items0+items1[k]进行Ck与Lk-1测试,判断Ck是否是Lk-1的超集,
                            //如果不是超集 则合并后的项集的支持度肯定小于最小支持度阈值
                            bool mmm = ItemTest(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);
                    }              
                //更新C视图说明
                    if (C0.Count != 0)
                        this.Msg.Text = "由L产生C,并扫描D,对每个候选计数";
                    else
                    {
                        this.Msg.Text = "由于C为空,算法终止";
                        this.Next.Text = "完成(重新开始)";
                        finish = true;
                    }
            }
            #endregion
        }
        //计算项集的支持度Sup
        private int FindItemSup(ArrayList item)
        {
            //初始化支持度为0
            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++)
                {
                    //只要有一个项不存在于事务中,flag=0,则此项集不存于事务中
                    if (!(t.items.Contains(item[j])))
                    {
                        flag = false;
                        break;
                    }
                }
                //如果项集存在于事务中,则支持度加1
                if (flag == true)
                    count++;
            }
            //返回支持度计数
            return count;
        }
        //对items0+items1[k]进行Ck与Lk-1测试,判断Ck是否是Lk-1的超集,如果是超集,则返回true,如果不是则返回false
        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();
                for (int j = 0; j < L0.Count; j++)
                {
                    bool flag2=true;
                    ArrayList tempItems = ((itemAndSup)L0[j]).items;
                    for (int k = 0; k < tempItems.Count;k++ )
                    {
                        if (newItems[k]!=tempItems[k])
                        {
                            flag2 = false;                       
                            break;
                        }
                    }
                    //只要有一个存在于Lk-1中即可返回true,结束本测试
                    if (flag2==true)
                    {
                        return true;
                    }
                }               
            }
            //如果所有对比均进行完毕,则返回false
            return false;          
        }
        //推导项里添加项集
        private void btnAddConf_Click(object sender, EventArgs e)
        {
            if (this.confList.SelectedIndex < 0)
                return;
            for (int i = 0; i < this.confEnd.Items.Count; i++)
            {
                if (this.confEnd.Items[i] == this.confList.SelectedItem)
                    return;
            }
            this.confEnd.Items.Add(this.confList.SelectedItem);
        }
        //推导项里删除项
        private void btnCancelConf_Click(object sender, EventArgs e)
        {
            if (this.confEnd.SelectedIndex < 0)
                return;
            this.confEnd.Items.RemoveAt(this.confEnd.SelectedIndex);
        }
        //关联项添加项集
        private void btnConf_Click(object sender, EventArgs e)
        {
            if (this.ListConf.SelectedIndex < 0)
                return;
            for (int i = 0; i < this.EndConf.Items.Count; i++)
            {
                if (this.EndConf.Items[i] == this.ListConf.SelectedItem)
                    return;
            }
            this.EndConf.Items.Add(this.ListConf.SelectedItem);
        }
        //关联项删除项
        private void BtnConfCancel_Click(object sender, EventArgs e)
        {
            if (this.EndConf.SelectedIndex < 0)
                return;
            this.EndConf.Items.RemoveAt(this.EndConf.SelectedIndex);
        }
        //计算置信度
        private void confBtn_Click(object sender, EventArgs e)
        {
            float sumconf = FindItemSup(insertSumConf());
            float refconf = FindItemSup(insertConf());
            float result = (sumconf / refconf) * tData.Count;
            txtConfidence.Text = (result).ToString();
        }
        //获取推导项集
        private ArrayList insertConf()
        {
            ArrayList items = new ArrayList();
            for (int i = 0; i < this.confEnd.Items.Count; i++)
            {
                string itemID = this.confEnd.Items[i].ToString();
                items.Add(itemID);
            }
            items.Sort();
            return items;
        }
        //获取关联项集
        private ArrayList insertSumConf()
        {
            ArrayList items = new ArrayList();
            for (int i = 0; i < this.EndConf.Items.Count; i++)
            {
                string itemID = this.EndConf.Items[i].ToString();
                items.Add(itemID);
            }
            items.Sort();
            return items;
        }
    }
}

关联规则挖掘算法