Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4229235
  • 博文数量: 473
  • 博客积分: 12019
  • 博客等级: 上将
  • 技术积分: 6515
  • 用 户 组: 普通用户
  • 注册时间: 2005-08-01 16:46
文章分类

全部博文(473)

文章存档

2020年(30)

2019年(4)

2018年(10)

2017年(5)

2016年(2)

2015年(4)

2014年(4)

2013年(16)

2012年(47)

2011年(65)

2010年(46)

2009年(34)

2008年(52)

2007年(52)

2006年(80)

2005年(22)

分类: 数据库开发技术

2006-11-22 09:04:38

1、相关概念

 项目(item):定义为在事务中呈现的一个东西

 关联规则:项目之间的关系

 事务:一次活动

Item出现频度:表示一个item在所有的事务活动中呈现的次数

支持度:就是针对每一个item,在所有事务中出现大事务比率。

S=出现该项目事务的总数/事务总数

显然,如果计算出一个频繁项集是 很消耗时间的。设计到的算法有apriori算法

 

2、apriori算法过程个人理解:

 
扫描所有事务(或者遍历事务集合),计算出频繁集L1(频繁集合Lk表示集合内的每个项k个元素组成,比如L2={ {a,b},{c,d} });然后采用apriorigen算法计算出候选集合C2(候选集合Ck表示集合内的每个项k个元素组成。注意在产生候选集合时候,可判定每个项内的元素组成的项集是否在Lk-1内,若不在,则抛弃该项目,显然支持度不满足,这样可提高效率);产生候选集合C2后遍历一遍事务集合,计算每个项的支持度,并根据支持度阀值筛选出频繁集合L2,依此类推,直到Lk为空集合。

 
上述特点分析:

1、  每个频繁集合Lk的产生都根据候选集合Ck,通过遍历事务集合,也就是LkCk的子集合。

2、  每个候选集合Ck的产生都根据频繁集合Lk-1apriorigen算法合并Lk-1

3、  apriorigen算法.

nsert into Ck

Select p[1], p[2],……,p[k-1]q[k-1]

From Lk-1 p Lk-1 q

Where p[1] = q[1],……,p[k-2] = q[k-2]

              p[k-1] < q[k-1]

Ck中的每一个项是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的(如果不清楚连接,可以单独分析集合合并问题)。注意为了提高效率,可以同时判断组合后新的项元素组成的项(由k-1个元素组成)否属如Lk-1集合的项,如不是则抛弃。

 

 

3、apriorigen算法举例

 本算法主要是集合构造。如下
集合合并:

C1={A,B,C,D}

C2={AB,AC,AD,BC,BD,CD}

C3={ABAC,ABAD,ABBC,ABBD,ABCD

ACAD,ACBC, ACBD, ACCD

,ADBC, ADBD, ADCD

BCBD, BCCD

BDCD

}

合并相同元素(且忽略次序)后====C3={ABC,ABD,ACD BCD}

经过程序测试,对于26个字母,110元的组合,产生10970271个记录项,消耗时间大约12分(CPU intel P 2.93),计算相当消耗时间。所以候选集合尽量不用,可采用FP-tree算法



5、apriorigen相应的实现代码:

// apr-gen.cpp : 定义控制台应用程序的入口点。
//单独测试集合合并的情况,验证apriori-gen算法功能
//结果:没有考虑频繁集合的过滤情况,单纯的集合合并过于消耗CPU和内存
//

#include "stdafx.h"
#include
#include
#include
#include
#include

using namespace std;
#define MAX_SIZE 30


//判断两个项的组合情况,根据前1-k个元素进行比较
//最后把合并的结果存放到sOut内
int get_condition(const char* s1,const char* s2,char *sOut)
{
    int n = strlen(s1)-1;
    int nRet = strncmp(s1,s2,n);
    if(nRet!=0)
        return -1;
    if(*(s1+n) < *(s2+n))
    {
        memmove(sOut,s1,n);
        *(sOut+n)=*(s1+n);
        *(sOut+n+1)=*(s2+n);
        return 0;
    }
    else
        return -1;
}
//nElemNum表示一个项的最大元素个数
//vec 初始数组。如A,B,C,D,
//产生1--nElemNum个集合中的所有项
//注意:此种算法过于消耗CPU和内存
int main_process(vector &vec,int nElemNum)
{
    int nTotalNum =0;
    char szTemp[1024];
    int nEndPos ,nBegPos;
    string str;
    int i,k,m;
       
    nTotalNum =0;
    for(i=0;i    {
        for(k=i+1;k < MAX_SIZE; k++)
        {
            str = vec[i]+vec[k];
            //cout<            vec.push_back(str);
            nTotalNum++;
           
        }
    }
    for(m =1;m    {
        nEndPos =vec.size();
        nBegPos= nEndPos -nTotalNum;
        nTotalNum =0;
        memset(szTemp,0,sizeof(szTemp));
        for(i=nBegPos;i        {
            for(k=i+1;k < nEndPos; k++)
            {
               
                if(get_condition(vec[i].c_str(),vec[k].c_str(),szTemp) < 0)
                    //continue;      //按照有序增长,后面不需要在比较
                    break;
                //str = vec[i]+vec[k];
                str = szTemp;
                //cout<                vec.push_back(str);
                nTotalNum++;
                memset(szTemp,0,sizeof(szTemp));
           
            }
        }
    }
    return 0;

}

int _tmain(int argc, _TCHAR* argv[])
{
    //ofstream myfile("c:\\1.txt",ios::out|ios::trunc,0);
    ofstream myfile("d:\\1.txt");
    int nTotalNum =0;
    char szTemp[1024];
    vector  vec;
   
    char ch[] ="A";
    string str=ch;
    int i,k;
   
    for(i=0;i    {
        nTotalNum++;
        str=ch;
        vec.push_back(str);
        ch[0]++;
    }

    main_process(vec,5);
    for(i=0;i    //    cout<        myfile<//    cout<<"Num="<myfile<<"Num="<    return 0;
}


阅读(8013) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~