Apriori 购物栏挖掘算法的C#实现。原创代码

c# 代码

c# 代码

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;


    class Program
    {
        static void Main(string[] args)
        {
            string file = @"c:\test.csv";
            string sup = "2";
            if (args.Length > 0) {
                file = args[0];

            }
            if (args.Length== 2)
            {
                sup= args[1];

            }


            double support = double.Parse(sup);

            CSVReader cr = new CSVReader();
            ItemSet data = cr.Read(file);



            Program p = new Program();
            ItemSet a= p.apriori( data, support);
            for (int i = 0; i < a.Count;i++ )
            {
                ItemSet cur = (ItemSet)a[i];
                for (int j = 0; j < cur.Count; j++) {
                    ItemSet now = (ItemSet)cur[j];
                    foreach (DataItem item in now)
                    {

                        Console.Write("编号" + item.Id + ":" + item.ItemName+"  ");


                    }
                    Console.WriteLine("  支持度:"+now.ICount);
                }

            }

            Console.Read();
        }

        private ItemSet FindOneColSet(ItemSet data, double support)
        {
            ItemSet cur=null;
            ItemSet result = new ItemSet();

            ItemSet set=null;
            ItemSet newset=null;
            DataItem cd=null;
             DataItem td=null;
             bool flag = true;

            for (int i = 0; i < data.Count; i++) {
                cur = (ItemSet)data[i];
                for (int j = 0; j < cur.Count; j++) {
                    cd = (DataItem)cur[j];

                    for (int n = 0; n < result.Count; n++) {
                        set = (ItemSet)result[n];
                        td= (DataItem)set[0];
                        if (cd.Id == td.Id)
                        {
                            set.ICount++;
                            flag = false;
                            break;

                        }
                        flag=true;
                    }
                    if (flag) {
                        newset = new ItemSet();
                        newset.Add(cd);
                        result.Add(newset);
                        newset.ICount = 1;


                    }



                }



            }
            ItemSet finalResult = new ItemSet();
            for (int i = 0; i < result.Count; i++)
            {
                ItemSet con = (ItemSet)result[i];
                if (con.ICount >= support)
                {

                    finalResult.Add(con);
                }


            }
            //finalResult.Sort();
            return finalResult;


        }


        private ItemSet apriori(  ItemSet data, double support)
        {

            ItemSet result = new ItemSet();
            ItemSet li = new ItemSet();
            ItemSet conList = new ItemSet();
            ItemSet subConList = new ItemSet();
            ItemSet subDataList = new ItemSet();
            int k = 2;
            li.Add( new ItemSet());
            li.Add(this.FindOneColSet(data,support));

            while (((ItemSet)li[k-1]).Count != 0)
            {

                conList = AprioriGenerate((ItemSet)li[k - 1],k-1, support);
                for (int i = 0; i < data.Count; i++)
                {
                    subDataList = SubSet((ItemSet)data[i], k);
                    for (int j = 0; j < subDataList.Count; j++)
                    {
                        for (int n = 0; n < conList.Count; n++)
                        {
                            ((ItemSet)subDataList[j]).Sort();
                            ((ItemSet)conList[n]).Sort();
                            if (((ItemSet)subDataList[j]).Equals(conList[n]))
                            {
                                ((ItemSet)conList[n]).ICount++;

                            }
                        }

                    }

                }

                li.Add(new ItemSet());
                for (int i = 0; i < conList.Count; i++)
                {
                    ItemSet con = (ItemSet)conList[i];
                    if (con.ICount >= support)
                    {

                        ((ItemSet)li[k]).Add(con);
                    }


                }

                k++;
            }
            for (int i = 0; i < li.Count; i++)
            {

                result.Add(li[i]);



            }
            return result;



        }

        private ItemSet AprioriGenerate(ItemSet li,int k, double support)
        {

            ItemSet curList = null;
            ItemSet durList = null;
            ItemSet candi = null;
            ItemSet result = new ItemSet();
            for (int i = 0; i < li.Count; i++)
            {
                for (int j = 0; j < li.Count; j++)
                {
                    bool flag = true ;
                    curList = (ItemSet)li[i];
                    durList = (ItemSet)li[j];
                    for (int n = 2; n < k; n++)
                    {

                        if (((DataItem)curList[n - 2]).Id == ((DataItem)durList[n - 2]).Id)
                        {

                            flag = true;

                        }
                        else {
                            break;
                            flag = false;


                        }


                    }

                    if (flag && ((DataItem)curList[k - 1] ).Id< ((DataItem)durList[k - 1]).Id)
                    {

                        flag = true;
                    }
                    else {
                        flag = false;
                    }
                    if (flag)
                    {
                        candi = new ItemSet();


                        for(int m=0;m<k;m++){
                            candi.Add(durList[m]);

                        }
                        candi.Add(curList[k-1]);





                        if (HasInFrequentSubset(candi, li,k))
                        {
                            candi.Clear();

                        }
                        else
                        {
                            result.Add(candi);
                        }
                    }

                }
            }
            return result;

        }



        private bool HasInFrequentSubset(ItemSet candidate, ItemSet li,int k)
        {
            ItemSet subSet = SubSet(candidate,k);
            ItemSet curList = null;
            ItemSet liCurList = null;

            for (int i = 0; i < subSet.Count; i++)
            {
                curList = (ItemSet)subSet[i];
                for (int j = 0; j < li.Count; j++)
                {

                    liCurList = (ItemSet)li[j];
                    if (liCurList.Equals(curList))
                    {
                       return false;

                    }

                }
            }
            return true;;
        }
        //划分子集
        private ItemSet SubSet(ItemSet set)
        {
            ItemSet subSet = new ItemSet();

            ItemSet itemSet = new ItemSet();
            //移位求2n次访
            int num = 1 << set.Count;

            int bit;
            int mask = 0; ;
            for (int i = 0; i < num; i++)
            {
                itemSet = new ItemSet();
                for (int j = 0; j < set.Count; j++)
                {
                    //mask与i可以得出某位是否为零
                    mask = 1 << j;
                    bit = i & mask;
                    if (bit > 0)
                    {

                        itemSet.Add(set[j]);

                    }
                }
                if (itemSet.Count > 0)
                {
                    subSet.Add(itemSet);
                }


            }



            return subSet;
        }



        //划分子集
        private ItemSet SubSet(ItemSet set, int t)
        {
            ItemSet subSet = new ItemSet();

            ItemSet itemSet = new ItemSet();
            //移位求2n次访
            int num = 1 << set.Count;

            int bit;
            int mask = 0; ;
            for (int i = 0; i < num; i++)
            {
                itemSet = new ItemSet();
                for (int j = 0; j < set.Count; j++)
                {
                    //mask与i可以得出某位是否为零
                    mask = 1 << j;
                    bit = i & mask;
                    if (bit > 0)
                    {

                        itemSet.Add(set[j]);

                    }
                }
                if (itemSet.Count == t)
                {
                    subSet.Add(itemSet);
                }


            }



            return subSet;
        }
    }

分享到：

一段没有空格的中英文分词的n-gram算法实现 | 得到一个集合的所有子集的算法,非常巧,用 ...

• 2007-02-01 23:09
• 浏览 8424
• 评论(4)
• 查看更多

评论

4 楼 aimilo2008 2008-09-21  

我对数据挖掘也很感兴趣，可否告诉我以后的一个方向或者你的体会，谢谢

3 楼 takitesy 2007-06-20  

你好，请问一下你用的ItemSet和DataItem是什么数据结构阿？自己写的结构吗？另外第69行中result数据集是个刚初始化的ItemSet,这里对它的操作（ for (int n = 0; n < result.Count; n++)... ）是否有问题？

2 楼 hermitte 2007-02-02  

数据库中的知识发现 (Knowledge Discovery in Databases,KDD) 是利用计算机自动地从海量信息中提取有用的知识 , 是一种有效利用信息的新方法 , 目前已成为数据库领域的研究热点之一。 KDD 的研究焦点在于数据挖掘。数据挖掘是从大型数据库或数据仓库中提取人们感兴趣的知识 , 这些知识是隐含的 , 事先未知的潜在的有用信息。主要包括的方法有 : 分类、回归分析、聚类、关联分析等 [1][5] 。关联规则的提取主要针对大型事务数据库。由于关联规则提取需要重复扫描数据库 , 因而提高算法的效率是至关重要的。

1 关联规则的基本概念

假设 I={i1 ,i2 ,…,im} 是所有项的集合 , 相当于商品的所有种类的集合 ,D 是所有事务的集合 , 也即数据库中记录的集合 , 事务 T={t1 ,t2 , … ,tn},ti ∈ I, 相当于交易中的商品列表 . 若 X 、 Y 是数据项集 ,X 中含有的项数目为 K, 则称为 K- 数据项集 .

事务集 D 中的规则 X Y( 其中 X I,Y I,X ∩ Y= Φ ) 是由支持度 (support) 和确信度 (confidence) 约束的 , 支持度表示规则的频度 , 确信度表示规则的强度 .

规则 X Y 在交易数据库 D 中的支持度是交易集中同时包含 XY 的交易数与所有交易数之比 , 记为 support(X Y)=|{T:X ∪ Y T,T ∈ D}|/|D|。

规则 X Y 在交易数据库 D 中的可信度是交易集中同时包含 XY 的交易数与包含 X 的交易数之比 , 记为 confidence(X Y)=|{T:X ∪ Y T,T ∈ D}|/|{T:X T,T ∈ D}|。

给定一个交易集 D, 挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度 (minsupp) 和最小确信度 (minconf) 的关联规则 . 当规则的确信度和支持度分别大于 minsupp 、 minconf 时 , 我们认为规则是有效的 , 称为强关联规则 . 当数据项集 X 的支持度大于 minsupp 时 , 称 X 为高频数据项集 .

2 Apriori算法

??? Agrawal等在1993年设计了一个基本算法Apriori[4]，为生 成所有频繁项集，Apriori使用了递推的方法,其核心思想是：

（1） L1 = find_frequent_1-itemsets(D);

（2） for (k=2;Lk-1 ≠Φ ;k++) {

（3）  Ck = apriori_gen(Lk-1 ,min_sup);

（4）  for each transaction t ∈ D {//scan D for counts

（5）  Ct = subset(Ck,t);//get the subsets of t that are candidates

（6） for each candidate c ∈ Ct

（7） c.count++;

（8）  }

（9）? ?Lk ={c ∈ Ck|c.count≥min_sup}

（10） }

（11） return L= ∪ k Lk;

首先扫描一次数据库，产生频繁1项集 L1 ；然后进行循环，在第k次循环中，首先由频繁k-1项集进行自连接和剪枝产生候选频繁k项集 Ck ，然后使用 Hash 函数把 Ck 存储到一棵树上，扫描数据库，对每一个交易T使用同样的 Hash 函数，计算出该交易T内包含哪些候选频繁k项集，并对这些候选频繁k项集的支持数加1，如果某个候选频繁k项集的支持数大于或等于最小支持数，则该候选频繁k项集为频繁k项集；该循环直到不再产生候选频繁k项集结束。

Apriori算法的缺点：(1)由频繁k-1项集进行自连接生成的候选频繁k项集数量巨大。(2)在验证候选频繁k项集的时候需要对整个数据库进行扫描，非常耗时。

3 几种改进的算法思想

虽然 Apriori 算法自身已经进行了一定的优化，但是在实际的应用中，仍存在不尽人意之处，于是相继出现了一些优化的方法，例如：

a. 基于划分的方法 . Savasere 等提出了一种基于划分 (partition) 算法 , 该算法首先将数据库从逻辑上分成几个互不相交的块 , 每次单独考虑一个分块并生成所有的频集 , 然后把产生的频集合并 , 用来生成所有可能的频集 , 最后计算这些项集的支持度 .

b. 基于 Hash 的方法 . 通过实验可以发现寻找频集主要的计算是在生成频繁 2_ 项集 L K 上 ,

Park 等利用这一性质引入 Hash 技术来改进产生频繁 2_ 项集的方法 .

c. 基于采样的方法 . 对上一遍扫描得到的信息进行仔细的组合分析 , 可以得到改进的算法 .Toivonen 进一步发展了这个思想 , 他首先使用从数据库中抽取出来的、由采样得到的一些在整个数据库中可能成立的规则 , 然后用数据库的剩余部分验证这些规则 .

d. 减少交易的个数 . 减少用于未来扫描的事务集的大小 , 其基本原理是：若一个事务不包含长度为 k 的大项集 , 则必然不包含长度为 k+1 的大项集 . 因此可以将这些事务移去 , 这样就减少了下一遍扫描中扫描的事务集的个数 , 这就是 Apriori-Tid 的基本思想 .

下面介绍几个改进算法的思想：

3.1 减少数据库内事务的方法

从 Apriori 算法可以看出 , 对每一 C i 均对数据库扫描一次 , 而这时有些事务已经对频繁项集的生成不产生作用 , 减少数据库 D 内不起作用的事务对于算法来说是很有必要的 , 本算法的基本思想就基于此。文 [6] 中对此进行了刻划 , 文 [6] 的算法是在每次计算 C i 支持记数的过程中 , 给不包含 C i 中的任何项集的事务打上删除标记 , 在以后的扫描计数中不加考虑。其实在 C i 扫描过数据库后 , 与 C i 中某一项集相同的事务 t , 如果其支持记数小于 Vmin_sup , 这一事务对后面的频繁项集将不产生作用 , 因此它也可以从数据库中删去。本算法通过增加这一事实 , 得出的算法比 [6] 中算法更有效。随着 i 值的增大 , 删除的事务也不断增大 , 因而有效降低了候选项集的计数速度 , 提高了整个算法的效率。

本算法命名为 DDApriori 算法 [7] , 描述如下：

算法： DDApriori 使用根据候选生成的逐行迭代找出频繁项集。

　　输入：事务数据库 D ；最小支持记数阈值 Vmin_sup 。

　　输出： D 中的频繁项集 L 。

　　方法：

10) 　 L 1 =find_frequent_1- itemsets(D) ;

20) 　 for (i = 2 ;L i - 1 ≠ ￠ ;i ++ ) {

30) 　 C k = apriori_gen(L i - 1 ,Vmin_sup) ; ‖产生新的候选项集 , 此函数同于 Apriori 算法中的函数

40) 　 for each transaction t ∈ D{ ‖扫描 D 并计数

41) 　　　　 if t . delete = 0 then do begin

50) 　　　　　 C t = subset (C i ,t) ; ‖获取 t 的子集作为候选

51) 　　　　 if C t = ￠ then

52) 　　　　　 t . delete = 1 ‖打上删除标志

53) 　　　　 else ‖对每一个 Ct 进行计数并记录内容

54) 　　　　　 if C t = c then t . count ++ ,t . text = c

60) 　　　　　 for each candidate c ∈ C t .

70) 　　　　　 c. count ++ ;

71) 　　　 end

80) 　 }

81) 　 if 0 < t . count and t.text.count < Vmin_sup then

82) 　 t . delete = 1 ‖去掉已无作用的事务 t

90) 　 L i = {c ∈ C i | c. count ≥ Vmin_sup} ‖得到满足条件的 L i

100) }

110) return L = ∪ i L i ;

这个是《数据挖掘概念与技术》中的

1 楼 ouspec 2007-02-02  

Apriori 算法能概叙一下么？