關聯規則演演算法

所謂關聯，反映的是一個事件和其他事件之間依賴或關聯的知識。當我們查找英文文獻的時候，可以發現有兩個英文詞都能形容關聯的含義。第一個是相關性relevance，第二個是關聯性association，兩者都可以用來描述事件之間的關聯程度。

設I={i1,i2…,im}為所有項目的集合，設A是一個由項目構成的集合，稱為項集。事務T是一個項目子集，每一個事務具有唯一的事務標識Tid。事務T包含項集A，當且僅當AT。如果項集A中包含k個項目，則稱其為k項集。D為事務資料庫，項集A在事務資料庫D中出現的次數佔D中總事務的百分比叫做項集的支持度（support）。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集（或大項集）。

關聯規則就是形如XY的邏輯蘊含關係，其中XI，YI且XY=Φ，X稱作規則的前件，Y是結果，對於關聯規則XY，存在支持度和信任度。

支持度是指規則中所出現模式的頻率，如果事務資料庫有s%的事務包含XY，則稱關聯規則XY在D中的支持度為s%，實際上，可以表示為概率P（XY），即support（XY）= P（XY）。信任度是指蘊含的強度，即事務D中c%的包含X的交易同時包含XY。若X的支持度是support(x)，規則的信任度為即為：support(XY)/support(X)，這是一個條件概率P（Y|X），即confidence（XY）= P（Y|X）。

關聯演演算法是數據挖掘中的一類重要演演算法。1993年,R.Agrawal等人首次提出了挖掘顧客交易數據中項目集間的關聯規則問題，其核心是基於兩階段頻繁集思想的遞推演演算法。該關聯規則在分類上屬於單維、單層及布爾關聯規則，典型的演演算法是Apriori演演算法。

Apriori演演算法將發現關聯規則的過程分為兩個步驟：第一步通過迭代，檢索出事務資料庫1中的所有頻繁項集，即支持度不低於用戶設定的閾值的項集；第二步利用頻繁項集構造出滿足用戶最小信任度的規則。其中，挖掘或識別出所有頻繁項集是該演演算法的核心，占整個計算量的大部分。