面向海量物聯(lián)網(wǎng)的數(shù)據(jù)處理技術(shù)

1、 數(shù)據(jù)庫新技術(shù)課 程 報 告題 目： 面向物聯(lián)網(wǎng)的海量數(shù)據(jù)處理研究 學(xué) 院： 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院 專 業(yè)： 計算機(jī)軟件與理論 年 級： 2012級1班 學(xué) 號： 120320042 姓 名： 賈福運(yùn) 成 績： 摘要 物聯(lián)網(wǎng)近年來受到人們的廣泛關(guān)注 伴隨各種感知技術(shù)的綜合應(yīng)用，物聯(lián)網(wǎng)所處理的數(shù)據(jù)量較之以往的任何網(wǎng)絡(luò)都巨大，呈現(xiàn)真正意義上的海量特征，如何高效 自動智能化地處理這些數(shù)據(jù)是物聯(lián)網(wǎng)亟待解決的關(guān)鍵技術(shù)之一 提出一種基于多級數(shù)據(jù)處理的嵌入式中間件系統(tǒng)的體系結(jié)構(gòu)，采用數(shù)據(jù)分級和分布式處理技術(shù)，實(shí)現(xiàn)實(shí)時信息處理的負(fù)載均衡，并提出當(dāng)今流行的多種數(shù)據(jù)降維算法,從而盡可能多地保留原始信息的基礎(chǔ)上，減

2、少信息處理的數(shù)據(jù)量，從而提高物聯(lián)網(wǎng)應(yīng)用系統(tǒng)的整體效率.關(guān)鍵詞：物聯(lián)網(wǎng)；海量數(shù)據(jù)；分級處理；降維處理1 引言物聯(lián)網(wǎng)(The Internet of Things，IoT)的概念是1999年提出的。簡單來講就是把各類物品通過射頻識別(RFID)、傳感器件與設(shè)備、全球定位系統(tǒng)等種種裝置與互聯(lián)網(wǎng)結(jié)合起來而形成一個巨大的網(wǎng)絡(luò)，實(shí)現(xiàn)智能化的識別與管理，進(jìn)而實(shí)現(xiàn)各類物品的遠(yuǎn)程感知和控制，由此生成一個更加智慧的生產(chǎn)和生活體系1根據(jù)丁明治,高需等人的分析, 物聯(lián)網(wǎng)的以下4個特點(diǎn)對數(shù)據(jù)處理技術(shù)形成了巨大的挑戰(zhàn)1：（1）首先物聯(lián)網(wǎng)數(shù)據(jù)的海量性物聯(lián)網(wǎng)系統(tǒng)通常包含著海量的傳感器結(jié)點(diǎn)。其中，大部分傳感器(如溫度傳感器、G

3、PS傳感器、壓力傳感器等)的采樣數(shù)據(jù)是數(shù)值型的，但也有許多傳感器的采樣值是多媒體數(shù)據(jù)(如交通攝像頭視頻數(shù)據(jù)、音頻傳感器采樣數(shù)據(jù)、遙感成像數(shù)據(jù)等)每一個傳感器均頻繁地產(chǎn)生新的采樣數(shù)據(jù)，系統(tǒng)不僅需要存儲這些采樣數(shù)據(jù)的最新版本，且在多數(shù)情況下，還需要存儲某個時間段(如1個月)內(nèi)所有的歷史采樣值，以滿足溯源處理和復(fù)雜數(shù)據(jù)分析的需要可以想象，上述數(shù)據(jù)是海量的，對它們的存儲、傳輸、查詢以及分析處理將是一個前所未有的挑戰(zhàn)(2)傳感器結(jié)點(diǎn)及采樣數(shù)據(jù)的異構(gòu)性在同一個物聯(lián)網(wǎng)系統(tǒng)中，可以包含形形色色的傳感器，如交通類傳感器、水文類傳感器、地質(zhì)類傳感器、氣象類傳感器、生物醫(yī)學(xué)類傳感器等，其中每一類傳感器又包括諸多具體

4、的傳感器如交通類傳感器可以細(xì)分為GPS傳感器、RFID傳感器、車牌識別傳感器、電子照相身份識別傳感器，交通流量傳感器(紅外、線圈、光學(xué)、視頻傳感器)、路況傳感器、車況傳感器等這些傳感器不僅結(jié)構(gòu)和功能不同，而且所采集的數(shù)據(jù)也是異構(gòu)的這種異構(gòu)性極大地提高了軟件開發(fā)和數(shù)據(jù)處理的難度(3)物聯(lián)網(wǎng)數(shù)據(jù)的時空相關(guān)性與普通互聯(lián)網(wǎng)結(jié)點(diǎn)不同，物聯(lián)網(wǎng)中的傳感器結(jié)點(diǎn)普遍存在著空間和時間屬性每個傳感器結(jié)點(diǎn)都有地理位置，個數(shù)據(jù)采樣值都有時間屬性，而且許多傳感器結(jié)點(diǎn)的地理位置還是隨著時間的變化而連續(xù)移動的，如智能交通系統(tǒng)中，每個車輛安裝了高精度的GPS或RFID標(biāo)簽，在交通網(wǎng)絡(luò)中動態(tài)地移動與物聯(lián)網(wǎng)數(shù)據(jù)的時空相關(guān)性相對應(yīng)，

5、物聯(lián)網(wǎng)應(yīng)用中對傳感器數(shù)據(jù)的查詢也并不僅僅局限于關(guān)鍵字查詢很多時候，我們需要基于復(fù)雜的邏輯約束條件進(jìn)行查詢，如查詢某個指定地理區(qū)域中所有地質(zhì)類傳感器在規(guī)定時間段內(nèi)所采集的數(shù)據(jù)，并對它們進(jìn)行統(tǒng)計分析由此可見，對物聯(lián)網(wǎng)數(shù)據(jù)的空間與時間屬性進(jìn)行智能化的管理與分析處理是至關(guān)重要的(4)物聯(lián)網(wǎng)數(shù)據(jù)的序列性與動態(tài)流式特性在物聯(lián)網(wǎng)系統(tǒng)中，要查詢某個監(jiān)控對象在某一時刻的物理狀態(tài)是不能簡單地通過對時間點(diǎn)的關(guān)鍵字匹配來完成的，這是因為采樣過程是間斷進(jìn)行的，查詢時間與某個采樣時間正好匹配的概率極低為了有效地進(jìn)行查詢處理，需要將同一個監(jiān)控對象的歷次采樣數(shù)據(jù)組合成一個采樣數(shù)據(jù)序列，并通過插值計算的方式得到監(jiān)控對象在指定時

6、刻的物理狀態(tài)采樣數(shù)據(jù)序列反映了監(jiān)控對象的狀態(tài)隨時問變化的完整過程，因此包含比單個采樣值豐富得多的信息此外，采樣數(shù)據(jù)序列表現(xiàn)出明顯的動態(tài)流式特性隨著新采樣值的不斷到來和過時采樣值的不斷淘汰，采樣數(shù)據(jù)序列是不斷的動態(tài)變化的針對物聯(lián)網(wǎng)海量數(shù)據(jù)管理所面臨的上述挑戰(zhàn)，目前尚沒有有效的解決方法.本文提出處理這些海量數(shù)據(jù)的兩種方法：(1)對這些數(shù)據(jù)進(jìn)行分級處理；（2）對這些數(shù)據(jù)進(jìn)行降維處理.分級處理可以有效的減輕系統(tǒng)的負(fù)荷；降維處理可以有效的壓縮數(shù)據(jù)量，并且降維處理是處理一些數(shù)據(jù)必須進(jìn)行的步驟，降維處理已經(jīng)在大規(guī)模的圖像處理算法中得到應(yīng)用.2 物聯(lián)網(wǎng)的海量數(shù)據(jù)分級處理策略2.1 海量數(shù)據(jù)分級的必要性2010

7、年JiKui Wang論證并提出了數(shù)據(jù)分級存儲的必要性4.他認(rèn)為：如左圖所示，通常40%或者更多的企業(yè)數(shù)據(jù)是非活躍的，但是這些非活躍的數(shù)據(jù)卻：（1） 消耗了昂貴的存儲空間（2） 不得不如同活躍數(shù)據(jù)一樣需要一些不必要管理，備份，復(fù)制等操作（3） 有嚴(yán)重的法律風(fēng)險（4） 不得不在DR方案中進(jìn)行一些不必要的恢復(fù)操作 由此，我們可以把2000年的292TB的總數(shù)據(jù)可以分為：（1）115TB的活躍數(shù)據(jù)（2）77TB的非活躍數(shù)據(jù)截止到2010年，JiKui Wang得出如下圖所示的活躍數(shù)據(jù)與非活躍數(shù)據(jù)之間的關(guān)系：分級與具體的環(huán)境相關(guān)，比如說，它與下面的幾個方面相關(guān)：（1） 服務(wù)屬性質(zhì)量，速率，可靠性（2）

8、 分級可以被專業(yè)化，比如合規(guī)存檔（3） 分級可以無硬盤存儲，比如用CDR,磁帶存儲等如下圖所示則很好地處理了數(shù)據(jù)分級處理問題：2.2 海量物聯(lián)網(wǎng)數(shù)據(jù)分級處理海量物聯(lián)網(wǎng)數(shù)據(jù)分級模型海量物聯(lián)網(wǎng)分級存儲系統(tǒng)是針對基于服務(wù)需求和成本構(gòu)建的層次存儲系統(tǒng)。 它由具有不同性能、可用性和單位價格等指標(biāo)的存儲級別構(gòu)成, 數(shù)據(jù)存放在不同的存儲級別中(固態(tài)磁盤、光纖盤陣、IDE盤陣、SATA盤陣和磁帶庫)。該系統(tǒng)可滿足海量數(shù)據(jù)存儲的高性能、大容量和低成本等要求。分級存儲系統(tǒng)的核心是數(shù)據(jù)遷移技術(shù)。該技術(shù)在不同存儲層次之間遷移數(shù)據(jù), 同時保證遷移過程中數(shù)據(jù)訪問的一致性。數(shù)據(jù)遷移分為離線遷移和在線遷移兩種。 離線遷移需要

9、將應(yīng)用停止服務(wù)后再進(jìn)行遷移,它避免了遷移過程中對數(shù)據(jù)一致性的維護(hù)。由于目前企業(yè)級應(yīng)用都要求7*24h在線, 離線遷移已不適合大規(guī)模存儲系統(tǒng)的需要, 因此在線遷移成為遷移技術(shù)的研究熱點(diǎn). 目前, 已有的在線數(shù)據(jù)遷移技術(shù)都存在如下缺陷:（1）遷移條件缺乏自適應(yīng)機(jī)制。一些分級存儲系統(tǒng)的遷移策略是由管理員預(yù)先制定好的。如在生命周期管理的體系結(jié)構(gòu)STEPS中,具體遷移策略由管理員手工設(shè)定,文件在創(chuàng)建時就按照一定的放置策略放入不同的存儲池中, 在文件的生命周期內(nèi),由預(yù)先設(shè)定好的遷移策略將文件在不同存儲池之間遷移。 該遷移方法簡單易操作, 但不能很好地適應(yīng)動態(tài)變化的負(fù)載。（2）遷移代價高。如基于Lustre

10、的分級存儲管，理系統(tǒng)中,文件從離線設(shè)備遷移到在線設(shè)備都是由訪問缺失觸發(fā)的, 因此造成一次訪問缺失的代價很大,且不支持文件的在線遷移。 （3）傳統(tǒng)的文件遷移方法的升級策略都是on-demand類型。如果被訪問的文件沒有在高端存儲系統(tǒng)中命中，則將其從低端存儲系統(tǒng)遷移到高端存儲系統(tǒng)中。 該方法的缺點(diǎn)是沒有考慮文件的其他信息,比如文件大小、訪問間隔等,造成升級的文件過多。具有代表性的兩種文件遷移為:(1)LRU(least-recently-used), 優(yōu)先將最近最不常使用的文件進(jìn)行替換。LRU的缺陷在于平等地對待全部文件，沒有考慮到文件的大小而文件大小決定了文件的遷移代價。（2）GreedyDua

11、lSize,基于文件的recency,size和migrationcost對文件進(jìn)行替換。該方式升級遷移的數(shù)據(jù)量大，而且文件升級前需要通過降級來替換文件，增加了文件訪問響應(yīng)時間。針對已有在線數(shù)據(jù)遷移技術(shù)存在的不足,清華大學(xué)敖莉，于得水等人提出了一種高效的數(shù)據(jù)遷移方法 CuteMig【2】,該方法采用基于升級成本和升級收益的文件分級策略, 動態(tài)地考慮了文件大小和文件訪問頻度,將升級成本與收益比值滿足條件的文件進(jìn)行遷移, 既保證了升級必要的熱點(diǎn)文件達(dá)到較高的命中率，也解決on-demand升級方式遷移數(shù)據(jù)量大的問題。同時CuteMig采用基于剩余空間的文件自適應(yīng)降級選擇策略,根據(jù)高端存儲系統(tǒng)的剩余

12、空間情況主動地選取文件來降級,保證了高端存儲系統(tǒng)中始終有剩余空間, 解決了傳統(tǒng)替換策略在升級前必須先執(zhí)行DEMOTE操作進(jìn)行替換的問題。在CuteMig遷移方法的基礎(chǔ)上,他們?yōu)橐环N物理數(shù)值模擬的海量數(shù)據(jù)存儲, 設(shè)計并實(shí)現(xiàn)了一個分級存儲系統(tǒng)TH-TS, 該系統(tǒng)基于并行文件系統(tǒng)PVFS2, 采用增量掃描的方式獲取文件訪問頻度信息,建立升級和降級隊列管理遷移任務(wù), 減少了遷移決策的開銷, 提高了系統(tǒng)的遷移效率. 評測結(jié)果表明, TH-TS可以根據(jù)文件訪問頻度在不同數(shù)據(jù)服務(wù)器之間有效地遷移數(shù)據(jù),同時CuteMig遷移方法和傳統(tǒng)遷移方法LRU和GreedyDualSize相比, 升級遷移量下降了32%和

13、59%; 降級遷移量下降了47%和66%, 且CuteMig 的平均IPO響應(yīng)時間比LRU最多可降低10%, 比GreedyDualSize最多可降低39%。THTS體系結(jié)構(gòu)的硬件結(jié)構(gòu)按功能劃分，包括客戶端，元數(shù)據(jù)服務(wù)器和數(shù)據(jù)服務(wù)器3部分，如圖1所示：在圖1中, 元數(shù)據(jù)服務(wù)器和客戶端之間的通路稱為元數(shù)據(jù)路徑,數(shù)據(jù)服務(wù)器和客戶端之間的通路稱為數(shù)據(jù)路徑.元數(shù)據(jù)服務(wù)器負(fù)責(zé)把位于不同數(shù)據(jù)服器上的數(shù)據(jù)文件組織成統(tǒng)一的文件系統(tǒng)視圖,為客戶端軟件提供元數(shù)據(jù)操作服務(wù), 同時執(zhí)行文件掃描、數(shù)據(jù)分級、遷移決策和遷移速率控制等操作,實(shí)現(xiàn)對遷移操作的單點(diǎn)管理;數(shù)據(jù)服務(wù)器保存每個文件分片后的數(shù)據(jù)文件, 為客戶端軟件提供

14、文件IPO操作,同時執(zhí)行元數(shù)據(jù)服務(wù)器發(fā)來的文件遷移指令;文件系統(tǒng)客戶端軟件實(shí)現(xiàn)虛擬文件系統(tǒng)層和MPI-IO層的各種文件操作.THTS體系結(jié)構(gòu)的軟件體系結(jié)構(gòu)包括3部分客戶端軟件,元數(shù)據(jù)服務(wù)器軟件和數(shù)據(jù)服務(wù)器軟件?？蛻舳塑浖譃閼?yīng)用層、系統(tǒng)接口層、任務(wù)管理層和網(wǎng)絡(luò)通信層。元數(shù)據(jù)服務(wù)器是整個TH-TS系統(tǒng)中負(fù)責(zé)遷移和數(shù)據(jù)管理的主控節(jié)點(diǎn),其設(shè)計主要包括: 1)獲取數(shù)據(jù)服務(wù)器的文件訪問頻度信息; 2)管理并調(diào)度遷移任務(wù);3)與數(shù)據(jù)服務(wù)器交互來控制遷移的執(zhí)行. 為了現(xiàn)以上功能, 元數(shù)據(jù)服務(wù)器軟件設(shè)計了文件遷移決策模塊,它包含了增量掃描器,文件訪問表管理器以及遷移調(diào)度控制器3個子模塊.數(shù)據(jù)服務(wù)器負(fù)責(zé)向客戶端

15、軟件提供IPO服務(wù)記錄數(shù)據(jù)文件的訪問頻度信息、執(zhí)行元數(shù)據(jù)服務(wù)器發(fā)來的遷移請求. 數(shù)據(jù)服務(wù)器軟件的設(shè)計主要包括:1) 數(shù)據(jù)分片. 為了提高IPO性能, 文件數(shù)據(jù)按照一定分片規(guī)則分布在不同數(shù)據(jù)服務(wù)器上. 數(shù)據(jù)服務(wù)器需要保證客戶端軟件和元數(shù)據(jù)服務(wù)器軟件按照分布信息可以獲取正確的數(shù)據(jù).2) 記錄數(shù)據(jù)文件的訪問頻度信息. 數(shù)據(jù)服務(wù)器軟件需定時記錄數(shù)據(jù)文件的訪問頻度信息, 并在收到元數(shù)據(jù)的掃描指令后把數(shù)據(jù)文件的訪問頻度信息返回給元數(shù)據(jù)服務(wù)器.3) 數(shù)據(jù)服務(wù)器不僅在收到元數(shù)據(jù)服務(wù)器的遷移指令后開始執(zhí)行遷移, 而且還需把要遷移的數(shù)據(jù)文件寫入目標(biāo)數(shù)據(jù)服務(wù)器的數(shù)據(jù)文件中, 以完成遷移任務(wù).為了實(shí)現(xiàn)以上3個技術(shù)點(diǎn),

16、數(shù)據(jù)服務(wù)器軟件設(shè)計了數(shù)據(jù)分片策略、IPO記錄模塊和遷移執(zhí)行模塊來完成其功能 CuteMig數(shù)據(jù)遷移分級存儲系統(tǒng)中數(shù)據(jù)遷移是核心技術(shù). 為提高分級存儲系統(tǒng)的IPO性能,達(dá)到高的IPO命中率及少的數(shù)據(jù)遷移量, 我們設(shè)計了CuteMig數(shù)據(jù)遷移方法, 主要包括以下3種關(guān)鍵技術(shù)。.1基于升級成本和升級收益的文件分級策略基于升級成本和升級收益的文件分級策略是根據(jù)文件大小和文件訪問頻度信息分別計算文件升級的成本和升級后的收益, 使用二者的比值對文件進(jìn)行分級, 并根據(jù)文件分級結(jié)果決定是否對文件升級,以提高系統(tǒng)的整體性能.1) 文件升級的成本定義為升級需要傳送的數(shù)據(jù)量:Cost = filesize (1)傳

17、送數(shù)據(jù)過程增大了高端和低端存儲系統(tǒng)的IPO負(fù)載, 也通過競爭帶寬資源增大了前端應(yīng)用的響應(yīng)時間, 文件越大遷移過程對前端應(yīng)用的影響也越大.2) 文件升級后的收益定義為文件升級后被訪問的吞吐率. 其計算過程包括如下兩個步驟:步驟1. 計算文件的平均訪問時間間隔:其中文件的當(dāng)前訪問間隔為current_interval = current _access_time- last_access_time. (3)式(2)中, 如果文件以前沒有被訪問過, 它的平均訪問時間間隔INFINITE; 如果文件是第2次被訪問, 將它的平均訪問間隔就是當(dāng)前訪問間隔,否則按遺忘因子A將當(dāng)前訪問間隔和舊的平均訪問間隔加

18、權(quán)求和, 得到新的平均訪問間隔. 該方法既考慮了文件當(dāng)前的訪問間隔,也通過遺忘因子A把文件過去的訪問間隔信息反映到平均訪問間隔中.步驟2. 計算文件的升級收益. 設(shè)access_num,access_bytes,filesize, avg_interval分別表示文件的總訪問次數(shù)、總訪問字節(jié)數(shù)、文件大小和文件的平均訪問間隔, 文件升級后經(jīng)過T時間的升級收益表示為（4）T/g_interval 表示文件在T 時間內(nèi)的預(yù)期訪問次數(shù)cess_bytes/ccess_num表示文件每次訪問的平均字節(jié)數(shù). 式(4)中升級收益是隨著時間T 不斷累積的, 因此平均收益為 由于access_num, acce

19、ss_bytes, avg_interval 都是文件的歷史訪問特征, 可近似認(rèn)為文件的訪問特征在短時間內(nèi)不會發(fā)生變化, 因此Benef it 是根據(jù)文件歷史訪問特征預(yù)測的文件近期內(nèi)的平均收益.為保證升級熱點(diǎn)文件提高訪問性能的同時, 盡量降低遷移的數(shù)據(jù)量, 我們使用遷移成本和收益的比值表示文件的遷移優(yōu)先級MigLaziness, 即該優(yōu)先級越小文件被升級的概率越大. 每當(dāng)文件被訪問, 即更新平均訪問間隔、總訪問大小、總訪問字節(jié)數(shù)等遷移相關(guān)信息, 計算升級遷移的優(yōu)先級值. 該值越小說明升級的成本越小, 而且升級后的收益越大, 如果文件的遷移優(yōu)先級小于升級閾值, 即對該文件執(zhí)行升級操作.2.2.2

20、.2基于剩余空間的文件自適應(yīng)降級選擇策基于剩余空間的文件自適應(yīng)降級選擇策略根據(jù)文件的訪問情況和高端存儲設(shè)備的剩余空間, 主動地選擇需要降級的文件, 以保證高端存儲系統(tǒng)中始終有剩余空間. 該方法解決了傳統(tǒng)替換策略在升級前必須先執(zhí)行DEMOTE操作進(jìn)行替換的問題.1) 維護(hù)一個LRU棧. 所有升級到高端存儲系統(tǒng)上的文件都放入該LRU棧中. 每當(dāng)高端存儲系統(tǒng)上的文件訪問完成后, 則將其放入LRU棧的MRU端, 同時檢查LRU棧中LRU端的文件, 根據(jù)該文件的上次訪問時間和當(dāng)前時間來計算它的未訪問時間2) 根據(jù)文件未訪問時間與降級閾值的比值進(jìn)行降級判斷. 如果它的未訪問時間大于降級閾值Demotion

21、_threshold, 那么將其放入降級候選隊列中, 由降級調(diào)度程序處理. 降級閾值在初始化時被賦值為初始值Init_demotion( 該值為可變參數(shù)) ,之后自適應(yīng)地變化: 每當(dāng)降級候選隊列中的文件被訪問, 把該文件重新放入LRU棧,同時把降級閾值設(shè)置為該文件的本次訪問和上次訪問的時間間隔, 作為對降級閾值的懲罰; 每當(dāng)降級線程從降級候選隊列中成功降級了一個文件, 把降級閾值設(shè)置為LRU棧中LRU端文件的未訪問時間,為對降級閾值的獎勵, 以使LRU棧中更多的文件進(jìn)入到降級候選隊列中來3) 降級頻率. 如圖5所示降級后候選隊列保存了LRU棧中大于降級閾值的文件. 每隔時間T, 調(diào)度程序從降級

22、候選隊列的隊首取出降級候選文件執(zhí)行降級操作. T 的計算公式如下:式(7)中K是可調(diào)參數(shù), f reeratio是高端存儲系統(tǒng)的剩余空間占其總空間的例, 取值范圍是 0, 1 ,因此T 的取值范圍是 0, Demotion_threshold . 降級的頻率根據(jù)Demotion_threshold和f reeratio 自適應(yīng)化。因此該策略是一個反饋過程, 最終降級閾值和高端存儲系統(tǒng)的剩余空間都會穩(wěn)定在一個范圍內(nèi)。.3 移調(diào)度控制為了避免遷移過程影響前端應(yīng)用, TH-TS采用了遷移調(diào)度控制, 按照遷移目標(biāo)的不同, 將遷移任務(wù)分為升級遷移和降級遷移, 并用雙候選隊列技術(shù), 使用升和降級隊列分別管

23、理調(diào)度這兩種遷移任務(wù).這種遷移任務(wù)區(qū)分的方法保證了緊迫的升級任務(wù)可以迅速執(zhí)行, 同時不緊迫的降級任務(wù)在負(fù)載較輕時才執(zhí)行。TH-TS把遷移任務(wù)分成兩類: 將數(shù)據(jù)從低端存儲系統(tǒng)遷移到高端存儲系統(tǒng)的過程稱為升級遷移;將數(shù)據(jù)從高端存儲系統(tǒng)遷移到低端存儲系統(tǒng)的過程稱為降級遷移. 這兩類遷移的目標(biāo)不同: 升級遷移是為了把熱點(diǎn)數(shù)據(jù)遷移到高端存儲系統(tǒng)中, 以提高系統(tǒng)的訪問性能; 降級遷移是為了把非熱點(diǎn)數(shù)據(jù)遷移到低端存儲系統(tǒng)中, 以使高端存儲系統(tǒng)擁有足夠的剩余空間, 來保存后續(xù)可能升級的熱點(diǎn)文件.3 海量物聯(lián)網(wǎng)的降維處理隨著物聯(lián)網(wǎng)技術(shù)的應(yīng)用，人們將會不分時間和地點(diǎn)，可以方便的獲得大量的信息，人們獲得的數(shù)據(jù)量將以

24、指數(shù)形式快速增長，這些數(shù)據(jù)具有快速更新，數(shù)據(jù)維數(shù)更高，非結(jié)構(gòu)化等特點(diǎn)。從大規(guī)模的海量數(shù)據(jù)發(fā)現(xiàn)和探索新的知識是人類獲取信息的主要目標(biāo)之一。 目前人們對這些數(shù)據(jù)的處理還沒有形成相應(yīng)的有效方法，傳統(tǒng)的數(shù)據(jù)分析方法在處理這些數(shù)據(jù)集合時，往往效果并不好，甚至在某些情況下失效，蘊(yùn)含在數(shù)據(jù)中的知識和規(guī)律我們無法得知，將會導(dǎo)致 數(shù)據(jù)災(zāi)難問題。因此人們就迫切希望去認(rèn)識和探索這些數(shù)據(jù)之間的奧秘 如何能有效的利用這些高維數(shù)據(jù)是面臨的基本問題。近年來, 數(shù)據(jù)降維在物聯(lián)網(wǎng)海量數(shù)據(jù)領(lǐng)域起著越來越重要的作用。通過數(shù)據(jù)降維可以減輕維數(shù)災(zāi)難和高維空間中其他不相關(guān)屬性,從而促進(jìn)高維數(shù)據(jù)的分類、可視化及壓縮。所謂數(shù)據(jù)降維是指通過線

25、性或非線性映射將樣本從高維空間映射到低維空間,從而獲得高維數(shù)據(jù)的一個有意義的低維表示的過程。數(shù)據(jù)降維的數(shù)學(xué)描述如下: a)X= XiNi=1是D維空間中的一個樣本集,Y= YINi=1是d(d Y, x-y=M(x), 稱y為x的低維表示。目前，在很多情況下，首先將數(shù)據(jù)的維數(shù)將到一個合理的大小，同時盡可能多的保留原始的信息，然后再將降維處理后的數(shù)據(jù)送入信息處理系統(tǒng)，這樣的做法是非常有用的 同時降維算法也是一些機(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘方法的組成部分 對數(shù)據(jù)降維處理，結(jié)合一些具體的業(yè)務(wù)需求，是一個行之有效對海量數(shù)據(jù)進(jìn)行處理的方法 降維算法主要分為線性降維算法和非線性降維算法 降維的實(shí)質(zhì)就是尋找投影變換：

26、從高維空間到低維空間變換 現(xiàn)在有一種最小量嵌入算法，在保持局部等距和角度不變的約束條件下，能很好的揭示數(shù)據(jù)內(nèi)在的流形結(jié)構(gòu).針對海量物聯(lián)網(wǎng)高維數(shù)據(jù)目前已經(jīng)提出了許多降維方法, 主要包括主成分分析( PCA)、多維尺度分析(multidimensional scaling, MDS)以及近年來提出的基于流形學(xué)習(xí)的算法, 如Isomap、局部線性嵌入( LLE)、拉普拉斯特征映射( LaplacianEigenmaps)等。對現(xiàn)有的降維方法, 可以從不同角度進(jìn)行分類。從待處理的數(shù)據(jù)的性質(zhì)角度考慮可分為線性和非線性的;從算法執(zhí)行的過程可分為基于特征值求解的方法和迭代方法;從幾何結(jié)構(gòu)的保留角度考慮可分為

27、全局方法和局部方法。本文依據(jù)降維方法間的主要區(qū)別, 將現(xiàn)有的降維方法進(jìn)行了系統(tǒng)的分類, 如圖1所示,并對幾種典型的線性和非線性降維方法進(jìn)行了詳細(xì)的闡述,最后對這些降維方法進(jìn)行了系統(tǒng)的分析比較。3.1典型的降維方法線性降維方法1) PCAPCA是通過對原始變量的相關(guān)矩陣或協(xié)方差矩陣內(nèi)部結(jié)構(gòu)的研究, 將多個變量轉(zhuǎn)換為少數(shù)幾個綜合變量即主成分,從而達(dá)到降維目的的一種線性降維方法。這些主成分能夠反映原始變量的絕大部分信息,它們通常表示為原始變量的線性組合。2)LDAFisher在1936年提出著名的Fisher準(zhǔn)則, 對于二類(分別稱為正類和負(fù)類)問題,希望投影后得到的y=wTx能夠使得J(w)最大：

28、其中: m1、m2分別是正、負(fù)樣本在投影方向上的均值; ，是正、負(fù)樣本在投影方向上方差?？蓪⑵渫茝V到多類問題, 此時希望找到的優(yōu)化方向是使得在低維空間中同類數(shù)據(jù)盡量靠近,而非同類數(shù)據(jù)盡量分離, 從而保留豐富的辨別信息, 使投影后的數(shù)據(jù)具有最大的可分性。非線性降維方法1)核主成分分析(KPCA)核方法是一系列非線性數(shù)據(jù)處理技術(shù)的總稱,它們的共同特征是這些數(shù)據(jù)處理方法均用到了核映射。近幾年,使用核函數(shù)對線性方法的重建提出一些成功方法如支持向量機(jī)回歸、核PCA、核Fisher分析等。核PCA是線性PCA的推廣, 主要思想是把輸入數(shù)據(jù)x經(jīng)由一個非線性映射A(x)映射到特征空間F,然后在特征空間F上執(zhí)行

29、線性PCA。2)MDSMDS是保留數(shù)據(jù)點(diǎn)間相似性或距離的一種非線性降維方法。MDS可分為度量性MDS和非度量性MDS。度量MDS利用數(shù)據(jù)點(diǎn)間的距離或相似性獲得數(shù)據(jù)的低維幾何表示,而非度量MDS僅利用原始數(shù)據(jù)點(diǎn)間的順序信息來獲得其低維表示。前者將距離平方陣轉(zhuǎn)換為內(nèi)積陣,通過求內(nèi)積陣的特征值和特征向量獲取低維表示;后者采用迭代方法。3) IsomapTenenbaum等人提出的Isomap算法是對經(jīng)典MDS的一種推廣。但MDS是基于歐式距離的且沒有考慮鄰近數(shù)據(jù)點(diǎn)的分布。假如高維數(shù)據(jù)點(diǎn)分布或近似分布于一個彎曲的流形上, 如Swiss-roll數(shù)據(jù)集, MDS可能將兩個數(shù)據(jù)點(diǎn)看做是近鄰點(diǎn), 然而它們沿著流形的距離要遠(yuǎn)遠(yuǎn)大于它們的輸入距離。Isomap的基本思想是首先使用最近鄰圖中的最短路徑得到近似的測地線距離(圖2),代替不能表示內(nèi)在流形結(jié)構(gòu)的Eucl-idean距離, 然后應(yīng)用MDS算法,進(jìn)而發(fā)現(xiàn)嵌入在高維空間的低維坐標(biāo)。測地線距離是兩點(diǎn)之間沿著流形的距離.4)LLE局部線性嵌入( LLE)是與Isomap相似的一種局部降維方法。但與Isomap不同的是, Isomap中建立了數(shù)據(jù)點(diǎn)的鄰接圖表示, 而LLE只試圖保留數(shù)據(jù)點(diǎn)的局部性質(zhì), 這使它對短環(huán)路問題沒有Isomap敏感。此外, 局部性質(zhì)的保留允許非凸流形的成功嵌入。其基本思想是假設(shè)每個數(shù)據(jù)點(diǎn)與它的鄰