关联分析进阶概念

第7章關聯分析：進階概念

©2008台灣培生教育出版(PearsonEducationTaiwan)處理類別的屬性有很多應用是包含對稱式二元屬性和名目（nominal）屬性。例如性別、家裡有無電腦、線上聊天、線上購物和隱私權的問題；也包含名目屬性，如教育層級與州名使用關聯分析，我們可能會發現一些與網際網路使用者有關的有趣資訊，例如{線上購物=Yes}→{關心隱私權問題=Yes}這個規則表示：大部份線上購物的網際網路使用者會關心他們的個人隱私當關聯分析應用至二元化的資料上時，要考慮的議題包括：一些屬性值不是高頻項目，而不足以成為高頻樣式的一部份。這個問題對於名目屬性而言（如州名）會更明顯和其他屬性值相較，有一些屬性值會有相當高的次數一個用來減少計算時間的方式，是避免產生包含一個以上且為相同屬性項目的候選集處理連續屬性的方法離散式方法（discretization-basedmethod）統計式方法（statistics-basedmethod）非離散式方法（non-discretizationmethod）離散式方法離散是最常用以處理連續屬性的方法。這個方法是將鄰近之連續屬性值分群至有限數值的區間中屬性離散化中的一個重要參數是區間數量，此參數被用來切割每一個屬性，這個參數基本上是由使用者提供，且可被表示成區間寬度（相等區間寬度方法；等寬）、每個區間的平均交易數量（相等次數方法；等深）、或所需的群集數量（以分群為基礎之方法）當針對年齡屬性做離散化時，區間寬度的取捨

若區間太寬，會因為信賴度不足而遺漏一些樣式若區間太窄，會因為支持度不足而遺漏一些樣式統計式方法數量關聯規則（quantitativeassociationrule）可被用來推論母體的統計特徵為了產生以統計為基礎之數量關聯規則，必須指定目標屬性以用來區分母體中感興趣的部份（interestingsegments）。藉由保留目標屬性，資料中剩餘的類別與連續屬性會用離散式的方法來做二元化，現存的演算法如Apriori或FP-growth則被應用於二元化資料中，以萃取高頻項目集，每個高頻項目表示母體的一個興趣部份數量關聯規則是有趣的，只要用規則所涵蓋的交易資料而求得的統計量，與規則不涵蓋的交易資料而求得的統計量不同非離散化方法分析者在某些應用中，最感興趣的是在連續屬性（continuousattribute）中發現關聯，而不是在連續屬性中發現離散區間的關聯在文字探勘中，分析者最感興趣的是去發掘字之間的關係（即data和mining），而不是字出現次數範圍間的關係min-Apriori是另一個找尋字的關聯的方法，與傳統關聯分析類似，項目集會被視為一群字的集合，而它的支持度測量是根據字之間的關聯程度項目集的支持度可根據其對應字的正規化次數（normalizedfrequencies）來計算在min-Apriori中，某一特定文章中字的關聯可以取他們正規化次數的最小值，即min(word1,word2)=min(0.3,0.6)=0.3。項目集的支持度可以藉由整合所有文件中的關聯來計算在min-Apriori中的支持度測量有下列特性，使得它適用於發掘文件中字的關聯：當字的正規化次數增加時，支持度單調地增加當包含字的文件數量增加時，支持度單調地增加支持度有反單調的特性。舉例來說，假設一對項目集{A,B}與{A,B,C}，由於min({A,B})min({A,B,C})，則s({A,B})s({A,B,C})。因此，在項目集中字的數量增加，則支持度單調地降低概念階層是在某個特定領域中，表示各種不同項目或概念之多層級組織架構定義概念階層是根據領域知識（domainknowledge），或以某組織定義之標準分類架構為基礎（例如，國會圖書館之分類架構可用來組織資料的主題分類）概念階層可使用有向無迴圈圖（directedacyclicgraph）來表示，如前頁投影片圖所示整合概念階層至關聯分析中的主要優點如下：在階層中較低層級之項目可能沒有足夠的支持度以出現於任何高頻項目集中在概念階層之低階層中所發現的規則會有過度特殊的（overlyspecific）傾向，且不如高階層之規則有趣序列樣式序列資料對於識別動態系統中再發生的特性，或在某些事件中預測未來的發生是很有用的。問題定義序列樣式探勘時間限制替代的計算方法序列樣式：問題定義發掘序列樣式之問題的輸入為序列資料集合，每一列記錄某一特定物件在某時間內發生的相關事件序列樣式：問題定義序列可由它的長度和發生事件的數量來描述，序列的長度表示出現於序列中的元素數量，而k-sequence為一個包含k個事件的序列序列樣式：問題定義在序列資料集合中元素和事件的範例序列樣式：序列樣式探勘序列樣式探勘在計算上是一個具挑戰性的工作，因為在給定的資料序列中可能包含很多序列序列樣式發掘：假設序列資料集合D和使用者指定之最小支持度門檻值，序列樣式發掘可以找尋所有支持度最小支持度門檻值得序列樣式序列樣式：時間限制Maxspan限制maxspan限制說明在整個序列中最晚與最早發生事件之間，可允許的最大時間差異一般來說，maxspan越長，越有可能會發現資料序列中的樣式。然而，較長的maxspan會增加兩個不相關事件中時間相關的可能性，而獲得不正確的樣式maxspan限制會影響序列樣式發掘演算法中支持度計算的步驟Mingap與maxgap限制可透過設定時間限制的方式限制序列中兩個連續元素之間時間的差異，若最大時間差異（maxgap）是一週，則一個元素中事件的發生必須與前面元素的事件發生時間差距一週時間以內。若最小時間差異（mingap）是0，則在前面元素的事件發生後，另一個元素的事件必須馬上發生在各種應用領域中實體的圖形表示法應用圖形項點邊網路探勘網頁瀏覽樣式網頁網頁之間的超連結計算化學化學化合物的結構分子或離子分子或離子之間的聯結網路計算電腦網路電腦或伺服器機器之間的連結語意網路XML文件的集合XML的元素在元素之間的父子（parent-child）關係生物資訊蛋白質結構氨基酸接觸的殘餘物資料探勘可在這種類型的資料上執行，以得到圖集中共同子結構（commonsubstructures）的集合，這樣的任務稱為高頻子圖探勘（frequentsubgraphmining）。一個高頻子圖探勘的應用於在計算化學（computationalchemistry），每天都會有新的化學化合物出現，可運用在藥、殺蟲劑、肥料等發展上，雖然化合物的結構在化學特性的決定上扮演重要的角色，然而卻很難建立這些特性間的關係子圖形的範例（b）子圖形（a）標記圖形高頻子圖形探勘

窮舉法可用來產生所有相連結的子圖形以此當成候選項目，並分別計算其支持度

候選子圖形的數量，會比在傳統關聯規則探勘演算法中的候選項目集數量來得大，理由如下：一個項目最多只會在一個項目集中出現一次，而一個頂點標記在圖形中可以出現一次以上成對且相同的頂點標記可有多個邊的標記高頻子圖形探勘演算法之一般結構用於探勘高頻子圖形之Apriori-like演算法包含下列步驟：候選項目的產生，這個步驟合併兩兩之高頻(k-1)-子圖形，以得到一個候選k-子圖形候選項目的刪除，這個步驟刪除有包含非高頻(k-1)-子圖形之所有候選k-子圖形支持度計算，這個步驟計算包含每個候選圖形中的圖形數量候選項目的淘汰，捨棄支持個數小於最小支持度之所有候選子圖形非高頻樣式很少在資料庫中出現的樣式，通常會被視為不感興趣的項目，並使用支持度測量進行刪除，而這樣的樣式為非高頻樣式非高頻樣式：非高頻樣式是一個項目集或一條規則的支持度小於最小支持