基于云計算的物聯網數據挖掘

張海江，趙建民，朱信忠，徐慧英

0 引言

隨著物聯網的迅猛發展，芯片技術、無線網絡技術、傳感技術、全球導航系統等技術不斷完善與成熟，信息傳感、信息收集、信息感知已不再是問題。物聯網中會產生RFID數據流、地址/唯一標識、位置數據、環境數據和傳感器網絡數據等數據，如何在這海量的數據集中發現有用的信息已成為數據挖掘研究的熱點。云計算與數據挖掘技術相結合，可以增強物聯網的數據處理能力，利用云模式下數以百萬的計算機集群，提供強大的可信計算能力，彈性可擴展技術、分布式存儲機制以及分布式計算技術，快速地對海量的業務數據進行分析、處理、存儲、挖掘，在短時間內提取有價值的信息，為物聯網的商業決策服務。

物聯網數據挖掘主要以RFID 信息數據為研究對象，利用數據挖掘的技術分析發現各種物品的潛在的有價值的信息。在實際領域中，對RFID 數據的挖掘主要集中在對RFID數據流分析、基于路徑的分類和聚類分析、頻繁模式和序列模式分析以及孤立點分析等問題[1]上。其中，RFID 路徑挖掘對于企業分析貨物流通方向和流通時間，商業決策，有著非常重要的意義。RFID 采集的原始數據是一個三元組：EPC（標簽的標識碼）、Location（閱讀器讀取標簽的地點）、Time（閱讀器讀取標簽的時間），這些數據總是海量的、分布式的、時間和空間相關的。同時，這些海量的數據是異構的、動態的，節點的資源是有限的等這些特征，對數據進行精確的挖掘就十分困難。目前物聯網數據挖掘待研究的兩個問題：一是如何整合存儲這些動態異構的數據；二是如何實現高性能、可伸縮的分布式并行的數據挖掘算法，保證挖掘的精確性及效率性。

物聯網數據挖掘處理的是海量的數據，并且這些動態異構的數據都是以指數級增長的，制定物聯網數據交換的標準也頗具難度，同時數據挖掘的算法的設計也面臨著巨大的挑戰。本文采用PML[2]（實體標識語言）來來描述物聯網上采集到的RFID 異構數據信息，并且融入云計算技術，可以解決物聯網中分布的海量數據信息的數據挖掘問題，具有非常重要的意義。

1 云計算的概述

1.1 云計算的定義

云計算是將各種資源通過整合、抽象后提供給用戶的一種產業模式及技術體系的總稱，其核心就是集中計算資源、分布式存儲、分布式并行計算，處理效率得到充分發揮，用于千變萬化的應用，實現IT 架構中的資源抽象和簡化，經過資源整合而形成簡潔的資源池。

1.2 Hadoop 開源架構概述

1.2.1 Hadoop 基本結構

Hadoop 從上層架構上看是一個典型的主從式結構，它提供一個開源的框架，用于開發高度可擴展的分布式計算應用軟件。Hadoop 框架負責處理任務并行分配的細節，使得應用程序開發者可以專注于應用程序邏輯上[4]。其基本結構，如圖1所示：

圖1 Hadoop 基本結構

Hadoop 真正的創新在于不相信節點服務器，將服務器作為一種不穩定的系統來對待，利用低檔的服務器集群來存儲與計算，大大降低服務器成本，同時采用副本策略的計算存儲遷移，解決了節點失效問題。

1.2.2 Map/Reduce 編程模型

Map/Reduce 編程可以屏蔽底層的實現機制，向上層提供大量的接口，使開發者方便的開發分布式計算程序。Map/Reduce 兩項重要的核心操作：Map 和 Reduce，即映射和規約。一個Map 函數就是對存儲在HDFS 各個節點上的原始數據進行指定的操作，每個Map 之間是并行的，且相互獨立的。一個Reduce 函數就是對每一個Map所產生的中間結果進行歸約合并操作，每個Reduce 處理所得的中間結果是不相交的。這整個計算過程中，Map/Reduce 模型都是使用（key，value）的鍵值對作為輸入和輸出的，最后由Reduce 輸出結果。

Map/Reduce 操作過程[5]：

（1）Map/Reduce 先把輸入的文件分成M 塊，通過參數決定每塊的大小（大概16M-64M）；

（2）執行程序，分為主控程序Master 和分工作機Worker。總共有M 個Map 操作和R 個Reduce 操作，由Master把這些Map 或Reduce 處理任務分配給處于空閑列表中的Worker；

（3）一個被分配Map 任務的Worker 讀取處理數據后將對傳給Map 函數，由此產生的中間結果暫時緩沖到內存；

（4）這些緩存中的中間結果被定時寫到本地硬盤，通過分區函數分成R 個塊區，然后Master 把這些數據在本地硬盤上的位置信息傳送給Reduce 函數；

（5）Reduce Worker 根據Master 傳遞的文件信息以遠程讀取的方式找到對應的本地文件，對文件中的中間Key進行有序排列后再遠程發送到具體執行的Reduce 上；

（6）Reduce Worker 根據key 遍歷排序后的中間數據，并把key 和相關的中間結果集傳給Reduce 函數來把結果寫到一個最終的輸出文件；

（7）當所有的Map 和Reduce 任務都完成時，Master激活用戶程序。此時，MapReduce 返回用戶程序的調用點。

2 基于云計算的物聯網數據挖掘系統的設計與實現

2.1 系統概述

基于云計算的物聯網數據挖掘系統處理海量的動態異構數據，其流程與一般的數據挖掘基本一致，但是其處理數據的方式卻是不同的，借助了Hadoop 中的Map/Reduce模式來處理：一、首先把物聯網中的RFID 異構數據進行過濾、轉換、合并轉為一種PML 文件后，保存到分布式系統HDFS 中，同時采用副本策略，一個文件都會產生2-3 個副本并將其保存在同一機構的不同節點上或者不同機構的某個節點上，這樣子可以解決高效率存儲與處理問題，同時解決了節點失效問題。二、執行任務時，由主控程序Master負責任務的創建、管理控制，同時分配任務給空閑狀態下的Worker 去處理，經過Map/Reduce 操作后由Master 負責將最終結果歸并，返回給客戶。

2.2 計算和存儲的整合及遷移

數據存儲的分布式方式可以實現計算向存儲的遷移，因此云計算的一個重要特征就是計算和存儲的整合。Map/Reduce 處理過程中，Map 在每一個節點上的操作都是相互獨立的，沒有數據的傳輸，只有在Reduce 過程中會向Master 傳送計算結果，對于物聯網中的挖掘是計算和數據同時密集的任務，實現計算向存儲的遷移，可以大大節省數據的傳輸時間。其實現策略為：采用Map/Reduce思想分割PML文件（大小為16M-64M），先暫存到緩存中，然后定時發送至本地硬盤中，由Master 保存這些信息的位置信息，并在保存這些數據塊的Worker 上執行Map 任務，這種策略是在本地計算機上操作的，大大節省了數據的傳輸時間。此外，還采用了PML 文件副本策略。在當前節點失效的情況下，Master 節點會根據DataNode 節點上副本數據的存儲情況找到一個存有副本的DataNode 節點，并把計算遷移到該節點重新對該數據進行處理工作，這樣不會重啟整個工作，同時在計算遷移的過程中數據不會在DataNode 節點間相互傳遞，因此節省了數據傳輸時間，效率非常高。

2.3 系統架構的設計與實現

圖2 基于云計算的物聯網數據挖掘系統基本架構圖

本文設計的基于云計算的物聯網數據挖掘系統的基本結構，如圖2所示：由數據存儲層、數據挖掘算法層、挖掘任務處理層這三層組成。整個系統由Master 作為主控節點，負責與用戶進行交互，并且負責調度與管理整個系統中節點之間的工作；系統中有一部分節點用于存儲Map/Reduce 化的數據挖掘算法，用于進行高效地挖掘；此外，HDFS 分布式存儲系統中，有一個NameNode 主節點和若干DataNode 子節點。用戶的請求由 NameNode 進行接收并將存儲數據的DataNode的 IP 返回給用戶，并通知其他接收副本的DataNode。

2.3.1 數據存儲層數據存儲層采用主從式分布式系統存儲HDFS，系統由一個NameNode 主節點和多個DataNode 子節點組成，其基本結構，如圖3所示：

圖3 HDHS 基本結構

數據存儲層負責存儲和讀取由物聯網上采集并轉化的PML 文件。該層集成了過濾轉化中間件，可自動把物聯網上的海量數據解析為結構化的PML 文件，并且由NameNode分割成大小為16M-64M的文件存入HDFS 中，同時提供了大量的分布式數據訪問接口。NameNode 存儲著PML 文件的元數據，元數據中包含了文件系統的名字空間等，向用戶映射文件系統，并且負責管理PML 文件的存儲和處理，但是實際的數據并不存放在NameNode 下，NameNode的作用就像文件系統的總指揮，而實際數據存放在DataNode 下，因此，用戶直接與DataNode 建立通信，進行訪問。另外，本系統還采用數據塊副本策略來解決節點失效問題，使計算向存儲遷移，同時節省了數據傳輸的時間，大大提高了處理效率。每個PML 文件都有2 個副本，一個存放在同一機構下的不同節點，另一個存放在不同機構下的某個節點上，當當前節點失效的情況下，由NameNode 找到存有當前處理PML 數據塊副本的節點，然后將計算遷移過去來完成數據的處理。

2.3.2 數據挖掘算法層

算法節點中集成了數據挖掘的常用算法，這些算法都是進行Map/Reduce 化的，可以運用于云計算平臺的。在實際的使用過程中是由Master 主控節點來控制管理的，按照客戶請求將算法傳輸到相應的節點進行計算。本文的分布式并行的關聯規則算法是將Apriori 算法Map/Reduce 化而得到的。

2.3.3 挖掘任務處理層

任務調度是基于云計算的分布式數據挖掘系統設計的核心所在,系統中所有的挖掘器都由 Master 負責調度,執行流程如下:由Mater 查找空閑的DataNode 節點，找到后將該DataNode 放入空閑節點列表。Master 接收用戶的請求,獲得各DataNode 中數據塊的存儲信息以及挖掘時所需調用的算法,然后向算法存儲節點申請所需的挖掘算法,挖掘算法存儲節點直接將所需的算法發送到原始數據所在的DataNode 節點上,計算任務立即在HDFS 服務器啟動計算工作,完成后只向Master 傳送相關結果,期間并不向Master傳送文件數據塊,Master 匯總后生成最終的結果返回給用戶。這一處理過程中沒有了數據重組和傳送的過程,計算和存儲在一個節點上,節省了文件傳輸時間。

2.4 基于云計算的數據挖掘算法

數據挖掘算法種類繁多，有序列模式、分類聚類、關聯規則等，其中關聯規則在物聯網數據挖掘中發揮著重要作用。Apriori 算法使用逐層搜索迭代的方式利用K 項集來探索（K+1）項集。第一步先掃描一次數據集，產生頻繁1-項集L1，然后利用L1來探索頻繁項集L2，不斷迭代，直到頻繁項集為空為止。同時，運用頻繁項集的任意子集都是頻繁項集這一性質來進行對搜索空間的壓縮處理，提高生成頻繁項集的效率。其具體過程如下：在第K 次循環搜索中，首先進行連接（JOIN）操作，由LK-1產生候選集候選集CK，然后進行連接操作，再根據Apriori的一些性質進行統計支持度操作以及剪枝操作，接著由CK產生頻繁項集LK。此算法的缺點就是需要對數據庫進行多次掃描才能夠發現所有的頻繁項集，在物聯網如此海量的數據面前，多次掃描的話會耗費大量的時間和內存，本文利用云計算平臺的分布式并行計算的性質把Apriori 算法移植上去，把掃描數據庫查找頻繁項集得到并聯規則的工作放進Hadoop 架構中，在各個DataNode 節點并行掃描處理，得到各自計算節點上的局部頻繁項集，然后再由Master 統計出實際的全局支持度，并且最終確定全局的頻繁項集，將Apriori 算法移植進云平臺可以大大提高其挖掘的效率，同時節省了時間和內存耗費。

將Apriori 算法Map/Reduce 化及其處理流程如下：首先由用戶提出挖掘服務的請求，并且設置給出所需關聯規則的最小支持度和最小置信度。接著當Master 接到請求后，向NameNode 申請所需的PML 數據文件，同時訪問空閑節點列表，對空閑的DataNode 分配任務，把存儲算法節點的算法調度到各個DataNode 進行并行處理。每個DataNode都可以通過Map 函數把對映射成新的鍵值對，形成一個局部候選頻繁K 項集記為，并且把每一個的支持度記為1；然后調用通過Reduce 函數進行計算，把每個DataNode 節點上相同的候選項集的支持度累加起來，由此產生一個實際支持度，并與用戶提交申請時所制定的最小支持度對比，從而形成局部頻繁K 項集的集合記為；最后把所有的處理結果合并起來，產生全局頻繁K 項集Lk。Apriori 算法的Map/Reduce 化的實現流程如，圖4所示：

圖4 M ap/ Reduce 化的的Apriori 挖掘算法實現流程

3 結論

隨著物聯網的不斷發展，物聯網上海量的動態異構的數據在不斷增長，對這些數據的挖掘越來越困難，與傳統的物聯網數據挖掘相比，基于云計算的物聯網數據挖掘系統，其分布式存儲機制、分布式并行計算、計算存儲遷移等功能解決了數據存儲以及節點失效的問題，降低了數據傳輸的時間，同時大大提高了挖掘的效率。系統能夠面向商業運用，為商業決策服務。

[1]頓海強，趙文，鄧鵬鵬，等.一種基于RFlD 數據集的物品工作流挖掘方法[J].電子學報，200802A).

[2]David L.Brock The Physical Markup Language,Feb,2001.

[3]Hsu I-Ching，Chi Li-Pin，Bor Sheau-Shong.A platform for transcoding heterogeneous markup documents usingontology-based metadata［J］.Journal of Network and Computer Applications，2009，32(3):616-629.

[4]王鵬.云計算的關鍵技術與應用實例.[M]人民郵電出版社，2010.1

[5]劉鵬.云計算.[M]電子工業出版社。2010

[6]萬至臻.基于MapReduce 模型的并行計算平臺的設計與實現[ D].杭州:浙江大學,2008

[7]王鄂,李銘.云計算下的海量數據挖掘研究[ J].現代計算機,2009,319(1):22 -25.