基于ARIZ的關(guān)聯(lián)規(guī)則知識(shí)發(fā)現(xiàn)模式研究

翟霞　宋毅

【摘 要】 本文借助ARIZ思想深入研究了關(guān)聯(lián)規(guī)則挖掘模式，綜合介紹了關(guān)聯(lián)規(guī)則的理論基礎(chǔ)，進(jìn)一步明確了項(xiàng)、項(xiàng)集、候選項(xiàng)集、頻繁項(xiàng)集、支持度、置信度這些重要知識(shí)點(diǎn)，對(duì)關(guān)聯(lián)規(guī)則進(jìn)行了多角度的分類(lèi)，研究分析了關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法，并對(duì)關(guān)聯(lián)規(guī)則的評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行了創(chuàng)新研究，引入了主觀興趣度和客觀相關(guān)性分析，為后續(xù)研究和改進(jìn)關(guān)聯(lián)規(guī)則的算法提供了理論基礎(chǔ)。

【關(guān)鍵詞】 ARIZ 關(guān)聯(lián)規(guī)則 興趣度 相關(guān)性分析

1 ARIZ主導(dǎo)思想

ARIZ（Algorithm for Inventive-Problem Solving，發(fā)明問(wèn)題解決算法）最初由Ahshuller于1956年提出，是TRIZ中最強(qiáng)有力的工具，集成了TRIZ理論中大多數(shù)觀點(diǎn)和工具[1]。ARIZ的主導(dǎo)思想和觀點(diǎn)中最重要的就是克服思維慣性。思維慣性是創(chuàng)新設(shè)計(jì)的最大障礙，ARIZ強(qiáng)調(diào)在解決問(wèn)題過(guò)程中必須開(kāi)闊思路克服思維慣性，主要通過(guò)利用TRIZ已有工具和一系列心理算法克服思維慣性。

TRIZ認(rèn)為，一個(gè)創(chuàng)新問(wèn)題解決的困難程度取決于對(duì)該問(wèn)題的描述和問(wèn)題的標(biāo)準(zhǔn)化程度，描述得越清楚，問(wèn)題的標(biāo)準(zhǔn)化程度越高，問(wèn)題就越容易解決。ARIZ中，創(chuàng)新問(wèn)題求解的過(guò)程是對(duì)問(wèn)題不斷地描述，不斷地標(biāo)準(zhǔn)化的過(guò)程。在這一過(guò)程中，初始問(wèn)題最根本的矛盾被清晰地顯現(xiàn)出來(lái)。如果方案庫(kù)里已有的數(shù)據(jù)能夠用于該問(wèn)題則是有標(biāo)準(zhǔn)解；如果已有的數(shù)據(jù)不能解決該問(wèn)題則無(wú)標(biāo)準(zhǔn)解，需等待科學(xué)技術(shù)的進(jìn)一步發(fā)展。該過(guò)程是通過(guò)ARIZ算法實(shí)現(xiàn)的。

2 關(guān)聯(lián)規(guī)則挖掘的基本理論

關(guān)聯(lián)分析是和分類(lèi)、聚類(lèi)、演化分析等并列的一種知識(shí)發(fā)現(xiàn)模式，受到人們的廣泛關(guān)注。Agrawal等人在1993年首次提出了商業(yè)數(shù)據(jù)庫(kù)中各種商品間的關(guān)聯(lián)問(wèn)題，之后關(guān)于關(guān)聯(lián)規(guī)則的研究層出不窮。關(guān)聯(lián)規(guī)則的應(yīng)用也由最初的購(gòu)物籃分析擴(kuò)展到其他各個(gè)領(lǐng)域，挖掘得到的規(guī)則說(shuō)明也呈現(xiàn)多元化。

設(shè)I={i1，i2，…，im}是常數(shù)的集合，其中m是任意有限的正整數(shù)常量，每個(gè)常數(shù)ik（k=1，2，……，m）稱(chēng)為一個(gè)數(shù)據(jù)項(xiàng)，簡(jiǎn)稱(chēng)為項(xiàng)（item）。若X是由I中的任意數(shù)據(jù)項(xiàng)組成的集合，即XI，則稱(chēng)X為項(xiàng)集，若X是包含K個(gè)數(shù)據(jù)項(xiàng)的項(xiàng)集稱(chēng)為K-項(xiàng)集。

關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫(kù)中數(shù)據(jù)項(xiàng)之間存在的潛在關(guān)系的規(guī)則，一個(gè)關(guān)聯(lián)規(guī)則是形如XY的蘊(yùn)涵式，其中XI，YI，并且X∩Y=Φ。項(xiàng)集X稱(chēng)為規(guī)則的前提或前項(xiàng)，Y稱(chēng)為結(jié)果或后項(xiàng)。關(guān)聯(lián)規(guī)則直觀描述事件中各個(gè)數(shù)據(jù)項(xiàng)同時(shí)出現(xiàn)概率較高的情況，如何找出這種高概率的發(fā)生，也就是說(shuō)，這種高概率達(dá)到什么標(biāo)準(zhǔn)才能被認(rèn)為是數(shù)據(jù)項(xiàng)之間是關(guān)聯(lián)的。最常規(guī)的評(píng)價(jià)標(biāo)準(zhǔn)是由支持度和置信度這兩個(gè)概念決定，通常被稱(chēng)為關(guān)聯(lián)規(guī)則的評(píng)價(jià)函數(shù)。

關(guān)聯(lián)規(guī)則AB在事務(wù)數(shù)據(jù)庫(kù)D中成立，其中事務(wù)同時(shí)包含A和B的百分比，叫做該規(guī)則的覆蓋率或支持度，記為Support（A∪B）。覆蓋率高表示規(guī)則在數(shù)據(jù)庫(kù)中出現(xiàn)的頻率較高，這樣規(guī)則所表現(xiàn)的現(xiàn)象發(fā)生的可能性也比較大。

關(guān)聯(lián)規(guī)則AB在事務(wù)數(shù)據(jù)庫(kù)D中成立，在數(shù)據(jù)庫(kù)中同時(shí)出現(xiàn)項(xiàng)集A和B的記錄數(shù)與出現(xiàn)項(xiàng)集A的記錄數(shù)的百分比，叫做該規(guī)則的正確率或置信度，記為Confidence（A∪B）。正確率高表示規(guī)則比較可信的，正確率在90%以上的規(guī)則，我們稱(chēng)之為強(qiáng)規(guī)則。

項(xiàng)集的頻率是事務(wù)數(shù)據(jù)庫(kù)中出現(xiàn)該項(xiàng)集的記錄數(shù)。如果某一項(xiàng)集頻率大于或等于最小支持度設(shè)定的閾值，我們通常稱(chēng)它為頻繁項(xiàng)集（frequent itemset）。包含有k個(gè)項(xiàng)的頻繁項(xiàng)集即通常表示為k-頻集。當(dāng)一條規(guī)則同時(shí)滿(mǎn)足最小支持度和最小置信度設(shè)定的閾值時(shí)，這條規(guī)則就是我們要找的真正的關(guān)聯(lián)規(guī)則。

3 關(guān)聯(lián)規(guī)則挖掘的分類(lèi)

根據(jù)規(guī)則中所涉及的數(shù)據(jù)項(xiàng)的數(shù)據(jù)類(lèi)型分為布爾關(guān)聯(lián)規(guī)則和量化關(guān)聯(lián)規(guī)則，例如：烤鴨甜面醬，被稱(chēng)為布爾關(guān)聯(lián)規(guī)則，該規(guī)則前件和后件取值都是離散的，考慮的是某數(shù)據(jù)項(xiàng)存在或者不存在。在關(guān)聯(lián)規(guī)則中出現(xiàn)數(shù)值型數(shù)據(jù)，例如：職稱(chēng)（“副教授”）年齡（“32…37”），這類(lèi)規(guī)則稱(chēng)為量化關(guān)聯(lián)規(guī)則。

根據(jù)規(guī)則中項(xiàng)或?qū)傩陨婕暗降木S度數(shù)分為單維和多維關(guān)聯(lián)規(guī)則。規(guī)則中涉及的數(shù)據(jù)項(xiàng)只來(lái)自于一個(gè)屬性，例如：面包牛奶，這樣的規(guī)則稱(chēng)為單維關(guān)聯(lián)規(guī)則。而多維關(guān)聯(lián)規(guī)則涉及事務(wù)數(shù)據(jù)庫(kù)中的多個(gè)屬性，例如：性別（“女”）職業(yè)（“教師”），可以稱(chēng)為二維關(guān)聯(lián)規(guī)則。

根據(jù)規(guī)則中數(shù)據(jù)的抽象層次分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則[2]。在單層關(guān)聯(lián)規(guī)則中，所有的數(shù)據(jù)項(xiàng)都是概括級(jí)別低的細(xì)節(jié)數(shù)據(jù)，沒(méi)有層次的劃分。多層關(guān)聯(lián)規(guī)則體現(xiàn)了數(shù)據(jù)的層次性，規(guī)則中的數(shù)據(jù)可能位于同一層次，也可能位于不同的層次。例如：聯(lián)想臺(tái)式機(jī)HP掃描儀是單層關(guān)聯(lián)規(guī)則，而“臺(tái)式機(jī)HP掃描儀”是一個(gè)高一級(jí)概括層次和細(xì)節(jié)層次之間的層間關(guān)聯(lián)規(guī)則，而“臺(tái)式機(jī)掃描儀”則是高概括層次上的同級(jí)別關(guān)聯(lián)規(guī)則。

4 關(guān)聯(lián)規(guī)則挖掘的方法

Apriori算法是關(guān)聯(lián)規(guī)則算法中經(jīng)典的算法，它采用“寬度優(yōu)先搜索策略”，核心思想是首先尋找頻繁項(xiàng)集，然后根據(jù)找到的頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則的產(chǎn)生比較容易，只需保證規(guī)則滿(mǎn)足事先設(shè)定好的最小正確率即可。而尋找頻繁項(xiàng)集的過(guò)程要復(fù)雜很多，整個(gè)算法的總體執(zhí)行效率也是由這一步?jīng)Q定的。因此，針對(duì)該算法的研究熱門(mén)都集中在如何快速找到頻繁項(xiàng)集。

頻繁模式增長(zhǎng)樹(shù)（Frequent Pattern-Growth）算法，是基于Apriori算法產(chǎn)生的，簡(jiǎn)稱(chēng)FP-Growth。該算法使用深度優(yōu)先搜索策略替代了Apriori算法的寬度優(yōu)先搜索策略[3]，把數(shù)據(jù)庫(kù)壓縮映射到一個(gè)小而緊湊的數(shù)據(jù)結(jié)構(gòu)頻繁模式樹(shù)FP-Tree中，避免了多次掃描數(shù)據(jù)庫(kù)。利用“模式分段增長(zhǎng)”法避免產(chǎn)生大量的候選集。采用分而治之的遞歸算法將挖掘任務(wù)分解成若干較小任務(wù)，從而有效的縮小了搜索空間。

在關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘過(guò)程中，若是因?yàn)閿?shù)據(jù)的分散性，很難在概念層次的細(xì)節(jié)層發(fā)現(xiàn)規(guī)則，這時(shí)一般采用多層關(guān)聯(lián)規(guī)則挖掘的方法。多層關(guān)聯(lián)規(guī)則挖掘一般采用自頂向下的方式，從最一般的概念層開(kāi)始，到較具體的某一特定概念層，逐層尋找頻繁項(xiàng)集，直到不能找到頻繁項(xiàng)集為止。對(duì)于每一層，可以使用上面介紹的Apriori算法和FP-Growth算法，或是其他關(guān)聯(lián)規(guī)則算法。

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

為了衡量挖掘出的某條規(guī)則是否有用，并且從結(jié)果集中過(guò)濾掉那些無(wú)用的規(guī)則，提出了基于興趣度的定義方法，可以分為主觀興趣度和相關(guān)性分析。

一條規(guī)則是否有價(jià)值最終取決于用戶(hù)的實(shí)際需求，只有用戶(hù)才可以最終決定所獲得的規(guī)則是否有效和可行。主觀興趣度的評(píng)價(jià)標(biāo)準(zhǔn)主要有兩種：不可預(yù)期性和可操作性[4]。不可預(yù)期性是指如果挖掘出來(lái)的規(guī)則用戶(hù)以前不知道，或者說(shuō)與用戶(hù)已知的知識(shí)剛好相反，則說(shuō)該規(guī)則具有不可預(yù)期性?？刹僮餍允侵溉绻脩?hù)可以利用規(guī)則采取對(duì)自己有利的操作行為，則說(shuō)該規(guī)則具有可操作性。

參考文獻(xiàn)：

[1]沈萌紅.《TRIZ理論及機(jī)械創(chuàng)新實(shí)踐》[M].機(jī)械工業(yè)出版社，2012：18-26.

[2]段玉琴.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究[D].西安：西安電子科技大學(xué)碩士論文，2011：1-10.

[3]SHENG P，HUANG J R，HUANG S M，BEI G.Turbo-Charging Vertical Mining of Large Databases[C]. SIGMOD Conference，New York，2010：492-50l.

[4]常同善.數(shù)據(jù)挖掘技術(shù)在美國(guó)院校研究中的應(yīng)用[J].復(fù)旦教育論，2009，（2）：72-79.

[5]吳青，傅秀芬.水平分布數(shù)據(jù)庫(kù)的正負(fù)關(guān)聯(lián)規(guī)則挖掘[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010，（6）：113-117.

【摘 要】 本文借助ARIZ思想深入研究了關(guān)聯(lián)規(guī)則挖掘模式，綜合介紹了關(guān)聯(lián)規(guī)則的理論基礎(chǔ)，進(jìn)一步明確了項(xiàng)、項(xiàng)集、候選項(xiàng)集、頻繁項(xiàng)集、支持度、置信度這些重要知識(shí)點(diǎn)，對(duì)關(guān)聯(lián)規(guī)則進(jìn)行了多角度的分類(lèi)，研究分析了關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法，并對(duì)關(guān)聯(lián)規(guī)則的評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行了創(chuàng)新研究，引入了主觀興趣度和客觀相關(guān)性分析，為后續(xù)研究和改進(jìn)關(guān)聯(lián)規(guī)則的算法提供了理論基礎(chǔ)。

【關(guān)鍵詞】 ARIZ 關(guān)聯(lián)規(guī)則 興趣度 相關(guān)性分析

1 ARIZ主導(dǎo)思想

ARIZ（Algorithm for Inventive-Problem Solving，發(fā)明問(wèn)題解決算法）最初由Ahshuller于1956年提出，是TRIZ中最強(qiáng)有力的工具，集成了TRIZ理論中大多數(shù)觀點(diǎn)和工具[1]。ARIZ的主導(dǎo)思想和觀點(diǎn)中最重要的就是克服思維慣性。思維慣性是創(chuàng)新設(shè)計(jì)的最大障礙，ARIZ強(qiáng)調(diào)在解決問(wèn)題過(guò)程中必須開(kāi)闊思路克服思維慣性，主要通過(guò)利用TRIZ已有工具和一系列心理算法克服思維慣性。

TRIZ認(rèn)為，一個(gè)創(chuàng)新問(wèn)題解決的困難程度取決于對(duì)該問(wèn)題的描述和問(wèn)題的標(biāo)準(zhǔn)化程度，描述得越清楚，問(wèn)題的標(biāo)準(zhǔn)化程度越高，問(wèn)題就越容易解決。ARIZ中，創(chuàng)新問(wèn)題求解的過(guò)程是對(duì)問(wèn)題不斷地描述，不斷地標(biāo)準(zhǔn)化的過(guò)程。在這一過(guò)程中，初始問(wèn)題最根本的矛盾被清晰地顯現(xiàn)出來(lái)。如果方案庫(kù)里已有的數(shù)據(jù)能夠用于該問(wèn)題則是有標(biāo)準(zhǔn)解；如果已有的數(shù)據(jù)不能解決該問(wèn)題則無(wú)標(biāo)準(zhǔn)解，需等待科學(xué)技術(shù)的進(jìn)一步發(fā)展。該過(guò)程是通過(guò)ARIZ算法實(shí)現(xiàn)的。

2 關(guān)聯(lián)規(guī)則挖掘的基本理論

關(guān)聯(lián)分析是和分類(lèi)、聚類(lèi)、演化分析等并列的一種知識(shí)發(fā)現(xiàn)模式，受到人們的廣泛關(guān)注。Agrawal等人在1993年首次提出了商業(yè)數(shù)據(jù)庫(kù)中各種商品間的關(guān)聯(lián)問(wèn)題，之后關(guān)于關(guān)聯(lián)規(guī)則的研究層出不窮。關(guān)聯(lián)規(guī)則的應(yīng)用也由最初的購(gòu)物籃分析擴(kuò)展到其他各個(gè)領(lǐng)域，挖掘得到的規(guī)則說(shuō)明也呈現(xiàn)多元化。

設(shè)I={i1，i2，…，im}是常數(shù)的集合，其中m是任意有限的正整數(shù)常量，每個(gè)常數(shù)ik（k=1，2，……，m）稱(chēng)為一個(gè)數(shù)據(jù)項(xiàng)，簡(jiǎn)稱(chēng)為項(xiàng)（item）。若X是由I中的任意數(shù)據(jù)項(xiàng)組成的集合，即XI，則稱(chēng)X為項(xiàng)集，若X是包含K個(gè)數(shù)據(jù)項(xiàng)的項(xiàng)集稱(chēng)為K-項(xiàng)集。

關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫(kù)中數(shù)據(jù)項(xiàng)之間存在的潛在關(guān)系的規(guī)則，一個(gè)關(guān)聯(lián)規(guī)則是形如XY的蘊(yùn)涵式，其中XI，YI，并且X∩Y=Φ。項(xiàng)集X稱(chēng)為規(guī)則的前提或前項(xiàng)，Y稱(chēng)為結(jié)果或后項(xiàng)。關(guān)聯(lián)規(guī)則直觀描述事件中各個(gè)數(shù)據(jù)項(xiàng)同時(shí)出現(xiàn)概率較高的情況，如何找出這種高概率的發(fā)生，也就是說(shuō)，這種高概率達(dá)到什么標(biāo)準(zhǔn)才能被認(rèn)為是數(shù)據(jù)項(xiàng)之間是關(guān)聯(lián)的。最常規(guī)的評(píng)價(jià)標(biāo)準(zhǔn)是由支持度和置信度這兩個(gè)概念決定，通常被稱(chēng)為關(guān)聯(lián)規(guī)則的評(píng)價(jià)函數(shù)。

關(guān)聯(lián)規(guī)則AB在事務(wù)數(shù)據(jù)庫(kù)D中成立，其中事務(wù)同時(shí)包含A和B的百分比，叫做該規(guī)則的覆蓋率或支持度，記為Support（A∪B）。覆蓋率高表示規(guī)則在數(shù)據(jù)庫(kù)中出現(xiàn)的頻率較高，這樣規(guī)則所表現(xiàn)的現(xiàn)象發(fā)生的可能性也比較大。

關(guān)聯(lián)規(guī)則AB在事務(wù)數(shù)據(jù)庫(kù)D中成立，在數(shù)據(jù)庫(kù)中同時(shí)出現(xiàn)項(xiàng)集A和B的記錄數(shù)與出現(xiàn)項(xiàng)集A的記錄數(shù)的百分比，叫做該規(guī)則的正確率或置信度，記為Confidence（A∪B）。正確率高表示規(guī)則比較可信的，正確率在90%以上的規(guī)則，我們稱(chēng)之為強(qiáng)規(guī)則。

項(xiàng)集的頻率是事務(wù)數(shù)據(jù)庫(kù)中出現(xiàn)該項(xiàng)集的記錄數(shù)。如果某一項(xiàng)集頻率大于或等于最小支持度設(shè)定的閾值，我們通常稱(chēng)它為頻繁項(xiàng)集（frequent itemset）。包含有k個(gè)項(xiàng)的頻繁項(xiàng)集即通常表示為k-頻集。當(dāng)一條規(guī)則同時(shí)滿(mǎn)足最小支持度和最小置信度設(shè)定的閾值時(shí)，這條規(guī)則就是我們要找的真正的關(guān)聯(lián)規(guī)則。

3 關(guān)聯(lián)規(guī)則挖掘的分類(lèi)

根據(jù)規(guī)則中所涉及的數(shù)據(jù)項(xiàng)的數(shù)據(jù)類(lèi)型分為布爾關(guān)聯(lián)規(guī)則和量化關(guān)聯(lián)規(guī)則，例如：烤鴨甜面醬，被稱(chēng)為布爾關(guān)聯(lián)規(guī)則，該規(guī)則前件和后件取值都是離散的，考慮的是某數(shù)據(jù)項(xiàng)存在或者不存在。在關(guān)聯(lián)規(guī)則中出現(xiàn)數(shù)值型數(shù)據(jù)，例如：職稱(chēng)（“副教授”）年齡（“32…37”），這類(lèi)規(guī)則稱(chēng)為量化關(guān)聯(lián)規(guī)則。

根據(jù)規(guī)則中項(xiàng)或?qū)傩陨婕暗降木S度數(shù)分為單維和多維關(guān)聯(lián)規(guī)則。規(guī)則中涉及的數(shù)據(jù)項(xiàng)只來(lái)自于一個(gè)屬性，例如：面包牛奶，這樣的規(guī)則稱(chēng)為單維關(guān)聯(lián)規(guī)則。而多維關(guān)聯(lián)規(guī)則涉及事務(wù)數(shù)據(jù)庫(kù)中的多個(gè)屬性，例如：性別（“女”）職業(yè)（“教師”），可以稱(chēng)為二維關(guān)聯(lián)規(guī)則。

根據(jù)規(guī)則中數(shù)據(jù)的抽象層次分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則[2]。在單層關(guān)聯(lián)規(guī)則中，所有的數(shù)據(jù)項(xiàng)都是概括級(jí)別低的細(xì)節(jié)數(shù)據(jù)，沒(méi)有層次的劃分。多層關(guān)聯(lián)規(guī)則體現(xiàn)了數(shù)據(jù)的層次性，規(guī)則中的數(shù)據(jù)可能位于同一層次，也可能位于不同的層次。例如：聯(lián)想臺(tái)式機(jī)HP掃描儀是單層關(guān)聯(lián)規(guī)則，而“臺(tái)式機(jī)HP掃描儀”是一個(gè)高一級(jí)概括層次和細(xì)節(jié)層次之間的層間關(guān)聯(lián)規(guī)則，而“臺(tái)式機(jī)掃描儀”則是高概括層次上的同級(jí)別關(guān)聯(lián)規(guī)則。

4 關(guān)聯(lián)規(guī)則挖掘的方法

Apriori算法是關(guān)聯(lián)規(guī)則算法中經(jīng)典的算法，它采用“寬度優(yōu)先搜索策略”，核心思想是首先尋找頻繁項(xiàng)集，然后根據(jù)找到的頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則的產(chǎn)生比較容易，只需保證規(guī)則滿(mǎn)足事先設(shè)定好的最小正確率即可。而尋找頻繁項(xiàng)集的過(guò)程要復(fù)雜很多，整個(gè)算法的總體執(zhí)行效率也是由這一步?jīng)Q定的。因此，針對(duì)該算法的研究熱門(mén)都集中在如何快速找到頻繁項(xiàng)集。

頻繁模式增長(zhǎng)樹(shù)（Frequent Pattern-Growth）算法，是基于Apriori算法產(chǎn)生的，簡(jiǎn)稱(chēng)FP-Growth。該算法使用深度優(yōu)先搜索策略替代了Apriori算法的寬度優(yōu)先搜索策略[3]，把數(shù)據(jù)庫(kù)壓縮映射到一個(gè)小而緊湊的數(shù)據(jù)結(jié)構(gòu)頻繁模式樹(shù)FP-Tree中，避免了多次掃描數(shù)據(jù)庫(kù)。利用“模式分段增長(zhǎng)”法避免產(chǎn)生大量的候選集。采用分而治之的遞歸算法將挖掘任務(wù)分解成若干較小任務(wù)，從而有效的縮小了搜索空間。

在關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘過(guò)程中，若是因?yàn)閿?shù)據(jù)的分散性，很難在概念層次的細(xì)節(jié)層發(fā)現(xiàn)規(guī)則，這時(shí)一般采用多層關(guān)聯(lián)規(guī)則挖掘的方法。多層關(guān)聯(lián)規(guī)則挖掘一般采用自頂向下的方式，從最一般的概念層開(kāi)始，到較具體的某一特定概念層，逐層尋找頻繁項(xiàng)集，直到不能找到頻繁項(xiàng)集為止。對(duì)于每一層，可以使用上面介紹的Apriori算法和FP-Growth算法，或是其他關(guān)聯(lián)規(guī)則算法。

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

為了衡量挖掘出的某條規(guī)則是否有用，并且從結(jié)果集中過(guò)濾掉那些無(wú)用的規(guī)則，提出了基于興趣度的定義方法，可以分為主觀興趣度和相關(guān)性分析。

一條規(guī)則是否有價(jià)值最終取決于用戶(hù)的實(shí)際需求，只有用戶(hù)才可以最終決定所獲得的規(guī)則是否有效和可行。主觀興趣度的評(píng)價(jià)標(biāo)準(zhǔn)主要有兩種：不可預(yù)期性和可操作性[4]。不可預(yù)期性是指如果挖掘出來(lái)的規(guī)則用戶(hù)以前不知道，或者說(shuō)與用戶(hù)已知的知識(shí)剛好相反，則說(shuō)該規(guī)則具有不可預(yù)期性?？刹僮餍允侵溉绻脩?hù)可以利用規(guī)則采取對(duì)自己有利的操作行為，則說(shuō)該規(guī)則具有可操作性。

參考文獻(xiàn)：

[1]沈萌紅.《TRIZ理論及機(jī)械創(chuàng)新實(shí)踐》[M].機(jī)械工業(yè)出版社，2012：18-26.

[2]段玉琴.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究[D].西安：西安電子科技大學(xué)碩士論文，2011：1-10.

[3]SHENG P，HUANG J R，HUANG S M，BEI G.Turbo-Charging Vertical Mining of Large Databases[C]. SIGMOD Conference，New York，2010：492-50l.

[4]常同善.數(shù)據(jù)挖掘技術(shù)在美國(guó)院校研究中的應(yīng)用[J].復(fù)旦教育論，2009，（2）：72-79.

[5]吳青，傅秀芬.水平分布數(shù)據(jù)庫(kù)的正負(fù)關(guān)聯(lián)規(guī)則挖掘[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010，（6）：113-117.

【摘 要】 本文借助ARIZ思想深入研究了關(guān)聯(lián)規(guī)則挖掘模式，綜合介紹了關(guān)聯(lián)規(guī)則的理論基礎(chǔ)，進(jìn)一步明確了項(xiàng)、項(xiàng)集、候選項(xiàng)集、頻繁項(xiàng)集、支持度、置信度這些重要知識(shí)點(diǎn)，對(duì)關(guān)聯(lián)規(guī)則進(jìn)行了多角度的分類(lèi)，研究分析了關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法，并對(duì)關(guān)聯(lián)規(guī)則的評(píng)價(jià)標(biāo)準(zhǔn)進(jìn)行了創(chuàng)新研究，引入了主觀興趣度和客觀相關(guān)性分析，為后續(xù)研究和改進(jìn)關(guān)聯(lián)規(guī)則的算法提供了理論基礎(chǔ)。

【關(guān)鍵詞】 ARIZ 關(guān)聯(lián)規(guī)則 興趣度 相關(guān)性分析

1 ARIZ主導(dǎo)思想

ARIZ（Algorithm for Inventive-Problem Solving，發(fā)明問(wèn)題解決算法）最初由Ahshuller于1956年提出，是TRIZ中最強(qiáng)有力的工具，集成了TRIZ理論中大多數(shù)觀點(diǎn)和工具[1]。ARIZ的主導(dǎo)思想和觀點(diǎn)中最重要的就是克服思維慣性。思維慣性是創(chuàng)新設(shè)計(jì)的最大障礙，ARIZ強(qiáng)調(diào)在解決問(wèn)題過(guò)程中必須開(kāi)闊思路克服思維慣性，主要通過(guò)利用TRIZ已有工具和一系列心理算法克服思維慣性。

TRIZ認(rèn)為，一個(gè)創(chuàng)新問(wèn)題解決的困難程度取決于對(duì)該問(wèn)題的描述和問(wèn)題的標(biāo)準(zhǔn)化程度，描述得越清楚，問(wèn)題的標(biāo)準(zhǔn)化程度越高，問(wèn)題就越容易解決。ARIZ中，創(chuàng)新問(wèn)題求解的過(guò)程是對(duì)問(wèn)題不斷地描述，不斷地標(biāo)準(zhǔn)化的過(guò)程。在這一過(guò)程中，初始問(wèn)題最根本的矛盾被清晰地顯現(xiàn)出來(lái)。如果方案庫(kù)里已有的數(shù)據(jù)能夠用于該問(wèn)題則是有標(biāo)準(zhǔn)解；如果已有的數(shù)據(jù)不能解決該問(wèn)題則無(wú)標(biāo)準(zhǔn)解，需等待科學(xué)技術(shù)的進(jìn)一步發(fā)展。該過(guò)程是通過(guò)ARIZ算法實(shí)現(xiàn)的。

2 關(guān)聯(lián)規(guī)則挖掘的基本理論

關(guān)聯(lián)分析是和分類(lèi)、聚類(lèi)、演化分析等并列的一種知識(shí)發(fā)現(xiàn)模式，受到人們的廣泛關(guān)注。Agrawal等人在1993年首次提出了商業(yè)數(shù)據(jù)庫(kù)中各種商品間的關(guān)聯(lián)問(wèn)題，之后關(guān)于關(guān)聯(lián)規(guī)則的研究層出不窮。關(guān)聯(lián)規(guī)則的應(yīng)用也由最初的購(gòu)物籃分析擴(kuò)展到其他各個(gè)領(lǐng)域，挖掘得到的規(guī)則說(shuō)明也呈現(xiàn)多元化。

設(shè)I={i1，i2，…，im}是常數(shù)的集合，其中m是任意有限的正整數(shù)常量，每個(gè)常數(shù)ik（k=1，2，……，m）稱(chēng)為一個(gè)數(shù)據(jù)項(xiàng)，簡(jiǎn)稱(chēng)為項(xiàng)（item）。若X是由I中的任意數(shù)據(jù)項(xiàng)組成的集合，即XI，則稱(chēng)X為項(xiàng)集，若X是包含K個(gè)數(shù)據(jù)項(xiàng)的項(xiàng)集稱(chēng)為K-項(xiàng)集。

關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫(kù)中數(shù)據(jù)項(xiàng)之間存在的潛在關(guān)系的規(guī)則，一個(gè)關(guān)聯(lián)規(guī)則是形如XY的蘊(yùn)涵式，其中XI，YI，并且X∩Y=Φ。項(xiàng)集X稱(chēng)為規(guī)則的前提或前項(xiàng)，Y稱(chēng)為結(jié)果或后項(xiàng)。關(guān)聯(lián)規(guī)則直觀描述事件中各個(gè)數(shù)據(jù)項(xiàng)同時(shí)出現(xiàn)概率較高的情況，如何找出這種高概率的發(fā)生，也就是說(shuō)，這種高概率達(dá)到什么標(biāo)準(zhǔn)才能被認(rèn)為是數(shù)據(jù)項(xiàng)之間是關(guān)聯(lián)的。最常規(guī)的評(píng)價(jià)標(biāo)準(zhǔn)是由支持度和置信度這兩個(gè)概念決定，通常被稱(chēng)為關(guān)聯(lián)規(guī)則的評(píng)價(jià)函數(shù)。

關(guān)聯(lián)規(guī)則AB在事務(wù)數(shù)據(jù)庫(kù)D中成立，其中事務(wù)同時(shí)包含A和B的百分比，叫做該規(guī)則的覆蓋率或支持度，記為Support（A∪B）。覆蓋率高表示規(guī)則在數(shù)據(jù)庫(kù)中出現(xiàn)的頻率較高，這樣規(guī)則所表現(xiàn)的現(xiàn)象發(fā)生的可能性也比較大。

關(guān)聯(lián)規(guī)則AB在事務(wù)數(shù)據(jù)庫(kù)D中成立，在數(shù)據(jù)庫(kù)中同時(shí)出現(xiàn)項(xiàng)集A和B的記錄數(shù)與出現(xiàn)項(xiàng)集A的記錄數(shù)的百分比，叫做該規(guī)則的正確率或置信度，記為Confidence（A∪B）。正確率高表示規(guī)則比較可信的，正確率在90%以上的規(guī)則，我們稱(chēng)之為強(qiáng)規(guī)則。

項(xiàng)集的頻率是事務(wù)數(shù)據(jù)庫(kù)中出現(xiàn)該項(xiàng)集的記錄數(shù)。如果某一項(xiàng)集頻率大于或等于最小支持度設(shè)定的閾值，我們通常稱(chēng)它為頻繁項(xiàng)集（frequent itemset）。包含有k個(gè)項(xiàng)的頻繁項(xiàng)集即通常表示為k-頻集。當(dāng)一條規(guī)則同時(shí)滿(mǎn)足最小支持度和最小置信度設(shè)定的閾值時(shí)，這條規(guī)則就是我們要找的真正的關(guān)聯(lián)規(guī)則。

3 關(guān)聯(lián)規(guī)則挖掘的分類(lèi)

根據(jù)規(guī)則中所涉及的數(shù)據(jù)項(xiàng)的數(shù)據(jù)類(lèi)型分為布爾關(guān)聯(lián)規(guī)則和量化關(guān)聯(lián)規(guī)則，例如：烤鴨甜面醬，被稱(chēng)為布爾關(guān)聯(lián)規(guī)則，該規(guī)則前件和后件取值都是離散的，考慮的是某數(shù)據(jù)項(xiàng)存在或者不存在。在關(guān)聯(lián)規(guī)則中出現(xiàn)數(shù)值型數(shù)據(jù)，例如：職稱(chēng)（“副教授”）年齡（“32…37”），這類(lèi)規(guī)則稱(chēng)為量化關(guān)聯(lián)規(guī)則。

根據(jù)規(guī)則中項(xiàng)或?qū)傩陨婕暗降木S度數(shù)分為單維和多維關(guān)聯(lián)規(guī)則。規(guī)則中涉及的數(shù)據(jù)項(xiàng)只來(lái)自于一個(gè)屬性，例如：面包牛奶，這樣的規(guī)則稱(chēng)為單維關(guān)聯(lián)規(guī)則。而多維關(guān)聯(lián)規(guī)則涉及事務(wù)數(shù)據(jù)庫(kù)中的多個(gè)屬性，例如：性別（“女”）職業(yè)（“教師”），可以稱(chēng)為二維關(guān)聯(lián)規(guī)則。

根據(jù)規(guī)則中數(shù)據(jù)的抽象層次分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則[2]。在單層關(guān)聯(lián)規(guī)則中，所有的數(shù)據(jù)項(xiàng)都是概括級(jí)別低的細(xì)節(jié)數(shù)據(jù)，沒(méi)有層次的劃分。多層關(guān)聯(lián)規(guī)則體現(xiàn)了數(shù)據(jù)的層次性，規(guī)則中的數(shù)據(jù)可能位于同一層次，也可能位于不同的層次。例如：聯(lián)想臺(tái)式機(jī)HP掃描儀是單層關(guān)聯(lián)規(guī)則，而“臺(tái)式機(jī)HP掃描儀”是一個(gè)高一級(jí)概括層次和細(xì)節(jié)層次之間的層間關(guān)聯(lián)規(guī)則，而“臺(tái)式機(jī)掃描儀”則是高概括層次上的同級(jí)別關(guān)聯(lián)規(guī)則。

4 關(guān)聯(lián)規(guī)則挖掘的方法

Apriori算法是關(guān)聯(lián)規(guī)則算法中經(jīng)典的算法，它采用“寬度優(yōu)先搜索策略”，核心思想是首先尋找頻繁項(xiàng)集，然后根據(jù)找到的頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則的產(chǎn)生比較容易，只需保證規(guī)則滿(mǎn)足事先設(shè)定好的最小正確率即可。而尋找頻繁項(xiàng)集的過(guò)程要復(fù)雜很多，整個(gè)算法的總體執(zhí)行效率也是由這一步?jīng)Q定的。因此，針對(duì)該算法的研究熱門(mén)都集中在如何快速找到頻繁項(xiàng)集。

頻繁模式增長(zhǎng)樹(shù)（Frequent Pattern-Growth）算法，是基于Apriori算法產(chǎn)生的，簡(jiǎn)稱(chēng)FP-Growth。該算法使用深度優(yōu)先搜索策略替代了Apriori算法的寬度優(yōu)先搜索策略[3]，把數(shù)據(jù)庫(kù)壓縮映射到一個(gè)小而緊湊的數(shù)據(jù)結(jié)構(gòu)頻繁模式樹(shù)FP-Tree中，避免了多次掃描數(shù)據(jù)庫(kù)。利用“模式分段增長(zhǎng)”法避免產(chǎn)生大量的候選集。采用分而治之的遞歸算法將挖掘任務(wù)分解成若干較小任務(wù)，從而有效的縮小了搜索空間。

在關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘過(guò)程中，若是因?yàn)閿?shù)據(jù)的分散性，很難在概念層次的細(xì)節(jié)層發(fā)現(xiàn)規(guī)則，這時(shí)一般采用多層關(guān)聯(lián)規(guī)則挖掘的方法。多層關(guān)聯(lián)規(guī)則挖掘一般采用自頂向下的方式，從最一般的概念層開(kāi)始，到較具體的某一特定概念層，逐層尋找頻繁項(xiàng)集，直到不能找到頻繁項(xiàng)集為止。對(duì)于每一層，可以使用上面介紹的Apriori算法和FP-Growth算法，或是其他關(guān)聯(lián)規(guī)則算法。

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

為了衡量挖掘出的某條規(guī)則是否有用，并且從結(jié)果集中過(guò)濾掉那些無(wú)用的規(guī)則，提出了基于興趣度的定義方法，可以分為主觀興趣度和相關(guān)性分析。

一條規(guī)則是否有價(jià)值最終取決于用戶(hù)的實(shí)際需求，只有用戶(hù)才可以最終決定所獲得的規(guī)則是否有效和可行。主觀興趣度的評(píng)價(jià)標(biāo)準(zhǔn)主要有兩種：不可預(yù)期性和可操作性[4]。不可預(yù)期性是指如果挖掘出來(lái)的規(guī)則用戶(hù)以前不知道，或者說(shuō)與用戶(hù)已知的知識(shí)剛好相反，則說(shuō)該規(guī)則具有不可預(yù)期性?？刹僮餍允侵溉绻脩?hù)可以利用規(guī)則采取對(duì)自己有利的操作行為，則說(shuō)該規(guī)則具有可操作性。

參考文獻(xiàn)：

[1]沈萌紅.《TRIZ理論及機(jī)械創(chuàng)新實(shí)踐》[M].機(jī)械工業(yè)出版社，2012：18-26.

[2]段玉琴.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究[D].西安：西安電子科技大學(xué)碩士論文，2011：1-10.

[3]SHENG P，HUANG J R，HUANG S M，BEI G.Turbo-Charging Vertical Mining of Large Databases[C]. SIGMOD Conference，New York，2010：492-50l.

[4]常同善.數(shù)據(jù)挖掘技術(shù)在美國(guó)院校研究中的應(yīng)用[J].復(fù)旦教育論，2009，（2）：72-79.

[5]吳青，傅秀芬.水平分布數(shù)據(jù)庫(kù)的正負(fù)關(guān)聯(lián)規(guī)則挖掘[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010，（6）：113-117.