apriori.cs

数据挖掘Apriori算法

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Data.OleDb;
using System.Data;


namespace MyAprioriAlg
{
    class Apriori
    {
        int _MinSupportDegree;

        private List<AprioriSet> GetAprioriSetList()
        {
            List<AprioriSet> apprioriSetList = new List<AprioriSet>();

            OleDbConnection cn = new OleDbConnection("Provider=Microsoft.Jet.OLEDB.4.0;Data Source=ApriroriTransction.mdb");
            string selectStr;
            selectStr = "SELECT *FROM [AprioriTranction]";
            OleDbCommand cmd = new OleDbCommand(selectStr, cn);

            try
            {
                cn.Open();
                OleDbDataReader myReader = cmd.ExecuteReader();
                while (myReader.Read())
                {
                    List<string> itemList = StringTrimByCommaToList(myReader.GetString(1));
                    //AprioriSet apprioriSet = GetItemAppendToAprioriSet(myReader.GetString(0), itemList);
                    AprioriSet apprioriSet = new AprioriSet(myReader.GetString(0), itemList);
                    apprioriSetList.Add(apprioriSet);
                }

                myReader.Close();
            }
            finally
            {
                cn.Close();
            }
            return apprioriSetList;

        }

        private List<string> StringTrimByCommaToList(string preString)
        {
            List<string> listString = new List<string>();
            int preIndex=0;
            for (int i = 0; i < preString.Length; i++)
            {
                if (preString[i] == ',')
                {
                    listString.Add(preString.Substring(preIndex,i-preIndex));
                    preIndex = i;
                    preIndex++;
                }
            }
            listString.Add(preString.Substring(preIndex,preString.Length-preIndex));

            return listString;
 
        }
  
        private List<ItemSet> InitializeItemSetFromAprioriSetList(List<AprioriSet> aprioriSetList)
        {
            List<ItemSet> itemSetList = new List<ItemSet>();

            foreach (AprioriSet aprioriSet in aprioriSetList)
            {
                foreach (string item in aprioriSet.Item)
                {
                    List<string> itemtemp = new List<string>();
                    itemtemp.Add(item);
                    ItemSet itemSet = new ItemSet(itemtemp, 1);
                    if (!IsEqualItem(itemSetList, itemtemp))
                    {
                        itemSetList.Add(itemSet);
                       
                    }
                    else
                    {
                       itemSetList= ItemDegreeAdd(itemSetList, itemtemp);

                    }
                }
            }

            return itemSetList;
        }

        private bool IsEqualItem(List<ItemSet> itemSetList, List<string> item)
        {
            bool isEqual = false;
            bool isBreak = false;
            if (itemSetList.Count == 0)
                return false;
            foreach (ItemSet itemSet in itemSetList)
            {
                if (itemSet.Item.Count == item.Count)
                {
                    for (int i = 0; i < item.Count; i++)
                    {
                        if (!itemSet.Item[i].Equals(item[i]))
                        {
                            isBreak = true;
                            break;
                        }
                        isBreak = false;

                    }
                    if (!isBreak)
                    {
                        isEqual = true;
                        break;
                    }

                }
              
            }
            return isEqual;

        }

        private int EqualItemIndex(List<ItemSet> itemSetList, List<string> item)
        {
            for (int i = 0; i < itemSetList.Count; i++)
            {
                if(IsEqualItemString(itemSetList[i].Item,item))
                    return i;

            }
            return -1;

        }

        private bool IsEqualItemString(List<string> set1, List<string> set2)
        {
            bool isEqual = false;
            bool isBreak = false;

            if (set1.Count == 0 || set2.Count==0)
                return false;
            foreach (string s in set1)
            {
                if (set1.Count == set2.Count)
                {
                    for (int i = 0; i < set1.Count; i++)
                    {
                        if (!set1[i].Equals(set2[i]))
                        {
                            isBreak = true;
                            break;
                        }
                        isBreak = false;

                    }
                    if (!isBreak)
                    {
                        isEqual = true;
                        break;
                    }

                }

            }
            return isEqual;
        }

        private List<ItemSet> ItemDegreeAdd(List<ItemSet> itemSetList, List<string> itemTemp)
        {
            foreach (ItemSet itemSet in itemSetList)
            {
                if (IsEqualItemString(itemSet.Item,itemTemp))
                {
                    itemSet.SupportDegree++;
                    break;
                }
            }
            return itemSetList;
        }

        private bool HasInFrequentSubset(ItemSet candidate, List<ItemSet> itemSetList)
        {
            foreach (ItemSet set in itemSetList)
            {
                List<ItemSet> itemSetListTemp = new List<ItemSet>();

                itemSetListTemp=ItemSetCopy(itemSetList);
                itemSetListTemp.Remove(set);

                if (! IsSubList(itemSetList,itemSetListTemp))
                    return true;
            }

            return false;
        }

        private bool IsSubList(List<ItemSet> itemSetList,List<ItemSet> subItemSetList)
        {
            foreach (ItemSet set in subItemSetList)
            {
                if (!itemSetList.Contains(set))
                    return false;
            }

            return true;
 
        }

        private List<ItemSet> ItemSetCopy(List<ItemSet> itemSet)
        {
            List<ItemSet> itemSet1 = new List<ItemSet>();
            foreach (ItemSet set in itemSet)
            {
                itemSet1.Add(set);
            }
            return itemSet1;
        }

        private List<string> ListStringCopy(List<string> item)
        {
            List<string> item1 = new List<string>();
            foreach (string s in item)
            {
                item1.Add(s);
            }
            return item1;
        }

        private List<ItemSet> AprioriGenerate(List<ItemSet> itemSetList)
        {
            List<ItemSet> itemSetKList = new List<ItemSet>();

            foreach (ItemSet itemSet1 in itemSetList)
            {
            

                foreach (ItemSet itemSet2 in itemSetList)
                {
                    for (int i = 0; i < itemSet1.Item.Count - 1; i++)
                    {
                        if (!itemSet1.Item[i].Equals(itemSet2.Item[i]))
                            break;
                    }

                    int isGreaterIndex=string.Compare(itemSet1.Item[itemSet1.Item.Count-1] , itemSet2.Item[itemSet1.Item.Count-1]);
                  
                    if ( isGreaterIndex<0) 
                    {
                  
                        string sTemp = itemSet2.Item[itemSet2.Item.Count-1];

                        List<string> item = new List<string>();
                        item = ListStringCopy(itemSet1.Item);
                        int supportDegree = itemSet1.SupportDegree;
                        ItemSet itemSetTemp = new ItemSet(item, supportDegree);

                     
                        itemSetTemp.Item.Add(sTemp);
                        ItemSet set = new ItemSet(itemSetTemp.Item, 0);

                        List<ItemSet> itemSetListTemp = new List<ItemSet>();
                        itemSetListTemp = ItemSetCopy(itemSetList);

                        if (!HasInFrequentSubset(set, itemSetListTemp))
                            itemSetKList.Add(set);
                    }
                }
            }

            return itemSetKList;

        }

        private List<AprioriSet> SubSet(AprioriSet set)
        {
            List<AprioriSet> subSetList = new List<AprioriSet>();

           //移位求2n次方    
            int num = 1 << set.Item.Count;

            int bit;
            int mask = 0;

            for (int i = 0; i < num; i++)
            {
                List<string> sList = new List<string>();
                AprioriSet aprioriSet = new AprioriSet(null,sList);
                for (int j = 0; j < set.Item.Count; j++)
                {
                    //mask与i可以得出某位是否为零    
                    mask = 1 << j;
                    bit = i & mask;
                    if (bit > 0)
                    {
                        aprioriSet.Item.Add(set.Item[j]);
                    }
                }
                if (aprioriSet.Item.Count>0)
                {
                    subSetList.Add(aprioriSet);
                }
            }

            return subSetList;
        }

        private List<ItemSet> GenerateAprioriSetListToItemSetList(List<AprioriSet> aprioriSetList)
        {
            List<ItemSet> itemSetList = new List<ItemSet>();
            foreach (AprioriSet set in aprioriSetList)
            {
                ItemSet itemSet = new ItemSet(set.Item, 0);
                itemSetList.Add(itemSet);
            }
            return itemSetList;
        }

        public int MinSupportDegree
        {
            get
            {
                return _MinSupportDegree;
            }
            set
            {
                _MinSupportDegree = value;
            }
        }

        public List<ItemSet> AprioriAlgrithm()
        {
            List<ItemSet> L = new List<ItemSet>();

            List<AprioriSet> aprioriSetList = GetAprioriSetList();

            List<ItemSet> L1 = new List<ItemSet>();
            L1 = InitializeItemSetFromAprioriSetList(aprioriSetList);

            foreach (ItemSet se in L1)
            {
                L.Add(se);
            }

            do
            {
                List<ItemSet> CListK = AprioriGenerate(L1);

                foreach (AprioriSet aprioriSet in aprioriSetList)
                {
                    List<AprioriSet> aprioriSetListT = new List<AprioriSet>();
                    aprioriSetListT = SubSet(aprioriSet);
                    List<ItemSet> itemSetList = GenerateAprioriSetListToItemSetList(aprioriSetListT);

                    foreach (ItemSet set in itemSetList)
                    {
                        if (IsEqualItem(CListK, set.Item))
                        {
                            int index = EqualItemIndex(CListK, set.Item);

                            CListK[index].SupportDegree++;
                        }
                    }

                }
                List<ItemSet> cListKTemp = ItemSetCopy(CListK);
                foreach (ItemSet s in cListKTemp)
                {
                    if (s.SupportDegree < _MinSupportDegree)
                        CListK.Remove(s);
                }

                L1 = ItemSetCopy(CListK);
                foreach (ItemSet s in CListK)
                {
                    L.Add(s);
                }
            }

            while (L1.Count > 0);

            return L;


        }

        public Apriori(int minSupportDegree)
        {
            _MinSupportDegree = minSupportDegree;
        }

    }
}