基于Spark平臺的巖石圖像聚類分析

楊艷梅，柳 娜，程國建，強新建，王敘喬

(1.西安石油大學(xué) 經(jīng)濟管理學(xué)院，陜西 西安 710065；2.長慶油田分公司 低滲透油氣田勘探開發(fā)國家工程實驗室，陜西 西安 710018；3.西安石油大學(xué) 計算機學(xué)院，陜西 西安 710065；4.長慶油田分公司 第十一采油廠，甘肅 慶陽 745000)

?

基于Spark平臺的巖石圖像聚類分析

楊艷梅1，柳 娜2，程國建3，強新建3，王敘喬4

(1.西安石油大學(xué) 經(jīng)濟管理學(xué)院，陜西 西安 710065；2.長慶油田分公司 低滲透油氣田勘探開發(fā)國家工程實驗室，陜西 西安 710018；3.西安石油大學(xué) 計算機學(xué)院，陜西 西安 710065；4.長慶油田分公司 第十一采油廠，甘肅 慶陽 745000)

提出了一種基于概率選擇的K-means聚類算法，并將其應(yīng)用到Spark平臺進(jìn)行圖像聚類，得到的數(shù)據(jù)集遠(yuǎn)小于初始數(shù)據(jù)集，大大降低了算法的迭代次數(shù)，聚類速度非常快。在Spark平臺應(yīng)用改進(jìn)的K-means算法進(jìn)行巖石圖像處理，對巖石圖像進(jìn)行特征提取，使得巖石圖像易于區(qū)分，解決了傳統(tǒng)的聚類算法無法確定初始中心、聚類數(shù)目K的選取不當(dāng)可能導(dǎo)致聚類失敗、算法容易受到噪聲和孤立點影響等問題。

巖石圖像；聚類分析；Spark平臺；K-means

楊艷梅,柳娜,程國建,等.基于Spark平臺的巖石圖像聚類分析[J].西安石油大學(xué)學(xué)報(自然科學(xué)版)，2016，31(6)：114-118.

YANG Yanmei,LIU Na,CHENG Guojian,et al.Clustering analysis of rock images based on spark platform[J].Journal of Xi'an Shiyou University (Natural Science Edition),2016,31(6):114-118.

引 言

大數(shù)據(jù)時代的到來使得信息的種類呈現(xiàn)出復(fù)雜多變的局面，由剛開始的純文本信息發(fā)展成為圖像、音頻、視頻及其混雜格式，數(shù)據(jù)量更是以人們難以想象的速度增長[1]。巖石圖像的挖掘?qū)τ筒乇碚骷捌淇梢暬_辟了新的途徑。聚類分析作為圖像信息挖掘領(lǐng)域一個重要的研究分支，是對原始圖像的海量數(shù)據(jù)進(jìn)行合理歸類的一種有效方法[2]。

20世紀(jì)90年代后期，隨著圖像處理技術(shù)的不斷發(fā)展，出現(xiàn)了對圖像內(nèi)容進(jìn)行檢索的需求，如對圖像的顏色、紋理、布局等進(jìn)行分析和檢索。圖像檢索技術(shù)是基于對圖像內(nèi)容的特征描述，在圖像數(shù)據(jù)庫中搜索出具有所描述特征或與所描述的特征有相似之處的圖像[3]。而目前圖像檢索技術(shù)所面臨的問題之一就是圖像的檢索時間[4]，人們所了解的以往的檢索方法是根據(jù)用戶提供的待查詢樣本圖像，然后按照特定的相似性度量規(guī)則，來查詢數(shù)據(jù)庫中的所有圖像，最終找出最相似的一些查詢結(jié)果，來返回給用戶。有關(guān)巖石圖像的研究及其工程應(yīng)用，特別是在油氣勘探中的應(yīng)用可參閱文獻(xiàn)[5-14]。對一般自然圖像的聚類分析研究已有大量研究論文，但對巖石圖像，特別是基于大數(shù)據(jù)平臺Spark的致密砂巖圖像研究尚屬探索階段。

本文對Spark平臺的巖石圖像進(jìn)行聚類處理，提出了一種基于概率選擇的改進(jìn)的K-means算法，通過此算法得到的數(shù)據(jù)集遠(yuǎn)遠(yuǎn)小于初始數(shù)據(jù)集，因此會大大提高K-means聚類的速度。基于Spark平臺，將改進(jìn)的K-means算法應(yīng)用于處理巖石圖像中，使用K-means算法對巖石圖像進(jìn)行特征提取，使得巖石圖像易于區(qū)分。

1 K-means聚類算法的改進(jìn)

1.1 Spark平臺簡介

Apache Spark是發(fā)源于美國加州大學(xué)伯克利分校AMPlab所開源的類HadoopMapReduce的通用并行框架，適用于如機器學(xué)習(xí)與數(shù)據(jù)挖掘等一些需要迭代的MapReduce算法[15-16]。為了避免應(yīng)用程序之間的相互影響，Apache Spark為每個應(yīng)用程序都設(shè)置了相應(yīng)的運行時環(huán)境，含有4種過程[17]：初始化過程、轉(zhuǎn)換過程、調(diào)度執(zhí)行及其終止過程。Spark工作原理如圖1所示[18]。

圖1 Apache Spark平臺的工作原理Fig.1 Working principle of Apache Spark platform

彈性分布式數(shù)據(jù)集(Resilient Distributed Datasets，RDD)是Spark的核心技術(shù)，在設(shè)計時不僅保留了數(shù)據(jù)流模型框架的優(yōu)點(諸如本地優(yōu)化分配、自動容錯及可拓展性等)，同時也使得用戶能夠?qū)⒉糠謹(jǐn)?shù)據(jù)集緩存在內(nèi)存中，這樣可大大加速對這部分?jǐn)?shù)據(jù)之后的查詢和計算過程。

Spark與Hadoop相似，但較Hadoop更優(yōu)，具體體現(xiàn)在以下方面：

(1)為提高計算時的迭代速度，Spark平臺將中間的過渡數(shù)據(jù)都存放在存儲器中。因為Spark中有了RDD的抽象概念，所以Spark更適合于迭代運算較多的DM運算[19]。

(2)由于Spark中有RDD的抽象概念，因此更適用于含有較多迭代過程的機器學(xué)習(xí)(ML)和數(shù)據(jù)挖掘(DM)運算。

(3)Spark比Hadoop更加具有通用性。Hadoop只提供2種運算操作：Map和Reduce，而Spark平臺能夠提供的數(shù)據(jù)集操作類型有很多。因此，給一些資深的用戶提供了方便[20]。各個處理節(jié)點之間的通信模型不再是惟一的一種模式?？梢哉f編程模型比Hadoop更靈活。

(4)處理速度高。由于Hadoop優(yōu)先追求高吞吐量，所以并沒有針對低延遲數(shù)據(jù)訪問做一些優(yōu)化；此外，由于作業(yè)的容錯性需求，Hadoop要將計算中間結(jié)果寫回到文件系統(tǒng)中，這就導(dǎo)致了繁瑣的I/O操作，大幅降低了短作業(yè)的處理速度[21]。

(5)高可用性。Spark比Hadoop提供了更加豐富的Scala、Java、Python API及交互式Shell，并以此來提高可用性。

1.2 K-means算法的改進(jìn)

在傳統(tǒng)的K-means聚類算法中，通常會通過隨機采樣的方法首先選定k個聚類中心，而經(jīng)由手動選定的初始中心將直接影響到待聚類數(shù)據(jù)集的最終聚類效果。如此這般，每個點被選為聚類中心之概率均相同。而在通常情況下，數(shù)據(jù)點的分布往往不均勻，必須根據(jù)不同的概率來選擇不同的數(shù)據(jù)點，將其作為聚類中心，因此本文提出了一種基于概率選擇的K-means改進(jìn)算法。

首先定義代價函數(shù)

(1)

數(shù)據(jù)采樣的概率函數(shù)為：

(2)

該函數(shù)所要表達(dá)的是：某個數(shù)據(jù)點到其所屬聚類中心之距的平方和。最小化代價函數(shù)的作用是通過不斷迭代，從而判斷聚類結(jié)果是否達(dá)到收斂。將首次代價定義為Φ，將過采樣系數(shù)定義為λ，采樣系數(shù)表示在每次迭代中對λ個點進(jìn)行采樣?；谏鲜龈怕蔬x擇機理的聚類算法如下：

(1)從數(shù)據(jù)集中隨機采樣一個點C；

(2)計算該點的初始代價λ；

(3)循環(huán)次數(shù)為logφ次；

(5)C″←C∪C′；

(6)結(jié)束；

(7)按照K-means算法找到數(shù)據(jù)集C的k個聚類中心。

首先在數(shù)據(jù)集中隨機選擇一個點，將其作為初始聚類中心并計算該點的初始代價值φ，隨后進(jìn)行l(wèi)ogφ次的迭代。這樣做的原因是本文的初始聚類中心是隨機選擇的，因此無法判斷其選擇的好壞，根據(jù)此值的好壞并基于代價函數(shù)可有效地確定本算法的迭代次數(shù)。式(1)為每次迭代過程中的采樣概率。為

盡可能地使新的聚類中心遠(yuǎn)離當(dāng)前的聚類中心，每次迭代時，都會從數(shù)據(jù)集中采樣λ個數(shù)據(jù)點，距離當(dāng)前聚類中心越遠(yuǎn)的數(shù)據(jù)點有更高的被采樣概率。為了更新每個點在下一次被采樣的概率，每次迭代完成之后，都會更新ΦX(C)的值。同時可將每次采樣的聚類中心合并到上次迭代后的聚類中心數(shù)據(jù)集當(dāng)中，直到完成logφ次迭代。此時將會得到一個全新的數(shù)據(jù)集C，其中包含了λlogφ個數(shù)據(jù)采樣。最后通過傳統(tǒng)的K-means聚類算法，再將數(shù)據(jù)集C劃分為k個聚類。

因為基于概率選擇的K-means聚類算法對數(shù)據(jù)進(jìn)行了適當(dāng)?shù)念A(yù)處理，所得到的新數(shù)據(jù)集C的規(guī)模遠(yuǎn)小于初始數(shù)據(jù)集X，因此在新數(shù)據(jù)集上進(jìn)行聚類處理的速度將會大幅度的提高。同時，傳統(tǒng)的K-means算法往往是根據(jù)經(jīng)驗設(shè)定收斂閾值，這樣一來無論是復(fù)雜的聚類還是簡單的聚類，算法的迭代次數(shù)都是確定的，而使用logφ次迭代能夠根據(jù)代價函數(shù)自動調(diào)整收斂閾值，這樣可有效地降低算法執(zhí)行所需要的迭代次數(shù)，對于海量數(shù)據(jù)的聚類劃分來說更具有時間上的優(yōu)越性。

2 實驗結(jié)果與分析

2.1 圖像分割測試

利用傳統(tǒng)的K-means算法對圖像分割，巖石薄片圖像的原圖如圖2所示，進(jìn)行圖像分割后的結(jié)果如圖3所示。從分割效果看，可以實現(xiàn)巖石圖像分割，但是分割后圖像目標(biāo)出現(xiàn)很多不連續(xù)點。因此提出了基于概率的改進(jìn)的K-means算法進(jìn)行巖石圖像的處理，處理結(jié)果如圖4所示，明顯地看出其按顏色分割的特點，連續(xù)點也比傳統(tǒng)的K-means算法有所改善。

圖2 原始巖石圖像Fig.2 Original rock image

圖3 聚類中心隨機選擇的分割效果(對應(yīng)2個分割區(qū)域)Fig.3 Segmentation effect by random selection of clustering center (corresponding to two segmented regions)

圖4 聚類中心概率選擇的分割效果(對應(yīng)2個分割區(qū)域)Fig.4 Segmentation effect by probability selection of cluster center (corresponding to two segmentation regions)

2.2 聚類算法有效性測試

使用K-means算法進(jìn)行聚類分析時需要進(jìn)行多次迭代運算，迭代次數(shù)直接影響算法的收斂速度。為了測試本文算法的有效性，分別比較了傳統(tǒng)K-means算法與本文算法將圖像分成12塊時迭代相同次數(shù)所需的時間(見表1)，以及不同迭代次數(shù)的情況下，使用改進(jìn)的K-means算法將圖像分成不同大小的圖像塊所需的時間(見表2)。

表1 不同算法不同迭代次數(shù)所需時間的對比Tab.1 Time required for different iteration times

表2 相同迭代次數(shù)與圖像分塊條件下所需時間的對比Tab.2 Time required under image blocks and iteration times

本文中改進(jìn)的K-means算法采用了自適應(yīng)的初始化聚類中心，從表1可以看出，相同迭代次數(shù)下，改進(jìn)后的算法比傳統(tǒng)K-means算法運行時間短很多，迭代3次時，改進(jìn)的K-means算法將圖像分為12塊所需要的運行時間幾乎是傳統(tǒng)K-means算法所需時間的十分之一，算法的速度有了很大的提高；迭代次數(shù)增加到15次時，改進(jìn)的K-means算法所需時間也有所增加，而傳統(tǒng)K-means算法所需時間的增加與改進(jìn)的算法相差不多。從表2可以看出，迭代次數(shù)相同時，將圖像分為3塊和12塊所需的時間相差不多，但是將圖像分為48塊所需的時間比分為3塊和12塊所需的時間長。

3 結(jié) 論

傳統(tǒng)K-means算法聚類效果特別依賴于初始聚類中心的選擇，一旦初始聚類中心選擇的不大合適，算法的執(zhí)行過程就很容易陷入某個聚類的局部最優(yōu)值，并且分割效果與聚類數(shù)目K的選取有很大的關(guān)聯(lián)性。如果聚類數(shù)目K的選取不當(dāng)可能導(dǎo)致聚類失敗，此外，算法容易受到噪聲和孤立點的影響，因此論文研究了一種基于概率選擇的改進(jìn)聚類算法，通過改進(jìn)算法的預(yù)處理，將其應(yīng)用到Spark平臺進(jìn)行圖像聚類，得到的數(shù)據(jù)集遠(yuǎn)小于初始數(shù)據(jù)集，且聚類速度非常快，同時也降低了算法執(zhí)行過程中的迭代次數(shù)，因此大大提高了K-means聚類的速度，這對于海量數(shù)據(jù)的聚類可能效果更為顯著。

[1] 吳哲夫,張彤,肖鷹.基于Spark平臺的K-means聚類算法改進(jìn)及并行化實現(xiàn)[J].互聯(lián)網(wǎng)天地,2016,12(1):44-50. WU Zhefu,ZHANG Tong,XIAO Ying.An improved K-means clustering algorithm based on spark platform and its parallel implementation[J].Internet World,2016,12(1):44-50.

[2] 邱榮財.基于Spark平臺的CURE算法并行化設(shè)計與應(yīng)用[D].廣州：華南理工大學(xué),2014. QIU Rongcai.Parallelization Design and Application of CURE Algorithm Based on Spark Platform[D].Guangzhou:South China University of Technology,2014.

[3] 黎光譜.改進(jìn)K-Means聚類算法在基于Hadoop平臺的圖像檢索系統(tǒng)中的研究與實現(xiàn)[D].廈門：廈門大學(xué),2014. LI Guangpu.Research and Implementation of Improved K-means Clustering Algorithm Based on Hadoop Platform in Image Retrieval System[D].Xiamen:Xiamen University,2014.

[4] 楊傳慧.圖像聚類及其在圖像檢索中的應(yīng)用研究[D].南京:南京師范大學(xué),2013. YANG Chuanhui.Image Clustering and Image Retrieval Application[D].Nanjing:Nanjing Normal University,2013.

[5] SHAINA Kelly,HESHAM El-Sobky.Assessing the utility of FIB-SEM images for shale digital rock physics[J].Advances in Water Resources,2016,95(9):302-316.

[6] SUN Hai,YAO Jun,CAO Yingchang,et al.Characterization of gas transport behaviors in shale gas and tight gas reservoirs by digital rock analysis[J].International Journal of Heat and Mass Transfer,2017,104(1):227-239.

[7] HE Jianhua,DING Wenlong,LI Ang,et al.Quantitative microporosity evaluation using mercury injection and digital image analysis in tight carbonate rocks:a case study from the Ordovician in the Tazhong Palaeouplift,Tarim Basin,NW China[J].Journal of Natural Gas Science and Engineering,2016,34(8):627-644.

[8] JAFAR Qajar,CHRISTOPH H Arns.Characterization of reactive flow-induced evolution of carbonate rocks using digital core analysis part1:assessment of pore-scale mineral dissolution and deposition[J].Journal of Contaminant Hydrology,2016,192(9):60-86.

[9] OLSON L,SAMSON C,MCKINNON S D.3-D laser imaging of drill core for fracture detection and rock quality designation[J].International Journal of Rock Mechanics and Mining Sciences,2015,73(1):156-164.

[10] GAO G,YAO W,XIA K,et al.Investigation of the rate dependence of fracture propagation in rocks using digital image correlation (DIC) method[J].Engineering Fracture Mechanics,2015,138(4):146-155.

[11] SWARUP Chauhan,WOLFRAM Rühaak,FAISAL Khan,et al.Processing of rock core microtomography images:using seven different machine learning algorithms[J].Computers & Geosciences,2016,86(1):120-128.

[12] SAFARI Alireza,DOWLATABAD Mojtaba Moradi,HASSANI A,et al.Numerical simulation and X-ray imaging validation of wormhole propagation during acid core-flood experiments in a carbonate gas reservoir[J].Journal of Natural Gas Science and Engineering,2016,30(3):539-547.

[13] HEIKO Andr?,NICOLAS Combaret.Digital rock physics benchmarks:Part I Imaging and segmentation[J].Computers & Geosciences,2013,50(1):25-32.

[14] HEIKO Andr?,NICOLAS Combaret.Digital rock physics benchmarks:part II computing effective properties[J].Computers & Geosciences,2013,50(1):33-43.

[15] ZHOU Y,OUYANG Z,LIU J,et al.A novel K-means image clustering algorithm Based on glowworm swarm optimization[J].Przeglad Elektrotechniczny,2012,88(8):4031-4032.

[16] ZHAO Weizhong,MA Huifang,HE Qing.Parallel K-means clustering based on map reduce[J].Lecture Notes in Computer Science,1990,5931:674-679.

[17] 陳虹君.基于Spark框架的聚類算法研究[J].電腦知識與技術(shù),2015(4):56-57. CHEN Hongjun.Clustering algorithm research based on spark architecture[J].Computer Knowledge & Technology,2015(4):56-57.

[18] 張杰.PyGel:基于DPark的分布式圖計算引擎的研究與實現(xiàn)[D].廣州：華南理工大學(xué),2013. ZHANG Jie.PyGel:Distributed Graph Computing Engine Research & Implementation Based on DPark[D].Guangzhou:South China University of Technology,2013.

[19] 王詔遠(yuǎn),王宏杰,邢煥來,等.基于Spark的蟻群優(yōu)化算法[J].計算機應(yīng)用,2015,35(10):2777-2780. WANG Zhaoyuan,WANG Hongjie,XING Huanlai,et al.Ant colony optimization algorithm based on Spark[J].Computer Applications,2015,35(10):2777-2780.

[20] 蘭葉芳,鄧秀芹,程黨性,等.鄂爾多斯盆地三疊系延長組次生孔隙形成機制[J].地質(zhì)科技情報,2014,33(6):128-136. LAN Yefang,DENG Xiuqin,CHENG Dangxing,et al.Formation mechanisms of secondary porosity in the triassic yanchang formation in the Ordos basin[J].Geological Science and Technology Information,2014,33(6):128-136.

[21] 黃震華,向陽,張波,等.一種進(jìn)行K-Means聚類的有效方法[J].模式識別與人工智能,2010,23(4):516-521. HUANG Zhenhua,XIANG Yang,ZHANG Bo,et al.An efficient method for K-means clustering[J].Pattern Recognition and Artificial Intelligence,2010,23(4):516-521.

責(zé)任編輯：張新寶

Clustering Analysis of Rock Images Based on Spark Platform

YANG Yanmei1,LIU Na2,CHENG Guojian3,QIANG Xinjian3,WANG Xuqiao4

(1.College of Economics and Management,Xi'an Shiyou University,Xi'an 710065,Shaanxi,China;2.National Engineering Laboratory for Exploration and Development of Low Permeability Oil and Gas Field,Changqing Oilfield Company,Xi'an 710018,Shaanxi,China;3.College of Computer Science,Xi'an Shiyou University,Xi'an 710065,Shaanxi,China;4.The 11th Oil Production Plant,Changqing Oilfield Company,Qingyang 745000,Gansu,China)

K-means clustering algorithm based on probability selection is discussed,and it is applied to the Spark platform for the cluster of images.The generated data set is much smaller than the initial data sets,which greatly reduces the iteration times and improves clustering speed.The improved K-means algorithm is applied to the processing of rock images.The feature of the rock image is extracted,which makes the rock image to be very easily distinguished.This method overcomes the shortcomings of the traditional clustering algorithms,such as clustering fails due to the unable determination of initial center and the improper selection of cluster number K,the cluster algorithm is susceptible to noise,isolated points,and so on.

rock image;cluster analysis;Spark platform;K-means

2016-07-15

國家科技重大專項(編號：2016ZX05007G003)；陜西省工業(yè)科技攻關(guān)項目(編號：2015GY104)；中國石油天然氣股份有限公司重大科技專項(編號：2011EG1301)

楊艷梅 (1968-),女，碩士，高級工程師，主要從事計算機信息處理研究。 E-mail: ymyang@xsyu.edu.cn

10.3969/j.issn.1673-064X.2016.06.018

TE19；TP319

1673-064X(2016)06-0114-05

A