一類(lèi)帶有模糊算子的滿(mǎn)意度依賴(lài)關(guān)聯(lián)算法

[摘要] 隨著經(jīng)濟(jì)的迅猛發(fā)展，市場(chǎng)信息化和現(xiàn)代化程度的不斷提高，信息不確定性的影響越來(lái)越大，在數(shù)據(jù)挖掘中引入模糊邏輯，以及部分不確定性的表達(dá)很有必要。本文在引入相似度算子等相關(guān)概念，以及對(duì)原有的算法進(jìn)行了相應(yīng)的模糊改進(jìn)后，使得原有的帶有滿(mǎn)意度的依賴(lài)關(guān)聯(lián)在保留更多有用的初始信息基礎(chǔ)上有了更進(jìn)一步的修正。

[關(guān)鍵詞] 數(shù)據(jù)挖掘 關(guān)聯(lián)規(guī)則 模糊邏輯 相似度算子

隨著經(jīng)濟(jì)的迅猛發(fā)展，企業(yè)信息化的程度不斷得以提高，于是，信息不確定性的影響越來(lái)越大。數(shù)據(jù)挖掘引起了信息產(chǎn)業(yè)界的極大關(guān)注，其主要原因是存在大量數(shù)據(jù)，可以廣泛使用，尤其是在有關(guān)互聯(lián)網(wǎng)的海量數(shù)據(jù)搜索，并且迫切需要將這些數(shù)據(jù)轉(zhuǎn)換成有用的信息和知識(shí)。獲取的信息和知識(shí)可以廣泛用于各種應(yīng)用，包括商務(wù)管理、生產(chǎn)控制、市場(chǎng)分析、工程設(shè)計(jì)和科學(xué)探索等。數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取或挖掘知識(shí)，而數(shù)據(jù)挖掘技術(shù)則是對(duì)一些相關(guān)技術(shù)的集成，所以數(shù)據(jù)挖掘的方法也都是基于機(jī)器學(xué)習(xí)、模式識(shí)別，以及統(tǒng)計(jì)方法等來(lái)實(shí)現(xiàn)的。當(dāng)然，不同的技術(shù)下的方法得到的知識(shí)的表達(dá)形式可能是不同的。從知識(shí)的表達(dá)形式上，可以將數(shù)據(jù)挖掘分為分類(lèi)、回歸、關(guān)聯(lián)、聚類(lèi)、概要、發(fā)現(xiàn)變化和偏差等等，其中，關(guān)聯(lián)因?yàn)槠鋸V泛適用性，以及方法的成熟性，成為了最重要的也是應(yīng)用最為廣泛的數(shù)據(jù)挖掘方法之一，于是，基于關(guān)聯(lián)規(guī)則的研究是始終受到關(guān)注。

自從關(guān)聯(lián)規(guī)則的概念由Agrawal等人提出，關(guān)聯(lián)規(guī)則在眾多領(lǐng)域的應(yīng)用，如金融、證券市場(chǎng)、氣象學(xué)、營(yíng)銷(xiāo)、醫(yī)學(xué)、制造業(yè)、電子商務(wù)等等促使人們對(duì)于關(guān)聯(lián)規(guī)則的挖掘有了大量的研究。此外，Agrawal及Srikant等人研究發(fā)現(xiàn)關(guān)聯(lián)規(guī)則是利用Apriori這一典型的有關(guān)于挖掘的運(yùn)算法則來(lái)運(yùn)算的最基本的挖掘方法。除了關(guān)聯(lián)規(guī)則之外，另一種普遍關(guān)注的關(guān)聯(lián)是功能依賴(lài)，它是另外一種興趣度的關(guān)聯(lián)。功能依賴(lài)可以從邏輯上在原先設(shè)計(jì)好的關(guān)系上面假設(shè)或者構(gòu)造。同時(shí)，在將數(shù)據(jù)挖掘看成是一種反轉(zhuǎn)工程的情況下，功能依賴(lài)的發(fā)現(xiàn)受到了很高的重視。模式關(guān)聯(lián)是第三種關(guān)聯(lián)方式。真正的應(yīng)用軟件中遇到時(shí)間序列模式一般會(huì)有如下幾種情況：生產(chǎn)、銷(xiāo)售、經(jīng)濟(jì)學(xué)，以及股票數(shù)據(jù)。由于時(shí)間序列反映了在連續(xù)的因素如時(shí)間中的數(shù)據(jù)變化的演變過(guò)程，所以發(fā)現(xiàn)時(shí)間序列中的關(guān)系有比較特殊的作用。通常時(shí)間序列模式會(huì)有很多方式的彼此相互關(guān)聯(lián)。

通常在商務(wù)智能或人工智能的知識(shí)發(fā)現(xiàn)中引入不確定性的描述和表達(dá)源自于兩個(gè)方面的需要:一個(gè)是在知識(shí)表達(dá)和發(fā)現(xiàn)中的內(nèi)在不確定性的需要;另一個(gè)是在復(fù)雜決策過(guò)程中經(jīng)常遇到的對(duì)抽象化概念，以及具有自然語(yǔ)言表達(dá)的需要。這兩個(gè)方面的問(wèn)題使得在知識(shí)發(fā)現(xiàn)中引入模糊邏輯，以及部分不確定性的表達(dá)很有必要。

一、滿(mǎn)意度依賴(lài)關(guān)聯(lián)

依賴(lài)關(guān)聯(lián)作為關(guān)系數(shù)據(jù)庫(kù)理論和應(yīng)用中的一個(gè)重要概念，在知識(shí)發(fā)現(xiàn)領(lǐng)域的研究非常不夠，首先，它對(duì)普遍存在于數(shù)據(jù)庫(kù)中的噪音不能很好地在挖掘模型中進(jìn)行處理，從而導(dǎo)致大量有價(jià)值的信息的丟失；其次，傳統(tǒng)依賴(lài)關(guān)聯(lián)概念表達(dá)的是一種完全的知識(shí)，也就是說(shuō)對(duì)于整個(gè)關(guān)系都成立的，但是除了諸如此類(lèi)的強(qiáng)知識(shí)之外，有一些在部分程度上成立的知識(shí)也是存在并且有意義的。因此一種新的依賴(lài)關(guān)聯(lián)的概念——帶有滿(mǎn)意度的依賴(lài)關(guān)聯(lián)就產(chǎn)生了。簡(jiǎn)而言之，它是通過(guò)概率估計(jì)來(lái)描述某個(gè)依賴(lài)關(guān)聯(lián)在數(shù)據(jù)庫(kù)中成立的程度的。一方面，它能夠以滿(mǎn)意度來(lái)描述某個(gè)依賴(lài)關(guān)聯(lián)在該數(shù)據(jù)庫(kù)中成立的程度，從而能夠容納噪音所帶來(lái)的問(wèn)題。另一方面，它能夠量化地表達(dá)部分成立的知識(shí)，并且，由于它通過(guò)簡(jiǎn)單加總來(lái)描述滿(mǎn)意度的測(cè)度，從而得到的結(jié)果更具有直觀(guān)性和易于解釋性。這個(gè)新的概念有一系列的相關(guān)定義及性質(zhì)的證明。在相關(guān)的定義下，關(guān)系T不再是完全支持或者只完全不支持某個(gè)依賴(lài)關(guān)聯(lián)，而是以某個(gè)度——滿(mǎn)意度——來(lái)支持。具體來(lái)說(shuō)，TRUTHT(A→B)就稱(chēng)為依賴(lài)關(guān)聯(lián)A→B的滿(mǎn)意度，它的含義為關(guān)系T支持依賴(lài)關(guān)聯(lián)的程度。總得來(lái)說(shuō)，該概念可以容納噪音并且能夠?qū)⒉糠种R(shí)量化進(jìn)行表達(dá)和評(píng)價(jià)，而且和在數(shù)據(jù)庫(kù)中挖掘傳統(tǒng)關(guān)聯(lián)規(guī)則相比，帶有滿(mǎn)意度的依賴(lài)關(guān)聯(lián)具有更加好的理論和數(shù)學(xué)性質(zhì)，也具有更容易理解的語(yǔ)義和更重要的價(jià)值。

二、相似度算子的選擇與實(shí)現(xiàn)

由于很多實(shí)際的數(shù)據(jù)庫(kù)中的數(shù)據(jù)是龐雜而凌亂的，基本上沒(méi)有什么數(shù)值完全一致的數(shù)據(jù)，而根據(jù)原有的帶有滿(mǎn)意度的依賴(lài)關(guān)聯(lián)的定義“如果ti(A)≠tj(A)，則TRUTH(ti，tj)(A→B)=1”，那么基本上所有的數(shù)據(jù)都是可以相互依賴(lài)關(guān)聯(lián)的，這樣做出的結(jié)果是沒(méi)有任何意義的。所以，為了尋求數(shù)據(jù)在一定意義上的同一性，我們引入了相似度算子對(duì)數(shù)據(jù)庫(kù)中同一屬性的不同值進(jìn)行了相似度的計(jì)算，然后用相似度作為衡量標(biāo)準(zhǔn)對(duì)數(shù)據(jù)進(jìn)行進(jìn)一步的依賴(lài)關(guān)聯(lián)上的處理。

這里選擇e-t作為相似度的算子，其具體的實(shí)現(xiàn)方式是對(duì)同一屬性在不同時(shí)期的值做一個(gè)差的絕對(duì)值運(yùn)算，然后再對(duì)其進(jìn)行相似度的運(yùn)算。例如，在一個(gè)股票交易市場(chǎng)的數(shù)據(jù)庫(kù)中，現(xiàn)有兩只股票A、B，假設(shè)每只股票有三天的收盤(pán)價(jià)格a1、a2、a3，b1、b2、b3，不失一般性地，a1、a2、a3，b1、b2、b3每三個(gè)數(shù)互不相同，如果按照以往的依賴(lài)關(guān)聯(lián)的計(jì)算方式，那么一定可以得到A→B是成立的，而這種結(jié)論是沒(méi)有意義的，所以，現(xiàn)在要改用相似度算子的方式來(lái)計(jì)算A與B之間的依賴(lài)關(guān)聯(lián)程度:先算出a1、a2之間的差的絕對(duì)值d12，然后計(jì)算得出α12=e-d12，同理得到α13，α23;先算出b1、b2之間的差的絕對(duì)值s12，然后計(jì)算得出β12=e-s12，同理得到β13，β23。

在計(jì)算完了相似度之后，就要對(duì)計(jì)算所得出的α12、α13、α23，以及β12、β13、β23進(jìn)行模糊關(guān)聯(lián)運(yùn)算來(lái)得出A與B的依賴(lài)關(guān)聯(lián)程度。用于計(jì)算模糊關(guān)聯(lián)的算子有很多，像S算子，G算子，KDL算子，DA算子等等，我們挑選了其中的KD算子來(lái)使用。KD模糊關(guān)聯(lián)算子的公式為KD(a，b)=max(1-a，b)。也就是說(shuō)我們可以算出k12=KD(α12，β12)=max(1-α12，β12)，同理可得k13及k23，當(dāng)k12即依賴(lài)關(guān)聯(lián)A→B的滿(mǎn)意度不小于預(yù)先規(guī)定的最小支持度θ的時(shí)候，則認(rèn)為（t1，t2）(A→B)的值為有意義的。最后，根據(jù)這幾個(gè)值來(lái)計(jì)算最后的TRUTHT（A→B）的值。另外，需要注意的是，如果有多個(gè)前件的話(huà)，那么每次取其中最小的一個(gè)來(lái)進(jìn)行KD運(yùn)算，同理，有多個(gè)后件也照此處理。下面給出相關(guān)規(guī)則的定義及其擴(kuò)展：

1.設(shè)R（I1，I2，…，Im）為一個(gè)在論域D1，D2，…，Dm上的關(guān)系模式，其中Ik的論域?yàn)镈k。若A和B分別為屬性集合I={I1，I2，…，Im}的子集，即A，B包含于I，且T為R的一個(gè)關(guān)系，即T 包含于D1×D2×…×Dm，其中ti，tj∈T，且ti≠tj。則我們稱(chēng)，對(duì)于一個(gè)事物記錄對(duì)（ti，tj），B依賴(lài)關(guān)聯(lián)于A(yíng)，表示為（ti，tj）(A→B)，假設(shè)TRUTH（ti，tj）(A→B)=kij。

（1）如果ti(A)與tj(A)相似度很高，并且ti(B)與tj(B)相似度也很高，也就是說(shuō)αij與βij都不小于θ，那么，kij一定不小于θ，則（ti，tj）(A→B)有意義，取TRUTH（ti，tj）(A→B)=kij。

（2）如果ti(A)與tj(A)相似度很高，并且ti(B)與tj(B)相似度不高，也就是說(shuō)αij不小于θ，可是βij小于θ，那么（a）如果θ不大于0.5，那么kij一定不小于θ，則（ti，tj）(A→B)有意義，取TRUTH（ti，tj）(A→B)=kij。（b）如果θ大于0.5，那么kij一定小于θ，則（ti，tj）(A→B)沒(méi)有意義，但仍取TRUTH（ti，tj）(A→B)=kij。

（3）如果ti(A)與tj(A)相似度不高，也就是說(shuō)αij小于θ，那么（a）如果αij<0.5，那么kij一定不小于θ，則（ti，tj）(A→B)有意義，取TRUTH（ti，tj）(A→B)=kij。（b）如果αij<0.5，那么如果可是βij不小于θ，則（ti，tj）(A→B)有意義，取TRUTH（ti，tj）(A→B)=kij，反之則（ti，tj）(A→B)沒(méi)有意義，但仍取TRUTH（ti，tj）(A→B)=kij。

2.給定T(有n條事務(wù)記錄)和I，且A包含于I，B包含于I。設(shè)T（A→B）表示為，對(duì)于關(guān)系T上，B依賴(lài)關(guān)聯(lián)于A(yíng)。則T支持依賴(lài)關(guān)聯(lián)A→B的度σ表示為T(mén)RUTHT(A→B）。

3.給定一個(gè)R(I1，I2，…，Im)上的關(guān)系T(T包含n條事務(wù)記錄)，并且給定閾值ρ（0≤ρ≤1），A，B包含于I，如果A→B的滿(mǎn)意度，即TRUTHT(A→B）≥ρ，則我們將A→B稱(chēng)為是一個(gè)合格的依賴(lài)關(guān)聯(lián)。

在引入了相關(guān)概念及對(duì)原有的算法進(jìn)行了相應(yīng)的模糊改進(jìn)后，原有的帶有滿(mǎn)意度的依賴(lài)關(guān)聯(lián)就有了更進(jìn)一步的修正，從而較以前可以保留更多有用的信息，并且，需要說(shuō)明的是，這種帶有模糊的滿(mǎn)意度依賴(lài)關(guān)聯(lián)算法同樣也適用于原來(lái)的同一屬性的值基本相同的情況。也就是說(shuō)，這種帶有模糊算子的滿(mǎn)意度依賴(lài)關(guān)聯(lián)算法更具有一般性。

三、結(jié)束語(yǔ)

由于模糊關(guān)聯(lián)挖掘具有對(duì)自然語(yǔ)言的表達(dá)和不確定知識(shí)的處理上的優(yōu)越性，它無(wú)論是對(duì)于研究人員還是對(duì)于實(shí)際應(yīng)用者來(lái)說(shuō)都是一個(gè)十分有前途的領(lǐng)域。另外對(duì)于理論研究領(lǐng)域，一些應(yīng)用軟件和系統(tǒng)平臺(tái)已經(jīng)被開(kāi)發(fā)出來(lái)甚至應(yīng)用到實(shí)際中了。大量的理論研究包括知識(shí)發(fā)現(xiàn)，不確定性模型、工具、計(jì)算復(fù)雜度和算法改進(jìn)在近些年來(lái)不斷地出現(xiàn)，而日益增加的豐富的應(yīng)用和執(zhí)行軟件又促使著發(fā)展不斷地前進(jìn)。更具體地來(lái)說(shuō)，模糊關(guān)聯(lián)規(guī)則是大家的研究重點(diǎn)，其中，為了規(guī)則表達(dá)而進(jìn)行的分割或者聚類(lèi)連續(xù)賦值數(shù)據(jù)、語(yǔ)義摘要、語(yǔ)言學(xué)修正和邏輯牽連等得到了大量的關(guān)注。另外，有越來(lái)越多的研究表明了有不確定性關(guān)系的數(shù)據(jù)之間是存在著依賴(lài)的。最后，模式關(guān)聯(lián)的發(fā)現(xiàn)被看作是一個(gè)在未來(lái)很有發(fā)展前途的研究領(lǐng)域，時(shí)間序列數(shù)據(jù)和順序行為很值得去研究。

參考文獻(xiàn):

[1]Jiawei Han，Micheline Kamber，《數(shù)據(jù)挖掘概念與技術(shù)》，機(jī)械工業(yè)出版社

[2]C. Giannella， C. M. Wyss， Finding Minimal Keys in a Relation Instance， http://citeseer.nj.nec.com/