基于社會(huì)計(jì)算的大數(shù)據(jù)集關(guān)聯(lián)規(guī)則的研究

馬憲敏

(黑龍江外國(guó)語(yǔ)學(xué)院 信息工程系， 哈爾濱 150025)

0 引言

在社會(huì)計(jì)算方面，需要提供認(rèn)為最適合用戶(hù)當(dāng)前場(chǎng)景的某種服務(wù)[1]。本文研究從大量用戶(hù)數(shù)據(jù)中提取出規(guī)則。近年來(lái)，社會(huì)計(jì)算受到廣泛應(yīng)用，包括醫(yī)療保健系統(tǒng)和智能車(chē)輛系統(tǒng)均是這方面的應(yīng)用典范。實(shí)施過(guò)程中，關(guān)鍵一點(diǎn)在于從大數(shù)據(jù)中準(zhǔn)確、快速地提取有用規(guī)則，并高效地處理用戶(hù)所處環(huán)境以便為用戶(hù)提供最好的服務(wù)[2]。

實(shí)踐中，社會(huì)計(jì)算系統(tǒng)往往需要滿足實(shí)時(shí)性。因此，重要的是通過(guò)應(yīng)用可簡(jiǎn)化關(guān)聯(lián)規(guī)則數(shù)目的方案減少運(yùn)算數(shù)據(jù)量；從而縮短數(shù)據(jù)處理時(shí)間。規(guī)則簡(jiǎn)化方案保證數(shù)據(jù)完整性和較高的時(shí)間效率，為現(xiàn)實(shí)環(huán)境中部署社會(huì)計(jì)算提供了關(guān)鍵因素[3]。

規(guī)格簡(jiǎn)化方案所適用的數(shù)據(jù)很特別地存在二進(jìn)制屬性。先后有人提出了利用數(shù)據(jù)二進(jìn)制屬性來(lái)挖掘關(guān)聯(lián)規(guī)則的各種算法，如直接散列，修剪，劃分法和動(dòng)態(tài)項(xiàng)目集計(jì)數(shù)法。這些方法普遍用來(lái)增強(qiáng)挖掘效果，減少數(shù)據(jù)庫(kù)掃描次數(shù)及降低候選數(shù)據(jù)集數(shù)目。此外，有人提出了利用屬性分類(lèi)或用戶(hù)屬性約束來(lái)挖掘廣義關(guān)聯(lián)規(guī)則的方法；通過(guò)借助于直方圖和樣本，找到不相關(guān)項(xiàng)目來(lái)挖掘負(fù)關(guān)聯(lián)規(guī)則的技術(shù)。對(duì)目標(biāo)數(shù)據(jù)的關(guān)聯(lián)性進(jìn)行分析所采用的基礎(chǔ)方法，其目的在于找出交易中頻繁出現(xiàn)的次數(shù)高于下限值的項(xiàng)目。由于所采用的數(shù)據(jù)結(jié)構(gòu)較簡(jiǎn)單，且結(jié)果存在確定性，故基于頻率的方法已得到廣泛應(yīng)用。但是，隨著項(xiàng)目數(shù)不斷增多，計(jì)算時(shí)間急速增加，提取不頻繁出現(xiàn)的數(shù)據(jù)規(guī)則方面的信息就變得困難[4-5]。

為克服已有算法對(duì)大數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘存在的弊端，本文提出以二進(jìn)制數(shù)字形式來(lái)表示數(shù)據(jù)集，對(duì)每個(gè)項(xiàng)目分配一個(gè)權(quán)重的WTabular算法。而且，利用奎因-麥克拉斯基算法[6]將邏輯函數(shù)簡(jiǎn)化成一個(gè)算法。本文算法可減少不必要的規(guī)則，改善關(guān)聯(lián)規(guī)則的挖掘效率。實(shí)驗(yàn)表明，無(wú)論是實(shí)用性和有效性還是規(guī)則簡(jiǎn)化率和處理時(shí)間，本文算法較APRIORI算法[7]和FP增長(zhǎng)算法[8]這兩種代表性算法均表現(xiàn)更佳。本文算法更適用于要求對(duì)大數(shù)據(jù)及時(shí)處理的社會(huì)計(jì)算領(lǐng)域。

1 相關(guān)研究工作

關(guān)聯(lián)規(guī)則是許多交易進(jìn)行累積后交易與數(shù)據(jù)庫(kù)之間關(guān)聯(lián)性挖掘過(guò)程的結(jié)果；通過(guò)統(tǒng)計(jì)方法可以找到存在關(guān)聯(lián)的項(xiàng)目之間的規(guī)則性。例如，它們之間存在關(guān)聯(lián)：“如果發(fā)生了事故，其他事故也會(huì)發(fā)生”。

通過(guò)搜集大量交易，一個(gè)項(xiàng)目集與另一個(gè)項(xiàng)目集之間的關(guān)聯(lián)可以提取到，表明它們之間存在相似性或一個(gè)模式。關(guān)聯(lián)規(guī)則的基本特性是：對(duì)于一組交易表示為I，如果非空集合X和Y滿足XI和YI，表明當(dāng)事故X發(fā)生后，事故Y也會(huì)發(fā)生。

規(guī)則的關(guān)聯(lián)等級(jí)由支持度和置信度來(lái)衡量。給定兩個(gè)數(shù)據(jù)集A和B，支持度S決定一條規(guī)則如何頻繁應(yīng)用到給定的數(shù)據(jù)集；置信度C決定隸屬于B的項(xiàng)目在A中出現(xiàn)的次數(shù)。這兩個(gè)指標(biāo)分別定義，如式(1)、(2)。

支持度：

(1)

置信度：

(2)

其中，σ(A)表示A含有的項(xiàng)目個(gè)數(shù)；支持度用來(lái)衡量關(guān)聯(lián)規(guī)則的有用性。一個(gè)非常低的“支持”的規(guī)則可以被判斷為偶爾發(fā)生，因此很難說(shuō)這條規(guī)則是有用的。置信度衡量一個(gè)規(guī)則推理的有效性，

可以說(shuō)給定規(guī)則A→B的可靠性越高，B在A中出現(xiàn)的概率就越大。因此，置信度界定B對(duì)A的條件概率。

從數(shù)據(jù)庫(kù)找到關(guān)聯(lián)規(guī)則分兩步：(1)尋找頻繁項(xiàng)；(2)生成關(guān)聯(lián)規(guī)則。

步驟1: 尋找頻繁項(xiàng)

頻繁項(xiàng)的最大數(shù)即項(xiàng)目集的冪集的大小。如果用戶(hù)感興趣的項(xiàng)目個(gè)數(shù)增加，項(xiàng)目集也呈幾何級(jí)數(shù)增長(zhǎng)。掃描數(shù)據(jù)庫(kù)，計(jì)算每個(gè)項(xiàng)目的支持度，從而找到頻繁項(xiàng)。

步驟2: 生成關(guān)聯(lián)規(guī)則

1.1 APRIORI算法

APRIORI算法應(yīng)用于候選項(xiàng)目。首先計(jì)算每個(gè)候選項(xiàng)目的頻率[8]；再根據(jù)數(shù)據(jù)集的最小支持度確定頻繁項(xiàng)；算法過(guò)程如下：

APRIORI算法

L1={Large-itemsets};

For(k=2;Lk-1=0;k++) do begin;

Ck=Apriori-gen(Lk-1);

For all transactionst∈Ddo begin;

Ct=subset(Ck,t);

For all candidatesc∈Ctdo

c.count++;

End

Lk={c∈Ct|c.count≥minsup};

End;

首先，生成包含了候選頻繁項(xiàng)C1；然后，對(duì)屬于C1的每個(gè)候選頻繁項(xiàng)的數(shù)據(jù)庫(kù)進(jìn)行掃描；計(jì)算每個(gè)元素的支持度值；接下來(lái)，選出支持度值滿足置信度要求的項(xiàng)目，作為一個(gè)集合L1；對(duì)兩個(gè)元素的各子集進(jìn)行上述操作；因?yàn)槊總€(gè)子集的元素個(gè)數(shù)會(huì)逐個(gè)增加，該過(guò)程需重復(fù)下去，直至不再有滿足要求的元素出現(xiàn)。

APRIORI算法生成由支持度大于最小置信度的項(xiàng)目構(gòu)成的候選項(xiàng)目集；從而縮小搜索空間。但是，隨著滿足最小支持度的項(xiàng)目數(shù)量增多，會(huì)有大量要求重復(fù)掃描數(shù)據(jù)庫(kù)的候選集產(chǎn)生。要生成候選集，所有項(xiàng)目集的冪集生成為候選集且候選集的每個(gè)元素的頻率通過(guò)掃描數(shù)據(jù)庫(kù)可得到。這么做會(huì)導(dǎo)致產(chǎn)生并不存在的項(xiàng)目，充當(dāng)交易數(shù)據(jù)里的候選集，浪費(fèi)時(shí)間和空間。

1.2 FP樹(shù)算法

另一個(gè)將與本文算法對(duì)比的FP增長(zhǎng)算法將含有頻繁項(xiàng)的數(shù)據(jù)庫(kù)壓縮成FP樹(shù)，生成條件模式樹(shù)，采用分而治之方法對(duì)與每個(gè)項(xiàng)目關(guān)聯(lián)的樹(shù)進(jìn)行挖掘，同時(shí)挖掘關(guān)聯(lián)規(guī)則。

給定一個(gè)FP樹(shù)R，按照支持度升序方式對(duì)R里的每個(gè)頻繁項(xiàng)構(gòu)建隨后的FP樹(shù)。[9]找出樹(shù)里頻繁項(xiàng)的所有出現(xiàn)次數(shù)；對(duì)每次出現(xiàn)，確定到達(dá)根部的路徑。記錄下每條路徑上項(xiàng)目的支持度值；將該路徑插入新構(gòu)建的樹(shù)Rx，其中X是對(duì)項(xiàng)目加以前綴P后獲取到的項(xiàng)目集。插入路徑時(shí)，Rx上每個(gè)節(jié)點(diǎn)的權(quán)重隨著項(xiàng)目-i的路徑支持度pathsup(i)而增長(zhǎng)；之后，遞歸調(diào)用FP增長(zhǎng)函數(shù)，Rx與X作為參數(shù)。當(dāng)輸入FP樹(shù)是單路徑時(shí)，存在一個(gè)基本情況：窮舉路徑子集的所有項(xiàng)目集來(lái)處理單路徑FP樹(shù)，以這樣的項(xiàng)目集的支持度值作為其中的最小頻繁項(xiàng)。

由于FP增長(zhǎng)算法不生成候選集，也不共享頻繁集，所以比APRIORI算法浪費(fèi)空間較小。它在速度方面也很出色，因?yàn)閿?shù)據(jù)庫(kù)掃描只進(jìn)行兩次。不過(guò)，F(xiàn)P增長(zhǎng)算法要求對(duì)樹(shù)結(jié)構(gòu)進(jìn)行壓縮以對(duì)關(guān)聯(lián)規(guī)則進(jìn)行快速挖掘，導(dǎo)致新數(shù)據(jù)添加困難。

1.3 奎因-麥克拉斯基算法

奎因-麥克拉斯基算法使布爾函數(shù)最小化。功能上它與卡諾映射大同小異，只是其制表形式效率高，所以經(jīng)常作為作計(jì)算機(jī)算法。該算法采用一種確定性方式來(lái)檢查布爾函數(shù)是否達(dá)到極小形式。有時(shí)可稱(chēng)為制表法。此法分兩步：

1. 尋找函數(shù)的所有主蘊(yùn)含項(xiàng)

2. 從主蘊(yùn)含項(xiàng)圖表里，找到函數(shù)的必要主蘊(yùn)含項(xiàng)

例如，假設(shè)減少方程的功能如式(3)。

f(A,B,C,D)=∑(4,8,9,10,11,12,14,15)

(3)

通過(guò)對(duì)最小項(xiàng)求和，可以形成式(4)乘積和正準(zhǔn)表現(xiàn)式。

fA,B,C,D=A′BC′D′+AB′C′D′+AB′C′D+AB′CD′+AB′CD+ABC′D′+ABCD′+ABCD

(4)

式(4)不是最小的。為了使函數(shù)最小化，將所有評(píng)估成1的最小項(xiàng)首先以最小項(xiàng)形式按表格排列，然后與其他最小項(xiàng)合并。如果兩個(gè)項(xiàng)目相差只有一個(gè)單位數(shù)，用連接符“-”取代它，表明它無(wú)足輕重。

繼續(xù)操作直至不再有項(xiàng)目可以合并，至此創(chuàng)建主要的主蘊(yùn)含項(xiàng)表格。

2 本文研究方法

本文提出一種新的挖掘方法，它有效減少大數(shù)據(jù)的關(guān)聯(lián)規(guī)則數(shù)目，同時(shí)具有較高的置信度和支持度。從大規(guī)模數(shù)據(jù)庫(kù)的數(shù)據(jù)里找到置信度高的規(guī)則，是包括社會(huì)化計(jì)算在內(nèi)諸多領(lǐng)域里的一項(xiàng)非常重要的工作，其中主要涉及對(duì)大數(shù)據(jù)的高效處理問(wèn)題。因此，本文提出WTabular算法，它以二進(jìn)制數(shù)字形式來(lái)表現(xiàn)交易數(shù)據(jù)集；通過(guò)與奎因-麥克拉斯基法和權(quán)重分配法結(jié)合，提高了關(guān)聯(lián)規(guī)則的挖掘效率。

2.1 基本運(yùn)算

本文提出的WTabular算法以二進(jìn)制數(shù)字形式表達(dá)數(shù)據(jù)集以及將權(quán)重與奎因-麥克拉斯基法相結(jié)合來(lái)簡(jiǎn)化挖掘過(guò)程，有效改善了數(shù)據(jù)挖掘的效率。該過(guò)程由兩部分構(gòu)成：(1)預(yù)處理：分3步；(2)后處理：分4步。前3步預(yù)處理環(huán)節(jié)去除疊加或不必要的數(shù)據(jù)并將數(shù)據(jù)轉(zhuǎn)化為適合分析的格式；具體步驟如下：

步驟1：先行部分的規(guī)則由小到大依次按1進(jìn)行排列；

步驟2：從數(shù)據(jù)庫(kù)的規(guī)則里，找出先行部分之后部分的值為1的規(guī)則；

步驟3：計(jì)算步驟2找到的規(guī)則的權(quán)重；剔除權(quán)重值小于預(yù)設(shè)值的那些規(guī)則；

步驟4：通過(guò)預(yù)處理方式生成的數(shù)據(jù)相互比較，然后再進(jìn)行簡(jiǎn)化；

步驟5：通過(guò)比較數(shù)目1為i及i+1的項(xiàng)目將其進(jìn)行簡(jiǎn)化；

步驟6：重復(fù)步驟4和5步對(duì)初次簡(jiǎn)化的結(jié)果進(jìn)一步簡(jiǎn)化； 如果沒(méi)有更多的減少是可能的，就停止工作；

步驟7：刪除重疊的規(guī)則。

2.2 分配權(quán)重到關(guān)聯(lián)規(guī)則

隨機(jī)生成的數(shù)據(jù)集用來(lái)解釋文中算法，如表1所示。

表1 輸入數(shù)據(jù)集

S1-S4表示傳感器；根據(jù)給定規(guī)則，將它所獲取到的數(shù)據(jù)轉(zhuǎn)化為二進(jìn)制數(shù)據(jù)；F事件在二進(jìn)制數(shù)據(jù)里出現(xiàn)情況(1：出現(xiàn)；0：未出現(xiàn))，取決于S的值。

本文算法進(jìn)行預(yù)處理后對(duì)表2數(shù)據(jù)進(jìn)行挖掘得到的結(jié)果，如表2所示。

表2 預(yù)處理的數(shù)據(jù)值為1

利用表2里F值為1的行而形成的數(shù)據(jù)集；APRIORI概率PPij，PPij由表2的數(shù)據(jù)得到如表3所示。

表3 表2數(shù)據(jù)的先驗(yàn)概率

PPij表示Sj的APRIORI概率Di。APRIORI概率是傳感器值的百分比。例如，表2有7行，每一行都存在0值；所以S1的0值百分比計(jì)算為5/7=0.7；0.3是1值的百分比。同樣，S2的0值是3/7=0.4。

根據(jù)貝葉斯理論，將后驗(yàn)權(quán)重分配給表3的數(shù)據(jù)。由式(5)可得到Di的后驗(yàn)權(quán)重Wi。

(5)

在式(5)，n表示傳感器的數(shù)目；Wi是Di的平均后驗(yàn)概率。由式(5)得到的權(quán)重，如表4所示。

表4 表3數(shù)據(jù)的權(quán)重

因?yàn)槠錂?quán)重小于最小權(quán)重0.5，所以要?jiǎng)h除D3，才能保證關(guān)聯(lián)規(guī)則簡(jiǎn)化所需的置信度和支持度。

2.3 規(guī)則的簡(jiǎn)化

采用本文的WTabular算法對(duì)規(guī)則進(jìn)行簡(jiǎn)化。在移除權(quán)重低于最小權(quán)重的規(guī)則后得到的規(guī)則，如表5所示。

表5 簡(jiǎn)化后的規(guī)則

當(dāng)表5中，數(shù)據(jù)f=1時(shí)，應(yīng)用后處理環(huán)節(jié)步驟4的初次簡(jiǎn)化；初次簡(jiǎn)化后得到的結(jié)果，如表6所示。

表6 初次簡(jiǎn)化的結(jié)果

在初次簡(jiǎn)化之后，反復(fù)采用后處理環(huán)節(jié)的步驟5和步驟6直至不能簡(jiǎn)化。表7給出二次簡(jiǎn)化后的結(jié)果，如表7所示。

表7 二次簡(jiǎn)化后的結(jié)果

最后得到的關(guān)聯(lián)規(guī)則，如表8所示。

表8 最后關(guān)聯(lián)規(guī)則

2.4 關(guān)聯(lián)規(guī)則的評(píng)價(jià)

根據(jù)式(1)和式(2)定義的方程，假設(shè)存在規(guī)則，表7的{S4}→f，其支持度和置信度均為100%。利用APRIORI算法，可計(jì)算{S4}→f滿足表1最小支持度20%的支持度和置信度，分別是38%和87%。APRIORI算法和WTabular算法的簡(jiǎn)化率分別大約是69%和92%。由上述例子可知，本文提出的WTabular算法無(wú)論在支持度和置信度還是規(guī)則的簡(jiǎn)化率方面都要優(yōu)于APRIORI算法。

3 實(shí)驗(yàn)結(jié)果與討論

本文采取計(jì)算機(jī)模擬實(shí)驗(yàn)來(lái)評(píng)估本文算法的性能。實(shí)驗(yàn)采用的系統(tǒng)是INTER2.8Ghz酷睿2四核CPU，8GB RAM，32位Windows7；模擬代碼是Visual studio 2010的C++語(yǔ)言。

同時(shí)對(duì)APRIORI算法和FP增長(zhǎng)算法進(jìn)行評(píng)估；將它們與文中WTabular算法在數(shù)據(jù)規(guī)模不斷變化情況下對(duì)置信度、支持度、規(guī)則簡(jiǎn)化率和數(shù)據(jù)處理速度的表現(xiàn)進(jìn)行比較。

實(shí)驗(yàn)數(shù)據(jù)庫(kù)取自人體感知的數(shù)據(jù)，隨機(jī)創(chuàng)建而成，具有7個(gè)預(yù)處理和兩個(gè)后處理屬性。每個(gè)數(shù)據(jù)項(xiàng)以二進(jìn)制來(lái)表示，如果比閾值大,值就是1；否則為0。例如，如果權(quán)重正常，是0；否則是1。實(shí)驗(yàn)用到的數(shù)據(jù)集大小從10萬(wàn)逐漸擴(kuò)大到100萬(wàn)。

選擇規(guī)則{S5}→f1時(shí)，數(shù)據(jù)規(guī)模不同情況下三種算法的支持度和置信度比較結(jié)果，如圖2、圖3所示。

圖2 三種算法的支持度比較結(jié)果

圖3 三種算法的置信度比較結(jié)果

由圖2可知文中算法的支持度和置信度均優(yōu)于另兩種算法；而且，本文算法的規(guī)則簡(jiǎn)化率最高，如圖4所示。

圖4 規(guī)則簡(jiǎn)化率比較

所以，本文算法適合于通過(guò)快速對(duì)比最小數(shù)據(jù)，并且又保持較高置信度來(lái)提供準(zhǔn)確服務(wù)社會(huì)化計(jì)算領(lǐng)域。

不同數(shù)據(jù)規(guī)模情況下規(guī)則挖掘次數(shù)的對(duì)比結(jié)果，如圖5所示。

當(dāng)數(shù)據(jù)相對(duì)較小在50萬(wàn)以下時(shí)，文中算法用時(shí)比FP增長(zhǎng)算法稍長(zhǎng)；但對(duì)更大規(guī)模的數(shù)據(jù)運(yùn)算更快。所以我們認(rèn)為

文中算法更適合用來(lái)處理大數(shù)據(jù)。

圖5 數(shù)據(jù)處理時(shí)間比較

4 總結(jié)

對(duì)給定數(shù)據(jù)集的關(guān)聯(lián)規(guī)則進(jìn)行簡(jiǎn)化是處理大規(guī)模數(shù)據(jù)的社會(huì)化計(jì)算領(lǐng)域一個(gè)非常重要的問(wèn)題。目前，已有許多研究提出利用屬性分類(lèi)學(xué)和負(fù)關(guān)聯(lián)規(guī)則的做法來(lái)有效簡(jiǎn)化數(shù)據(jù)并找出關(guān)聯(lián)規(guī)則。本文提出WTabular算法是通過(guò)去除不滿足最小權(quán)重的數(shù)據(jù)并利用奎因-麥克拉斯基簡(jiǎn)化方法來(lái)達(dá)到對(duì)關(guān)聯(lián)規(guī)則的數(shù)目進(jìn)行刪減的目的。通過(guò)計(jì)算機(jī)模擬實(shí)驗(yàn)，發(fā)現(xiàn)本文算法的支持度、置信度、規(guī)則簡(jiǎn)化率和數(shù)據(jù)處理時(shí)間都較現(xiàn)有方法有所改善。

今后研究的重心在于該算法對(duì)流動(dòng)數(shù)據(jù)的實(shí)時(shí)處理方面。關(guān)注傳感器實(shí)時(shí)收集無(wú)格式的流數(shù)據(jù)。因此，有必要對(duì)關(guān)聯(lián)規(guī)則簡(jiǎn)化方面的方法論進(jìn)行研究，以便不需要將無(wú)格式數(shù)據(jù)轉(zhuǎn)化為二進(jìn)制數(shù)據(jù)而直接進(jìn)行處理。而且，還要考慮通過(guò)語(yǔ)義傳感器網(wǎng)提前建立傳感器之間的關(guān)聯(lián)來(lái)提高關(guān)聯(lián)規(guī)則簡(jiǎn)化的效果；并在多種領(lǐng)域和不同規(guī)模數(shù)據(jù)集方面對(duì)其進(jìn)行驗(yàn)證。

[1] 程學(xué)旗,靳小龍,王元卓,等. 大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J]. 軟件學(xué)報(bào),2014,09:1889-1908.

[2] 張峰. 基于網(wǎng)絡(luò)化數(shù)據(jù)分析的社會(huì)計(jì)算關(guān)鍵問(wèn)題研究[D].北京：北京郵電大學(xué),2014.

[3] 陳翔,徐佳,吳敏,等. 基于社會(huì)行為分析的群智感知數(shù)據(jù)收集研究[J].計(jì)算機(jī)應(yīng)用研究,2015,12:3534-3541.

[4] 陳愛(ài)東,劉國(guó)華,費(fèi)凡,等. 滿足均勻分布的不確定數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法[J]. 計(jì)算機(jī)研究與發(fā)展,2013,S1:186-195.

[5] 張璽. 數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究與改進(jìn)[D].北京郵電大學(xué),2015.

[6] Chiu H P, Tang Y T, Hsieh K L. Applying clusterbased fuzzy association rules mining framework into EC environment[J]. Applied Soft Computing, 2012,12(8): 2114-2122.

[7] Sun D, Teng S, Wei Zhang, Haibin Zhu. An Algorithm to Improve the Effectiveness of Apriori[C]∥International Conference on Cognitive Informatics, 2007:385-390.

[8] Zhang W, Liao H, Zhao N. Research on the FP Growth Algorithm about Association Rule Mining[J].International Seminar Business and Information Management, 2008:315-318.

[9] Nelson V P, Nagle H T. Digital Logic Circuit Analysis and Design[M]. Prentice Hall, 1995.