數(shù)據(jù)挖掘?qū)д摰?章(編輯修改稿)
2025-05-27 23:56 本頁面
【文章內(nèi)容簡介】 最早發(fā)生時間的最大時間差。 ? 假定最大時間跨度 maxspan=3，下面的表包含了給定的數(shù)據(jù)序列支持和不支持的序列模式。 數(shù)據(jù)序列 s 序列模式 t S支持 t? {1,3} {3,4} {4} {5} {6,7} {8} {3} {4} 是 {1,3} {3,4} {4} {5} {6,7} {8} {3} {6} 是 {1,3} {3,4} {4} {5} {6,7} {8} {1,3} {6} 否 ? 一般， maxspan越長，在數(shù)據(jù)序列中 檢測到模式的可能性就越大。然而，較長的 maxspan也可能捕獲不真實的模式可能涉及陳舊事件。 ? 最大跨度約束影響序列模式發(fā)現(xiàn)算法的支持度計數(shù)。施加最大時間跨度約束之后，有些數(shù)據(jù)序列就不再支持候選模式。 最小間隔和最大間隔約束 ? 時限約束也可以通過限制序列中兩個相繼元素之間的時間差來指定。 ? 如果最大時間差（ maxgap）是一周，則元素中的事件必須在前一個元素的事件出現(xiàn)后的一周之內(nèi)出現(xiàn)。 ? 如果最小時間差（ mingap）是 0，則元素中的事件必須在前一個元素的事件出現(xiàn)之后出現(xiàn)。 ? 假定 maxgap=3， mingap=1，下表給出了模式通過或未通過最大間隔和最小間隔約束的例子。 數(shù)據(jù)序列 s 序列模式 t maxgap mingap {1,3} {3,4} {4} {5} {6,7} {8} {3} {6} 通過 通過 {1,3} {3,4} {4} {5} {6,7} {8} {6} {8} 通過 未通過 {1,3} {3,4} {4} {5} {6,7} {8} {1,3} {6} 未通過 通過 {1,3} {3,4} {4} {5} {6,7} {8} {1} {3} {8} 未通過 未通過 ? 與最大跨度一樣，這些約束也影響序列模式發(fā)現(xiàn)算法的支持度計數(shù)，因為當(dāng)最小間隔和最大間隔約束存在時，有些數(shù)據(jù)序列就不再支持候選模式。 ? 使用最大間隔約束可能違反先驗原理。 ? 為了解釋這一點，考慮圖 75中的數(shù)據(jù)集。如果沒有最小間隔或最大間隔約束， {2},{5}和{2}{3}{5}的支持度都是 60%。然而，如果mingap=0， maxgap=1，則 {2}{5}的支持度下降至 40%，而 {2}{3}{5}的支持度仍然是 60%。這與先驗原理相違背。 例子 Minsup = 50% Examples of Frequent Subsequences: {1,2} s=60% {2,3} s=60% {2,4} s=80% {3} {5} s=80% {1} {2} s=80% {2} {2} s=60% {1} {2,3} s=60% {2} {2,3} s=60% {1,2} {2,3} s=60% O b je ct T imes t amp E v ent sA 1 1, 2, 4A 2 2, 3A 3 5B 1 1, 2B 2 2, 3, 4C 1 1, 2C 2 2, 3, 4C 3 2, 4, 5D 1 2D 2 3, 4D 3 4, 5E 1 1, 3E 2 2, 4 , 5? 定義 鄰接子序列 – 序列 s是序列 w=e1e2…e k的鄰接子序列 (contiguous subsequence)，如果下列條件之一成立 ： – （ 1） s是從 e1或 ek中刪除一個事件后由 w得到。 – （ 2） s是從至少包含兩個事件的任意 ei∈ w中刪除一個 事件后由 w得到。 – （ 3） s是 t的鄰接子序列，而 t是 w的鄰接子序列。 數(shù)據(jù)序列 s 序列模式 t t是 s的鄰接子序列 {1} {2,3} {1} {2} 是 {1,2} {2} {3} {1} {2} 是 {3,4} {1,2} {2,3} {4} {1} {2} 是 {1} {3} {2} {1} {2} 否 {1,2} {1} {3} {2} {1} {2} 否 ? 定義 修訂的先驗原理 – 如果一個 k序列是頻繁的，則它的所有鄰接 (k1)子序列也一定是頻繁的。 ? 在候選剪枝階段，并非所有的 k序列都需要檢查，因為它們中的一些可能違反最大間隔約束。例如，如果 maxgap=1，則不必檢查候選 {1}{2,3}{4}{5}的子序列 {1}{2,3}{5}是否是頻繁的，因為元素{2,3}和 {5}之間的時間差大于一個時間單位。 ? 我們只需要考察 {1}{2,3}{4}{5}的鄰接子序列，包括 {1}{2,3}{4}， {2,3}{4}{5}， {1}{2}{4}{5}和{1}{3}{4}{5}。 窗口大小約束 ? 最后，元素 sj中的事件不必同時出現(xiàn)。可以定義一個窗口大小閾值（ ws）來指定序列模式的任意元素中事件最晚和最早出現(xiàn)之間的最大允許時間差。窗口大小為 0表明模式同一元素中的所有事件必須同時出現(xiàn)。 ? 下面的例子使用 ws=2， mingap=0， maxgap=3，maxspan=∞ 數(shù)據(jù)序列 s 序列模式 t S支持 t？ {1,3} {3,4} {4} {5} {6,7} {8} {3,4} {5} 是 {1,3} {3,4} {4} {5} {6,7} {8} {4,6} {8} 是 {1,3} {3,4} {4} {5} {6,7} {8} {3,4,6} {8} 否 {1,3} {3,4} {4} {5} {6,7} {8} {1,3,4} {6,7,8} 否 子圖模式 ? 關(guān)聯(lián)分析方法應(yīng)用到遠(yuǎn)比項集和序列更復(fù)雜實體。例子包括化學(xué)化合物、 3D蛋白質(zhì)結(jié)構(gòu)、網(wǎng)絡(luò)拓?fù)浜蜆浣Y(jié)構(gòu)的 XML文檔。這些實體可以用圖形表示建模。 ? 在這種類型的數(shù)據(jù)上進(jìn)行數(shù)據(jù)挖掘的任務(wù)是，在圖的集合中發(fā)現(xiàn)一組公共子結(jié)構(gòu)。這樣的任務(wù)稱作 頻繁子圖挖掘 Da tabasesHo mepageRe searchArtificia lInt el li genc eDa ta Mini ng圖與子圖 ? 定義 支持度 – 給定一個圖的集族 ζ ,子圖 g的支持度定義為包含它的所有圖所占的百分比，即 ? 例 考慮 5個圖 G1到 G5，如圖 710所示。右上角的圖 g1是 G1， G3， G4， G5的子圖，因此 s(g1)=4/5=80%。類似地，我們由 s(g2)=60%，因為 g2是 G G2和 G3的子圖；而 s(g3)=40%，因為 g3是 G1和 G3的子圖。 |||},|{|)(????? iii GsGgGgs頻繁子圖挖掘 ? 定義 頻繁子圖挖掘 – 給定圖的集合和支持度閾值 minsup，頻繁子圖挖掘的目標(biāo)是找出所有使得 s(g)=minsup的子圖 g。 ? 本章的討論主要關(guān)注無向連通圖（ undirected，connected graph）。 ? 挖掘頻繁子圖是一項計算量很大的任務(wù)，因為搜索空間是指數(shù)的。為了解釋這項任務(wù)的復(fù)雜性，考慮一個包含 d個實體的數(shù)據(jù)集。在頻繁項集挖掘中，每個實體是一個項，待考察的搜索空間是 2d，這是可能產(chǎn)生的候選項集的個數(shù)。 ? 在頻繁子圖挖掘中，每個實體是一個頂點，并且最多可以有 d1條到其他頂點的邊。假定頂點的標(biāo)號是唯一的，則子圖的總數(shù)是 其中， 是選擇 i個頂點形成子圖的方法數(shù)，而 是子圖的頂點之間邊的最大值。表 78對不同的 d比較了項集和子圖的個數(shù)。 ? ? ??
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1