數據挖掘規則更新計算機

導語：數據挖掘規則更新計算機一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

一、數據庫中數據挖掘的基本定義及定理

在計算機數據庫的數學墨鏡建立過程中，可以將數據分為項目數據與事務數據，其中項目數據代表的是某種物品，而事務數據代表的是動作。假設項目集合為I={i1，i2，i3，……，im}，事務集合為D，T是集合D中的非空子集，代表某一組物品，此時必然滿足條件T∈I。下面將根據上述的數學因子來解釋數據庫中關聯規則如何被挖掘。

（一）關聯規則的內涵

以超市的銷售情況為例，我們假設數據庫內為超市門店的詳細交易數據，任意一次交易的事務t是商品集合I的子集，而關聯規則在事務集合D的支持度代表的是在子事務中同時包含了事務元素X與Y的概率；而置信度則是表示含有事務元素X的子事務中同時包含了事務元素Y的條件概率。根據超市門店銷售人員對消費者購買商品的市場了解需求，可以制定出相應的支持度與置信度的最小閾值，此時，利用數據庫即可找出符合銷售人員需要了解的商品之間的關聯規則。

（二）相關定義

定義1：若項目集X包含于T，那么我們可以認為事務T支持X；定義2：若事務集D中存在s%的事務支持項目集X，則稱項目集X的支持度為s%，并記為sup（X）；定義3：當支持度不小于數據庫用戶所定義的最小支持度閾值min_sup時，稱該項目集為繁榮項目集；當支持度小于數據庫用戶定義的最小支持度閾值min_sup時，稱該項目集為非繁榮項目集，其中項目集中的項目數量成為項目集的長度或維度；定義4：關聯規則可以用如下的蘊含形式表示：X→Y，X、Y∈I，并且X∩Y=Ф；定義5：若X→Y的關聯規則在事務集合D內支持度為s%，如果項目集（X∪Y）具有大小為s%的支持度，則存在support（X→Y）=P（X∪Y）。定義6：若X→Y的關聯規則在事務集合D內支持度為c%，如果事務集D內有c%的事務支持項目集（X∪Y），則存在confidence（X→Y）=P（X∪Y）/P（X）；定義7：設集合S全部由繁榮集構成，那么將S的否定邊界記做Bd-（S），符合如下等式：Bd（S）={X|XS，|x|=1}Y{X|任意Y屬于X，Y∈S，且XS}，也就是說集合S的否定邊界包含了所有本身不是繁榮集但子集全是繁榮集的事務集合，以及所有不是繁榮集的單個因子。

（三）相關定理

針對繁榮集與非繁榮集的關系，也存在以下定理：定理1：繁榮集一定是由繁榮集組成（子集概念）；定理2：非繁榮集的子集一定是非繁榮集。

二、挖掘關聯規則過程中的問題分析

關聯規則初次生成中的問題數據庫關聯規則的挖掘過程可分為兩部分，首先，需要找出一個繁榮項目集，該集合內所有因子的支持度均大于給定的支持度最低閾值；接下來一步，就是從此繁榮項目集中挖掘出關聯規則，當該規則滿足可信度條件conf≥min_conf時，該規則即為用戶所需規則。算法的挖掘效能高低主要由發掘符合支持度的繁榮項目集決定，第二步的算法主要為判別過程，耗費時間短，因此數據發掘關聯規則算法的研究焦點對準了繁榮項目集的發現。已有的算法主要是以重復多次掃描為主，不僅做法復雜，而且效率較低。在事務D數據庫中，參數可信度c和參數支持度s對關聯規則影響較大，一旦用戶定義的支持度s發生改變，繁榮集和信任度也會發生改變，最終引起關聯規則的變化。

三、更新關聯規則的算法

（一）關聯規則更新的數學建模

假設用戶原定義的支持度最小閾值為s，用戶新定義的支持度最小閾值為s’，那么更新關聯規則可以分為以下兩種情況：（1）當s’＞s時，由于前一次產生的繁榮集合為Apriori算法求得，那么根據該算法的定義可知，任意一個的繁榮集均存在一個標記屬性count記錄符合條件的事務元素個數，當新的支持度大于原有支持度時，可以使用原繁榮集的count值排除不符合新要求的繁榮集；（2）當s’＜s時，那么前一次產生的繁榮集是否能夠滿足新定義支持度閾值而成為繁榮集則需要因情況而定，甚至衍生新的繁榮集。根據上述的定理2不難發現，當用戶新給出的支持度閾值s’小于原有的s時，原來繁榮集中的所有元素組成的幾何仍舊為繁榮集，但是此時的S否定邊界Bd（S）中的部分元素則可能滿足條件而成為滿足新支持度的繁榮集元素。根據這個原理，在前一次已生成的關聯規則上，適當更新算法，即可避免重復的掃描過程，明顯降低重新計算時的工作量。當支持度最小閾值降低時，非繁榮集的否定邊界集合中部分元素可能轉換為繁榮集元素，當且僅當所有子集均為繁榮集時，父集才是繁榮集。所以在進行數據挖掘過程中，只有當否定邊界集元素滿足新輸入的支持度s’時，該元素才有可能從非繁榮集轉入繁榮集。接下來，需要使用可信度做進一步的驗證，而非繁榮集中的元素由于不滿足新支持度s’，因此不需要進行再次驗證。重新定義條件與求解內容：條件：數據庫DB中已存在某種關聯規則r，在該關聯規則存在時，S為滿足員支持度s的繁榮集，用戶改變可信度閾值為c''''，支持度閾值s’滿足s’＜s。求解：滿足c''''以及s''''的關聯規則r''''。

（二）算法程序

根據上述條件與求解內容，可知更新計算分析的重點在于怎樣在更短時間內求得新增如繁榮集的元素，也就是上文所提的關聯規則挖掘步驟的第一部分，繁榮集的求解。編輯更新算法如下：S={x|support(x)≥s，X是項目集合}Candidate=ΦL.Gets’(s’＜s)fromuser//用戶輸入s’ComputeTemp：={X∈Bd-(S)|Support(X，A.r)≥s’}//Temp表示從Bd-(s)中找到的滿足新支持度s’的元素集合B.S1=S，S=STempC.RepeatD.S2=S1TempE.Temp=Bd(S2)-[Bd-(S1)-temp]//Temp表示新衍生出的候選集F.S1=S2G.Candidate=CandidateTemp//candidate表示當前的新候選集全集H.UntilTemp=ΦputeNew：=(X∈Candidate{support(X，r)≥s’})//求出新增繁榮集J.Result=SNew//將新增繁榮集和原有繁榮集合并，得出符合新支持度s’的所有繁榮集K.Find_Rule（Result，c）更新后的算法首先也需要經過一次數據庫掃描來獲取部分的新產生繁榮集，并據已得的繁榮集求出推演所得的候選集。對候選集并不急于做驗證步驟，而是從衍生候選集中循環計算以求得更多的候選集，直到無法再產生候選集為止，退出循環。在挖掘新繁榮子集的過程中，需要兩次掃描數據庫，一次目的是搜索Bd(S)否定邊界集合中是否存在滿足用戶新輸入支持度s’的可疑元素，并利用這些可疑元素生成下一步的候選集；另一次掃描的目的是驗證既得的候選集中是否所有元素均滿足用戶新輸入支持度s’。

（三）改進算法的證明與更新

[Bd(S1)-Temp]集合包含了所有BD(S1)中非繁榮集合，該集合肯定為Bd(S1temp)的子集，因此不滿足用戶新的定義，可刪除。若要得出[Bd(S1)-Temp]真包含于Bd(S1YTemp)，則必有任意Z∈[Bd(S1)-Temp]，同時Z∈Bd(S1YTemp)。根據對否定邊界Bd（S）的定義可知，當五、|Z|=1，并Z∈Bd(S1)時，ZTemp又Z(S1)，ZTemp→ZBd(S1YTemp)→Z∈Bd(S1)六、|Z|＞1，并Z∈Bd(S1)時，ZTemp又任意Y屬于Z，Y∈S1，并Z(S1)∵Z(S1)并ZTemp→ZBd(S1YTemp)∴綜上所述，上述命題成立。

四、更新算法的測試及結果

（一）更新算法的環境要求

在P4-2.4c/512M內存/120G硬盤計算機環境下，運行delphi7.0編輯器實現Aproiri算法的模擬測試，以某彩票售票點的銷售額與日期之間的關系為目標關聯規則，在經過兩種算法的多次運行和數據采集后，取各量化平均值，得出如下數據圖表：

（二）更新算法的效果分析

由圖可知，在使用本文所提出的更新算法后，原算法的效率得到大大的提高。提高原因主要是從原算法的反復掃描升級至現算法的兩次掃描，就可得出所需挖掘關聯規則，尤其是在大規模的數據庫環境下，本算法的優越性表現越明顯。