基于時態軟集的諾貝爾科學獎獲獎數據分析

馮 鋒，雒 靜，王 謙，肖昀澤

(1.西安郵電大學 理學院,陜西 西安 710121;2.西安郵電大學 通信與信息工程學院,陜西 西安 710121;3.北京郵電大學 經濟管理學院,北京 100876)

在“數據爆炸，知識匱乏”的大數據時代，海量的數據中存在很多的不確定性，這些不確定性信息直接影響人們在認知的過程中對現實問題的精確感知和預測。1999年，Molodtsov首次提出了經典軟集的概念，為處理不確定性問題提供了新的研究方向[1]。從不同角度刻畫同一復雜事物往往會得到其不同的側面，而這些不完備的側面都可以被視為對該復雜事物的近似描述，將這些近似描述綜合起來即可構成對該復雜事物較完備的刻畫。軟集理論作為一種從參數化角度刻畫不確定性問題的數學工具，引入對象論域和參數空間，能夠實現更為客觀且豐富的信息描述和處理，解決了概率論、模糊集[2]和粗糙集[3]等傳統方法中參數化不足的問題。在實際應用中，也能夠更靈活地處理復雜的不確定性問題，現已廣泛應用于數據挖掘、決策分析和代數學等諸多領域[4]。

數據挖掘旨在從數據庫中自動識別和提取出隱藏在其中的有價值信息，并將其表征為知識，進而提供輔助決策支持。關聯規則挖掘是數據挖掘中最早活躍的一個重要分支，其目的是從交易數據集中提取頻繁模式，并生成由頻繁模式組合的強關聯規則。Agrawal等[5-6]首次提出了關聯規則的概念，并給出了關聯規則挖掘問題的描述及具有代表性的Apriori算法。此后，還衍生了Apriori_LB[7]、XApriori[8]和基于權重的Apriori算法[9]等改進方法。Zaki等[10]提出了Eclat算法，這是一種基于垂直數據格式生成候選項集的深度優先算法，在挖掘過程中只需掃描一次數據庫。隨后也出現了Eclat的優化算法，如dEclat算法[11]和Eclat_opt算法[12]。FP-growth算法[13]是一種不產生候選項集的發現頻繁項集的挖掘方法，其依賴于基于樹的數據結構壓縮存儲有關頻繁項集的數據信息。Aryabarzan等提出了一種有效的數據結構NegNodeset[14]，并基于此結構設計了negFIN算法，該算法采用集合枚舉樹生成頻繁項集，并使用一種提升方法來修剪搜索空間。

傳統關聯規則挖掘是一種建立在事務數據集上的靜態挖掘方法，而時態關聯規則挖掘考慮到了傳統關聯規則挖掘所忽略的時間信息，旨在研究不同時段內有趣的關聯規則，能夠揭示潛藏在事物動態演進過程中的發展規律。Bettini等[15]研究了時間約束的事件結構粒度，發現了具有多粒度的頻繁事件模式。孟志青[16]系統地研究了時態型和時態粒度的相關理論概念，并給出了一類簡單頻繁事件模式發現的例子。Ye等[17]提出了一種能夠直接應用于時態數據集的關聯規則挖掘算法。歐陽為民等[18]在Apriori算法的基礎上進行擴展，提出了時間區間延展與歸并技術以及新的時態關聯規則發現算法，進一步推廣了關聯規則的應用。毛國君等[19]引入了時態區間代數，并給出了時態區間變量的時態交和時態并，提出了一種時態約束下的關聯規則挖掘算法，用于挖掘基于時態約束的頻繁項目序列集。臧國心等[20]研究了時態約束下各屬性狀態之間的周期時態關聯規則，給出了相關描述語義及其實現算法。Gharib 等[21]利用時間粒度分層的概念解決了時間序列數據庫動態關聯規則的挖掘問題，開發了一種增量時態關聯規則挖掘方法。Hong 等[22]提出了一個三階段挖掘框架，可在時態數據庫中找到具有分層粒度的時態關聯規則。

2011年，Herawan和Deris首次將軟集理論應用于交易數據集中的關聯規則挖掘[23]。Feng等修正了文獻[23]中的一些重要概念，并給出了參數陪集、參數類化軟集和實現集等定義，進一步完善并闡明了基于軟集的關聯規則挖掘方法的本質[24]。之后，Feng等[25]提出了以軟集理論和軟集邏輯公式為主要工具描述和挖掘關聯規則的新路線。此外，Feng等[26]給出了常規關聯規則和極大關聯規則挖掘中相關核心概念的統一數學表征，并提出了基于軟集邏輯公式的極大關聯規則挖掘算法。然而，某些項集在整個事務數據集的時間跨度中并不會頻繁出現，但其在某些特定時間段內卻是頻繁的。上述基于軟集的挖掘方法缺乏對項集時間因素的考慮，會忽略附加時間信息的項集關聯性，遺漏部分有趣的關聯規則。基于以上研究動機，擬借助時態軟集進一步增強關聯規則挖掘，嘗試設計一種融合時態軟集和Apriori算法的新方法提取促進型強時態關聯規則，挖掘潛藏在時態信息中的數據關聯性。此外，將所提算法應用于分析諾貝爾科學獎獲獎數據，進一步驗證方法的有效性。

1 軟集理論

軟集的本質是由給定參數集及其相應的集值映射構成的一個二元組，下面主要簡述軟集和時態軟集的相關概念。

1.1 軟集

設U為初始論域，與U內對象相關的全體參數構成集合E，稱為參數空間，將(U,E)稱為軟論域。U的全部子集構成的類為U的冪集，記作P(U)。

定義1[1]二元組Ω=(G,B)稱為U上的一個軟集，其中B?E是軟集Ω的參數集，G:B→P(U)是一個集值映射，稱為Ω的近似函數。

對任一參數b∈B，由近似函數確定的子集G(b)稱作軟集Ω的b-近似集。

定義2[24]設Ω=(G,B)為論域U上的軟集，u∈U，則稱CΩ(u)={b∈B:u∈G(b)}為u在Ω中的參數陪集。

1.2 時態軟集

定義3[27]設U為初始論域，有若干互不相交的時間段pi(i=1,2,…,n)構成集合P={p1,p2,…,pn}，則稱映射τ:U→P是U上的時態粒化映射。

2 關聯規則挖掘

關聯規則挖掘旨在從交易數據集中發現數據項集之間潛在的、有意義的聯系。一般而言，關聯規則的挖掘分為兩步：1) 找出所有滿足最小支持閾值的頻繁項集；2) 由頻繁項集產生滿足最小置信度閾值的強關聯規則。

下面主要介紹常規關聯規則和時態關聯規則，對比發現時態在關聯規則中的重要意義。

2.1 常規關聯規則

假設項域I={i1,i2,…,i|I|}是給定交易數據中的全體項目之集，每條交易記錄t都是I的一個非空子集。集合D={t1,t2,…,t|D|}包含所有交易記錄，稱為交易數據集。由I中若干項目構成的非空集合X稱為項集，包含k個項目的項集稱為k-項集。若X?t，則稱交易記錄t在D中支持項集X。

定義6[24]令D為一交易數據集，X為一項集，將D中由所有支持項集X的交易記錄構成的集合稱為項集X在D內的實現集，記作ΔD(X)，即

ΔD(X)={t∈D:X?t}

該實現集的基數|ΔD(X)|為項集X在D中的支持，記為SD(X)。給定兩個互不相交的非空項集X,Y?I，形式表達式X?Y稱為一個關聯規則，其中，項集X與項集Y分別是規則的前件和后件。

定義7[24]關聯規則X?Y在交易數據集D內的實現集ΔD(X?Y)定義為

ΔD(X?Y)=ΔD(X∪Y)

規則X?Y在D內的支持SD(X?Y)定義為

SD(X?Y)=SD(X∪Y)=card(ΔD(X?Y))

定義8[24]關聯規則X?Y在交易數據集D內的置信度CD(X?Y)定義為

若式中SD(X)=0，則CD(X?Y)=0。

定義9關聯規則X?Y在交易數據集D內的提升度LD(X?Y)定義為

若式中SD(X)·SD(Y)=0，則LD(X?Y)=0。

提升度可以衡量項集X和項集Y之間的相關性，當規則X?Y滿足LD(X?Y)>1時，則代表項集X的出現促進了項集Y的出現，二者呈正相關，稱規則X?Y為促進型關聯規則。此外，LD(X?Y)值越大，項集X的出現對項集Y的出現帶來的增益越高，二者相關性越強。為了在交易數據集中挖掘出有意義的規則，需要預先設置最小支持閾值a和最小置信度閾值b。當SD(X)≥a時，稱項集X為頻繁項集。而當規則X?Y滿足SD(X?Y)≥a且CD(X?Y)≥b時，可稱X?Y為強關聯規則。

2.2 時態關聯規則

部分項集在交易數據集的整個時間跨度中并不是頻繁的，但在某些時間段內這些項集往往會頻繁出現。因此，在不同時段內挖掘項集之間的關聯性，可能會有意外的發現。下面具體闡明時態關聯規則挖掘的相關基本概念。

令D為交易數據集，t∈D為交易記錄，P={p1,p2,…,p|P|}為若干互不相交的時間段之集。若滿足pt=τ(t)∈P，即交易記錄t發生在時段pt內，則稱pt是t的時段標記，并稱T=(D,τ,P)為一個時態交易數據集。

定義10[27]令T=(D,τ,P)為一個時態交易數據集，且t∈D，Q?P。若有項集X?t，τ(t)∈Q，則稱t在Q所轄時段內支持項集X。

定義11[27]令T=(D,τ,P)為一個時態交易數據集，Q?P，X為一項集，則T中項集X在Q所轄時段內的時態實現集為

定義12[27]時態關聯規則X?QY在時態交易數據集T中的時態實現集定義為

定義13[27]時態關聯規則X?QY在時態交易數據集T中的時態置信度定義為

定義14時態關聯規則X?QY在時態交易數據集T中的時態提升度定義為

3 基于時態軟集的關聯規則挖掘

下面結合時態軟集的相關理論和時態關聯規則的基本概念，研究時態關聯規則的軟集描述方法及相應挖掘算法。

3.1 時態關聯規則的軟集描述

設U為初始論域，u∈U，若干互不相交的時間段構成集合P={p1,p2,…,p|P|}，Q?P。

為了闡明上述概念在實際動態場景中的現實意義，下面以某醫院患者的病例信息為例作簡要論述。

例1假設某醫院提供了12位入院治療患者的相關信息，對這些病例數據進行統計，具體如表1所示。

表1 某醫院12位患者的確診信息

設入院治療的12名患者ui(i=1,2,…,12)構成了論域U，與其相關的屬性構成了參數空間E。令參數集B=A∪D?E，其中A={a1,a2,a3}為患者所患疾病，am(m=1,2,3)分別表示新冠肺炎、普通感冒和流行性感冒。D={d1,d2,…,d7}表示臨床癥狀，其中dn(n=1,2,…,7)分別代表發熱、咳嗽、咽痛、呼吸困難、乏力、腹瀉和頭痛。令P={p1,p2,p3}，其中pk(k=1,2,3)分別表示患者的確診時間為“2022年1月14日”“2022年1月16日”“2022年1月17日”。

由表1構建時態粒化映射τ:U→P，該映射基于時態信息給出論域U的劃分為

{τ-1(pk)|pk∈P}={{u1,u2,u3,u4,u5},
{u6,u7,u8},{u9,u10,u11,u12}}

在此基礎上，進一步構建U上的一個時態軟集Φ=(F,B,τ,P)，如表2所示。

表2 時態軟集Φ=(F,B,τ,P)的表格表示

令Q={p1,p2}?P，由定義5易見

τ-1(Q)={u1,u2,…,u8}

記時態軟集Φ的Q-片段軟集為ΦQ=(H,B)，計算可得

H(a1)={u1,u3,u4,u6,u8}
H(a2)={u2,u7}
H(a3)={u5}

此外，

H(d1)={u1,u2,u3,u4,u5,u6,u8}
H(d2)={u2,u4,u6,u7,u8}
H(d3)={u2,u3,u6,u7}
H(d4)={u4,u8}
H(d5)={u1,u4,u6,u8}
H(d6)=?
H(d7)={u5}

根據定義15，項集{a1}的Q-實現集為

考慮時態關聯規則{a1}?Q{d1,d4,d5}，由定義16，其在時態軟集Φ中的Q-實現集為

其Q-支持為

由定義17，該規則的Q-置信度為

根據定義18可得其Q-提升度為

取α=2和β=30%，則{a1}?Q{d1,d4,d5}是Q所轄時段中的促進型強時態關聯規則，其含義可解釋為2022年1月14日和16日這兩天，被確診為新冠肺炎的患者中有40%的人臨床癥狀表現為發熱、呼吸困難和乏力。

3.2 基于時態軟集的關聯規則挖掘算法

Agrawal等提出的Apriori算法[6]是一種經典的候選項集生成法算法，采用逐層搜索的方法篩選頻繁項集，進而由頻繁項集生成滿足置信度閾值的強關聯規則。下面，基于時態關聯規則的軟集描述，提出一種融合時態軟集和Apriori算法的促進型強時態關聯規則挖掘算法(Apriori-based Soft Promotive Temporal Association Rule Mining，Apriori-SPTARM)。

Apriori-SPTARM算法以時態交易數據集T=(D,τ,P)、集合Q?P、最小時態支持α∈N*和最小時態置信度β∈(0,1]作為輸入，其輸出為所有促進型強時態關聯規則構成的集合SPTAR(T,Q,α,β)。算法的具體步驟如下。

步驟4連接剪枝，生成(k+1)-候選項集，并保留所有(k+1)-頻繁項集。

4 實例驗證及結果分析

為了驗證Apriori-SPTARM算法的有效性，將其應用于諾貝爾科學獎的部分獲獎數據，分析特定時段內項集的關聯性，對比該方法與常規關聯規則挖掘方法的不同及其相較于傳統方法的優勢。

4.1 數據介紹

諾貝爾獎旨在表彰在化學、物理學、生理學或醫學、和平以及文學領域作出巨大貢獻的個人或組織，在國際上具有廣泛而深遠的影響。

在Kaggle網站中獲取有關諾貝爾獎獲獎者的數據集，該數據集共包含969條記錄，涉及1901年至2016年所有獲獎者的相關信息，包括獲獎者姓名、性別、獲獎年份、獎項類別和所屬國家等內容。為簡化問題，在此僅分析科學領域的獲獎數據，包括諾貝爾化學獎(Nobel Prize in Chemistry,NPC)、諾貝爾物理學獎(Nobel Prize in Physics,NPP)和諾貝爾生理學或醫學獎(Nobel Prize in Physiology or Medicine,NPPM)，并將諾貝爾科學獎簡稱為諾獎。對原始數據集進行數據清洗以達到分析需求，完成預處理后，人工添加2017年至2020年的獲獎信息，最終得到滿足條件的簡化數據337條，僅包含獲獎年份、獎項類別和所屬國家等3類屬性，可將每條記錄視為一條交易數據。預處理后的部分獲獎記錄如表3所示。

表3 預處理后的部分獲獎數據

4.2 數值實驗

實驗配置為Windows 10 x64操作系統、 Intel(R) Core(TM) i5-7200U CPU @ 2.50 GB處理器和8.00 GB內存，軟件為Matlab R2019a。

設論域U={u1,u2,…,u337}包含1901年—2020年頒發的所有諾貝爾科學獎，與諾獎相關的屬性構成U對應的參數空間E。取參數集B=C1∪C2，其中C1={c1,c2,…,c30}為諾獎的所屬國家，C2={NPC,NPP,NPPM}。根據表3中的數據，令P={p1,p2,p3,p4,p5,p6}，其中p1=[1901,1920]，p2=[1921,1940]，p3=[1941,1960]，p4=[1961,1980]，p5=[1981,2000]，p6=[2001,2020]，即主要研究P所轄的6個時段。時態粒化映射τ:U→P可誘導出U劃分為

{τ-1(pk)|pk∈P}=
{{u1,…,u52},…,{u278,…,u337}}

表4 時態軟集=(G,B,τ,P)中參數集的支持

利用表4構建模糊集

直觀地，基于預處理后得到表3中的簡化數據，模糊集F能夠描述每個國家的總體科學影響力，可將其稱為總體科學影響力模糊集(Overall Scientific Impact Fuzzy Set,OSIFS)。篩選出支持不小于12的8個主要國家，通過計算得到的隸屬度分別為

F(c1)=F(USA)=0.531
F(c2)=F(UK)=0.226
F(c3)=F(Germany)=0.125
F(c4)=F(France)=0.080
F(c5)=F(FRG)=0.056
F(c6)=F(Switzerland)=0.056
F(c7)=F(Japan)=0.047
F(c8)=F(Sweden)=0.045

根據總體科學影響力模糊集F的隸屬度降序，8個國家的排名為

c1c2c3c4c5=c6c7c8

由此可見，美國的總體科學影響力位居第一，英國次之，排名第三的是德國。根據隸屬度的相關含義，上述排名從諾貝爾科學獎的總體獲獎情況角度反映了各國的科學影響力。

圖1和圖2給出了8個主要國家在6個時段中的隸屬度計算結果，能夠從獲得諾貝爾科學獎的角度反映各國在不同時期科學影響力的變化情況。

圖2 國家cj(j=5,6,7,8)在各時段的隸屬度

根據隸屬度的相關含義，由圖1和圖2可以看出，1901—2020年美國的科學影響力穩步提升，與此同時，德國的科學影響力逐漸下降，而英國則長期處于穩態。進入21世紀后，日本在科技領域發展較快。

4.3 結果分析

基于已構建的時態軟集，利用Apriori-SPTARM算法提取6個時段內滿足閾值條件的促進型強時態關聯規則。將每個時段內的最小時態支持α設置為2和最小時態置信度β為70%，最終結果如表5所示。

表5 時態軟集=(G,B,τ,P)中的時態關聯規則

續表5 時態軟集=(G,B,τ,P)中的時態關聯規則

1) 考慮促進型強時態關聯規則R1，其p1-支持為

p1-置信度為

p1-提升度為

該規則的實際意義可解釋為1901—1920年間，授予荷蘭的諾貝爾科學獎均為物理學獎。

考慮規則R4，其p2-支持為

p2-置信度為

p2-提升度為

該規則的實際意義可解釋為1921—1940年間，授予荷蘭的諾貝爾科學獎均為生理學或醫學獎。

2) 考慮規則R9，其p4-支持為

p4-置信度為

p4-提升度為

該規則的實際意義為1961—1980年間，授予英國的諾貝爾生理學或醫學獎有71.43%是與美國共享的。

再考慮規則R23，其p5-支持為

p5-置信度為

p5-提升度為

該規則的實際意義可解釋為1981—2000年間，授予加拿大的諾貝爾化學獎均是與美國共享的。

對于規則R27，其p6-支持為

p6-置信度為

p6-提升度為

該規則的實際意義可解釋為2001—2020年間，授予日本的諾貝爾化學獎均是與美國共享的。

可以發現，從1961年至今，各國在科技創新上的合作共享逐步加強。

3) 令Q=P={p1,p2,…,p6}，設置Q所轄時段內的最小支持為12，最小置信度為70%。對于規則{NPPM}?Q{USA}，其Q-支持為

Q-置信度為

Q-提升度為

利用常規關聯規則挖掘方法，在1901至2020年整個時間范圍內，規則{NPPM}?Q{USA}是頻繁出現的但并不滿足置信度閾值，故該規則不可被識別為強關聯規則。而根據表5，規則R7({NPPM}?p4{USA})、規則R16({NPPM}?p5{USA})分別在時段p4和p5內被識別為促進型強時態關聯規則。

再考慮規則{NPC,UK}?Q{USA}，其Q-支持為

Q-置信度為

Q-提升度為

因此，在傳統挖掘技術中，該規則在1901—2020年整個時間范圍內不是頻繁的，更不可被識別為強規則。根據時態信息劃分數據集后，對于規則R28，即規則{NPC,UK}?p6{USA}，其p6-支持為

p6-置信度為

p6-提升度為

顯然，規則R28為p6時段內的促進型強時態關聯規則，而借助傳統方法這條規則不可被發現。

由上述分析可知，某些項集只在特定的時間段內是頻繁出現的，而在整個數據集的時間跨度上并非是頻繁的，借助傳統方法不能提取出由這些頻繁項集生成的規則。此外，部分頻繁出現的規則不能滿足最小置信度閾值，將數據集按時態粒度劃分后，這些規則可被識別為某些時段內的強規則。總之，基于時態軟集的關聯規則挖掘方法可以幫助發現一些在常規關聯規則提取中被忽略的強時態關聯規則。

5 結語

探索了時態軟集及其在時態關聯規則挖掘中的應用。首先，借助時態粒化映射引入了時態事務數據集的粒度結構，定義了時態軟集及其Q-片段軟集，進而構建描述和挖掘時態關聯規則的一種數學框架。其次，通過融合時態軟集和Apriori算法，設計了一種基于時態軟集的關聯規則挖掘算法Apriori-SPTARM，可用于提取促進型強時態關聯規則。最后，將所提方法應用于分析諾貝爾科學獎獲獎數據。數值實驗表明，在實際場景中數據會隨時間產生動態變化，傳統關聯規則挖掘忽略了時間因素的影響，容易遺漏某些特定時段內的強規則。Apriori-SPTARM算法彌補了傳統方法的缺陷。通過時態軟集引入數據集的時態粒度結構后，局部時段內由頻繁項集生成的規則可被識別為強時態關聯規則。這為解決時態關聯規則挖掘問題提供了新思路，同時也拓展了軟集在關聯規則挖掘中的應用。

值得注意的是，基于時態軟集的關聯規則挖掘中僅考慮了數據的時態粒化，且實例分析中采用了等時間間隔的劃分方式，具有一定的局限性。在今后的研究中，可考慮自適應時段劃分方法。此外，如何通過更具一般性的粒化方法劃分事務數據集也是值得探索的方向。