熊聰聰，龐朝輝，王蘭婷，耿世潔

(天津科技大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，天津 300457)

云計(jì)算是一種基于互聯(lián)網(wǎng)的計(jì)算方式.通過(guò)這種方式，共享的軟硬件資源和信息可以按需求提供給計(jì)算機(jī)和其他設(shè)備[1].云計(jì)算是以并行計(jì)算為核心技術(shù)，同時(shí)使用多種計(jì)算資源解決計(jì)算問(wèn)題的過(guò)程.通過(guò)并行計(jì)算集群完成數(shù)據(jù)的處理，再將處理的結(jié)果返回給用戶(hù)，可以減少計(jì)算時(shí)間，提高系統(tǒng)的使用效率.云計(jì)算實(shí)現(xiàn)了高效的并行計(jì)算與海量數(shù)據(jù)的管理，無(wú)疑是現(xiàn)今大數(shù)據(jù)時(shí)代的熱門(mén)產(chǎn)業(yè).

目前，無(wú)論是政府部門(mén)還是企業(yè)都將視角轉(zhuǎn)向了云計(jì)算領(lǐng)域.美國(guó)政府利用云計(jì)算技術(shù)建立了聯(lián)邦政府網(wǎng)站，英國(guó)政府建立了國(guó)家級(jí)云計(jì)算平臺(tái)(GCloud).在我國(guó)，北京、上海、深圳、杭州、無(wú)錫等城市開(kāi)展了云計(jì)算服務(wù)創(chuàng)新發(fā)展試點(diǎn)示范工作，以促進(jìn)產(chǎn)業(yè)信息化[2].對(duì)政府用戶(hù)而言，云計(jì)算能夠提高辦公效率、節(jié)約信息化成本，政府的推動(dòng)同時(shí)也可以促進(jìn)云計(jì)算產(chǎn)業(yè)的跨越式發(fā)展；對(duì)企業(yè)用戶(hù)而言，企業(yè)可以利用云計(jì)算整合其現(xiàn)有的數(shù)據(jù)中心，實(shí)現(xiàn)對(duì)已有IT 資源的充分利用，提高信息系統(tǒng)的效率和性能，加強(qiáng)經(jīng)營(yíng)決策的實(shí)時(shí)性.

CBR(case-based reasoning)技術(shù)[3]是通過(guò)重用或修改以前解決相似問(wèn)題的方案來(lái)實(shí)現(xiàn)的.隨著互聯(lián)網(wǎng)的飛速發(fā)展，數(shù)據(jù)量日益劇增，對(duì)于CBR 的研究也要適應(yīng)這一趨勢(shì).CBR 技術(shù)的一個(gè)典型的求解過(guò)程的基本步驟可以歸納為：案例檢索(retrieve)、案例重用(reuse)、案例修正(revise)和案例保存(retain).CBR 解決問(wèn)題的基本流程是利用目標(biāo)案例的描述信息對(duì)案例庫(kù)進(jìn)行檢索，得到與目標(biāo)案例相類(lèi)似的源案例，如果這個(gè)解答方案失敗將對(duì)其進(jìn)行調(diào)整，以獲得一個(gè)能保存的成功案例，通過(guò)案例修正并保存可以獲得一個(gè)新的源案例.在案例推理過(guò)程中，案例表示、案例檢索和案例調(diào)整是案例推理研究的核心問(wèn)題.由于CBR 技術(shù)對(duì)問(wèn)題的解決是以經(jīng)驗(yàn)知識(shí)為基礎(chǔ)的，所以在應(yīng)急事件處理、事件評(píng)估、醫(yī)療、企業(yè)管理等領(lǐng)域得到了廣泛的應(yīng)用.

常用的案例檢索算法有知識(shí)引導(dǎo)法、神經(jīng)網(wǎng)絡(luò)法、歸納索引法和最近鄰法.其中，最近鄰法是比較常見(jiàn)的一種檢索算法[4].但是，目前對(duì)于案例檢索算法的研究還停留在單節(jié)點(diǎn)檢索，隨著案例庫(kù)中案例的增多，不管采用哪種算法都不能高效地對(duì)案例進(jìn)行檢索.

本文將案例檢索中的最近鄰算法與云計(jì)算平臺(tái)進(jìn)行結(jié)合，使得在海量數(shù)據(jù)的案例庫(kù)中，可并行地對(duì)案例庫(kù)進(jìn)行檢索，從而提高檢索速度.

1 案例檢索算法的實(shí)現(xiàn)

1.1 案例的存儲(chǔ)

1.1.1 案例的表示

CBR 技術(shù)中知識(shí)的表示偏于半結(jié)構(gòu)化或者非結(jié)構(gòu)化，其知識(shí)的表示是一個(gè)重要的問(wèn)題.本文采用本體的知識(shí)表示方式，利用構(gòu)建工具protege 進(jìn)行本體的構(gòu)建.采用本體對(duì)案例庫(kù)進(jìn)行建模，能夠?yàn)椴煌I(lǐng)域知識(shí)及規(guī)則提供描述框架及規(guī)范，構(gòu)建易于擴(kuò)展的術(shù)語(yǔ)詞典，實(shí)現(xiàn)知識(shí)的統(tǒng)一描述和組織.

1.1.2 HDFS 存儲(chǔ)

HDFS(Hadoop distributed file system)[5]以容錯(cuò)性好、可伸縮性強(qiáng)、代碼開(kāi)源等優(yōu)勢(shì)倍受關(guān)注，成為當(dāng)前主流分布式文件系統(tǒng)之一.HDFS 是被設(shè)計(jì)成可以在大規(guī)模廉價(jià)機(jī)器上運(yùn)行的分布式文件系統(tǒng)，其設(shè)計(jì)思想源自GFS(Google file system).由于Hadoop 平臺(tái)上從節(jié)點(diǎn)可以隨時(shí)擴(kuò)充，且案例存儲(chǔ)在云平臺(tái)上，即HDFS 文件系統(tǒng)上，使得案例庫(kù)具有較好的橫向擴(kuò)展性，便于案例庫(kù)的擴(kuò)張與案例的存儲(chǔ).

1.2 案例的檢索

1.2.1 案例檢索算法

對(duì)于基于本體的表示方式，案例庫(kù)中的案例包括案例的標(biāo)識(shí)及各種屬性.本文提出的案例檢索算法是根據(jù)最近鄰的思想計(jì)算案例間的屬性值的相似度，進(jìn)行相似匹配[6].

以案例X 和案例Y 為例，它們的屬性分別為x1，x2，…，xm和y1，y2，…，ym.根據(jù)各屬性權(quán)值采用式(1)計(jì)算X 與Y 的相似度.

式中：ωi為相應(yīng)屬性的權(quán)值，根據(jù)屬性對(duì)案例的影響大小確定；sim(xi，yi)是案例X 的第i 個(gè)屬性與相應(yīng)Y的第i 個(gè)屬性的相似度.

根據(jù)案例的屬性類(lèi)型不同，相應(yīng)的相似度計(jì)算方法有一定的區(qū)別：

對(duì)于確定的屬性值(例如在農(nóng)業(yè)生產(chǎn)中的溫度，不同的溫度對(duì)農(nóng)作物產(chǎn)生不同的影響)，不同屬性間的相似度可由式(2)計(jì)算.

式中：d(xi，yi)是屬性值間的相對(duì)距離；maxi、mini是屬性i 的最大值和最小值.

對(duì)于不確定屬性，即類(lèi)型為布爾型的屬性(例如天氣是否下雨等)，可由式(3)計(jì)算不同屬性間的相似度.

上述是一種基于最近鄰算法的案例匹配算法，當(dāng)案例庫(kù)不大時(shí)可以及時(shí)地檢索出與所給問(wèn)題相似的案例的解決辦法.但是，當(dāng)案例不斷擴(kuò)充，案例庫(kù)增加至幾百GB 甚至TB 以上時(shí)，這種做法就顯得力所不及了.因此，考慮在云平臺(tái)上對(duì)算法進(jìn)行改進(jìn)，使得對(duì)海量數(shù)據(jù)的案例庫(kù)檢索仍然可以快速地返回結(jié)果.

1.2.2 算法改進(jìn)

開(kāi)源云計(jì)算平臺(tái)Hadoop 中的MapReduce 是一個(gè)軟件框架，基于它寫(xiě)出來(lái)的應(yīng)用程序能夠運(yùn)行在由上千臺(tái)商用服務(wù)器組成的大型集群上，并以一種可靠容錯(cuò)的方式并行處理TB 級(jí)別的數(shù)據(jù)集.MapReduce技術(shù)[7]最早由Google 公司提出，是一種通過(guò)在大規(guī)模的廉價(jià)服務(wù)器集群上進(jìn)行大數(shù)據(jù)處理的技術(shù).MapReduce 是一種并行編程模型，運(yùn)行在分布式文件系統(tǒng)之上，通過(guò)map 和reduce 操作分別進(jìn)行數(shù)據(jù)的處理.MapReduce 模型簡(jiǎn)單，支持系統(tǒng)的擴(kuò)展和高并發(fā)，是現(xiàn)階段應(yīng)用最多的大數(shù)據(jù)處理技術(shù).

MapReduce 在工作時(shí)由1 個(gè)主節(jié)點(diǎn)對(duì)集群進(jìn)行控制，同時(shí)由n 個(gè)從節(jié)點(diǎn)進(jìn)行實(shí)際任務(wù)的處理.在案例檢索時(shí)，先將同一地理位置上的數(shù)據(jù)進(jìn)行map 操作，并對(duì)中間結(jié)果進(jìn)行combine 操作，將中間結(jié)果存儲(chǔ)在本地的服務(wù)器上，這樣就節(jié)省了數(shù)據(jù)傳輸?shù)暮臅r(shí).然后，Reduce 節(jié)點(diǎn)根據(jù)Master 節(jié)點(diǎn)提供的地理信息提取中間結(jié)果，再對(duì)這些中間結(jié)果提取進(jìn)行reduce 操作，完成數(shù)據(jù)的分析工作，獲取數(shù)據(jù)中的知識(shí)，幫助完成決策的生成.MapReduce 的工作流程[8]見(jiàn)圖1.

圖1 MapReduce的工作流程Fig.1 Process of MapReduce

利用MapReduce 技術(shù)改進(jìn)的案例檢索算法，其工作流程如下：

(1)對(duì)案例庫(kù)中的案例進(jìn)行分片；

(2)Map 過(guò)程.每個(gè)從節(jié)點(diǎn)對(duì)本地案例庫(kù)中的案例進(jìn)行分片處理.輸入的鍵值對(duì)為(Case_ID，Case_Attri)，輸出的鍵值對(duì)為(Case_ID，Case_Attri)；

(3)Combine 過(guò)程，即案例間相似度的計(jì)算過(guò)程.輸入的鍵值對(duì)就是map 過(guò)程的輸出，輸出的鍵值對(duì)是(Case_ID，Case_Sim)；

(4)Reduce 過(guò)程.根據(jù)案例的相似度從高到低對(duì)案例庫(kù)中的案例進(jìn)行排序.輸入的鍵值對(duì)為Combine過(guò)程的輸出，輸出的鍵值對(duì)是(Case_Sim，Case_ID)；

(5)最后提取出相似性最高的案例，為后續(xù)的案例的生成提供方案.

2 實(shí) 驗(yàn)

為驗(yàn)證在云平臺(tái)上進(jìn)行案例檢索的可行性，分別在不同節(jié)點(diǎn)數(shù)的集群上進(jìn)行實(shí)驗(yàn).

2.1 實(shí)驗(yàn)環(huán)境

采用8 臺(tái)服務(wù)器，其中1 臺(tái)服務(wù)器作為主節(jié)點(diǎn)，7 臺(tái)作為從節(jié)點(diǎn).每臺(tái)服務(wù)器的軟硬件環(huán)境均相同.服務(wù)器配置見(jiàn)表1.

表1 集群節(jié)點(diǎn)配置Tab.1 Configurations of each node

實(shí)驗(yàn)中將8 臺(tái)服務(wù)器的存儲(chǔ)空間利用Hadoop的HDFS 進(jìn)行資源的虛擬，構(gòu)建成一個(gè)大容量的虛擬資源池，將實(shí)驗(yàn)數(shù)據(jù)存儲(chǔ)在虛擬資源池中.實(shí)驗(yàn)時(shí)，分別用不同節(jié)點(diǎn)數(shù)的服務(wù)器對(duì)資源池中的數(shù)據(jù)進(jìn)行檢索計(jì)算.

2.2 實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)中隨機(jī)生成2 個(gè)簡(jiǎn)單的數(shù)據(jù)集，數(shù)據(jù)量分別為638,GB 和1.31,TB，存儲(chǔ)于資源池中.數(shù)據(jù)集的樣式見(jiàn)圖2.

圖2 部分實(shí)驗(yàn)數(shù)據(jù)集Fig.2 Partial experimental data set

兩數(shù)據(jù)集分別在不同集群節(jié)點(diǎn)數(shù)量時(shí)的案例檢索實(shí)驗(yàn)結(jié)果見(jiàn)圖3.

圖3 集群節(jié)點(diǎn)數(shù)量和數(shù)據(jù)量對(duì)案例檢索時(shí)間的影響Fig.3 Effect of node number and data size on CBR

由圖3 可以看出：集群對(duì)638,GB 的數(shù)據(jù)進(jìn)行檢索時(shí)，8 個(gè)節(jié)點(diǎn)比單節(jié)點(diǎn)要快50,s；對(duì)1.31,TB 的數(shù)據(jù)量進(jìn)行檢索時(shí)，8 個(gè)節(jié)點(diǎn)比單節(jié)點(diǎn)要快71,s.實(shí)驗(yàn)表明：集群節(jié)點(diǎn)數(shù)量對(duì)于案例的檢索時(shí)間有一定的影響，對(duì)大數(shù)據(jù)量的數(shù)據(jù)進(jìn)行檢索，隨著節(jié)點(diǎn)的增加，案例的檢索速度會(huì)加快；同時(shí)，需要處理的數(shù)據(jù)量越大，這種效果表現(xiàn)的越明顯.

3 結(jié)語(yǔ)

本文提出一種基于云平臺(tái)上的案例檢索技術(shù).在分析現(xiàn)有最近鄰法基礎(chǔ)上，采用MapReduce 思想對(duì)算法進(jìn)行改進(jìn)，使得案例的檢索過(guò)程可以在不同的服務(wù)器上并行進(jìn)行，從而提高檢索速度.由于開(kāi)源的Hadoop 平臺(tái)將案例庫(kù)存儲(chǔ)在HDFS 文件系統(tǒng)上，減少不同平臺(tái)間的差異，弱化了物理位置對(duì)系統(tǒng)的影響，可以實(shí)現(xiàn)資源的均衡調(diào)度.同時(shí)，由于案例庫(kù)會(huì)在不同的服務(wù)器上進(jìn)行備份，也保證了數(shù)據(jù)的安全性.

實(shí)驗(yàn)表明：對(duì)大數(shù)據(jù)量的數(shù)據(jù)進(jìn)行檢索時(shí)，本文提出的基于云平臺(tái)的案例檢索技術(shù)可以明顯提高檢索速度，隨著節(jié)點(diǎn)的增加，案例的檢索速度加快，且需處理的數(shù)據(jù)量越大，這種效果表現(xiàn)的越明顯.

［1］劉楓.基于Google 云計(jì)算的Web 應(yīng)用與開(kāi)發(fā)[J].電腦開(kāi)發(fā)與應(yīng)用，2011(5)：29-31，34.

［2］羅軍舟，金嘉暉，宋愛(ài)波，等.云計(jì)算：體系架構(gòu)與關(guān)鍵技術(shù)[J].通信學(xué)報(bào)，2011，32(7)：3-21.

［3］倪志偉，李建洋，李鋒剛，等.案例決策技術(shù)及案例決策支持系統(tǒng)研究綜述[J].計(jì)算機(jī)科學(xué)，2009，36(11)：18-23，42.

［4］侯玉梅，許成媛.基于案例推理法研究綜述[J].燕山大學(xué)學(xué)報(bào)：哲學(xué)社會(huì)科學(xué)版，2011，12(4)：102-108.

［5］Venner J.Pro Hadoop[M].New York：Apress，2009.

［6］楊立，左春，王裕國(guó).基于語(yǔ)義距離的K-最近鄰分類(lèi)方法[J].軟件學(xué)報(bào)，2005，16(12)：2054-2062.

［7］Dean J，Ghemawat S.MapReduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51(1)：107-113.

［8］李成華，張新訪，金海，等.MapReduce：新型的分布式并行計(jì)算編程模型[J].計(jì)算機(jī)工程與科學(xué)，2011，33(3)：129-135.