基于物聯網海量信息處理的Binary AprioriAll序列挖掘算法的研究

摘 要：本文介紹了物聯網的概念、技術構架體系分析了物聯網的發展現狀，剖析了影響當前物聯網發展的依托性技術的相對不足。研究了數據挖掘技術在物聯網海量信息處理方面的應用，改進了原有的AprioriAll序列挖掘算法，創造了新的Binary AprioriAll序列挖掘算法，該改進算法通過減少數據庫中序列集的數量來提高算法的效率。

關鍵詞：物聯網；海量信息處理；數據挖掘；序列挖掘

中圖分類號：TP311.52 文獻標識碼：A 文章編號：1674-7712 （2014） 16-0000-02

一、物聯網及其體系結構

（一）物聯網的概念。物聯網是通信網和互聯網的拓展應用和網絡延伸，它利用感知技術與智能裝置對物理世界進行感知識別，通過網絡傳輸互聯，進行計算、處理和知識挖掘，實現人與物、物與物信息交互和無縫鏈接，達到對物理世界實時控制、精確管理和科學決策目的。物聯網發展的關鍵要素包括傳感和識別技術、

1.傳感和識別技術是物聯網感知物理世界獲取信息和實現物體控制的首要環節。傳感器將物理世界中的物理量、化學量、生物量轉化成可供處理的數字信號。識別技術實現對物聯網中物體標識和位置信息的獲取。

2.網絡通信技術主要實現物聯網數據信息和控制信息的雙向傳遞、路由和控制，重點包括低速近距離無線通信技術、低功耗路由、自組織通信、無線接入M2M通信增強、IP承載技術、網絡傳送技術、異構網絡融合接入技術以及認知無線電技術。

3.海量信息智能處理技術是綜合運用高性能計算、通過人工智能、數據庫和模糊計算等技術等，對收集的感知數據進行通用處理，重點涉及數據存儲、并行計算、數據挖掘、平臺服務、信息呈現等。

一般來講，物聯網的開展步驟主要如下：第一，對物體屬性進行標識，屬性包括靜態和動態的屬性，靜態屬性可以直接存儲在標簽中，動態屬性需要先由傳感器實時探測；第二，需要識別設備完成對物體屬性的讀取，并將信息轉換為適合網絡傳輸的數據格式，進行海量信息處理。第三，將物體的信息通過網絡傳輸到信息處理中心，由處理中心完成物體通信的相關計算。

圖1 物聯網工作步驟

（二）物聯網的技術構架體系。物聯網架構可分為三層：感知層、網絡層和應用層。（1）其中物聯網感知層是由各種傳感器構成，包括溫濕度傳感器、二維碼標簽、RFID標簽和讀寫器、攝像頭、紅外線、GPS等感知終端。感知層是物聯網識別物體、采集信息的來源；（2）網絡層由各種網絡，包括互聯網、廣電網、網絡管理系統和云計算平臺等組成，是整個物聯網的中樞，負責傳遞和處理感知層獲取的信息；（3）應用層是物聯網和用戶的接口，它與行業需求結合，實現物聯網的智能應用。

圖2 物聯網技術層次

二、物聯網的現狀

物聯網應用還處于起步階段，目前全球物聯網應用主要以RFID、傳感器、M2M等應用項目體現，大部分是試驗性或小規模部署的，處于探索和嘗試階段，覆蓋國家或區域性大規模應用較少。目前全球的物聯網應用大多是在特定行業或企業的閉環應用，信息的管理和互聯局限在較為有限的行業或企業內，不同地域間的互通也存在問題，沒有形成真正的物物互聯。自動化、智能化、協同化程度仍然較低。感知技術，網絡通信相關技術，及標準化協議的相關體系結構，都還不夠成熟。在智能處理方面的相關數據挖掘，模糊計算等依托技術還不夠完善。因此制約了物聯網技術的快速發展。在數據挖掘方面的相關算法也有待于進一步深化研究與應用。

三、數據挖掘技術

數據挖掘（Data Mining），就是從大量數據中獲取有效的、新穎的、潛在有用的、最終可理解的模式的過程，簡單的說，數據挖掘就是從大量數據中提取或“挖掘”有用數據。

數據挖掘把人們對數據的應用從低層次的簡單查詢，提升到從數據中挖掘知識，提供決策支持。隨著研究逐步走向深入，數據挖掘和知識發現的研究己經形成了三根強大的技術支柱：數據庫、人工智能和數理統計。數據挖掘是一門交叉學科，它把人們對數據的應用從低層次的簡單查詢，提升到從數據中挖掘知識，提供決策支持。

圖3 數據挖掘交叉技術

（一）AprioriAll序列挖掘模式理論。序列模式挖掘最早是由Agrawal等提出的，最初的動機是想通過在帶有交易時間屬性的交易數據庫中發現頻繁項目序列來發現某一時間段內顧客的購買活動規律。Agrawal與R.Srikant在1995年發表了關于序列模式發現研究的奠基性論文《Mining Sequential Patterns》。論文給出了序列模式挖掘算法的形式化定義，提出了序列模式挖掘的經典算法AprioriAll。

序列模式挖掘的一般步驟：序列模式挖掘過程一般分五個具體階段：分別是排序階段、大項目集階段、轉換階段、序列階段以及選最大階段。

1.排序階段。對數據庫進行排序（Sort），排序的結果將原始的數據庫轉換成序列數據庫。

2.大項目集階段。這個階段要找出所有頻繁的項集（大項集）組成的集合L。實際上，也同步得到所有大1-序列組的集合，即{|l∈L}。

3.轉換階段。在尋找序列模式的過程中，要不斷地檢測一個給定的大序列集合是否包含于一個客戶序列中。

4.序列階段。利用轉換后的數據庫尋找頻繁的序列，即高序列（Large Sequence）

5.選最大階段。在大序列集中找出極大序列（MaximalSequence）。

AprioriAll算法源于頻繁集算法Apriori，它把Apriori算法的基本思想運用到序列模式挖掘算法中，是一個多遍掃描數據庫的算法。在每一遍掃描中都利用遷移變得掃描產生的大序列集來產生候選序列，然后在完成對整個數據庫的遍歷后測試它們的支持度。在第一遍掃描中，利用大項目集階段輸出來初始化1-序列集。在每次遍歷中，從一個由大序列組成的種子集開始，利用這個種子集，來產生新的潛在的大序列。

（二）Binary AprioriAll改進序列挖掘模式。由AprioriAll算法可知任何頻繁序列的子序列一定也是頻繁序列；任何含有非頻繁子序列的序列一定也是非頻繁序列。那么，如果已知頻繁序列集合Lk，求Lk+1，并不需要對所有Ckm個候選序列子序列進行支持度的計算，只需要對所有k候選序列子集進行支持度的計算，因為只有這些子序列的支持度才有可能大于最小支持度。由此，我們便可以對原始的AprioriAll算法進行進一步改進，以便于提高對海量數據的數據挖掘效率。

改進算法Binary AprioriAl利用序列數據庫D產生1-候選序列C1，然后掃描序列數據庫D，計算C1在序列數據庫D中出現的頻數，當頻數不低于用戶給定的支持度時，確定為1-頻繁序列L1，刪除數據庫D中所有序列集不包含L1的子序列。計算序列數據庫D中所有序列集的長度，刪除所有長度低于2的序列集，產生新的序列數據庫D1。根據AprioriAll-generate算法由L1生成C2，掃描序列數據庫D1，計算C2在序列數據庫中出現的頻數，當頻數不低于用戶給定支持度是，確定為2-頻繁序列L2。找出C2在L2中沒有出現的序列S2，刪除序列數據庫中所有子序列S2，并且刪除長度小于3的序列集，得到新的序列數據庫D2，依次類推，這樣就使減小序列數據庫，減少了對序列數據庫掃描的記錄數，提高了算法的效率。

（三）Binary AprioriAl算法描述。首先輸入：大項集階段轉換后的序列數據庫D，然后輸出：頻數不低于2的模式L1={large 1-sequences}；//大項目集階段的結果；

S1=C1-L1 // S1為C1中所有非1-頻繁序列集；

FOR each id-sequence c in D DO

Begin

Del S1 in c //刪除序列數據庫D中所有序列集的子序列S1

If（|c|<2） //如果序列集的長度小于2，則將其從數據庫中刪除

Del c in D

End

FOR（k=2；Lk-1≠ ；k++） DO

BEGIN

Ck=AprioriAll-generate（Lk-1）；//Ck是從Lk-1中產生的新的候選者

FOR each id-sequence c in D DO//對于序列數據庫D中每個序列集c

Sum the count of all candidates in Ck that are contained in c；

//對包含c中的Ck內的所有候選者計數

Lk=Candidates in Ck with minium support；//Lk=Ck中滿足最小支持度的候選者

Sk=Ck-Lk //C1中所有非1-頻繁序列集；

FOR each id-sequence c in D DO

Begin

Del Sk in c

If（|c|

Del c in D

End

END

Answer=Maxinmal Sequence in ∪kLk

四、Binary AprioriAl算法在物聯網海量數據挖掘中的應用

掃描數據庫，搜索所有的序列集記錄，并統計每個序列集的支持度，產生候選序列集C1，C1中滿足最小支持度要求的序列為1-序列集L1。因為數據庫D中的ID6中的子序列{6}不包括在L1中的序列，所以刪除ID6中的子序列{6}。又因為ID6的長度小于2，所以把序列集ID6從數據庫中刪除。從而產生新的數據庫D1。下次查找，以D1為新的數據源序列集。

圖4

將Binary AprioriAll算法與AprioriAll相比較，可以發現Binary AprioriAll算法在每一次掃描數據庫的計算量都要比AprioriAll小，這是因為改進算法在每一次掃描數據庫的時候，已經過濾了那些候選序列的子序列，并且還過濾了那些長度小于K的序列集。所以Binary AprioriAll算法在計算候選序列的支持度所涉及的記錄數目小于原算法在數據庫中計算的記錄數，提高了算法效率。

五、結束語

本文介紹了物聯網的概念、技術構架體系分析了物聯網的發展現狀，剖析了影響當前物聯網發展的依托性技術的相對不足。研究了數據挖掘技術在物聯網海量信息處理方面的應用，改進了原有的AprioriAll序列挖掘算法，創造了新的Binary AprioriAll序列挖掘算法，該改進算法通過減少數據庫中序列集的數量來提高算法的效率。這樣在掃描候選序列集的支持度的時候，可以減少在數據庫中掃描的記錄數，減輕了系統負擔，提高了算法效率。從而提高了物聯網對海量數據處理的效率。

[作者簡介]王妍（1978.06-），吉林長春人，講師，碩士，研究方向：計算機教育。