论文导读：本文从程序设计的角度对组合枚举进行研究，并探讨其应用。5结论与讨论本文给出了组合枚举算法，并且在C#.NET中进行了实现，探讨了该算法在挖掘关联规则上的应用。
关键词：Apriori算法，组合枚举算法，应用
1 介绍 组合是一个古老的数学问题，中学数学中就有组合数的计算公式 ，然而当组合数很大时，要求把每一个组合都写出来就是一个困难的问题了。Shimon Even给出了纸上作业的方法来写出所有的组合[1]。知识发现领域的著名算法Apriori [2]，其基本数学思想也是组合枚举。许多研究者对该算法进行了改进，有效地降低了时间复杂度和空间复杂度[3,4,5,6,7]，但其基本数学思想不变。因而对组合枚举进行研究有重要的意义。
本文从程序设计的角度对组合枚举进行研究，并探讨其应用。
2 组合枚举 定义1 从n个物体构成的集合S中任意取出r个物体所得的集合记为 ，称为从n个物体中任取r个的组合，简称组合。
集合的元素个数记为 ，可证明，这正是我们熟知的公式。本文要研究的是如何让程序产生集合。
例 已知S={1,2,3,4,5}，求
从上述定义容易得到 ，且 =10。
3 组合枚举算法及C#.NET实现 通过分析集合 的元素我们可以设计出算法。论文参考网。把每一个元素中的数字按升序进行整理。以为例，如512整理成125。然后把集合中的元素按升序进行排序。结果如下：{123,124,125,134,135,145,234,235,245,345}可以看出最小元素是123，最大元素是345。最小元素123称为种子。在中，最小元素是123…r，最大元素是(n-r+1)(n-r+2)…(n-1)n。本文算法的基本思想就是通过种子123…r生成其余的元素。
3.1 组合枚举算法用数组a[1],a[2],a[3],…,a[r]来表示集合的元素。首先用种子对数组a[1],a[2],a[3],…,a[r]进行初始化，用最大元素对数组m[1],m[2],…,m[r]进行初始化。
3.2 组合枚举算法的C#.NET实现用C#实现的代码如下：
public partial classFormZh : Form
{string str='';
private void btnProduct_Click(object sender, EventArgse)
{ //生成组合元素
int n = 5, r = 3, i = 1, j = 1, L =0,num=0 ;
n = int.Parse(txtN.Text);
r = int.Parse(txtR.Text);
int[] a = new int[r+1];
int[] m = new int[r + 1];
str = '';
txtZs.Text = n_r_Zh(n, r).ToString();
for (i = 1; i <= r; i++)
{ a[i] = i; m[i] = n - r + i;
}
txtOut.Text = '';
do
{
num++;
txtDqSl.Text = num.ToString();
ScZh(a, r);
for (i = r; i > 0; i--)
{ if (a[i] < m[i])
{ //初始化后队
a[i]++; L = a[i] + 1;
for (j = i + 1; j <= r; j++, L++)
{ a[j] = L; }
break;
}
}
}while (!SfZdZh(a, m, r));
ScZh(m, r); num++;
txtDqSl.Text = num.ToString();
txtOut.Text =str;
}
private bool SfZdZh(int[] a, int [] m,int r)
{ //判断是否最大组合
bool flag = true;
for (int i = 1;i <= r && flag; i++)
{ if (a[i] < m[i])
{ flag = false; }
}
return flag;
}
private voidScZh(int[] a, intr)
{ //输出组合元素
lblDqZh.Text = '当前元素：';
for(inti=1;i<=r;i++)
{
str += a[i].ToString() + ' ';
lblDqZh.Text += a[i].ToString()+' ';
}
str+= ' ';
}
private int NdJc(int n)
{//求n的阶乘
int t = 1,i=1;
for (i = 1; i <= n;i++ )
{ t *= i; }
return t;
}
private intn_r_Zh(int n,intr)
{//求从n个中任取r个的组合数
int t = 1, i = 1;
for (i = n; i>=n-r+1; i--)
{ t *= i; }
t = t / NdJc(r);
return t;
}
}
程序运行界面如图2所示。论文参考网。
| 图2程序运行界面 figure 2 interface of program |
4 组合枚举算法的应用定理1设数据库表的属性集A有n个属性(字段)，A的所有非空子集构成的集合记为b(A)，设f为b(A)到 的映射， f: b(A)à ，则f是一一对应的映射关系。
证明：
把属性名依次改为1,2,…n则 集合b(A)恒等于集合，令f(x)=x，则映射f就是一一对应的映射关系。
任取r个属性进行查询和分析，则每一次取数据都对应一个组合枚举元素。由于有定理1的保证，在程序设计中就能建立起组合元素与属性子集之间的映射关系。在进行程序设计时，把n个属性名依次存入数组K[1],K[2],…,K[n]中，从而实现了属性名与自然数的基本对应关系，进一步就能实现f: b(A)à。论文参考网。就能把组合枚举算法用于关联规则的发现等问题中。我们在数据挖掘中曾用来查找最大频繁项目集并建立关联规则，取得了良好效果；也曾在基于Rough Sets的问题研究中用来查找达到给定依赖度的关联规则，同样取得了良好的效果。
5 结论与讨论本文给出了组合枚举算法，并且在C#.NET中进行了实现，探讨了该算法在挖掘关联规则上的应用。在应用中能够取得良好效果。
集合的每一个元素一般只做中间结果使用，并不一定要全部输出，当元素太多时，全部通过界面输出会带来的问题。如果确时需要输出，可写入数据文件。
实验表明，对于属性太多的表，如n>40，由于算法的时间复杂度剧增，无法得到结果。此时可先进行数据预处理，通过属性分组[7]，划分为属性较小的表(n<20)进行处理，或采用其它算法。
Apriori 算法的效率比本文的算法高，因为Apriori算法是在 的基上进行后继工作的。但本文的算法能为与组合枚举相关的问题提供一种参考思想。
参考文献
[1]ShimonEven. Algorithmic Combinatorics[M]. The Macmillan Company ,New York, Collier-MacmillianPublishers,London,1973,pp32-36.
[2]R.Agrawaland R.Srihant. Fast Algorithms for Mining Association Rules[C]. In 20 thVLDB Conference, Santiago, Chile, September 1994,pp487-499.
[3]DING Yan-hui,WANG Hong-guo,GAO Ming,GU Jian-jun. A New Parallel Algorithm forMining Association Rules[J]. Journal of Donghua University, 2006, (6), pp76-78.
[4]吴 简,李兴明.通信网告警关联规则的动态挖掘算法[J].计算应用研究, 2008,(4). pp1249-1252.
[5]邓悦,赵井文.关联规则挖掘算法研究[J] , 办公自动化,2008.1,pp38-40.(journal)
[6]朱其祥, 徐勇, 张林. 基于改进Apriori算法的关联规则挖掘研究[J]. 计算机技术与发展, 2006,(07).pp102-104.
[7]杨凯, 张小平, 马垣. 基于属性分组的高效挖掘关联规则算法[J]. 计算机工程与应用, 2005,(31), pp 157-159.
|
|
