科學(xué)計(jì)數(shù)法的規(guī)則精選(五篇)

序言：作為思想的載體和知識的探索者，寫作是一種獨(dú)特的藝術(shù)，我們?yōu)槟鷾?zhǔn)備了不同風(fēng)格的5篇科學(xué)計(jì)數(shù)法的規(guī)則，期待它們能激發(fā)您的靈感。

篇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.

關(guān)鍵詞： Apriori；頻繁項(xiàng)集；關(guān)聯(lián)規(guī)則；網(wǎng)元

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

中圖分類號：TN91 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2013）10-0183-02

1 Apriori算法簡介

Apriori算法是R.Agrawal和R.Srikant于1994年提出的為布爾關(guān)聯(lián)規(guī)則挖掘頻繁項(xiàng)集的原創(chuàng)性算法。Apriori使用一種稱作逐層搜索的迭代方法，k項(xiàng)集用于搜索（k+1）項(xiàng)集。首先，通過掃描數(shù)據(jù)庫，累計(jì)每個(gè)項(xiàng)的計(jì)數(shù)，并收集滿足最小支持度的項(xiàng)，找出頻繁1項(xiàng)集的集合，該集合記作L1，然后，L1用于找頻繁2項(xiàng)集的集合L2，L2用于找L3，如此下去，直到不能再找到頻繁k項(xiàng)集，找每個(gè)需要一次數(shù)據(jù)庫全掃描。

為提高頻繁項(xiàng)集逐層產(chǎn)生的效率，Apriori算法用先驗(yàn)性質(zhì)（Apriori性質(zhì)）壓縮搜索空間，Apriori性質(zhì)即：頻繁項(xiàng)集的所有非空子集也必須是頻繁的。

Apriori算法的基本思想

Lk：頻繁k-項(xiàng)集的集合

Ck：候選k-項(xiàng)集的集合

①首先，C1由所有項(xiàng)組成；掃描數(shù)據(jù)庫D，累計(jì)每個(gè)項(xiàng)的計(jì)數(shù)，并收集滿足最小支持度的項(xiàng)，產(chǎn)生L1。②然后，用L1中的項(xiàng)兩兩組合得到候選2-項(xiàng)集的集合C2；再次掃描數(shù)據(jù)庫D，累計(jì)C2每個(gè)2-項(xiàng)集的計(jì)數(shù)，產(chǎn)生L2。③接下來，用L2中的2-項(xiàng)集產(chǎn)生候選3-項(xiàng)集的集合C23；再次掃描數(shù)據(jù)庫D，累計(jì)C3每個(gè)3-項(xiàng)集的計(jì)數(shù)，產(chǎn)生L3。④一般地，由長度為k-1的頻繁項(xiàng)集的集合Lk產(chǎn)生長度為k的候選項(xiàng)集的集合Ck，并且掃描數(shù)據(jù)庫D，產(chǎn)生Lk。⑤如此下去，直到不能再產(chǎn)生更長的頻繁項(xiàng)集。

對于每個(gè)頻繁項(xiàng)集Y和任意X？奐Y，X≠？覫，如果support（Y）/support（X）？叟min_conf，則輸出強(qiáng)規(guī)則X？圯Y-X

2 告警數(shù)據(jù)準(zhǔn)備

告警原始數(shù)據(jù)舉例如下：

本文將單網(wǎng)元告警數(shù)據(jù)作為原始數(shù)據(jù)集，通過Apriori算法發(fā)現(xiàn)該類型網(wǎng)元的頻繁項(xiàng)集及告警關(guān)聯(lián)規(guī)則，因此如何準(zhǔn)備告警數(shù)據(jù)集是目前需要首先解決的問題。

告警數(shù)據(jù)準(zhǔn)備目標(biāo)是根據(jù)設(shè)備維護(hù)經(jīng)驗(yàn)，首先找到24小時(shí)內(nèi)每5分鐘內(nèi)的告警數(shù)據(jù)集，模型如下。

根據(jù)實(shí)際設(shè)備告警情況，用下表數(shù)據(jù)（記為：D）為例進(jìn)行說明。

3 告警數(shù)據(jù)頻繁項(xiàng)集挖掘

根據(jù)Apriori算法的基本原理，頻繁項(xiàng)集挖據(jù)過程如下所示，假定最小支持度為2：

①掃描D表，對每個(gè)候選計(jì)數(shù)得到下表C1。（表3）

②比較候選支持度計(jì)數(shù)與最小支持度計(jì)數(shù)得到下表L1。（表4）

③由L1產(chǎn)生候選表C2。（表5）

④掃描D，對C2中每個(gè)候選計(jì)數(shù)形成新的C2。（表6）

⑤比較候選支持度計(jì)數(shù)與最小支持度計(jì)數(shù)，得到表L2。（表7）

⑥有L2產(chǎn)生候選C3。（表8）

⑦掃描D，對C3中每個(gè)候選計(jì)數(shù)得到新的C3。（表9）

⑧比較候選支持度技術(shù)與最小支持度計(jì)數(shù)，得到L3。（表10）

由此，我們得到兩個(gè)頻繁項(xiàng)集。

4 告警關(guān)聯(lián)規(guī)則挖掘

4.1 基本思想 對于每個(gè)頻繁項(xiàng)集Y和任意X？奐Y，X≠？覫，如果support（Y）/support（X）？叟min_conf，則輸出強(qiáng)規(guī)則X？圯Y-X。

4.2 關(guān)聯(lián)規(guī)則挖掘 對于頻繁項(xiàng)集L31{2550、2235、1815}，L31的非空子集有{2550、2235}、{2550、1815}、{2235、1815}、{2550}、{2235}、{1815}，計(jì)算其置信度如下：

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%

對于頻繁項(xiàng)集L32{2550、2335、2229}，L32的非空子集有{2550、2235}、{2550、2229}、{2235、2229}、{2550}、{2235}、{2229}，計(jì)算其置信度如下：

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是強(qiáng)規(guī)則。

5 總結(jié)

通過Apriori算法，我們可以從大量的告警數(shù)據(jù)中發(fā)現(xiàn)更多有用的告警關(guān)聯(lián)規(guī)則，并提高告警的壓縮比，更快的發(fā)現(xiàn)故障根源，從而減少設(shè)備監(jiān)控、維護(hù)人員的工作量，提高工作效率，為電信行業(yè)的設(shè)備維護(hù)保障提供更好、更有效的維護(hù)手段和方法。

參考文獻(xiàn)：

[1]鄭明.淺談網(wǎng)絡(luò)數(shù)據(jù)挖掘在電子商務(wù)中的應(yīng)用[J].中小企業(yè)管理與科技（下旬刊），2009，02.

篇2

[關(guān)鍵詞]計(jì)數(shù)標(biāo)準(zhǔn)型一次抽樣檢驗(yàn)方案；計(jì)數(shù)調(diào)整型抽樣檢驗(yàn)方案

產(chǎn)品質(zhì)量檢驗(yàn)是指借助于某種手段或方法來測定產(chǎn)品的--個(gè)或多個(gè)質(zhì)量特性，然后把測得的結(jié)果同規(guī)定的產(chǎn)品質(zhì)量標(biāo)準(zhǔn)進(jìn)行比較，從而對產(chǎn)品作出合格或不合格判斷的活動(dòng)。通過觀察和判斷，適當(dāng)時(shí)結(jié)合測量、試驗(yàn)所進(jìn)行的符合性評價(jià)。

一、產(chǎn)品質(zhì)量抽樣檢驗(yàn)的意義

產(chǎn)品質(zhì)量的抽樣檢驗(yàn)是從產(chǎn)品總體中，抽取若干樣本，對樣本進(jìn)行檢測并按標(biāo)準(zhǔn)所規(guī)定的判定規(guī)則對總體做出合格與否的判定。因此，抽取樣本的科學(xué)性在很大程度上決定了產(chǎn)品質(zhì)量檢驗(yàn)結(jié)果的代表性和真實(shí)性。

產(chǎn)品質(zhì)量抽樣檢驗(yàn)方法，亦稱統(tǒng)計(jì)抽樣檢驗(yàn)方法，是建立在概率統(tǒng)計(jì)理論基礎(chǔ)上的。其關(guān)鍵是：如何設(shè)計(jì)合理的抽樣檢查方案，才能保證檢驗(yàn)過程公正、科學(xué)、有效

首先，要明確抽樣方案所依據(jù)的標(biāo)準(zhǔn)。目前我國有4個(gè)標(biāo)準(zhǔn)規(guī)定了質(zhì)量監(jiān)督抽樣方案和一個(gè)產(chǎn)品質(zhì)量監(jiān)督復(fù)查抽樣方案，即GB/T14162-1993；GB/T14437-1997；GB/T15482-1995；GB/T14900-1994；GB/T16306-1996。

其次，確定樣本量的多少。樣本量的確定主要應(yīng)先明確批量和樣本量之間的關(guān)系，當(dāng)批量N確定時(shí)，只要明確檢驗(yàn)水平，就可以檢索到樣本量的大小。

最后，確定判斷依據(jù)，即以極限質(zhì)量LQ為質(zhì)量指標(biāo)來判定。極限質(zhì)量的確定需考慮的問題主要有：產(chǎn)品的用途、檢驗(yàn)的經(jīng)濟(jì)性、生產(chǎn)企業(yè)的實(shí)際特點(diǎn)等。

目前國內(nèi)外抽樣檢驗(yàn)方案種類很多，但最基本和最常用的有兩種，即：計(jì)數(shù)標(biāo)準(zhǔn)型一次檢驗(yàn)方案和計(jì)數(shù)調(diào)整型檢驗(yàn)方案。

二、計(jì)數(shù)標(biāo)準(zhǔn)型一次抽樣檢驗(yàn)方案

1.計(jì)數(shù)標(biāo)準(zhǔn)型一次抽樣檢驗(yàn)方案的含義及應(yīng)用范圍

標(biāo)準(zhǔn)型一次抽樣檢驗(yàn)方案，是按供需雙方協(xié)商認(rèn)定的OC曲線，對一批產(chǎn)品進(jìn)行抽樣檢驗(yàn)的方案。制定該方案，需要確定4個(gè)參數(shù)p0，p1，α，β和抽檢方案（n，c）。

計(jì)數(shù)標(biāo)準(zhǔn)型一次抽樣檢驗(yàn)方案的應(yīng)用范圍：適合于一次交易（孤立的一批產(chǎn)品）或破壞性檢驗(yàn)的情況。

2.計(jì)數(shù)標(biāo)準(zhǔn)型一次抽樣檢驗(yàn)方案的設(shè)計(jì)步驟

（1）確定檢驗(yàn)的產(chǎn)品質(zhì)量標(biāo)準(zhǔn)：產(chǎn)品質(zhì)量的合格指標(biāo)，即產(chǎn)品的技術(shù)標(biāo)準(zhǔn)，包括各種功能指標(biāo)、生化指標(biāo)、缺陷的概念和程度等。

（2）確定4個(gè)參數(shù)p0，p1，α，β：

目前普遍認(rèn)同的供應(yīng)者的風(fēng)險(xiǎn)率α和使用者風(fēng)險(xiǎn)率β分別為：α≈0.05，β≈0.10 . p0，p1值的大小由供需雙方協(xié)商確定。先確定一個(gè)合理的p0值，再按一定比例確定p1值。

（3）批的組成：在同一生產(chǎn)條件下生產(chǎn)出來的一批產(chǎn)品，要盡可能直接取做檢驗(yàn)批。若批量過大，也可以劃分為小批后，將小批作為檢驗(yàn)批。但劃分的小批必須是隨機(jī)的。

（4）確定抽檢方案：確定樣本大小n和合格判定數(shù)c，可通過查計(jì)數(shù)標(biāo)準(zhǔn)型一次抽檢表獲得。

三、計(jì)數(shù)調(diào)整型抽樣檢驗(yàn)方案

1.計(jì)數(shù)調(diào)整型抽樣檢驗(yàn)方案的含義及應(yīng)用范圍

計(jì)數(shù)調(diào)整型抽樣檢驗(yàn)方案是由一組嚴(yán)格度不同的抽樣方案和一套轉(zhuǎn)移規(guī)則組成的抽樣體系。計(jì)數(shù)調(diào)整型抽樣檢驗(yàn)方案是根據(jù)過去的檢驗(yàn)的情況，按一套轉(zhuǎn)移規(guī)則隨時(shí)調(diào)整檢驗(yàn)的嚴(yán)格程度，從而改變抽樣檢驗(yàn)方案。

計(jì)數(shù)調(diào)整型抽樣檢驗(yàn)是應(yīng)用范圍最廣、最有影響的一類抽樣檢驗(yàn)方法。主要應(yīng)用于：

a.原材料和元器件的抽樣檢驗(yàn)；

b.過程各環(huán)節(jié)在制品的抽樣檢驗(yàn)；

c.最終產(chǎn)品的抽樣檢驗(yàn)；

d.庫存成品的抽樣檢驗(yàn)；

e.管理過程的抽樣檢驗(yàn)等。

計(jì)數(shù)調(diào)整型抽樣檢驗(yàn)方案的特點(diǎn)：可以根據(jù)產(chǎn)品質(zhì)量的實(shí)際情況，采用一組正常、加嚴(yán)和放寬三個(gè)不同嚴(yán)格程度的檢驗(yàn)方案，并且應(yīng)用一套轉(zhuǎn)換規(guī)則將它們有機(jī)地聯(lián)結(jié)起來。該方案可以起到一個(gè)鼓勵(lì)質(zhì)量好的企業(yè)，（通過放寬檢驗(yàn)）；也可以鞭策質(zhì)量差的企業(yè)，改進(jìn)質(zhì)量（通過加嚴(yán)檢驗(yàn)）。從而，可以起到一個(gè)對供應(yīng)者產(chǎn)品質(zhì)量的管控作用。

2.計(jì)數(shù)調(diào)整型抽樣檢驗(yàn)方案的設(shè)計(jì)步驟

（1）規(guī)定單位產(chǎn)品的質(zhì)量特性指標(biāo)

質(zhì)量特性指標(biāo)是產(chǎn)品、過程或體系與要求有關(guān)的固有可區(qū)分的特征值。如物理的、生化的、感官的、行為的、時(shí)間的、功能的等。有關(guān)指標(biāo)值達(dá)到什么標(biāo)準(zhǔn)才算合格，應(yīng)在檢驗(yàn)規(guī)范中或供銷合同中明確表述。

（2）確定不合格類別的等級

不合格品的分類和質(zhì)量缺陷嚴(yán)重性級別可以參照國家的有關(guān)標(biāo)準(zhǔn)。

不同級別的不合格，其對應(yīng)的不合格率上限值A(chǔ)QL也不同。一般A類不合格品的AQL值應(yīng)小于B類不合格品的AQL值，而B類不合格品的AQL值應(yīng)小于C類不合格品的AQL值。

（3）確定合格質(zhì)量水平AQL：接收質(zhì)量限

設(shè)計(jì)抽檢方案時(shí)，先要確定AQL值，如果供應(yīng)者的產(chǎn)品質(zhì)量水平接近AQL，則進(jìn)行正常檢驗(yàn)；若供應(yīng)者的產(chǎn)品質(zhì)量水平比AQL值低得多，則進(jìn)行放寬檢驗(yàn)；若供應(yīng)者的產(chǎn)品質(zhì)量水平比AQL值高多，則進(jìn)行加嚴(yán)檢驗(yàn)。

AQL值的確定方法，一般可采用檢驗(yàn)法：根據(jù)產(chǎn)品的使用要求、產(chǎn)品的性能、產(chǎn)品的檢驗(yàn)項(xiàng)目數(shù)量、不合格品和不合格種類這些因素予以確定。

實(shí)際操作時(shí)，可先參考有關(guān)資料，暫時(shí)確定一個(gè)AQL值，使用一段時(shí)間后，根據(jù)實(shí)際情況逐漸調(diào)整，達(dá)到合理。

（4）確定檢驗(yàn)水平

檢驗(yàn)水平是用來決定批量與樣本大小之間關(guān)系等級的，其作用就是明確批量N和樣本量n的關(guān)系。

國標(biāo)規(guī)定檢驗(yàn)水有兩類：一般檢驗(yàn)水平ⅰ、ⅱ、ⅲ級和特殊檢驗(yàn)水平S-1、S-2、S-3、S-4四個(gè)檢驗(yàn)水平。無特殊要求情況下，采用一般檢驗(yàn)水平ⅱ。

篇3

[關(guān)鍵詞] IS015189；血涂片復(fù)審；篩選標(biāo)準(zhǔn)；血細(xì)胞形態(tài)學(xué)；鏡檢

[中圖分類號]R446.11　[文獻(xiàn)標(biāo)識碼]C　[文章編號]1673-7210(2011)08(b)-085-03

在全國各醫(yī)院檢驗(yàn)科IS015189認(rèn)可實(shí)驗(yàn)室現(xiàn)場評審中所開的“不符合項(xiàng)”或“觀察項(xiàng)”中主要集中在有關(guān)細(xì)胞形態(tài)學(xué)檢驗(yàn)相關(guān)方面的工作占有相當(dāng)大的比例，血細(xì)胞分析儀的血涂片復(fù)檢率過低，缺乏適合本實(shí)驗(yàn)室使用儀器的篩選標(biāo)準(zhǔn)等是其主要原因。近年來雖然各種類型的血細(xì)胞分析儀得以廣泛應(yīng)用，幫助檢驗(yàn)人員快速完成大量血標(biāo)本的檢測，提高了工作效率，但迄今為止血細(xì)胞分析儀在形態(tài)學(xué)檢查中仍只能作為一種過篩手段，當(dāng)遇到可疑情況，尤其是在病理?xiàng)l件下，必須進(jìn)行人工鏡檢復(fù)查，這已是不爭的事實(shí)。如何能夠讓血細(xì)胞分析儀更好地為臨床服務(wù)，一直是各國血液學(xué)專家共同關(guān)注的問題。2005年國際血液學(xué)復(fù)檢專家組通過對13298份血標(biāo)本進(jìn)行詳細(xì)分析后，推薦了41條自動(dòng)血細(xì)胞分析和分類復(fù)檢規(guī)則。但這只是通則，由于不同儀器或?qū)嶒?yàn)室的病源及篩選目的不同，其并無針對性和特異性。為此IS015189認(rèn)可委要求各參評實(shí)驗(yàn)室必須在參考“血細(xì)胞涂片復(fù)審41條國際規(guī)則”的前提下結(jié)合各自實(shí)驗(yàn)室儀器性能特點(diǎn)及病源，制訂適合于本實(shí)驗(yàn)室的血涂片復(fù)檢規(guī)則。

1材料與方法

1.1材料

1.1.1標(biāo)本來源3800份血標(biāo)本均為來自我院檢驗(yàn)科就診做血常規(guī)的患者，其中，初診標(biāo)本3008份，復(fù)診標(biāo)本792份。所有標(biāo)本于采血后30 min～6h期間用XE-2100自動(dòng)進(jìn)樣模式進(jìn)行檢測，包括全血細(xì)胞計(jì)數(shù)(CBC)、白細(xì)胞分類(DC)、有核紅細(xì)胞(NRBC)、網(wǎng)織紅細(xì)胞(PET)，并將檢測報(bào)告?zhèn)浞荽鏅n。

1.1.2儀器與試劑XE-2100全自動(dòng)血細(xì)胞分析儀，原裝配套試劑，校準(zhǔn)品和質(zhì)控品均由日本Sysmex公司提供。兩臺(tái)顯微鏡均為OlympusCX31型，用于血涂片顯微鏡檢查。

1.2方法

1.2.1實(shí)驗(yàn)人員培訓(xùn)根據(jù)《全國臨床檢驗(yàn)操作規(guī)程》和《白細(xì)胞計(jì)數(shù)參考方法》中制訂的血涂片檢測操作程序(SOP)，對參加實(shí)驗(yàn)的人員進(jìn)行培訓(xùn)，并研討可能出現(xiàn)的問題和解決的措施。

1.2.2儀器的校準(zhǔn)、調(diào)試及報(bào)警(IP)信息的設(shè)置均由sys-mex公司工程師按照儀器標(biāo)準(zhǔn)要求進(jìn)行校準(zhǔn)、調(diào)試和設(shè)置。

1.2.3檢測方法每份標(biāo)本在上機(jī)檢測的同時(shí)制備2張血涂片，并編號用瑞氏染液進(jìn)行染色，然后按照標(biāo)準(zhǔn)操作程序(血涂片檢測SOP文件)進(jìn)行血細(xì)胞形態(tài)學(xué)的鏡檢，每2人為1組。

1.2.4初步復(fù)檢規(guī)則的制訂利用XE-2100血細(xì)胞分析儀的IP信息報(bào)警系統(tǒng)對WBC、RBC、PLT的數(shù)量異常和形態(tài)學(xué)異常的提示。并參照“國際血液學(xué)4l條復(fù)檢規(guī)則”，由sySHICX公司工程師制訂出的XE-2100血細(xì)胞分析儀自動(dòng)血細(xì)胞計(jì)數(shù)和WBC分類初步復(fù)檢規(guī)則共21條。見表1。

1.2.5制訂血涂片陽性判斷標(biāo)準(zhǔn)①RBC明顯大小不等，染色異常RBc>30％；②巨大PLT>15％；③見到PLT聚集；④存在Dohle小體細(xì)胞>10％；⑤中毒顆粒中性粒細(xì)胞>0.1；⑥空泡變性粒細(xì)胞>0.1；⑦原始細(xì)胞≥0.01；⑧早幼，中幼粒細(xì)胞≥0.01；⑨晚幼粒細(xì)胞>0.02；⑩桿狀核粒細(xì)胞>0.05；⑩異淋>0.05；⑩嗜酸粒細(xì)胞>0.05；⑩嗜堿粒細(xì)胞>0.01；有核紅細(xì)胞>0.01；⑩漿細(xì)胞>0.01。

1.2.6對比雙盲法(儀器分析和血涂片復(fù)審)兩者檢測結(jié)果，分別計(jì)算血涂片復(fù)審率及儀器分析的真陽性率(觸及初檢規(guī)則且鏡檢為陽性的比率)、真陰性率(不觸及初檢規(guī)則且鏡檢為陰性的比率)、假陽性率(觸及初檢規(guī)則但鏡檢為陰性的比率)、假陰性率(不觸及初檢規(guī)則但鏡檢為陽性的比率)；以及血涂片復(fù)檢率(復(fù)檢率=真陽性率+假陽性率)。

表1初步復(fù)檢規(guī)則織紅)超出儀器檢測線性；稀釋標(biāo)本后重新測定；并全部(初診+復(fù)診)推片鏡檢。

2.WBC、RBC、HGB、PLT無結(jié)果；檢查標(biāo)本是否有凝塊；重測標(biāo)本；并全部(初+復(fù))推片鏡檢。

3.WBC30，0x109／L；全部(初+復(fù))推片鏡檢。

4.PLT1000x10(sup)9(/sup)/L；全部(初+復(fù))推片鏡檢。

5.MCV(平均紅細(xì)胞體積)110n(成人)；全部(初+復(fù))推片鏡檢。

6.MCHC(平均紅細(xì)胞血紅蛋白濃度)>380 g/l或

7.DC(白細(xì)胞分類)無結(jié)果或結(jié)果不全；全部(初+復(fù))推片鏡檢及人工分類。

8.Neut#(中性粒細(xì)胞絕對計(jì)數(shù))20.0x10(sup)9(/sup)/I；全部(初+復(fù))推片鏡檢。

9.Lvmph#(淋巴細(xì)胞絕對計(jì)數(shù))>5.0x10(sup)9(/sup)/l；全部(初+復(fù))推片鏡檢。

10.Mono#(單核細(xì)胞絕對計(jì)數(shù))>1.5×10(sup)9(/sup)/L；全部(初+復(fù))推片鏡檢。

11.Fos#(嗜酸粒細(xì)胞絕對計(jì)數(shù))>2.0x10(sup)9(/sup)/L；全部(初+復(fù))推片鏡檢。

12.Baso#(嗜堿粒細(xì)胞絕對計(jì)數(shù))>0.Sxl0(sup)9(/sup)/l；全部(初+復(fù))推片鏡檢。

13.WBC IP Message(白細(xì)胞異常散點(diǎn)圖)；全部(初+復(fù))推片鏡檢。

14.WBC lP Message(未成熟粒細(xì)胞)；全部(初十復(fù))推片鏡檢。

15.WBC lP Message(核左移)；全部(初+復(fù))推片鏡檢。

16.WBC IP Message(異形淋巴細(xì)胞或原始細(xì)胞)；全部(初+復(fù))推片鏡檢。

17.WBC IP Message(原始細(xì)胞)；全部(初+復(fù))推片鏡檢。

18.WBC lP Message(有核紅細(xì)胞)；全部(初+復(fù))推片鏡檢。

19.PLT lP Message(除PLT聚集外的PLT和MPV(平均血小板體積)報(bào)警)；全部(初+復(fù))推片鏡檢。

20.CBC+DC(新生兒標(biāo)本)；全部(初+復(fù))推片鏡檢。

21.CBC+DC(血液病標(biāo)本)；全部(初+復(fù))推片鏡檢一

2結(jié)果

2.1鏡檢結(jié)果

3 800份標(biāo)本的儀器檢測數(shù)據(jù)和顯微鏡人工鏡檢結(jié)果：①根據(jù)“血細(xì)胞涂片復(fù)審41條國際規(guī)則”的檢測結(jié)果進(jìn)行統(tǒng)計(jì)學(xué)分析，真陽性率為13.73％(522/3800)，假陽性率為32.05％(1218/3800)，真陰性率為51.05％(1940/3800)，假陰性率為3.11％(120/3800)，涂片復(fù)審率為45.78％；②按Sysmex公司提供的21條規(guī)則對檢測結(jié)果進(jìn)行統(tǒng)計(jì)學(xué)分析，真陽性率為11.37％(432/3800)，假陽性率為17.97％(683/3800)，真陰性率為66.58％(2530/3800)，假陰性率為4.08％(155/3800)，涂片復(fù)審率為2934％。

2.2驗(yàn)證試驗(yàn)

為了驗(yàn)證svsmex公司提供的21條復(fù)檢規(guī)則的有效性，將這21條復(fù)檢規(guī)則設(shè)置在xE-2100血細(xì)胞分析儀的Lab-msn程序中，選擇300份(主要是血液病、感染性疾病、新生兒和腫瘤化療患者)血標(biāo)本在xE-2100血細(xì)胞分析儀上進(jìn)行檢測，并與涂片鏡檢結(jié)果對比分析。結(jié)果顯示：真陽性率為53.33％(160/300)，假陽性率為30.67％(92/300)，真陰性率為12.33％(37/300)，假陰性率為3.67％(11/300)，血液病細(xì)胞及原幼細(xì)胞無陽性漏檢現(xiàn)象發(fā)生。

3討論

為了保證血液細(xì)胞形態(tài)學(xué)檢查結(jié)果的準(zhǔn)確，原則上每個(gè)標(biāo)本都應(yīng)鏡檢，但實(shí)際是不可能做到的，因此復(fù)檢篩選標(biāo)準(zhǔn)的制訂至關(guān)重要。這是解決當(dāng)前“供需矛盾”最有效的辦法，而準(zhǔn)確的篩選取決于適合本實(shí)驗(yàn)室具體情況和要求的篩選標(biāo)準(zhǔn)的制訂及嚴(yán)格、準(zhǔn)確的實(shí)施。在IS015189認(rèn)可現(xiàn)場評審開出的“不符合項(xiàng)”或“觀察項(xiàng)”主要集中在有關(guān)細(xì)胞形態(tài)學(xué)檢驗(yàn)相關(guān)方面的工作缺乏適合本實(shí)驗(yàn)室使用的儀器篩選標(biāo)準(zhǔn)和復(fù)片率過低等現(xiàn)象。

血涂片復(fù)審雖然是血細(xì)胞分析后質(zhì)量保證措施，但顯微鏡檢查為定性或半定量分析方法，對于儀器法定量分析的項(xiàng)目是否適合以鏡檢“驗(yàn)證”，比如I)“RBC明顯大小不等”驗(yàn)證“紅細(xì)胞體積分布寬度(RDW)增大”、“低色素RBC>0.3”驗(yàn)證“平均紅細(xì)胞血紅蛋白濃度(MCHC)減低”科學(xué)與否。另外，由于觀察者的技術(shù)水平不同和涂片中細(xì)胞分布的差異，故要充分認(rèn)識顯微鏡檢查的局限性。總之。臨床實(shí)驗(yàn)室制訂血涂片復(fù)審篩選標(biāo)準(zhǔn)是一項(xiàng)科學(xué)性強(qiáng)、涉及面廣、影響因素多的工作。應(yīng)該循證規(guī)律，切勿草率從事。

“假陰性”是關(guān)鍵參數(shù)。具有診斷意義的重要參數(shù)不能出現(xiàn)假陰性。其他參數(shù)假陰性率也應(yīng)

對國際41條復(fù)檢規(guī)則和Sysmex公司提供的21條復(fù)檢規(guī)則進(jìn)行評估后發(fā)現(xiàn)在3800份標(biāo)本中，國際41條復(fù)檢規(guī)則得到的假陽性率為32.05％(1218/3800)；而Sysmex公司提供的21條復(fù)檢規(guī)則得到的假陽性率為17.97％(683/3800)；遠(yuǎn)低于國際41條復(fù)檢規(guī)則，但兩者的假陰性率分別為3.11％(120/3800)和4.08％(155/3800)，差異不大，均未超過5％的最大可接受的假陰性率標(biāo)準(zhǔn)。如果按照國際41條復(fù)檢規(guī)則進(jìn)行復(fù)檢。涂片復(fù)審率為45.78％；而按照Sysmex公司提供的21條復(fù)檢規(guī)則進(jìn)行復(fù)檢，涂片復(fù)審率為29.34％，復(fù)審率遠(yuǎn)低于國際41條復(fù)檢規(guī)則，并且試驗(yàn)血液病細(xì)胞及原幼細(xì)胞無陽性漏檢現(xiàn)象發(fā)生。從而在保證檢驗(yàn)質(zhì)量的前提下大大提高了工作效率。綜合SysmexXE-2100五分類血細(xì)胞分析儀的性能特點(diǎn)和我科的病源常規(guī)工作情況，筆者認(rèn)為Sysmex公司提供的21條復(fù)檢規(guī)則作為“三甲”醫(yī)院規(guī)模的檢驗(yàn)科血涂片復(fù)審篩選標(biāo)準(zhǔn)較為實(shí)用。在實(shí)際工作中只需根據(jù)具體情況對個(gè)別條款加以修正、完善和改進(jìn)即可。

篇4

關(guān)鍵詞：關(guān)聯(lián)規(guī)則挖掘；Apriori算法；頻繁項(xiàng)目集；侯選數(shù)據(jù)集

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：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 引 言

數(shù)據(jù)挖據(jù)［1］(Data Mining)是一個(gè)多學(xué)科交叉研究領(lǐng)域，是從大量數(shù)據(jù)中提取或“挖掘”出未知的、潛在的、有用的知識。從現(xiàn)狀來看，數(shù)據(jù)挖掘的研究仍然處于廣泛研究探索階段，主要包括特征化與比較、關(guān)聯(lián)規(guī)則挖掘、分類預(yù)測和聚類分析等方法。其中關(guān)聯(lián)規(guī)則挖掘(Association Rule Mining)是數(shù)據(jù)挖掘中最活躍的研究方法之一。

最早由Agrawal等人［2］(1993年)針對購物籃分析(Basket Analysis)問題提出的，其目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫(Transaction Database)中不同商品之間的聯(lián)系規(guī)則。通過關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法尋找形如“如果，那么”的規(guī)則，這種規(guī)則以其簡潔性已經(jīng)多次成功應(yīng)用到?jīng)Q策支持系統(tǒng)，指導(dǎo)人們在各個(gè)領(lǐng)域中的活動(dòng)。在關(guān)聯(lián)規(guī)則挖掘算法的研究中，Agrawal提出的Apriori算法最為經(jīng)典，但該算法本身固有的缺陷［3］是多次掃描數(shù)據(jù)庫，并產(chǎn)生龐大的候選數(shù)據(jù)集。

本文從這兩個(gè)缺陷入手，減少掃描數(shù)據(jù)庫的次數(shù)，并省去大量候選集的產(chǎn)生過程，從而提高算法效率。

2 關(guān)聯(lián)規(guī)則基本概念

一個(gè)事務(wù)數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則挖掘可以描述如下［3］：設(shè)I={i1,i2,…,im}是一個(gè)項(xiàng)目集合，事務(wù)數(shù)據(jù)庫D={t1,t2,…,tn}是由一系列具有惟一標(biāo)識TID的事務(wù)組成，每個(gè)事務(wù)ti(i=1,2,…,n)都對應(yīng)于I上的子集。

定義1 支持度(Support):

指包含項(xiàng)目集(Itemset)I1(I1∈I)的事務(wù)在D中所占的百分比。

定義2 信任度(Confidence):

在形如I1I2的關(guān)聯(lián)規(guī)則中(I1∈I，I2∈I)，信任度指包含I1和I2的事務(wù)數(shù)與包含I1的事務(wù)數(shù)之比，即在I1發(fā)生的情況下，I2也發(fā)生的可能性。

定義3 頻繁項(xiàng)目集(Frequent Itemset)和最大頻繁項(xiàng)目集:

對項(xiàng)目集和事務(wù)數(shù)據(jù)庫D，T中所有滿足用戶指定的最小支持度的項(xiàng)目集稱為頻繁項(xiàng)目集。在頻繁項(xiàng)目集中挑選出所有不被其他元素包含的頻繁項(xiàng)目集稱為最大頻繁項(xiàng)目集。

定義4 強(qiáng)關(guān)聯(lián)規(guī)則(Strong Association Rule)：

指D在I上滿足最小支持度和用戶指定的最小信任度的關(guān)聯(lián)規(guī)則。

關(guān)聯(lián)規(guī)則挖掘問題就是通過最小支持度和最小信任度在一個(gè)事務(wù)數(shù)據(jù)庫中尋找強(qiáng)關(guān)聯(lián)規(guī)則的過程，劃分為2個(gè)子問題：

(1) 發(fā)現(xiàn)最大頻繁項(xiàng)目集；

(2) 在最大頻繁項(xiàng)目集中生成強(qiáng)關(guān)聯(lián)規(guī)則。第一個(gè)子問題是本文的研究重點(diǎn)，即提出一種新的算法來發(fā)現(xiàn)最大頻繁項(xiàng)目集。

3 Apriori算法及缺點(diǎn)分析

1994年Agrawal等人建立用于事務(wù)數(shù)據(jù)庫挖掘的項(xiàng)目集的格空間理論［4］：頻繁項(xiàng)目集的子集是頻繁項(xiàng)目集，非頻繁項(xiàng)目集的超集是非頻繁項(xiàng)目集。Apriori算法［3］依據(jù)此理論進(jìn)行剪枝。該算法是通過項(xiàng)目集數(shù)目不斷增長來逐步發(fā)現(xiàn)頻繁項(xiàng)目集的，算法輸入數(shù)據(jù)集D和最小支持?jǐn)?shù)minsupcount(最小支持度與事務(wù)數(shù)的乘積)，輸出頻繁項(xiàng)目集L。算法首先產(chǎn)生1頻繁項(xiàng)目L1，然后是2頻繁項(xiàng)目集L2，直至不再能擴(kuò)展頻繁項(xiàng)目集的元素?cái)?shù)目而算法停止。在第k次循環(huán)中，過程先產(chǎn)生k候選項(xiàng)目集的集合Ck，然后通過掃描數(shù)據(jù)庫得到CK的支持度并測試產(chǎn)生k頻繁項(xiàng)目集Lk。算法過程［5］是：連接剪枝生成Ck掃描計(jì)數(shù)比較生成Lk。

從以上分析可以發(fā)現(xiàn)，Apriori算法使用逐層搜索的迭代方法，通過低維頻繁項(xiàng)目集產(chǎn)生高維頻繁項(xiàng)目集［4］。這樣，就致使Apriori算法存在2個(gè)致命的性能瓶頸：

(1) 多次掃描事務(wù)數(shù)據(jù)庫。每次k循環(huán)，候選集Ck中的每個(gè)元素都必須通過掃描數(shù)據(jù)庫1次來判斷其是否加入Lk。如果頻繁大項(xiàng)目集包含n項(xiàng)，則至少需要掃描事務(wù)數(shù)據(jù)庫n遍，需要很大的I/O負(fù)載。

(2) 可能產(chǎn)生龐大的候選集。由Lk-1產(chǎn)生k候選集Ck是呈指數(shù)增長的，例如104個(gè)1頻繁項(xiàng)目集有可能產(chǎn)生接近107個(gè)元素的2候選集，如此龐大的候選集對時(shí)間和存儲(chǔ)空間是一個(gè)挑戰(zhàn)。

4 改進(jìn)Apriori算法

Apriori算法使用候選集去找頻繁集，算法反復(fù)連接、剪枝，導(dǎo)致執(zhí)行效率低。因此，考慮使用其他方法來取代通過候選集去找頻繁集的過程，改變由低維頻繁項(xiàng)目集到高維頻繁項(xiàng)目集的多次連接運(yùn)算，這樣，既可以避免大量候選集的產(chǎn)生，又可以減少數(shù)據(jù)庫的掃描次數(shù)，從而提高算法效率。在介紹具體改進(jìn)措施之前，引入2條推論：

推論1 如果K頻繁項(xiàng)目集Lk中的項(xiàng)目集個(gè)數(shù)≤K時(shí)，則該集合為最大頻繁項(xiàng)目集的集合。

證明： 根據(jù)項(xiàng)目集格空間理論，假如存在K+1頻繁項(xiàng)目集Lk+1，那么對于Lk+1的K+1個(gè)K項(xiàng)目子集都是頻繁項(xiàng)目集，與題設(shè)項(xiàng)目集個(gè)數(shù)≤K矛盾，所以，如果頻繁項(xiàng)目Lk中項(xiàng)目集的個(gè)數(shù)≤K時(shí)，則無法產(chǎn)生K+1頻繁項(xiàng)目集Lk+1，因此，該推論成立。

推論2 最大頻繁項(xiàng)目集Lk的項(xiàng)目數(shù)K小于等于在所有事務(wù)中滿足支持計(jì)數(shù)的最大項(xiàng)目數(shù)k。對于事務(wù)T，若2項(xiàng)集的支持計(jì)數(shù)為sup2，3項(xiàng)集的支持計(jì)數(shù)為sup3，…，n-項(xiàng)集的支持計(jì)數(shù)為supn(n為所有事務(wù)中的最大項(xiàng)目數(shù))，其中，supk( Minsupport(2(k(n)且supk+1

證明： (反證法)假設(shè)K大于k，則存在頻繁項(xiàng)目集Lk滿足支持計(jì)數(shù)，而與滿足支持計(jì)數(shù)的項(xiàng)目數(shù)k最大矛盾，因此，最大頻繁項(xiàng)目數(shù)K不可能大于滿足支持計(jì)數(shù)的最大項(xiàng)目數(shù)k，推論得證。

一般地，只關(guān)心那些不被其他頻繁項(xiàng)目集所包含的最大項(xiàng)目集的集合，在這些頻繁項(xiàng)目集中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則。所以，問題歸結(jié)為如何高效確定最大頻繁項(xiàng)目集。改變通常的做法，應(yīng)用上述推論，先確定最大頻繁項(xiàng)目集的項(xiàng)目數(shù)K，然后找出所有頻繁項(xiàng)集Lk。算法NewApriori描述如下：

輸入：事務(wù)數(shù)據(jù)T；最小支持?jǐn)?shù)minsupcount。

輸出：最大頻繁項(xiàng)目集L。

(1) C［n］=0; //初始化數(shù)組C［n］，n為所有事務(wù)中的最大項(xiàng)目數(shù)

(2)for each ti∈Tdo begin

(3) i=|ti|;//i為每個(gè)事務(wù)所含的項(xiàng)目數(shù)

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

(5)end

(6) L1={large 1-itemsets};//所有滿足支持計(jì)數(shù)的1頻繁項(xiàng)目集

(7)for i=nto 2do begin

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

(9) k=i;

//根據(jù)推論2，k≤i，由于找最大的頻繁項(xiàng)集，因此可以假定k=i

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

(11) Lk={Ck|Ck.count(minsupcount and Ck.count(k};//根據(jù)推論1

(12)if Lk≠hthen

(13)return Lk

(14)end

(15)end

該算法的改進(jìn)主要體現(xiàn)在以下2方面：

(1) 最大頻繁集的產(chǎn)生過程改變?yōu)閺母呔S到低維的搜索過程，根據(jù)不同項(xiàng)目個(gè)數(shù)的出現(xiàn)頻率，直接從1頻繁項(xiàng)目集產(chǎn)生高維頻繁項(xiàng)目集，省去多次的連接運(yùn)算及大量候選集的產(chǎn)生，節(jié)約了運(yùn)行時(shí)間和主存空間。

(2) 減少掃描數(shù)據(jù)庫次數(shù)，該算法掃描數(shù)據(jù)庫的次數(shù)最少可以減少到3次(第1次，計(jì)算C\；第2次，得到1頻繁項(xiàng)目集；第3次，計(jì)算大于支持計(jì)數(shù)的Lk)，而Apriori算法則需要掃描k次，因此，對于維數(shù)較高(k值較大)的頻繁項(xiàng)目集的計(jì)算，效率提高更明顯。

5 實(shí)例分析

下面給出一個(gè)服裝店的20個(gè)收款機(jī)事務(wù)記錄，每一事務(wù)T代表購買的商品集合，I1-I6分別表示不同的商品，最小支持?jǐn)?shù)minsupcount=3,見表1所示。

根據(jù)NewAgriori算法

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

(2) 得到1頻繁項(xiàng)目集L1={{I2}，{I3}，{I4}，{I5}，{I6}}；

(3) 由于C［5］minsupcount，則先假定最大頻繁項(xiàng)目集的項(xiàng)目數(shù)k=4，從L1中產(chǎn)生所有4項(xiàng)目集，共5個(gè)，分別是：{I2，I3，I4，I5}，{I2，I3，I4，I6}，{I3，I4，I5，I6}，{I2，I4，I5，I6}，{I2，I3，I5，I6}，掃描數(shù)據(jù)庫計(jì)算該5個(gè)候選集的支持計(jì)數(shù)，求得滿足最小支持計(jì)數(shù)的項(xiàng)集為：{I2，I4，I5，I6}，其支持計(jì)數(shù)=4，根據(jù)推論1可知，該頻繁項(xiàng)目集即是最大頻繁項(xiàng)目集，計(jì)算結(jié)束。如果使用Apriori算法，則需要掃描4次數(shù)據(jù)庫，并且從1頻繁項(xiàng)目集到4頻繁項(xiàng)目集的連接計(jì)算共需產(chǎn)生24個(gè)候選集。而使用NewApriori算法，整個(gè)過程共掃描了3次數(shù)據(jù)庫，且只產(chǎn)生5個(gè)4項(xiàng)候選集，很明顯，無需產(chǎn)生大量的候選集同樣可以找到最大頻繁項(xiàng)目集，同時(shí)減少了掃描數(shù)據(jù)庫的次數(shù)。但從上述算法流程不難看出，如果第一次假定的k不是所要求的最大頻繁項(xiàng)目集的項(xiàng)目數(shù)時(shí)，則需要再次尋找符合要求的k值，多一次尋找，就多一次對數(shù)據(jù)庫的掃描，候選集的數(shù)量也會(huì)隨之增多。不過，數(shù)據(jù)庫的掃描次數(shù)不會(huì)超過k次，為了避免過多冗余的候選集，可以將1頻繁項(xiàng)目集按支持計(jì)數(shù)的大小順序排列，組合支持計(jì)數(shù)相對少的項(xiàng)目，及早發(fā)現(xiàn)非頻繁項(xiàng)目，以減少候選集的產(chǎn)生。因此，該算法特別適合于項(xiàng)目數(shù)比較大的最大頻繁項(xiàng)目的查找。

6 結(jié) 語

Apriori算法作為最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法被廣泛使用，由于其固有的局限性，出現(xiàn)了大量的改進(jìn)算法。本文提出的NewApriori算法也針對引起性能瓶頸的缺點(diǎn)而做出的改進(jìn)，提高了系統(tǒng)運(yùn)行效率。但不足的是，此算法只能找到項(xiàng)數(shù)最大的頻繁項(xiàng)目集，也就是說，得到的頻繁項(xiàng)目集不夠完整，因此，還需要進(jìn)一步完善。

參 考 文 獻(xiàn)

［1］Jiawei Han,Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)\.范明,孟小峰，譯.北京:機(jī)械工業(yè)出版社,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］毛國君,段立娟.數(shù)據(jù)挖掘原理與算法\.北京:清華大學(xué)出版社,2005.

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

［5］李小兵.關(guān)聯(lián)規(guī)則挖掘算法的改進(jìn)與優(yōu)化研究\.廈門大學(xué)學(xué)報(bào):自然科學(xué)版,2005(7):468471.

［6］謝宗毅.關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究與改進(jìn)\.杭州電子科技大學(xué)學(xué)報(bào),2006(6):7882.

篇5

關(guān)鍵詞：數(shù)據(jù)挖掘；頻繁項(xiàng)集；鏈表數(shù)組

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9599　（2012）　19-0000-03

1 引言

數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中，發(fā)掘出潛在有用的模式和信息的技術(shù)。當(dāng)前主要的數(shù)據(jù)挖掘方法有關(guān)聯(lián)規(guī)則、分類和聚類。其中，關(guān)聯(lián)規(guī)則致力于發(fā)現(xiàn)數(shù)據(jù)中的頻繁模式，它最早由R.Agrawal等人針對購物籃問題提出，其目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品間的聯(lián)系，以幫助商家進(jìn)行商品目錄和貨架設(shè)計(jì)，科學(xué)安排進(jìn)貨和庫存，實(shí)施交叉銷售。

最經(jīng)典的頻繁項(xiàng)集挖掘算法是Apriori算法[1]。它首次采用了基于頻繁項(xiàng)集性質(zhì)的自底向上的廣度優(yōu)先逐層搜索迭代技術(shù)，即利用已知的頻繁k-項(xiàng)集推導(dǎo)出頻繁（k+1）-項(xiàng)集。Apriori算法有三個(gè)主要步驟：（1）用頻繁（k-1）-項(xiàng)集進(jìn)行自連接來產(chǎn)生候選k-項(xiàng)集。（2）用Apriori性質(zhì)進(jìn)行對候選k-項(xiàng)集進(jìn)行剪枝操作。（3）掃描數(shù)據(jù)庫得到候選項(xiàng)集支持度。由上述分析可知，Apriori算法需要多次掃描數(shù)據(jù)庫，I/O開銷較大。另外，子集計(jì)算、共同前綴項(xiàng)集計(jì)算等也極大增加了算法的開銷。為提高Apriori算法的效率，先后出現(xiàn)了許多基于Apriori的改進(jìn)算法。文獻(xiàn)[2]提出DHP算法，它利用哈希技術(shù)壓縮候選項(xiàng)集集合Ck，同時(shí)也縮減了數(shù)據(jù)庫的大小，降低I/O開銷。此算法缺點(diǎn)在于哈希表會(huì)增加算法的內(nèi)存開銷，而且實(shí)現(xiàn)起來也較為麻煩。文獻(xiàn)[3]提出Partition算法，它采用劃分技術(shù)成功解決內(nèi)存不足的問題，具有較好的可擴(kuò)展性。然而，Partition算法可能產(chǎn)生大量虛假的候選項(xiàng)集。文獻(xiàn)[4]提出選樣技術(shù)，在給定數(shù)據(jù)的一個(gè)子集中挖掘頻繁模式。Sampling算法簡單并減少了I/O代價(jià)，但其產(chǎn)生的結(jié)果不精確，即存在所謂的數(shù)據(jù)扭曲。文獻(xiàn)[5]提出DIC算法，它放松了產(chǎn)生候選項(xiàng)集和計(jì)數(shù)的嚴(yán)格界限，采用動(dòng)態(tài)模式計(jì)數(shù)法以減少數(shù)據(jù)庫的掃描次數(shù)，具有較好效率。

盡管有如上所述的諸多改進(jìn)方法，但時(shí)間效率還不盡理想，為更進(jìn)一步提高算法性能，提出一種基于Apriori的改進(jìn)型算法FAA（Fast　Apriori　Algorithm）。FAA算法通過構(gòu)造鏈表數(shù)組來快速產(chǎn)生頻繁2-項(xiàng)集并減少數(shù)據(jù)庫的掃描次數(shù)，優(yōu)化對項(xiàng)集計(jì)數(shù)操作；改進(jìn)連接策略來簡化連接算法復(fù)雜度。

2 FAA算法思想

2.1 鏈表數(shù)組定義及生成算法。鏈表數(shù)組定義：數(shù)組為n個(gè)指針的一維數(shù)組P[n]，對應(yīng)數(shù)據(jù)庫中的頻繁項(xiàng)I1，I2，…，In，對應(yīng)數(shù)組長度n為數(shù)據(jù)庫中頻繁項(xiàng)的數(shù)量。結(jié)點(diǎn)為事務(wù)結(jié)點(diǎn)，分為事務(wù)域、計(jì)數(shù)域和指針域。事務(wù)域是以頻繁項(xiàng)為后綴的事務(wù)編碼。計(jì)數(shù)域是該事務(wù)編碼的數(shù)量，指針域是指向下一結(jié)點(diǎn)的指針。

編碼方法：設(shè)數(shù)據(jù)庫中有n個(gè)頻繁項(xiàng)I1，I2，…，In。事務(wù)t的編碼就是長度為n的0、1位串。在t中出現(xiàn)的項(xiàng)，其相應(yīng)位置用1表示，否則填0。例如，有四個(gè)頻繁項(xiàng)a，b，c，d。那么，一個(gè)包含a和c的事務(wù)就被映射為1010。