基于可拓學理論的高維大數據相似性研究

基于可拓學理論的高維大數據相似性研究

袁瑞萍，師鳴若

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

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

關鍵詞：大數據；高維數據；可拓學；相似性

收稿日期：2015-06-04

基金項目：北京市教委科技計劃面上項目(KM201510037001)；智能物流系統北京市重點實驗室(NO:BZ0211)；北京市屬高等學校創新團隊建設提升計劃項目(項目號:IDHT20130517)

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

中圖分類號：TP311.1文章標識碼：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月，《科學》雜志發表文章《Big Data: Science in the Petabyte Era》,“大數據”一詞正式走入公眾視線，并開始傳播。其實，“大數據”一詞早在上個世紀80年代由美國人提出來[1,2]。2011年6月，IDC研究報告《從混沌中提取價值》中三個基本論斷構成了大數據的理論基礎，人們對大數據的關注程度日益上升。據統計，Google“大數據”搜索量自2011年6月起呈直線上升趨勢，大數據時代的到來毋庸置疑[3]。根據國際數據資訊(IDC)公司監測，全球數據量大約每兩年翻一番，預計到 2020 年，全球將擁有 35ZB 的數據量，并且 85%以上的數據以非結構化或半結構化的形式存在。“大數據”2011年一路走紅，2012年后更加閃耀，成為業界當之無愧的焦點，很多國內外的學術會議均以“大數據”冠名。伴隨新型SNS 網絡的發展、視頻流量的猛增及圖片分享需求的涌現，人們迷失于茫茫的數據海洋中，如何從大數據中挖掘出有用的信息成為關注的焦點，其中高維大數據因其復雜性而備受關注，并成為數據領域中的研究熱點和前沿問題。

1高維大數據相似性研究綜述

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

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

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

以上研究分析表明，在高維數據處理的研究領域，尤其是基于相似性度量的聚類分析中，學者們致力于算法的改進和優化，應用于不同數據處理會得到不同的結果，但是到底哪種算法更適合處理高維數據尚無定論。因此，走出原有的研究路徑，尋找新的突破口是實現算法優化的一個思路。

2可拓學的引入

可拓學[12]是用來解決矛盾問題的一種方法，采用形式化的模型，實現了定性與定量的結合。高維數據處理中大量非結構化數據的客觀存在，為可拓學的應用奠定了基礎。

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

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

3基于可拓學理論的高維大數據相似度計算過程

可拓學方法因其獨有的形象化表示方法，在對定性和定量問題的研究中具有一定的優勢，尤其在定性研究方面更具特色。采用該方法進行高維數據相似性計算基于以下幾個環節。

(1)采用基元表示系統中的研究對象，其中涵蓋定性數據和定量數據。

如何定義相似性計算公式是問題的重點，但對高維數據來說，用形式化的語言描述高維數據是問題的起點。基元是可拓學的邏輯細胞[18,19]，也是采用可拓學研究問題的基礎。

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

(1)

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

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

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

vji(j=1,2,…,m;i=1,2,…,n)代表高維數據系統中屬性cj的取值，這個取值可以是定量的數據，也可以是定性數據，可以是結構化數據，也可以是非結構化數據。

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

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

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

(4)權重的確定。采用函數Hsim(X,Y)計算兩個對象之間的相似性需要定義屬性的權重。常用的權重確定方法有相對比較法、專家打分法和層次分析法等，也可以采用可拓權重法，基于各個待評對象關于各評價指標的取值，借助關聯函數獲得。

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

(7)計算高維數據的相似度，進而獲得聚類結果。基于已有的文獻可以定義兩個高維數據的相似性為：

(2)

4案例應用

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

表1　監測點數據　單位：mg/L -1

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

圖1各個檢測點的物元表示

(2)該數據集中屬性C6的取值范圍為定性數據，分別定義0,0.5,1，對應“無”、“一般”、“有”三項取值。

(3)在數據指標中，監測點的位置屬于冗余數據，不需要考慮，可以剔除。

(4)獲取各個指標的權重，如表1最后一行所示。

(5)根據各個指標的最優值和最劣值獲取離差度，如表1倒數第二行所示。

(6)由于案例中M2，M7，M10的部分數據缺失，可以補齊，不難發現屬性C6的取值與監測點的位置具有一定的對應關系，因此可以定義v6,2=0,v6,7=0,v6,10=0.5。

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

表2　相似度計算結果

5結論

高維大數據的相似性計算是數據挖掘領域的研究重點，本文在分析高維大數據相似性計算難點基礎上，提出采用可拓的方法解決其中的矛盾問題。在基元表示高維大數據的基礎上，借助數據轉換、數據篩選、權重的確定、數據預處理等技術實現了數據之間的相似性計算，并基于水污染常規分析數據進行了算法驗證。該方法在高維數據的表示方面具有一定的優勢，尤其是在定性數據表示方面。其次，該方法借助于合理的相似度計算公式可以得到數據之間的相似性度量，進而為數據的聚類分析奠定了基礎。論文提出的方法對高維數據的處理具有一定的理論價值，同時也為可拓學的研究拓展了應用空間。

參考文獻：

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

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

[3]楊風召.高維數據挖掘中若干關鍵問題的研究[D].上海:復旦大學,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]王曉陽,張洪淵,沈良忠,池萬樂.基于相似性度量的高維數據聚類算法研究[J].計算機技術與發展,2013,(5):30-33.

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

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

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

[12]蔡文.可拓集合和不相容問題[J].科學探索學報,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]楊春燕.可拓學的重要科學問題及其關鍵點[J].哈爾濱工業大學學報,2006,38(7):1087-1090.

[16]楊春燕.多評價特征基元可拓集研究[J].數學的實踐與認識,2005,35(9):203-208.

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

[18]李興森,張浩瀾,陳艷.大數據及其應用的矛盾問題與可拓學[J].科技促進發展,2014,(1):45-51.

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

[20]董吉文,曲朝霞,周勁.一種基于物元分析關聯度的聚類分析方法[J].濟南大學學報(自然科學版),2005,(2):175-177.

[21]陶雪嬌,胡曉峰,劉洋.大數據研究綜述[J].系統仿真學報,2013,(S1):142-146.

[22]崔春生,李群,孫大偉.大數據時代人才的培養、需求與貢獻[R].2014年中國人才發展報告(中國人才藍皮書),2014.

[23]樓巍.面向大數據的高維數據挖掘技術研究[D].上海:上海大學,2013.