序言：作為思想的載體和知識的探索者，寫作是一種獨特的藝術，我們為您準備了不同風格的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。