數(shù)據(jù)挖掘?qū)д摰?章-文庫(kù)吧資料
2025-05-06 23:56本頁(yè)面
【正文】 j中的事件不必同時(shí)出現(xiàn)。例如，如果 maxgap=1，則不必檢查候選 {1}{2,3}{4}{5}的子序列 {1}{2,3}{5}是否是頻繁的，因?yàn)樵貃2,3}和 {5}之間的時(shí)間差大于一個(gè)時(shí)間單位。 數(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} 否 ? 定義 修訂的先驗(yàn)原理 – 如果一個(gè) k序列是頻繁的，則它的所有鄰接 (k1)子序列也一定是頻繁的。 – （ 2） s是從至少包含兩個(gè)事件的任意 ei∈ w中刪除一個(gè) 事件后由 w得到。這與先驗(yàn)原理相違背。如果沒有最小間隔或最大間隔約束， {2},{5}和{2}{3}{5}的支持度都是 60%。 ? 使用最大間隔約束可能違反先驗(yàn)原理。 ? 假定 maxgap=3， mingap=1，下表給出了模式通過或未通過最大間隔和最小間隔約束的例子。 ? 如果最大時(shí)間差（ maxgap）是一周，則元素中的事件必須在前一個(gè)元素的事件出現(xiàn)后的一周之內(nèi)出現(xiàn)。施加最大時(shí)間跨度約束之后，有些數(shù)據(jù)序列就不再支持候選模式。然而，較長(zhǎng)的 maxspan也可能捕獲不真實(shí)的模式可能涉及陳舊事件。 ? 假定最大時(shí)間跨度 maxspan=3，下面的表包含了給定的數(shù)據(jù)序列支持和不支持的序列模式。 ? 圖 77解釋了可以施加在模式上的某些時(shí)限約束。 ? 顯然，該模式被這兩個(gè)學(xué)生支持，盡管他們都沒有同時(shí)選修統(tǒng)計(jì)學(xué)和數(shù)據(jù)庫(kù)系統(tǒng)。 圖 76 { 1 } { 2 } { 3 } { 1 } { 2 5 } { 1 } { 5 } { 3 } { 2 } { 3 } { 4 } { 2 5 } { 3 } { 3 } { 4 } { 5 } { 5 } { 3 4 } { 1 } { 2 } { 3 } { 4 } { 1 } { 2 5 } { 3 } { 1 } { 5 } { 3 4 } { 2 } { 3 } { 4 } { 5 } { 2 5 } { 3 4 } { 1 } { 2 5 } { 3 } F r e q u e n t3 s e q u e n c e sC a n d i d a t eG e n e r a t i o nC a n d i d a t eP r u n i n g時(shí)限約束 ? 模式的事件和元素都施加時(shí)限約束。 ? 支持度計(jì)數(shù) – 在支持度計(jì)數(shù)期間，算法將枚舉屬于一個(gè)特定數(shù)據(jù)序列的所有候選 k序列。我們需要檢查 {1} {2} {4}和 {1} {3} {4}是否是頻繁 3序列。 ? 候選剪枝 – 一個(gè)候選 k序列被剪枝，如果它的 (k1)序列最少有一個(gè)是非頻繁的 。 – {1} {5} {3,4} 通過合并 {1} {5} {3}和 {5} {3,4}得到 。 ? 例子 – {1} {2} {3} {4}通過合并 {1} {2} {3}和 {2} {3} {4}得到 。 ? 為了避免重復(fù)產(chǎn)生候選，傳統(tǒng)的 Apriori算法僅當(dāng)前k1項(xiàng)相同時(shí)才合并一對(duì)頻繁 k項(xiàng)集。 – 包含特定 k序列的任何數(shù)據(jù)序列必然包含該 k序列的所有 (k1)序列 。例如，{1,2}和 {2,1}表示同一個(gè)項(xiàng)集，而 {i1}{i2}和 {i2}{i1}對(duì)應(yīng)于不同的序列，因此必須分別產(chǎn)生。給定兩個(gè)項(xiàng) i1和 i2，只能產(chǎn)生一個(gè)候選 2項(xiàng)集 {i1， i2}，但卻可以產(chǎn)生許多候選 2序列，如{i1,i2}, {i1}{i2}, {i2,i2}, {i1,i1} 。 例子 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提取序列模式：蠻力方法 ? 給定 n個(gè)事件的集族 : i1, i2, i3, …, i n ? 候選 1序列 : {i1}, {i2}, {i3}, …, {i n} ? 候選 2序列 : {i1, i2}, {i1, i3}, …, {i n1} {in}, {i1} {i1}, {i1} {i2}, …, {i n1} {in} ? 候選 3序列 : {i1, i2 , i3}, {i1, i2 , i4}, …, {i 1, i2} {i1}, {i1, i2} {i2}, …, {i1} {i1 , i2}, {i1} {i1 , i3}, …, {i 1} {i1} {i1}, {i1} {i1} {i2}, … ? 候選序列的個(gè)數(shù)比候選項(xiàng)集的個(gè)數(shù)大得多。如果序列 s的支持度大于或等于用戶指定的閾值 minsup，則稱 s是一個(gè)序列模式（或頻繁序列）。 Sequence E1 E2 E1 E3 E2 E3 E4 E2 Element (Transaction) Event (Item) 序列數(shù)據(jù)的例子 子序列（ Subsequence） ? 序列 t是另一個(gè)序列 s的子序列（ subsequence），如果 t中每個(gè)有序元素都是 s中一個(gè)有序元素的子集。 ? 對(duì)于識(shí)別動(dòng)態(tài)系統(tǒng)的重現(xiàn)特征，或預(yù)測(cè)特定事件的未來(lái)發(fā)生，序列信息可能是非常有價(jià)值的?？梢允褂眠@種信息，將顧客在一段時(shí)間內(nèi)的購(gòu)物拼接成事務(wù)序列。規(guī)則 X ?Y是冗余的，如果存在一個(gè)更一般的規(guī)則 X’ ?Y’，其中 X‘是 X的祖先， Y’是 Y的祖先，并且兩個(gè)規(guī)則具有非常相似的置信度。 – （ 2）概念分層的引入增加了關(guān)聯(lián)分析的計(jì)算時(shí)間。如：事務(wù) {DVD，普通面包 }可以擴(kuò)展為 {DVD，普通面包，家電，電子產(chǎn)品，面包，食品 } – 然后對(duì)擴(kuò)展的數(shù)據(jù)庫(kù)使用如 Apriori等已有的算法來(lái)發(fā)現(xiàn)跨越多個(gè)概念層的規(guī)則。 – （ 2）在較低層發(fā)現(xiàn)的規(guī)則傾向于過于特殊，可能不如較高層的規(guī)則令人感興趣。 ? 概念分層可以用有向無(wú)環(huán)圖表示。隨包含該詞的文檔個(gè)數(shù)增加而單調(diào)遞增。 ?另一種方法是采用 minapriori方法。 ?一種方法是將數(shù)據(jù)變換成 0/1矩陣；其中，如果規(guī)范化詞頻超過某個(gè)閾值 t，則值為 1，否則為 0。 ?在文本挖掘中，分析者更感興趣的是發(fā)現(xiàn)詞之間的關(guān)聯(lián)（例如：數(shù)據(jù)和挖掘）。 – （ 2）如果區(qū)間太窄，則可能因?yàn)槿狈χС侄榷ツ承┮?guī)則 – 例如：當(dāng)區(qū)間寬度為 4歲時(shí)，上面的兩個(gè)規(guī)則變?yōu)? [16,20) ?網(wǎng)上聊天 =是（ s=%， %） [20,24) ?網(wǎng)上聊天 =是（ s=%， %） – （ 3）當(dāng)區(qū)間寬度為 8歲時(shí)，上面的兩個(gè)規(guī)則變?yōu)? [44,52) ?網(wǎng)上聊天 =否（
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1