基于可拓學(xué)理論的高維大數(shù)據(jù)相似性研究

基于可拓學(xué)理論的高維大數(shù)據(jù)相似性研究

袁瑞萍，師鳴若

(北京物資學(xué)院信息學(xué)院，北京101149)

摘要：高維大數(shù)據(jù)的相似性計(jì)算是數(shù)據(jù)挖掘領(lǐng)域的研究重點(diǎn)，論文通過分析高維大數(shù)據(jù)相似性計(jì)算的難點(diǎn)，提出采用可拓學(xué)的方法解決其中矛盾問題的研究思路。在基元表示高維大數(shù)據(jù)的基礎(chǔ)上，借助數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)篩選、權(quán)重的確定、數(shù)據(jù)預(yù)處理等技術(shù)實(shí)現(xiàn)了數(shù)據(jù)之間的相似性計(jì)算，并基于水污染常規(guī)分析數(shù)據(jù)進(jìn)行了算法驗(yàn)證。論文借助可拓的思想研究大數(shù)據(jù)相似性的問題，不僅對(duì)數(shù)據(jù)挖掘的研究有一定的理論促進(jìn)，同時(shí)也為可拓學(xué)的研究提供了新的應(yīng)用空間。

關(guān)鍵詞：大數(shù)據(jù)；高維數(shù)據(jù)；可拓學(xué)；相似性

收稿日期：2015-06-04

基金項(xiàng)目：北京市教委科技計(jì)劃面上項(xiàng)目(KM201510037001)；智能物流系統(tǒng)北京市重點(diǎn)實(shí)驗(yàn)室(NO:BZ0211)；北京市屬高等學(xué)校創(chuàng)新團(tuán)隊(duì)建設(shè)提升計(jì)劃項(xiàng)目(項(xiàng)目號(hào):IDHT20130517)

作者簡(jiǎn)介：袁瑞萍(1982-)，女，博士，講師,山東荷澤人,研究方向:物流信息化,數(shù)據(jù)挖掘;師鳴若(1976-),女,河南鄭州人,研究方向:商務(wù)智能。

中圖分類號(hào)：TP311.1文章標(biāo)識(shí)碼：A

Research on the Similarity of High Dimensional Big Data Based on Extenics

YUAN Rui-ping, SHI Ming-ruo

(SchoolofInformation,Beijingwuziuniversity,Beijing101149，China)

Abstract:The similarity calculation of high dimensional big data is a research focus in the field of data mining. In this paper, after analyzing the difficulty of similarity calculation of high dimensional data, a method based on extenics is put forward to solve the contradictory problems. Firstly, the element is used to represent high dimensional data. Then the similarity between data is calculated by means of data conversion, data selection, weight determination and data pre-processing technology. Finally the conventional analysis data of water pollution is used to verify the method. The idea of using extenics to solve similarity problem of big data can not only promote theoretical research of data mining, but also provide a new application for extenics.

Key words:big data; high dimensional data; extenics; similarity determination

0引言

2008 年9月，《科學(xué)》雜志發(fā)表文章《Big Data: Science in the Petabyte Era》,“大數(shù)據(jù)”一詞正式走入公眾視線，并開始傳播。其實(shí)，“大數(shù)據(jù)”一詞早在上個(gè)世紀(jì)80年代由美國人提出來[1,2]。2011年6月，IDC研究報(bào)告《從混沌中提取價(jià)值》中三個(gè)基本論斷構(gòu)成了大數(shù)據(jù)的理論基礎(chǔ)，人們對(duì)大數(shù)據(jù)的關(guān)注程度日益上升。據(jù)統(tǒng)計(jì)，Google“大數(shù)據(jù)”搜索量自2011年6月起呈直線上升趨勢(shì)，大數(shù)據(jù)時(shí)代的到來毋庸置疑[3]。根據(jù)國際數(shù)據(jù)資訊(IDC)公司監(jiān)測(cè)，全球數(shù)據(jù)量大約每兩年翻一番，預(yù)計(jì)到 2020 年，全球?qū)碛?35ZB 的數(shù)據(jù)量，并且 85%以上的數(shù)據(jù)以非結(jié)構(gòu)化或半結(jié)構(gòu)化的形式存在?！按髷?shù)據(jù)”2011年一路走紅，2012年后更加閃耀，成為業(yè)界當(dāng)之無愧的焦點(diǎn)，很多國內(nèi)外的學(xué)術(shù)會(huì)議均以“大數(shù)據(jù)”冠名。伴隨新型SNS 網(wǎng)絡(luò)的發(fā)展、視頻流量的猛增及圖片分享需求的涌現(xiàn)，人們迷失于茫茫的數(shù)據(jù)海洋中，如何從大數(shù)據(jù)中挖掘出有用的信息成為關(guān)注的焦點(diǎn)，其中高維大數(shù)據(jù)因其復(fù)雜性而備受關(guān)注，并成為數(shù)據(jù)領(lǐng)域中的研究熱點(diǎn)和前沿問題。

1高維大數(shù)據(jù)相似性研究綜述

聚類分析是高維數(shù)據(jù)處理的主要內(nèi)容，它根據(jù)數(shù)據(jù)對(duì)象屬性信息或?qū)ο箝g關(guān)系，將數(shù)據(jù)對(duì)象分成類或簇，使得同一個(gè)簇中對(duì)象之間具有較高相似度，而不同簇中對(duì)象彼此差別較大，即通常所說的“類內(nèi)聚合度高，類間耦合度低”。傳統(tǒng)的聚類算法包括分層法、劃分法、基于密度的方法和基于網(wǎng)格的方法等[3]。各種聚類算法的基礎(chǔ)都是數(shù)據(jù)相似性計(jì)算，因此探討數(shù)據(jù)的相似性是聚類實(shí)現(xiàn)的根本。但是，高維數(shù)據(jù)的相似性計(jì)算存在一定的困難，這種困難不僅體現(xiàn)在聚類算法效率的下降，更重要的是由于高維空間的稀疏性和最近鄰特性使得在高維空間中幾乎不可能存在數(shù)據(jù)簇，還有就是高維數(shù)據(jù)中的非結(jié)構(gòu)化數(shù)據(jù)讓問題變得難以表述。

高維數(shù)據(jù)的相似性一般用距離函數(shù)(或相似度函數(shù))表示，距離不單是空間上的距離，也包括時(shí)間、狀態(tài)、語義、密度等產(chǎn)生的差距。常見的距離有歐幾里得距離、曼哈頓距離、切比雪夫距離、閔可夫斯基距離、馬氏距離、相關(guān)系數(shù)和夾角余弦距離等等。目前為止，還沒有一個(gè)能適用于所有聚類任務(wù)的距離函數(shù)，在不同的聚類問題中應(yīng)該設(shè)計(jì)不同的相似性度量。Apostolico等[4]提出一種快速計(jì)算生物序列距離的方法；Vinga 等[5]比較了幾種用于計(jì)算 SCOP蛋白質(zhì)數(shù)據(jù)集的序列距離計(jì)算方法；Ververidis 等[6]考慮了馬氏距離在高維空間中的信息丟失問題；Yu 等[7]提出一種估計(jì)樣本間相似度的通用向?qū)А?/p>

王曉陽等[8]針對(duì)傳統(tǒng)數(shù)據(jù)相似性度量算法在高維數(shù)據(jù)空間的不適應(yīng)性，通過分析傳統(tǒng)距離度量方法，結(jié)合高維數(shù)據(jù)特性，提出了新的高維數(shù)據(jù)相似性度量函數(shù)，該方法在處理高值數(shù)據(jù)之間與低值數(shù)據(jù)之間的相對(duì)差異方面更具優(yōu)勢(shì)。邵昌昇等[9]對(duì)傳統(tǒng)度量算法進(jìn)行改進(jìn)，提出新的Close函數(shù)，以彌補(bǔ)傳統(tǒng)相似性度量算法應(yīng)用在高維空間時(shí)的不足。謝明霞等[10]提出了高維數(shù)據(jù)相似性度量函數(shù)的改進(jìn)HDsim(X,Y)函數(shù)，該函數(shù)整合了各類型數(shù)據(jù)的相似性度量方法，在處理數(shù)值型、二值型以及分類屬性數(shù)據(jù)上充分體現(xiàn)了原Hsim(X,Y)函數(shù)處理數(shù)值型數(shù)據(jù)、Jaccard系數(shù)處理二值數(shù)據(jù)以及匹配率處理分類屬性數(shù)據(jù)的優(yōu)越性。黃斯達(dá)等[11]針對(duì)傳統(tǒng)基于距離度量的聚類算法難以適合高維數(shù)據(jù)聚類以及高維數(shù)據(jù)之間相似度難定義的問題，首先計(jì)算對(duì)象兩兩之間的相似度并得出相似度矩陣，然后根據(jù)該相似度矩陣和閾值大小自底向上對(duì)數(shù)據(jù)進(jìn)行聚類分析。

以上研究分析表明，在高維數(shù)據(jù)處理的研究領(lǐng)域，尤其是基于相似性度量的聚類分析中，學(xué)者們致力于算法的改進(jìn)和優(yōu)化，應(yīng)用于不同數(shù)據(jù)處理會(huì)得到不同的結(jié)果，但是到底哪種算法更適合處理高維數(shù)據(jù)尚無定論。因此，走出原有的研究路徑，尋找新的突破口是實(shí)現(xiàn)算法優(yōu)化的一個(gè)思路。

2可拓學(xué)的引入

可拓學(xué)[12]是用來解決矛盾問題的一種方法，采用形式化的模型，實(shí)現(xiàn)了定性與定量的結(jié)合。高維數(shù)據(jù)處理中大量非結(jié)構(gòu)化數(shù)據(jù)的客觀存在，為可拓學(xué)的應(yīng)用奠定了基礎(chǔ)。

作為哲學(xué)、數(shù)學(xué)與工程學(xué)交叉的一門新興學(xué)科[13,14]，可拓學(xué)在各門學(xué)科和工程技術(shù)領(lǐng)域中應(yīng)用的成效, 不在于發(fā)現(xiàn)新的實(shí)驗(yàn)事實(shí), 而在于提供一種新的思想和方法。為了解決具體的矛盾問題，可拓學(xué)研究者探討了能處理一般矛盾問題和領(lǐng)域中矛盾問題所需要的形式化模型、定量化工具、推理的規(guī)則和特有的方法, 在理論、方法和技術(shù)上都取得了一定的進(jìn)展[15]。高維數(shù)據(jù)處理中，數(shù)據(jù)屬性的分析、數(shù)據(jù)歸類、數(shù)據(jù)相似性計(jì)算、數(shù)據(jù)閾值確定等都屬于矛盾性的問題，這些矛盾的處理可以借助于可拓學(xué)的思路來解決。

可拓創(chuàng)新方法是可拓學(xué)中特有的方法，通過對(duì)研究對(duì)象的拓展、變換、評(píng)價(jià)等，以生成解決各種矛盾問題的創(chuàng)意的形式化、定量化方法?？赏貏?chuàng)新方法的基礎(chǔ)是基元[16]，基元包括物元、事元和關(guān)系元[17]。其中，物元是應(yīng)用最為廣泛也是最早提出的基元，其一般定義為：以物Om為對(duì)象，cm為特征，Om關(guān)于cm的量值vm構(gòu)成的有序三元組M=(Om,cm,vm)作為描述物的基本元，稱為一維物元，Om,cm,vm三者稱為物元的三要素，其中cm,和vm構(gòu)成的二元組(cm,vm)稱為物Qm的特征元。這里，量值vm可以是數(shù)量化量值，也可以是非數(shù)量化量值。大數(shù)據(jù)時(shí)代，海量的半結(jié)構(gòu)化和非結(jié)構(gòu)化數(shù)據(jù)的處理正好契合了特征元的思想。量值vm在事物的定性描述和事物的定量評(píng)價(jià)之間架起了一座橋梁。在高維數(shù)據(jù)處理方面，二元組(cm,vm)將高維數(shù)據(jù)中的結(jié)構(gòu)化數(shù)據(jù)和非結(jié)構(gòu)化數(shù)據(jù)有機(jī)結(jié)合起來。所以，借助可拓學(xué)的思想和方法來解決高維數(shù)據(jù)處理問題成為可能。

3基于可拓學(xué)理論的高維大數(shù)據(jù)相似度計(jì)算過程

可拓學(xué)方法因其獨(dú)有的形象化表示方法，在對(duì)定性和定量問題的研究中具有一定的優(yōu)勢(shì)，尤其在定性研究方面更具特色。采用該方法進(jìn)行高維數(shù)據(jù)相似性計(jì)算基于以下幾個(gè)環(huán)節(jié)。

(1)采用基元表示系統(tǒng)中的研究對(duì)象，其中涵蓋定性數(shù)據(jù)和定量數(shù)據(jù)。

如何定義相似性計(jì)算公式是問題的重點(diǎn)，但對(duì)高維數(shù)據(jù)來說，用形式化的語言描述高維數(shù)據(jù)是問題的起點(diǎn)?；强赏貙W(xué)的邏輯細(xì)胞[18,19]，也是采用可拓學(xué)研究問題的基礎(chǔ)。

借助基元中物元的形式化表示符號(hào)M=(Qm，cm,vm)將高維數(shù)據(jù)的某一條記錄描述為多維物元形式，即：

(1)

其中，Mi(i=1,2,…,n)代表高維數(shù)據(jù)物元；

Qi(i=1,2,…,n)代表某一條數(shù)據(jù)記錄，并設(shè)定數(shù)據(jù)總量為n，在大數(shù)據(jù)背景下，n值將很大；

cj(j=1,2,…,m)代表高維數(shù)據(jù)屬性，該屬性可以是結(jié)構(gòu)化的也可以是非結(jié)構(gòu)化的，并設(shè)定數(shù)據(jù)維度為m；

vji(j=1,2,…,m;i=1,2,…,n)代表高維數(shù)據(jù)系統(tǒng)中屬性cj的取值，這個(gè)取值可以是定量的數(shù)據(jù)，也可以是定性數(shù)據(jù)，可以是結(jié)構(gòu)化數(shù)據(jù)，也可以是非結(jié)構(gòu)化數(shù)據(jù)。

需要說明的是，高維大數(shù)據(jù)中稀疏性[18]的客觀存在，高維數(shù)據(jù)物元中很多量值V均為空，此時(shí)可以用0補(bǔ)齊。

(2)數(shù)據(jù)轉(zhuǎn)換。將系統(tǒng)中的定性數(shù)據(jù)轉(zhuǎn)化為定量數(shù)據(jù)，一般的將“是”和“否”二維邏輯數(shù)據(jù)轉(zhuǎn)化為1和0，其他定性數(shù)據(jù)可以視具體情況而定。

(3)數(shù)據(jù)篩選。一方面，在多維數(shù)據(jù)中，有些數(shù)據(jù)是冗余數(shù)據(jù)，這些數(shù)據(jù)會(huì)帶來計(jì)算復(fù)雜度的提升，因此剔除可見的冗余數(shù)據(jù)對(duì)于計(jì)算是有益的；另一方面，基于數(shù)據(jù)的應(yīng)用目標(biāo)，有些數(shù)據(jù)在相似性研究或者問題的解決中不起任何作用，可以剔除。

(4)權(quán)重的確定。采用函數(shù)Hsim(X,Y)計(jì)算兩個(gè)對(duì)象之間的相似性需要定義屬性的權(quán)重。常用的權(quán)重確定方法有相對(duì)比較法、專家打分法和層次分析法等，也可以采用可拓權(quán)重法，基于各個(gè)待評(píng)對(duì)象關(guān)于各評(píng)價(jià)指標(biāo)的取值，借助關(guān)聯(lián)函數(shù)獲得。

(6)數(shù)據(jù)補(bǔ)齊。數(shù)據(jù)稀疏性是多維大數(shù)據(jù)的基本屬性，一般的可以根據(jù)屬性間關(guān)系借助粗糙集的方法補(bǔ)足數(shù)據(jù)，或者采用簡(jiǎn)單的設(shè)定方法獲取缺失數(shù)據(jù)。

(7)計(jì)算高維數(shù)據(jù)的相似度，進(jìn)而獲得聚類結(jié)果?；谝延械奈墨I(xiàn)可以定義兩個(gè)高維數(shù)據(jù)的相似性為：

(2)

4案例應(yīng)用

論文采用文獻(xiàn)[20]中的數(shù)據(jù)進(jìn)行計(jì)算。該文獻(xiàn)探討的是水污染常規(guī)數(shù)據(jù)聚類分析，通常水污染常規(guī)分析指標(biāo)包括臭味、水溫、渾濁度、pH值、電導(dǎo)率、溶解性固體、懸浮性固體、總氮、總有機(jī)碳(TOC)、溶解氧(DO)、生化需氧量(BOD)、化學(xué)需氧量(COD)、細(xì)菌總數(shù)、大腸菌群等，可以看成是一個(gè)高維的數(shù)據(jù)集。論文監(jiān)測(cè)了海河流域上馬頰河的11個(gè)監(jiān)測(cè)點(diǎn)(采樣點(diǎn))的溶解氧、化學(xué)需氧量、氨氮、揮發(fā)酚和石油類等5項(xiàng)水質(zhì)污染指標(biāo)數(shù)據(jù)，為了描述問題的一般性，引入定性指標(biāo)“臭味”，抽取各個(gè)指標(biāo)的最優(yōu)值和最劣值，獲取數(shù)據(jù)如表1所示。

表1　監(jiān)測(cè)點(diǎn)數(shù)據(jù)　單位：mg/L -1

(1)借助物元方法表示各個(gè)監(jiān)測(cè)點(diǎn)，如圖1所示，屬性C1到C6分別表示溶解氧、化學(xué)需氧量、氨氮、揮發(fā)酚、石油類和臭味。

圖1各個(gè)檢測(cè)點(diǎn)的物元表示

(2)該數(shù)據(jù)集中屬性C6的取值范圍為定性數(shù)據(jù)，分別定義0,0.5,1，對(duì)應(yīng)“無”、“一般”、“有”三項(xiàng)取值。

(3)在數(shù)據(jù)指標(biāo)中，監(jiān)測(cè)點(diǎn)的位置屬于冗余數(shù)據(jù)，不需要考慮，可以剔除。

(4)獲取各個(gè)指標(biāo)的權(quán)重，如表1最后一行所示。

(5)根據(jù)各個(gè)指標(biāo)的最優(yōu)值和最劣值獲取離差度，如表1倒數(shù)第二行所示。

(6)由于案例中M2，M7，M10的部分?jǐn)?shù)據(jù)缺失，可以補(bǔ)齊，不難發(fā)現(xiàn)屬性C6的取值與監(jiān)測(cè)點(diǎn)的位置具有一定的對(duì)應(yīng)關(guān)系，因此可以定義v6,2=0,v6,7=0,v6,10=0.5。

(7)借助相似度計(jì)算公式得到兩兩物元之間的相似度如表2所示。

表2　相似度計(jì)算結(jié)果

5結(jié)論

高維大數(shù)據(jù)的相似性計(jì)算是數(shù)據(jù)挖掘領(lǐng)域的研究重點(diǎn)，本文在分析高維大數(shù)據(jù)相似性計(jì)算難點(diǎn)基礎(chǔ)上，提出采用可拓的方法解決其中的矛盾問題。在基元表示高維大數(shù)據(jù)的基礎(chǔ)上，借助數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)篩選、權(quán)重的確定、數(shù)據(jù)預(yù)處理等技術(shù)實(shí)現(xiàn)了數(shù)據(jù)之間的相似性計(jì)算，并基于水污染常規(guī)分析數(shù)據(jù)進(jìn)行了算法驗(yàn)證。該方法在高維數(shù)據(jù)的表示方面具有一定的優(yōu)勢(shì)，尤其是在定性數(shù)據(jù)表示方面。其次，該方法借助于合理的相似度計(jì)算公式可以得到數(shù)據(jù)之間的相似性度量，進(jìn)而為數(shù)據(jù)的聚類分析奠定了基礎(chǔ)。論文提出的方法對(duì)高維數(shù)據(jù)的處理具有一定的理論價(jià)值，同時(shí)也為可拓學(xué)的研究拓展了應(yīng)用空間。

參考文獻(xiàn)：

[1]馮芷艷,郭迅華,曾大軍,陳煜波,陳國青.大數(shù)據(jù)背景下商務(wù)管理研究若干前沿課題[J].管理科學(xué)學(xué)報(bào),2013,16(1):1-9.

[2]徐子沛.大數(shù)據(jù)[M].廣西:廣西師范出版社,2012.

[3]楊風(fēng)召.高維數(shù)據(jù)挖掘中若干關(guān)鍵問題的研究[D].上海:復(fù)旦大學(xué),2003.

[4]Apostolico A, Denas O. Fast algorithms for computing sequence distances by exhaustive substring composition[J]. Algorithms for Molecular Biology, 2008, 3(1): 13-16.

[5]Vinga S, Gouveia-Oliveira R, Almeida J S. Comparative evaluation of word composition distances for the recognition of SCOP relationships[J]. Bioinformatics. 2004, 20(2): 206-215.

[6]Ververidis D, Kotropoulos C. Information loss of the mahalanobis distance in high dimensions: application to feature selection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2009, 31(12): 2275-2281.

[7]Yu J, Amores J, Sebe N. Distance learning for similarity estimation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2008, 30(12): 451-462.

[8]王曉陽,張洪淵,沈良忠,池萬樂.基于相似性度量的高維數(shù)據(jù)聚類算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2013,(5):30-33.

[9]邵昌昇,樓巍,嚴(yán)利民.高維數(shù)據(jù)中的相似性度量算法的改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011,(2):1-4.

[10]謝明霞,郭建忠,張海波,陳科.高維數(shù)據(jù)相似性度量方法研究[J].計(jì)算機(jī)工程與科學(xué),2010,(5):92-96.

[11]黃斯達(dá),陳啟買.一種基于相似性度量的高維數(shù)據(jù)聚類算法的研究[J].計(jì)算機(jī)應(yīng)用與軟件,2009,(9):102-105.

[12]蔡文.可拓集合和不相容問題[J].科學(xué)探索學(xué)報(bào),1983,(1):83-97.

[13]Cai Wen. Extension theory and its application[J]. Chinese science bulletin, 1999, 44(17): 1538-1548.

[14] Cai Wen, Yang Chunyan, Wang Guanghua. A new gross discipline-extenics[J]. Science foundation in china. 2005, 13(1): 55-61.

[15]楊春燕.可拓學(xué)的重要科學(xué)問題及其關(guān)鍵點(diǎn)[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2006,38(7):1087-1090.

[16]楊春燕.多評(píng)價(jià)特征基元可拓集研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2005,35(9):203-208.

[17]楊春燕.我國管理可拓工程研究進(jìn)展[J].中國科學(xué)基金,2010,24(1):13-16.

[18]李興森,張浩瀾,陳艷.大數(shù)據(jù)及其應(yīng)用的矛盾問題與可拓學(xué)[J].科技促進(jìn)發(fā)展,2014,(1):45-51.

[19]崔春生.推薦系統(tǒng)中顯式評(píng)分輸入的用戶聚類方法研究[J].計(jì)算機(jī)應(yīng)用研究,2011,28(8):2856-2868.

[20]董吉文,曲朝霞,周勁.一種基于物元分析關(guān)聯(lián)度的聚類分析方法[J].濟(jì)南大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,(2):175-177.

[21]陶雪嬌,胡曉峰,劉洋.大數(shù)據(jù)研究綜述[J].系統(tǒng)仿真學(xué)報(bào),2013,(S1):142-146.

[22]崔春生,李群,孫大偉.大數(shù)據(jù)時(shí)代人才的培養(yǎng)、需求與貢獻(xiàn)[R].2014年中國人才發(fā)展報(bào)告(中國人才藍(lán)皮書),2014.

[23]樓巍.面向大數(shù)據(jù)的高維數(shù)據(jù)挖掘技術(shù)研究[D].上海:上海大學(xué),2013.