科学计数法的规则精选(五篇)

序言：作为思想的载体和知识的探索者，写作是一种独特的艺术，我们为您准备了不同风格的5篇科学计数法的规则，期待它们能激发您的灵感。

篇1

Abstract： With the vigorous development of the communications industry， the level of service provided by the carrier to the user is also continuously improved， and therefore it puts forward a higher demand for communication equipment maintenance work. In the field of mobile network management， alarm monitoring and handling of equipment is always one of the vital works. In recent years， the network management system has realized equipment alarm correlation， but the alarm correlation function is dependent on the association rules of device alarm， at present， the alarm association rules is summed up by maintenance personnel experience， how to find unknown alarm association rules automatically through the analysis is the problem to be solved. Using Apriori algorithm and through the analysis of a large number of historical alarm data， it can be achieve frequent itemsets in data mining alarms data， eventually find the alarm association rules.

关键词： Apriori；频繁项集；关联规则；网元

Key words： Apriori；frequent itemsets；associated rule；network element

中图分类号：TN91 文献标识码：A 文章编号：1006-4311（2013）10-0183-02

1 Apriori算法简介

Apriori算法是R.Agrawal和R.Srikant于1994年提出的为布尔关联规则挖掘频繁项集的原创性算法。Apriori使用一种称作逐层搜索的迭代方法，k项集用于搜索（k+1）项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合，该集合记作L1，然后，L1用于找频繁2项集的集合L2，L2用于找L3，如此下去，直到不能再找到频繁k项集，找每个需要一次数据库全扫描。

为提高频繁项集逐层产生的效率，Apriori算法用先验性质（Apriori性质）压缩搜索空间，Apriori性质即：频繁项集的所有非空子集也必须是频繁的。

Apriori算法的基本思想

Lk：频繁k-项集的集合

Ck：候选k-项集的集合

①首先，C1由所有项组成；扫描数据库D，累计每个项的计数，并收集满足最小支持度的项，产生L1。②然后，用L1中的项两两组合得到候选2-项集的集合C2；再次扫描数据库D，累计C2每个2-项集的计数，产生L2。③接下来，用L2中的2-项集产生候选3-项集的集合C23；再次扫描数据库D，累计C3每个3-项集的计数，产生L3。④一般地，由长度为k-1的频繁项集的集合Lk产生长度为k的候选项集的集合Ck，并且扫描数据库D，产生Lk。⑤如此下去，直到不能再产生更长的频繁项集。

对于每个频繁项集Y和任意X？奂Y，X≠？覫，如果support（Y）/support（X）？叟min_conf，则输出强规则X？圯Y-X

2 告警数据准备

告警原始数据举例如下：

本文将单网元告警数据作为原始数据集，通过Apriori算法发现该类型网元的频繁项集及告警关联规则，因此如何准备告警数据集是目前需要首先解决的问题。

告警数据准备目标是根据设备维护经验，首先找到24小时内每5分钟内的告警数据集，模型如下。

根据实际设备告警情况，用下表数据（记为：D）为例进行说明。

3 告警数据频繁项集挖掘

根据Apriori算法的基本原理，频繁项集挖据过程如下所示，假定最小支持度为2：

①扫描D表，对每个候选计数得到下表C1。（表3）

②比较候选支持度计数与最小支持度计数得到下表L1。（表4）

③由L1产生候选表C2。（表5）

④扫描D，对C2中每个候选计数形成新的C2。（表6）

⑤比较候选支持度计数与最小支持度计数，得到表L2。（表7）

⑥有L2产生候选C3。（表8）

⑦扫描D，对C3中每个候选计数得到新的C3。（表9）

⑧比较候选支持度技术与最小支持度计数，得到L3。（表10）

由此，我们得到两个频繁项集。

4 告警关联规则挖掘

4.1 基本思想 对于每个频繁项集Y和任意X？奂Y，X≠？覫，如果support（Y）/support（X）？叟min_conf，则输出强规则X？圯Y-X。

4.2 关联规则挖掘 对于频繁项集L31{2550、2235、1815}，L31的非空子集有{2550、2235}、{2550、1815}、{2235、1815}、{2550}、{2235}、{1815}，计算其置信度如下：

2550Λ2235=>1815 confidence=2/4=50%

2550Λ1815=>2235 confidence=2/4=50%

2235Λ1815=>2550 confidence=2/4=50%

2550=>2235Λ1815 confidence=2/6=33%

2235=>2550Λ1815 confidence=2/7=29%

1815=>2550Λ2235 confidence=2/6=33%

对于频繁项集L32{2550、2335、2229}，L32的非空子集有{2550、2235}、{2550、2229}、{2235、2229}、{2550}、{2235}、{2229}，计算其置信度如下：

2550Λ2235=>2229 confidence=2/4=50%

2550Λ2229=>2235 confidence=2/2=100%

2235Λ2229=>2550 confidence=2/2=100%

2550=>2235Λ2229 confidence=2/6=33%

2235=>2550Λ2229 confidence=2/7=29%

2229=>2550Λ2235 confidence=2/2=100%

如果最小置信度阀值为80%，则只有上面2550^2229=>2235、2235^2229=>2550、2229=>2550^2235是强规则。

5 总结

通过Apriori算法，我们可以从大量的告警数据中发现更多有用的告警关联规则，并提高告警的压缩比，更快的发现故障根源，从而减少设备监控、维护人员的工作量，提高工作效率，为电信行业的设备维护保障提供更好、更有效的维护手段和方法。

参考文献：

[1]郑明.浅谈网络数据挖掘在电子商务中的应用[J].中小企业管理与科技（下旬刊），2009，02.

篇2

[关键词]计数标准型一次抽样检验方案；计数调整型抽样检验方案

产品质量检验是指借助于某种手段或方法来测定产品的--个或多个质量特性，然后把测得的结果同规定的产品质量标准进行比较，从而对产品作出合格或不合格判断的活动。通过观察和判断，适当时结合测量、试验所进行的符合性评价。

一、产品质量抽样检验的意义

产品质量的抽样检验是从产品总体中，抽取若干样本，对样本进行检测并按标准所规定的判定规则对总体做出合格与否的判定。因此，抽取样本的科学性在很大程度上决定了产品质量检验结果的代表性和真实性。

产品质量抽样检验方法，亦称统计抽样检验方法，是建立在概率统计理论基础上的。其关键是：如何设计合理的抽样检查方案，才能保证检验过程公正、科学、有效

首先，要明确抽样方案所依据的标准。目前我国有4个标准规定了质量监督抽样方案和一个产品质量监督复查抽样方案，即GB/T14162-1993；GB/T14437-1997；GB/T15482-1995；GB/T14900-1994；GB/T16306-1996。

其次，确定样本量的多少。样本量的确定主要应先明确批量和样本量之间的关系，当批量N确定时，只要明确检验水平，就可以检索到样本量的大小。

最后，确定判断依据，即以极限质量LQ为质量指标来判定。极限质量的确定需考虑的问题主要有：产品的用途、检验的经济性、生产企业的实际特点等。

目前国内外抽样检验方案种类很多，但最基本和最常用的有两种，即：计数标准型一次检验方案和计数调整型检验方案。

二、计数标准型一次抽样检验方案

1.计数标准型一次抽样检验方案的含义及应用范围

标准型一次抽样检验方案，是按供需双方协商认定的OC曲线，对一批产品进行抽样检验的方案。制定该方案，需要确定4个参数p0，p1，α，β和抽检方案（n，c）。

计数标准型一次抽样检验方案的应用范围：适合于一次交易（孤立的一批产品）或破坏性检验的情况。

2.计数标准型一次抽样检验方案的设计步骤

（1）确定检验的产品质量标准：产品质量的合格指标，即产品的技术标准，包括各种功能指标、生化指标、缺陷的概念和程度等。

（2）确定4个参数p0，p1，α，β：

目前普遍认同的供应者的风险率α和使用者风险率β分别为：α≈0.05，β≈0.10 . p0，p1值的大小由供需双方协商确定。先确定一个合理的p0值，再按一定比例确定p1值。

（3）批的组成：在同一生产条件下生产出来的一批产品，要尽可能直接取做检验批。若批量过大，也可以划分为小批后，将小批作为检验批。但划分的小批必须是随机的。

（4）确定抽检方案：确定样本大小n和合格判定数c，可通过查计数标准型一次抽检表获得。

三、计数调整型抽样检验方案

1.计数调整型抽样检验方案的含义及应用范围

计数调整型抽样检验方案是由一组严格度不同的抽样方案和一套转移规则组成的抽样体系。计数调整型抽样检验方案是根据过去的检验的情况，按一套转移规则随时调整检验的严格程度，从而改变抽样检验方案。

计数调整型抽样检验是应用范围最广、最有影响的一类抽样检验方法。主要应用于：

a.原材料和元器件的抽样检验；

b.过程各环节在制品的抽样检验；

c.最终产品的抽样检验；

d.库存成品的抽样检验；

e.管理过程的抽样检验等。

计数调整型抽样检验方案的特点：可以根据产品质量的实际情况，采用一组正常、加严和放宽三个不同严格程度的检验方案，并且应用一套转换规则将它们有机地联结起来。该方案可以起到一个鼓励质量好的企业，（通过放宽检验）；也可以鞭策质量差的企业，改进质量（通过加严检验）。从而，可以起到一个对供应者产品质量的管控作用。

2.计数调整型抽样检验方案的设计步骤

（1）规定单位产品的质量特性指标

质量特性指标是产品、过程或体系与要求有关的固有可区分的特征值。如物理的、生化的、感官的、行为的、时间的、功能的等。有关指标值达到什么标准才算合格，应在检验规范中或供销合同中明确表述。

（2）确定不合格类别的等级

不合格品的分类和质量缺陷严重性级别可以参照国家的有关标准。

不同级别的不合格，其对应的不合格率上限值AQL也不同。一般A类不合格品的AQL值应小于B类不合格品的AQL值，而B类不合格品的AQL值应小于C类不合格品的AQL值。

（3）确定合格质量水平AQL：接收质量限

设计抽检方案时，先要确定AQL值，如果供应者的产品质量水平接近AQL，则进行正常检验；若供应者的产品质量水平比AQL值低得多，则进行放宽检验；若供应者的产品质量水平比AQL值高多，则进行加严检验。

AQL值的确定方法，一般可采用检验法：根据产品的使用要求、产品的性能、产品的检验项目数量、不合格品和不合格种类这些因素予以确定。

实际操作时，可先参考有关资料，暂时确定一个AQL值，使用一段时间后，根据实际情况逐渐调整，达到合理。

（4）确定检验水平

检验水平是用来决定批量与样本大小之间关系等级的，其作用就是明确批量N和样本量n的关系。

国标规定检验水有两类：一般检验水平ⅰ、ⅱ、ⅲ级和特殊检验水平S-1、S-2、S-3、S-4四个检验水平。无特殊要求情况下，采用一般检验水平ⅱ。

篇3

[关键词] IS015189；血涂片复审；筛选标准；血细胞形态学；镜检

[中图分类号]R446.11　[文献标识码]C　[文章编号]1673-7210(2011)08(b)-085-03

在全国各医院检验科IS015189认可实验室现场评审中所开的“不符合项”或“观察项”中主要集中在有关细胞形态学检验相关方面的工作占有相当大的比例，血细胞分析仪的血涂片复检率过低，缺乏适合本实验室使用仪器的筛选标准等是其主要原因。近年来虽然各种类型的血细胞分析仪得以广泛应用，帮助检验人员快速完成大量血标本的检测，提高了工作效率，但迄今为止血细胞分析仪在形态学检查中仍只能作为一种过筛手段，当遇到可疑情况，尤其是在病理条件下，必须进行人工镜检复查，这已是不争的事实。如何能够让血细胞分析仪更好地为临床服务，一直是各国血液学专家共同关注的问题。2005年国际血液学复检专家组通过对13298份血标本进行详细分析后，推荐了41条自动血细胞分析和分类复检规则。但这只是通则，由于不同仪器或实验室的病源及筛选目的不同，其并无针对性和特异性。为此IS015189认可委要求各参评实验室必须在参考“血细胞涂片复审41条国际规则”的前提下结合各自实验室仪器性能特点及病源，制订适合于本实验室的血涂片复检规则。

1材料与方法

1.1材料

1.1.1标本来源3800份血标本均为来自我院检验科就诊做血常规的患者，其中，初诊标本3008份，复诊标本792份。所有标本于采血后30 min～6h期间用XE-2100自动进样模式进行检测，包括全血细胞计数(CBC)、白细胞分类(DC)、有核红细胞(NRBC)、网织红细胞(PET)，并将检测报告备份存档。

1.1.2仪器与试剂XE-2100全自动血细胞分析仪，原装配套试剂，校准品和质控品均由日本Sysmex公司提供。两台显微镜均为OlympusCX31型，用于血涂片显微镜检查。

1.2方法

1.2.1实验人员培训根据《全国临床检验操作规程》和《白细胞计数参考方法》中制订的血涂片检测操作程序(SOP)，对参加实验的人员进行培训，并研讨可能出现的问题和解决的措施。

1.2.2仪器的校准、调试及报警(IP)信息的设置均由sys-mex公司工程师按照仪器标准要求进行校准、调试和设置。

1.2.3检测方法每份标本在上机检测的同时制备2张血涂片，并编号用瑞氏染液进行染色，然后按照标准操作程序(血涂片检测SOP文件)进行血细胞形态学的镜检，每2人为1组。

1.2.4初步复检规则的制订利用XE-2100血细胞分析仪的IP信息报警系统对WBC、RBC、PLT的数量异常和形态学异常的提示。并参照“国际血液学4l条复检规则”，由sySHICX公司工程师制订出的XE-2100血细胞分析仪自动血细胞计数和WBC分类初步复检规则共21条。见表1。

1.2.5制订血涂片阳性判断标准①RBC明显大小不等，染色异常RBc>30％；②巨大PLT>15％；③见到PLT聚集；④存在Dohle小体细胞>10％；⑤中毒颗粒中性粒细胞>0.1；⑥空泡变性粒细胞>0.1；⑦原始细胞≥0.01；⑧早幼，中幼粒细胞≥0.01；⑨晚幼粒细胞>0.02；⑩杆状核粒细胞>0.05；⑩异淋>0.05；⑩嗜酸粒细胞>0.05；⑩嗜碱粒细胞>0.01；有核红细胞>0.01；⑩浆细胞>0.01。

1.2.6对比双盲法(仪器分析和血涂片复审)两者检测结果，分别计算血涂片复审率及仪器分析的真阳性率(触及初检规则且镜检为阳性的比率)、真阴性率(不触及初检规则且镜检为阴性的比率)、假阳性率(触及初检规则但镜检为阴性的比率)、假阴性率(不触及初检规则但镜检为阳性的比率)；以及血涂片复检率(复检率=真阳性率+假阳性率)。

表1初步复检规则织红)超出仪器检测线性；稀释标本后重新测定；并全部(初诊+复诊)推片镜检。

2.WBC、RBC、HGB、PLT无结果；检查标本是否有凝块；重测标本；并全部(初+复)推片镜检。

3.WBC30，0x109／L；全部(初+复)推片镜检。

4.PLT1000x10(sup)9(/sup)/L；全部(初+复)推片镜检。

5.MCV(平均红细胞体积)110n(成人)；全部(初+复)推片镜检。

6.MCHC(平均红细胞血红蛋白浓度)>380 g/l或

7.DC(白细胞分类)无结果或结果不全；全部(初+复)推片镜检及人工分类。

8.Neut#(中性粒细胞绝对计数)20.0x10(sup)9(/sup)/I；全部(初+复)推片镜检。

9.Lvmph#(淋巴细胞绝对计数)>5.0x10(sup)9(/sup)/l；全部(初+复)推片镜检。

10.Mono#(单核细胞绝对计数)>1.5×10(sup)9(/sup)/L；全部(初+复)推片镜检。

11.Fos#(嗜酸粒细胞绝对计数)>2.0x10(sup)9(/sup)/L；全部(初+复)推片镜检。

12.Baso#(嗜碱粒细胞绝对计数)>0.Sxl0(sup)9(/sup)/l；全部(初+复)推片镜检。

13.WBC IP Message(白细胞异常散点图)；全部(初+复)推片镜检。

14.WBC lP Message(未成熟粒细胞)；全部(初十复)推片镜检。

15.WBC lP Message(核左移)；全部(初+复)推片镜检。

16.WBC IP Message(异形淋巴细胞或原始细胞)；全部(初+复)推片镜检。

17.WBC IP Message(原始细胞)；全部(初+复)推片镜检。

18.WBC lP Message(有核红细胞)；全部(初+复)推片镜检。

19.PLT lP Message(除PLT聚集外的PLT和MPV(平均血小板体积)报警)；全部(初+复)推片镜检。

20.CBC+DC(新生儿标本)；全部(初+复)推片镜检。

21.CBC+DC(血液病标本)；全部(初+复)推片镜检一

2结果

2.1镜检结果

3 800份标本的仪器检测数据和显微镜人工镜检结果：①根据“血细胞涂片复审41条国际规则”的检测结果进行统计学分析，真阳性率为13.73％(522/3800)，假阳性率为32.05％(1218/3800)，真阴性率为51.05％(1940/3800)，假阴性率为3.11％(120/3800)，涂片复审率为45.78％；②按Sysmex公司提供的21条规则对检测结果进行统计学分析，真阳性率为11.37％(432/3800)，假阳性率为17.97％(683/3800)，真阴性率为66.58％(2530/3800)，假阴性率为4.08％(155/3800)，涂片复审率为2934％。

2.2验证试验

为了验证svsmex公司提供的21条复检规则的有效性，将这21条复检规则设置在xE-2100血细胞分析仪的Lab-msn程序中，选择300份(主要是血液病、感染性疾病、新生儿和肿瘤化疗患者)血标本在xE-2100血细胞分析仪上进行检测，并与涂片镜检结果对比分析。结果显示：真阳性率为53.33％(160/300)，假阳性率为30.67％(92/300)，真阴性率为12.33％(37/300)，假阴性率为3.67％(11/300)，血液病细胞及原幼细胞无阳性漏检现象发生。

3讨论

为了保证血液细胞形态学检查结果的准确，原则上每个标本都应镜检，但实际是不可能做到的，因此复检筛选标准的制订至关重要。这是解决当前“供需矛盾”最有效的办法，而准确的筛选取决于适合本实验室具体情况和要求的筛选标准的制订及严格、准确的实施。在IS015189认可现场评审开出的“不符合项”或“观察项”主要集中在有关细胞形态学检验相关方面的工作缺乏适合本实验室使用的仪器筛选标准和复片率过低等现象。

血涂片复审虽然是血细胞分析后质量保证措施，但显微镜检查为定性或半定量分析方法，对于仪器法定量分析的项目是否适合以镜检“验证”，比如I)“RBC明显大小不等”验证“红细胞体积分布宽度(RDW)增大”、“低色素RBC>0.3”验证“平均红细胞血红蛋白浓度(MCHC)减低”科学与否。另外，由于观察者的技术水平不同和涂片中细胞分布的差异，故要充分认识显微镜检查的局限性。总之。临床实验室制订血涂片复审筛选标准是一项科学性强、涉及面广、影响因素多的工作。应该循证规律，切勿草率从事。

“假阴性”是关键参数。具有诊断意义的重要参数不能出现假阴性。其他参数假阴性率也应

对国际41条复检规则和Sysmex公司提供的21条复检规则进行评估后发现在3800份标本中，国际41条复检规则得到的假阳性率为32.05％(1218/3800)；而Sysmex公司提供的21条复检规则得到的假阳性率为17.97％(683/3800)；远低于国际41条复检规则，但两者的假阴性率分别为3.11％(120/3800)和4.08％(155/3800)，差异不大，均未超过5％的最大可接受的假阴性率标准。如果按照国际41条复检规则进行复检。涂片复审率为45.78％；而按照Sysmex公司提供的21条复检规则进行复检，涂片复审率为29.34％，复审率远低于国际41条复检规则，并且试验血液病细胞及原幼细胞无阳性漏检现象发生。从而在保证检验质量的前提下大大提高了工作效率。综合SysmexXE-2100五分类血细胞分析仪的性能特点和我科的病源常规工作情况，笔者认为Sysmex公司提供的21条复检规则作为“三甲”医院规模的检验科血涂片复审筛选标准较为实用。在实际工作中只需根据具体情况对个别条款加以修正、完善和改进即可。

篇4

关键词：关联规则挖掘；Apriori算法；频繁项目集；侯选数据集

中图分类号：TP311 文献标识码：B 文章编号：1004373X(2008)1807803

Improvement of Apriori Algorithm in Association Rule Mining

ZHU Ye,YE Gaoying

(Chengdu University of Information Technology,Chengdu,610225,China)

Abstract：In this paper,the principle and performance of Apriori algorithm is introduced,and two defects of Apriori algorithm:scanning database too much and creating excessive candidate itemsets are analyzed.A new Apriori algorithm has been designed for finding out the highest dimension frequent itemsets from frequent 1itemset directly.A great number of linking operations in finding frequent itemsets dimension by dimension are canceled over all.The algorithm is improved efficiently.

Keywords：association rule mining;Apriori algorithm;frequent itemset;candidate itemset

1 引 言

数据挖据［1］(Data Mining)是一个多学科交叉研究领域，是从大量数据中提取或“挖掘”出未知的、潜在的、有用的知识。从现状来看，数据挖掘的研究仍然处于广泛研究探索阶段，主要包括特征化与比较、关联规则挖掘、分类预测和聚类分析等方法。其中关联规则挖掘(Association Rule Mining)是数据挖掘中最活跃的研究方法之一。

最早由Agrawal等人［2］(1993年)针对购物篮分析(Basket Analysis)问题提出的，其目的是为了发现交易数据库(Transaction Database)中不同商品之间的联系规则。通过关联规则发现算法寻找形如“如果，那么”的规则，这种规则以其简洁性已经多次成功应用到决策支持系统，指导人们在各个领域中的活动。在关联规则挖掘算法的研究中，Agrawal提出的Apriori算法最为经典，但该算法本身固有的缺陷［3］是多次扫描数据库，并产生庞大的候选数据集。

本文从这两个缺陷入手，减少扫描数据库的次数，并省去大量候选集的产生过程，从而提高算法效率。

2 关联规则基本概念

一个事务数据库中的关联规则挖掘可以描述如下［3］：设I={i1,i2,…,im}是一个项目集合，事务数据库D={t1,t2,…,tn}是由一系列具有惟一标识TID的事务组成，每个事务ti(i=1,2,…,n)都对应于I上的子集。

定义1 支持度(Support):

指包含项目集(Itemset)I1(I1∈I)的事务在D中所占的百分比。

定义2 信任度(Confidence):

在形如I1I2的关联规则中(I1∈I，I2∈I)，信任度指包含I1和I2的事务数与包含I1的事务数之比，即在I1发生的情况下，I2也发生的可能性。

定义3 频繁项目集(Frequent Itemset)和最大频繁项目集:

对项目集和事务数据库D，T中所有满足用户指定的最小支持度的项目集称为频繁项目集。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集。

定义4 强关联规则(Strong Association Rule)：

指D在I上满足最小支持度和用户指定的最小信任度的关联规则。

关联规则挖掘问题就是通过最小支持度和最小信任度在一个事务数据库中寻找强关联规则的过程，划分为2个子问题：

(1) 发现最大频繁项目集；

(2) 在最大频繁项目集中生成强关联规则。第一个子问题是本文的研究重点，即提出一种新的算法来发现最大频繁项目集。

3 Apriori算法及缺点分析

1994年Agrawal等人建立用于事务数据库挖掘的项目集的格空间理论［4］：频繁项目集的子集是频繁项目集，非频繁项目集的超集是非频繁项目集。Apriori算法［3］依据此理论进行剪枝。该算法是通过项目集数目不断增长来逐步发现频繁项目集的，算法输入数据集D和最小支持数minsupcount(最小支持度与事务数的乘积)，输出频繁项目集L。算法首先产生1频繁项目L1，然后是2频繁项目集L2，直至不再能扩展频繁项目集的元素数目而算法停止。在第k次循环中，过程先产生k候选项目集的集合Ck，然后通过扫描数据库得到CK的支持度并测试产生k频繁项目集Lk。算法过程［5］是：连接剪枝生成Ck扫描计数比较生成Lk。

从以上分析可以发现，Apriori算法使用逐层搜索的迭代方法，通过低维频繁项目集产生高维频繁项目集［4］。这样，就致使Apriori算法存在2个致命的性能瓶颈：

(1) 多次扫描事务数据库。每次k循环，候选集Ck中的每个元素都必须通过扫描数据库1次来判断其是否加入Lk。如果频繁大项目集包含n项，则至少需要扫描事务数据库n遍，需要很大的I/O负载。

(2) 可能产生庞大的候选集。由Lk-1产生k候选集Ck是呈指数增长的，例如104个1频繁项目集有可能产生接近107个元素的2候选集，如此庞大的候选集对时间和存储空间是一个挑战。

4 改进Apriori算法

Apriori算法使用候选集去找频繁集，算法反复连接、剪枝，导致执行效率低。因此，考虑使用其他方法来取代通过候选集去找频繁集的过程，改变由低维频繁项目集到高维频繁项目集的多次连接运算，这样，既可以避免大量候选集的产生，又可以减少数据库的扫描次数，从而提高算法效率。在介绍具体改进措施之前，引入2条推论：

推论1 如果K频繁项目集Lk中的项目集个数≤K时，则该集合为最大频繁项目集的集合。

证明： 根据项目集格空间理论，假如存在K+1频繁项目集Lk+1，那么对于Lk+1的K+1个K项目子集都是频繁项目集，与题设项目集个数≤K矛盾，所以，如果频繁项目Lk中项目集的个数≤K时，则无法产生K+1频繁项目集Lk+1，因此，该推论成立。

推论2 最大频繁项目集Lk的项目数K小于等于在所有事务中满足支持计数的最大项目数k。对于事务T，若2项集的支持计数为sup2，3项集的支持计数为sup3，…，n-项集的支持计数为supn(n为所有事务中的最大项目数)，其中，supk( Minsupport(2(k(n)且supk+1

证明： (反证法)假设K大于k，则存在频繁项目集Lk满足支持计数，而与满足支持计数的项目数k最大矛盾，因此，最大频繁项目数K不可能大于满足支持计数的最大项目数k，推论得证。

一般地，只关心那些不被其他频繁项目集所包含的最大项目集的集合，在这些频繁项目集中发现关联规则。所以，问题归结为如何高效确定最大频繁项目集。改变通常的做法，应用上述推论，先确定最大频繁项目集的项目数K，然后找出所有频繁项集Lk。算法NewApriori描述如下：

输入：事务数据T；最小支持数minsupcount。

输出：最大频繁项目集L。

(1) C［n］=0; //初始化数组C［n］，n为所有事务中的最大项目数

(2)for each ti∈Tdo begin

(3) i=|ti|;//i为每个事务所含的项目数

(4) C［i］=C［i］+1

(5)end

(6) L1={large 1-itemsets};//所有满足支持计数的1频繁项目集

(7)for i=nto 2do begin

(8)if(C［i］(minsupcount) then begin

(9) k=i;

//根据推论2，k≤i，由于找最大的频繁项集，因此可以假定k=i

(10) Ck={large k-itemsets};//直接从L1中生成Ck

(11) Lk={Ck|Ck.count(minsupcount and Ck.count(k};//根据推论1

(12)if Lk≠hthen

(13)return Lk

(14)end

(15)end

该算法的改进主要体现在以下2方面：

(1) 最大频繁集的产生过程改变为从高维到低维的搜索过程，根据不同项目个数的出现频率，直接从1频繁项目集产生高维频繁项目集，省去多次的连接运算及大量候选集的产生，节约了运行时间和主存空间。

(2) 减少扫描数据库次数，该算法扫描数据库的次数最少可以减少到3次(第1次，计算C\；第2次，得到1频繁项目集；第3次，计算大于支持计数的Lk)，而Apriori算法则需要扫描k次，因此，对于维数较高(k值较大)的频繁项目集的计算，效率提高更明显。

5 实例分析

下面给出一个服装店的20个收款机事务记录，每一事务T代表购买的商品集合，I1-I6分别表示不同的商品，最小支持数minsupcount=3,见表1所示。

根据NewAgriori算法

(1) 计算C［n］，C［1］=4，C［2］=6，C［3］=5，C［4］=4，C［5］=1；

(2) 得到1频繁项目集L1={{I2}，{I3}，{I4}，{I5}，{I6}}；

(3) 由于C［5］minsupcount，则先假定最大频繁项目集的项目数k=4，从L1中产生所有4项目集，共5个，分别是：{I2，I3，I4，I5}，{I2，I3，I4，I6}，{I3，I4，I5，I6}，{I2，I4，I5，I6}，{I2，I3，I5，I6}，扫描数据库计算该5个候选集的支持计数，求得满足最小支持计数的项集为：{I2，I4，I5，I6}，其支持计数=4，根据推论1可知，该频繁项目集即是最大频繁项目集，计算结束。如果使用Apriori算法，则需要扫描4次数据库，并且从1频繁项目集到4频繁项目集的连接计算共需产生24个候选集。而使用NewApriori算法，整个过程共扫描了3次数据库，且只产生5个4项候选集，很明显，无需产生大量的候选集同样可以找到最大频繁项目集，同时减少了扫描数据库的次数。但从上述算法流程不难看出，如果第一次假定的k不是所要求的最大频繁项目集的项目数时，则需要再次寻找符合要求的k值，多一次寻找，就多一次对数据库的扫描，候选集的数量也会随之增多。不过，数据库的扫描次数不会超过k次，为了避免过多冗余的候选集，可以将1频繁项目集按支持计数的大小顺序排列，组合支持计数相对少的项目，及早发现非频繁项目，以减少候选集的产生。因此，该算法特别适合于项目数比较大的最大频繁项目的查找。

6 结 语

Apriori算法作为最经典的关联规则挖掘算法被广泛使用，由于其固有的局限性，出现了大量的改进算法。本文提出的NewApriori算法也针对引起性能瓶颈的缺点而做出的改进，提高了系统运行效率。但不足的是，此算法只能找到项数最大的频繁项目集，也就是说，得到的频繁项目集不够完整，因此，还需要进一步完善。

参 考 文 献

［1］Jiawei Han,Micheline Kamber.数据挖掘概念与技术\.范明,孟小峰，译.北京:机械工业出版社,2001.

［2］Agrawal R,Imielinske T,Swami A.Mining Association Rules between Sets of Items in Large Databases.Proc.of the ACM SIGMOD International Conference on the Management of Data,Washington D.C.,1993:207216.

［3］毛国君,段立娟.数据挖掘原理与算法\.北京:清华大学出版社,2005.

［4］Agrawal R,Srikant R.Fast Algorithms for Mining Association Rules.Proc.1994 Int.Conf.Very Large Database.Santiago,Chile,1994:487499.

［5］李小兵.关联规则挖掘算法的改进与优化研究\.厦门大学学报:自然科学版,2005(7):468471.

［6］谢宗毅.关联规则挖掘Apriori算法的研究与改进\.杭州电子科技大学学报,2006(6):7882.

篇5

关键词：数据挖掘；频繁项集；链表数组

中图分类号：TP311 文献标识码：A 文章编号：1007-9599　（2012）　19-0000-03

1 引言

数据挖掘是从大量的数据中，发掘出潜在有用的模式和信息的技术。当前主要的数据挖掘方法有关联规则、分类和聚类。其中，关联规则致力于发现数据中的频繁模式，它最早由R.Agrawal等人针对购物篮问题提出，其目的是为了发现交易数据库中不同商品间的联系，以帮助商家进行商品目录和货架设计，科学安排进货和库存，实施交叉销售。

最经典的频繁项集挖掘算法是Apriori算法[1]。它首次采用了基于频繁项集性质的自底向上的广度优先逐层搜索迭代技术，即利用已知的频繁k-项集推导出频繁（k+1）-项集。Apriori算法有三个主要步骤：（1）用频繁（k-1）-项集进行自连接来产生候选k-项集。（2）用Apriori性质进行对候选k-项集进行剪枝操作。（3）扫描数据库得到候选项集支持度。由上述分析可知，Apriori算法需要多次扫描数据库，I/O开销较大。另外，子集计算、共同前缀项集计算等也极大增加了算法的开销。为提高Apriori算法的效率，先后出现了许多基于Apriori的改进算法。文献[2]提出DHP算法，它利用哈希技术压缩候选项集集合Ck，同时也缩减了数据库的大小，降低I/O开销。此算法缺点在于哈希表会增加算法的内存开销，而且实现起来也较为麻烦。文献[3]提出Partition算法，它采用划分技术成功解决内存不足的问题，具有较好的可扩展性。然而，Partition算法可能产生大量虚假的候选项集。文献[4]提出选样技术，在给定数据的一个子集中挖掘频繁模式。Sampling算法简单并减少了I/O代价，但其产生的结果不精确，即存在所谓的数据扭曲。文献[5]提出DIC算法，它放松了产生候选项集和计数的严格界限，采用动态模式计数法以减少数据库的扫描次数，具有较好效率。

尽管有如上所述的诸多改进方法，但时间效率还不尽理想，为更进一步提高算法性能，提出一种基于Apriori的改进型算法FAA（Fast　Apriori　Algorithm）。FAA算法通过构造链表数组来快速产生频繁2-项集并减少数据库的扫描次数，优化对项集计数操作；改进连接策略来简化连接算法复杂度。

2 FAA算法思想

2.1 链表数组定义及生成算法。链表数组定义：数组为n个指针的一维数组P[n]，对应数据库中的频繁项I1，I2，…，In，对应数组长度n为数据库中频繁项的数量。结点为事务结点，分为事务域、计数域和指针域。事务域是以频繁项为后缀的事务编码。计数域是该事务编码的数量，指针域是指向下一结点的指针。

编码方法：设数据库中有n个频繁项I1，I2，…，In。事务t的编码就是长度为n的0、1位串。在t中出现的项，其相应位置用1表示，否则填0。例如，有四个频繁项a，b，c，d。那么，一个包含a和c的事务就被映射为1010。