數(shù)據(jù)挖掘應(yīng)用ApplicationsofDataMining

數(shù)據(jù)挖掘應(yīng)用ApplicationsofDataMining目錄關(guān)聯(lián)規(guī)則挖掘聚類分析分類與預(yù)測Web挖掘流數(shù)據(jù)挖掘隱私保護(hù)數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘簡介關(guān)聯(lián)規(guī)則基本模型關(guān)聯(lián)規(guī)則價值衡量與發(fā)展關(guān)聯(lián)規(guī)則簡介關(guān)聯(lián)規(guī)則反映一個事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果兩個或者多個事物之間存在一定的關(guān)聯(lián)關(guān)系，那么，其中一個事物就能夠通過其他事物預(yù)測到。典型的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)問題是對超市中的貨籃數(shù)據(jù)（MarketBasket）進(jìn)行分析。通過發(fā)現(xiàn)顧客放入貨籃中的不同商品之間的關(guān)系來分析顧客的購買習(xí)慣。什么是關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘

首先被Agrawal,ImielinskiandSwami在1993年的SIGMOD會議上提出在事務(wù)、關(guān)系數(shù)據(jù)庫中的項(xiàng)集和對象中發(fā)現(xiàn)頻繁模式、關(guān)聯(lián)規(guī)則、相關(guān)性或者因果結(jié)構(gòu)頻繁模式:數(shù)據(jù)庫中頻繁出現(xiàn)的項(xiàng)集目的:發(fā)現(xiàn)數(shù)據(jù)中的規(guī)律超市數(shù)據(jù)中的什么產(chǎn)品會一起購買？—啤酒和尿布在買了一臺PC之后下一步會購買?哪種DNA對這種藥物敏感?我們?nèi)绾巫詣訉eb文檔進(jìn)行分類?頻繁模式挖掘的重要性許多重要數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)關(guān)聯(lián)、相關(guān)性、因果性序列模式、空間模式、時間模式、多維關(guān)聯(lián)分類、聚類分析更加廣泛的用處購物籃分析、交叉銷售、直銷點(diǎn)擊流分析、DNA序列分析等等關(guān)聯(lián)規(guī)則基本模型關(guān)聯(lián)規(guī)則基本模型Apriori算法關(guān)聯(lián)規(guī)則基本模型IBM公司Almaden研究中心的R.Agrawal首先提出關(guān)聯(lián)規(guī)則模型，并給出求解算法AIS。隨后又出現(xiàn)了SETM和Apriori等算法。其中，Apriori是關(guān)聯(lián)規(guī)則模型中的經(jīng)典算法。

給定一組事務(wù)產(chǎn)生所有的關(guān)聯(lián)規(guī)則滿足最小支持度和最小可信度關(guān)聯(lián)規(guī)則基本模型（續(xù)）設(shè)I={i1,i2,…,im}為所有項(xiàng)目的集合，D為事務(wù)數(shù)據(jù)庫，事務(wù)T是一個項(xiàng)目子集（TI）。每一個事務(wù)具有唯一的事務(wù)標(biāo)識TID。設(shè)A是一個由項(xiàng)目構(gòu)成的集合，稱為項(xiàng)集。事務(wù)T包含項(xiàng)集A，當(dāng)且僅當(dāng)AT。如果項(xiàng)集A中包含k個項(xiàng)目，則稱其為k項(xiàng)集。項(xiàng)集A在事務(wù)數(shù)據(jù)庫D中出現(xiàn)的次數(shù)占D中總事務(wù)的百分比叫做項(xiàng)集的支持度。如果項(xiàng)集的支持度超過用戶給定的最小支持度閾值，就稱該項(xiàng)集是頻繁項(xiàng)集（或大項(xiàng)集）。關(guān)聯(lián)規(guī)則基本模型（續(xù)）關(guān)聯(lián)規(guī)則是形如XY的邏輯蘊(yùn)含式，其中XI，YI，且XY=。如果事務(wù)數(shù)據(jù)庫D中有s%的事務(wù)包含XY，則稱關(guān)聯(lián)規(guī)則XY的支持度為s%，實(shí)際上，支持度是一個概率值。若項(xiàng)集X的支持度記為support(X)，規(guī)則的信任度為support(XY)／support(X)。這是一個條件概率P(Y|X)。也就是：support(XY)=P(XY)confidence(XY)=P(Y|X)規(guī)則度量：支持度與可信度查找所有的規(guī)則X&YZ具有最小支持度和可信度支持度,s,一次交易中包含{X、Y、Z}的可能性可信度,c,

包含{X、Y}的交易中也包含Z的條件概率設(shè)最小支持度為50%,最小可信度為50%,則可得到AC(50%,66.6%)CA(50%,100%)買尿布的客戶二者都買的客戶買啤酒的客戶關(guān)聯(lián)規(guī)則基本模型（續(xù)）關(guān)聯(lián)規(guī)則就是支持度和信任度分別滿足用戶給定閾值的規(guī)則。

發(fā)現(xiàn)關(guān)聯(lián)規(guī)則需要經(jīng)歷如下兩個步驟：

找出所有頻繁項(xiàng)集。

由頻繁項(xiàng)集生成滿足最小信任度閾值的規(guī)則。

Letmin_support=50%,min_conf=50%:AC(50%,66.7%)CA(50%,100%)CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTransaction-idItemsbought10A,B,C20A,C30A,D40B,E,FForruleA

C:support=support({A}{C})=50%confidence=support({A}{C})/support({A})=66.6%Min.support50%Min.confidence50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%Apriori算法的步驟Apriori算法命名源于算法使用了頻繁項(xiàng)集性質(zhì)的先驗(yàn)（Prior）知識。

Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個步驟：通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項(xiàng)集，即支持度不低于用戶設(shè)定的閾值的項(xiàng)集；利用頻繁項(xiàng)集構(gòu)造出滿足用戶最小信任度的規(guī)則。挖掘或識別出所有頻繁項(xiàng)集是該算法的核心，占整個計算量的大部分。頻繁項(xiàng)集為了避免計算所有項(xiàng)集的支持度（實(shí)際上頻繁項(xiàng)集只占很少一部分），Apriori算法引入潛在頻繁項(xiàng)集的概念。若潛在頻繁k項(xiàng)集的集合記為Ck，頻繁k項(xiàng)集的集合記為Lk，m個項(xiàng)目構(gòu)成的k項(xiàng)集的集合為

，則三者之間滿足關(guān)系LkCk

。構(gòu)成潛在頻繁項(xiàng)集所遵循的原則是“頻繁項(xiàng)集的子集必為頻繁項(xiàng)集”。

關(guān)聯(lián)規(guī)則的性質(zhì)：

性質(zhì)6.1頻繁項(xiàng)集的子集必為頻繁項(xiàng)集。性質(zhì)6.2非頻繁項(xiàng)集的超集一定是非頻繁的。Apriori算法運(yùn)用性質(zhì)6.1，通過已知的頻繁項(xiàng)集構(gòu)成長度更大的項(xiàng)集，并將其稱為潛在頻繁項(xiàng)集。潛在頻繁k項(xiàng)集的集合Ck是指由有可能成為頻繁k項(xiàng)集的項(xiàng)集組成的集合。以后只需計算潛在頻繁項(xiàng)集的支持度，而不必計算所有不同項(xiàng)集的支持度，因此在一定程度上減少了計算量。Apriori算法(1)L1={頻繁1項(xiàng)集};(2)for(k=2;Lk-1;k++)dobegin(3)Ck=apriori_gen(Lk-1);//新的潛在頻繁項(xiàng)集

(4)foralltransactions

tDdobegin(5)Ct=subset(Ck,t);//t中包含的潛在頻繁項(xiàng)集

(6)forallcandidatescCtdo(7)c.count++;(8)end;(9)Lk={cCk|c.countminsup}(10)end;(11)Answer=實(shí)例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2VisualizationofAssociationRules:PaneGraphVisualizationofAssociationRules:RuleGraph提高Apriori算法的方法Hash-baseditemsetcounting（散列項(xiàng)集計數(shù)）Transactionreduction（事務(wù)壓縮）Partitioning（劃分）Sampling（采樣）關(guān)聯(lián)規(guī)則挖掘算法Agrawal等人提出的AIS，Apriori和AprioriTidCumulate和Stratify，Houstsma等人提出的SETMPark等人提出的DHPSavasere等人的PARTITIONHan等人提出的不生成候選集直接生成頻繁模式FPGrowth其中最有效和有影響的算法為Apriori，DHP和PARTITION，F(xiàn)PGrowth。用Frequent-Patterntree(FP-tree)結(jié)構(gòu)壓縮數(shù)據(jù)庫,高度濃縮，同時對頻繁集的挖掘又完備的避免代價較高的數(shù)據(jù)庫掃描開發(fā)一種高效的基于FP-tree的頻繁集挖掘算法采用分而治之的方法學(xué)：分解數(shù)據(jù)挖掘任務(wù)為小任務(wù)避免生成關(guān)聯(lián)規(guī)則:只使用部分?jǐn)?shù)據(jù)庫!挖掘頻繁集不用生成候選集{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1頭表Itemfrequencyheadf 4c 4a 3b 3m 3p 3最小支持度=0.5TID Itemsbought (ordered)frequentitems100 {f,a,c,d,g,i,m,p}

{f,c,a,m,p}200 {a,b,c,f,l,m,o}

{f,c,a,b,m}300

{b,f,h,j,o}

{f,b}400

{b,c,k,s,p}

{c,b,p}500

{a,f,c,e,l,p,m,n}

{f,c,a,m,p}步驟:掃描數(shù)據(jù)庫一次，得到頻繁1-項(xiàng)集把項(xiàng)按支持度遞減排序再一次掃描數(shù)據(jù)庫，建立FP-tree用交易數(shù)據(jù)庫建立FP-tree完備:不會打破交易中的任何模式包含了頻繁模式挖掘所需的全部信息緊密去除不相關(guān)信息—不包含非頻繁項(xiàng)支持度降序排列:支持度高的項(xiàng)在FP-tree中共享的機(jī)會也高決不會比原數(shù)據(jù)庫大（如果不計算樹節(jié)點(diǎn)的額外開銷)例子:對于Connect-4數(shù)據(jù)庫,壓縮率超過100FP-tree結(jié)構(gòu)的好處基本思想(分而治之)用FP-tree地歸增長頻繁集方法對每個項(xiàng)，生成它的條件模式庫,然后是它的條件FP-tree對每個新生成的條件FP-tree，重復(fù)這個步驟直到結(jié)果FP-tree為空,或只含維一的一個路徑(此路徑的每個子路徑對應(yīng)的項(xiàng)集都是頻繁集)用FP-tree挖掘頻繁集為FP-tree中的每個節(jié)點(diǎn)生成條件模式庫用條件模式庫構(gòu)造對應(yīng)的條件FP-tree遞歸構(gòu)造條件FP-trees同時增長其包含的頻繁集如果條件FP-tree只包含一個路徑，則直接生成所包含的頻繁集。挖掘FP-tree的主要步驟從FP-tree的頭表開始按照每個頻繁項(xiàng)的連接遍歷FP-tree列出能夠到達(dá)此項(xiàng)的所有前綴路徑，得到條件模式庫條件模式庫item cond.patternbasec f:3a fc:3b fca:1,f:1,c:1m fca:2,fcab:1p fcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1頭表Itemfrequencyheadf 4c 4a 3b 3m 3p 3步驟1:從FP-tree到條件模式庫節(jié)點(diǎn)褳接任何包含ai,

的可能頻繁集，都可以從FP-tree頭表中的ai沿著ai的節(jié)點(diǎn)鏈接得到前綴路徑要計算路徑P中包含節(jié)點(diǎn)ai的頻繁集，只要考察到達(dá)ai的路徑前綴即可，且其支持度等于節(jié)點(diǎn)ai的支持度FP-tree支持條件模式庫構(gòu)造的屬性對每個模式庫計算庫中每個項(xiàng)的支持度用模式庫中的頻繁項(xiàng)建立FP-treem-條件模式庫:fca:2,fcab:1{}f:3c:3a:3m-conditionalFP-treeAllfrequentpatternsconcerningmm,fm,cm,am,fcm,fam,cam,fcam{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1頭表Itemfrequencyheadf 4c 4a 3b 3m 3p 3步驟2:建立條件FP-treeEmptyEmptyf{(f:3)}|c{(f:3)}c{(f:3,c:3)}|a{(fc:3)}aEmpty{(fca:1),(f:1),(c:1)}b{(f:3,c:3,a:3)}|m{(fca:2),(fcab:1)}m{(c:3)}|p{(fcam:2),(cb:1)}p條件FP-tree條件模式庫項(xiàng)通過建立條件模式庫得到頻繁集{}f:3c:3a:3m-條件

FP-tree“am”的條件模式庫:(fc:3){}f:3c:3am-條件FP-tree“cm”的條件模式:(f:3){}f:3cm-條件FP-tree“cam”條件模式庫:(f:3){}f:3cam-條件FP-tree第3步:遞歸挖掘條件FP-tree關(guān)聯(lián)規(guī)則價值衡量與發(fā)展關(guān)聯(lián)規(guī)則價值衡量關(guān)聯(lián)規(guī)則最新進(jìn)展規(guī)則價值衡量

對關(guān)聯(lián)規(guī)則的評價與價值衡量涉及兩個層面：系統(tǒng)客觀的層面用戶主觀的層面系統(tǒng)客觀層面

使用“支持度和信任度”框架可能會產(chǎn)生一些不正確的規(guī)則。只憑支持度和信任度閾值未必總能找出符合實(shí)際的規(guī)則。

用戶主觀層面

只有用戶才能決定規(guī)則的有效性、可行性。所以，應(yīng)該將用戶的需求和系統(tǒng)更加緊密地結(jié)合起來。

可以采用基于約束（Consraint-based）的數(shù)據(jù)挖掘方法。具體約束的內(nèi)容有：數(shù)據(jù)約束、限定數(shù)據(jù)挖掘的維和層次、規(guī)則約束。如果把某些約束條件與算法緊密結(jié)合，既能提高數(shù)據(jù)挖掘效率，又能明確數(shù)據(jù)挖掘的目標(biāo)。

關(guān)聯(lián)規(guī)則新進(jìn)展

在基于一維布爾型關(guān)聯(lián)規(guī)則的算法研究中先后出現(xiàn)了AIS、SETM等數(shù)據(jù)挖掘算法。R.Agrawal等人提出的Apriori是經(jīng)典算法。隨后的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法大多數(shù)建立在Apriori算法基礎(chǔ)上，或進(jìn)行改造，或衍生變種。比如AprioriTid和AprioriHybrid算法。Lin等人提出解決規(guī)則挖掘算法中的數(shù)據(jù)傾斜問題，從而使算法具有較好的均衡性。Park等人提出把哈希表結(jié)構(gòu)用于關(guān)聯(lián)規(guī)則挖掘。關(guān)聯(lián)規(guī)則新進(jìn)展（續(xù)）數(shù)據(jù)挖掘工作是在海量數(shù)據(jù)庫上進(jìn)行的，數(shù)據(jù)庫的規(guī)模對規(guī)則的挖掘時間有很大影響。Agrawal首先提出事務(wù)縮減技術(shù)，Han和Park等人也分別在減小數(shù)據(jù)規(guī)模上做了一些工作。抽樣的方法是由Toivonen提出的。Brin等人采用動態(tài)項(xiàng)集計數(shù)方法求解頻繁項(xiàng)集。Aggarwal提出用圖論和格的理論求解頻繁項(xiàng)集的方法。Prutax算法就是用格遍歷的辦法求解頻繁項(xiàng)集。關(guān)聯(lián)規(guī)則新進(jìn)展（續(xù)）關(guān)聯(lián)規(guī)則模型有很多擴(kuò)展，如順序模型挖掘，在順序時間段上進(jìn)行挖掘等。還有挖掘空間關(guān)聯(lián)規(guī)則，挖掘周期性關(guān)聯(lián)規(guī)則，挖掘負(fù)關(guān)聯(lián)規(guī)則，挖掘交易內(nèi)部關(guān)聯(lián)規(guī)則等。Guralnik提出順序時間段問題的形式描述語言，以便描述用戶感興趣的時間段，并且構(gòu)建了有效的數(shù)據(jù)結(jié)構(gòu)SP樹（順序模式樹）和自底向上的數(shù)據(jù)挖掘算法。最大模式挖掘是Bayardo等人提出來的。關(guān)聯(lián)規(guī)則新進(jìn)展（續(xù)）隨后人們開始探討頻率接近項(xiàng)集。Pei給出了一種有效的數(shù)據(jù)挖掘算法。B.?zden等人的周期性關(guān)聯(lián)規(guī)則是針對具有時間屬性的事務(wù)數(shù)據(jù)庫，發(fā)現(xiàn)在規(guī)律性的時間間隔中滿足最小支持度和信任度的規(guī)則。貝爾實(shí)驗(yàn)室的S.Ramaswamy等人進(jìn)一步發(fā)展了周期性關(guān)聯(lián)規(guī)則，提出挖掘符合日歷的關(guān)聯(lián)規(guī)則（CalendricAssociationRules）算法，用以進(jìn)行市場貨籃分析。Fang等人給出冰山查詢數(shù)據(jù)挖掘算法。關(guān)聯(lián)規(guī)則新進(jìn)展（續(xù)）T.Hannu等人把負(fù)邊界引入規(guī)則發(fā)現(xiàn)算法中，每次挖掘不僅保存頻繁項(xiàng)集，而且同時保存負(fù)邊界，達(dá)到下次挖掘時減少掃描次數(shù)的目的。Srikant等人通過研究關(guān)聯(lián)規(guī)則的上下文，提出規(guī)則興趣度尺度用以剔除冗余規(guī)則。Zakia還用項(xiàng)集聚類技術(shù)求解最大的近似潛在頻繁項(xiàng)集，然后用格遷移思想生成每個聚類中的頻繁項(xiàng)集。CAR，也叫分類關(guān)聯(lián)規(guī)則，是Lin等人提出的一種新的分類方法，是分類技術(shù)與關(guān)聯(lián)規(guī)則思想相結(jié)合的產(chǎn)物，并給出解決方案和算法。關(guān)聯(lián)規(guī)則新進(jìn)展（續(xù)）Cheung等人提出關(guān)聯(lián)規(guī)則的增量算法。Thomas等人把負(fù)邊界的概念引入其中，進(jìn)一步發(fā)展了增量算法。如，基于Apriori框架的并行和分布式數(shù)據(jù)挖掘算法。Oates等人將MSDD算法改造為分布式算法。還有其他的并行算法，如利用垂直數(shù)據(jù)庫探求項(xiàng)集聚類等。聚類分析聚類分析簡介聚類分析中的數(shù)據(jù)類型劃分方法層次方法聚類（Clustering）分析簡介聚類（Clustering）是對物理的或抽象的對象集合分組的過程。聚類生成的組稱為簇（Cluster），簇是數(shù)據(jù)對象的集合。簇內(nèi)部的任意兩個對象之間具有較高的相似度，而屬于不同簇的兩個對象間具有較高的相異度。相異度可以根據(jù)描述對象的屬性值計算，對象間的距離是最常采用的度量指標(biāo)。聚類分析簡介（續(xù)）聚類分析是數(shù)據(jù)分析中的一種重要技術(shù)，它的應(yīng)用極為廣泛。許多領(lǐng)域中都會涉及聚類分析方法的應(yīng)用與研究工作，如數(shù)據(jù)挖掘、統(tǒng)計學(xué)、機(jī)器學(xué)習(xí)、模式識別、生物學(xué)、空間數(shù)據(jù)庫技術(shù)、電子商務(wù)等。聚類分析簡介（續(xù)）從統(tǒng)計學(xué)的觀點(diǎn)看，聚類分析是通過數(shù)據(jù)建模簡化數(shù)據(jù)的一種方法。傳統(tǒng)的統(tǒng)計聚類分析方法包括系統(tǒng)聚類法、分解法、加入法、動態(tài)聚類法、有序樣品聚類、有重疊聚類和模糊聚類等。采用k-均值、k-中心點(diǎn)等算法的聚類分析工具已被加入到許多著名的統(tǒng)計分析軟件包中，如SPSS、SAS等。聚類分析簡介（續(xù)）從機(jī)器學(xué)習(xí)的角度講，簇相當(dāng)于隱藏模式。聚類是搜索簇的無監(jiān)督學(xué)習(xí)過程。與分類不同，無監(jiān)督學(xué)習(xí)不依賴預(yù)先定義的類或帶類標(biāo)記的訓(xùn)練實(shí)例，需要由聚類學(xué)習(xí)算法自動確定標(biāo)記，而分類學(xué)習(xí)的實(shí)例或數(shù)據(jù)對象有類別標(biāo)記。聚類是觀察式學(xué)習(xí)，而不是示例式的學(xué)習(xí)。聚類分析簡介（續(xù)）從實(shí)際應(yīng)用的角度看，聚類分析是數(shù)據(jù)挖掘的主要任務(wù)之一。就數(shù)據(jù)挖掘功能而言，聚類能夠作為一個獨(dú)立的工具獲得數(shù)據(jù)的分布狀況，觀察每一簇數(shù)據(jù)的特征，集中對特定的聚簇集合作進(jìn)一步地分析。聚類分析還可以作為其他數(shù)據(jù)挖掘任務(wù)（如分類、關(guān)聯(lián)規(guī)則）的預(yù)處理步驟。數(shù)據(jù)挖掘領(lǐng)域主要研究面向大型數(shù)據(jù)庫、數(shù)據(jù)倉庫的高效實(shí)用的聚類分析算法。聚類的常規(guī)應(yīng)用模式識別空間數(shù)據(jù)分析在GIS中，通過聚類發(fā)現(xiàn)特征空間來建立主題索引；在空間數(shù)據(jù)挖掘中，檢測并解釋空間中的簇；圖象處理經(jīng)濟(jì)學(xué)(尤其是市場研究方面)WWW文檔分類分析WEB日志數(shù)據(jù)來發(fā)現(xiàn)相似的訪問模式應(yīng)用聚類分析的例子市場銷售:

幫助市場人員發(fā)現(xiàn)客戶中的不同群體，然后用這些知識來開展一個目標(biāo)明確的市場計劃；土地使用:

在一個陸地觀察數(shù)據(jù)庫中標(biāo)識那些土地使用相似的地區(qū)；保險:

對購買了汽車保險的客戶，標(biāo)識那些有較高平均賠償成本的客戶；城市規(guī)劃:

根據(jù)類型、價格、地理位置等來劃分不同類型的住宅；地震研究:

根據(jù)地質(zhì)斷層的特點(diǎn)把已觀察到的地震中心分成不同的類；什么是一個好的聚類方法?一個好的聚類方法要能產(chǎn)生高質(zhì)量的聚類結(jié)果——簇，這些簇要具備以下兩個特點(diǎn)：高的簇內(nèi)相似性低的簇間相似性聚類結(jié)果的好壞取決于該聚類方法采用的相似性評估方法以及該方法的具體實(shí)現(xiàn)；聚類方法的好壞還取決與該方法是能發(fā)現(xiàn)某些還是所有的隱含模式；聚類分析中的數(shù)據(jù)類型聚類分析主要針對的數(shù)據(jù)類型包括區(qū)間標(biāo)度變量、二元變量、標(biāo)稱變量、序數(shù)型變量，以及由這些變量類型構(gòu)成的復(fù)合類型。一些基于內(nèi)存的聚類算法通常采用數(shù)據(jù)矩陣和相異度矩陣兩種典型的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)矩陣（DataMatrix）設(shè)有n個對象，可用p個變量（屬性）描述每個對象，則np矩陣稱為數(shù)據(jù)矩陣。數(shù)據(jù)矩陣是對象-變量結(jié)構(gòu)的數(shù)據(jù)表達(dá)方式。

相異度矩陣（DissimilarityMatrix）

按n個對象兩兩間的相異度構(gòu)建n階矩陣（因?yàn)橄喈惗染仃囀菍ΨQ的，只需寫出上三角或下三角即可）：

其中d(i,j)表示對象i與j的相異度，它是一個非負(fù)的數(shù)值。當(dāng)對象i和j越相似或“接近”時，d(i,j)值越接近0；而對象i和j越不相同或相距“越遠(yuǎn)”時，d(i,j)值越大。顯然，d(i,j)=d(j,i)，d(i,i)=0。相異度矩陣是對象-對象結(jié)構(gòu)的一種數(shù)據(jù)表達(dá)方式。

評價聚類質(zhì)量差異度/相似度矩陣:相似度通常用距離函數(shù)來表示；有一個單獨(dú)的質(zhì)量評估函數(shù)來評判一個簇的好壞；對不同類型的變量，距離函數(shù)的定義通常是不同的；根據(jù)實(shí)際的應(yīng)用和數(shù)據(jù)的語義，在計算距離的時候，不同的變量有不同的權(quán)值相聯(lián)系；很難定義“足夠相似了”或者“足夠好了”只能憑主觀確定；聚類分析中的數(shù)據(jù)類型區(qū)間標(biāo)度變量；二元變量；標(biāo)稱型，序數(shù)型變量；混合類型變量；對象間距離的計算設(shè)兩個p維向量xi

=

(xi1,xi2,…,xip)T和xj=(xj1,xj2,…,xjp)T分別表示兩個對象，有多種形式的距離度量可以采用。

閔可夫斯基（Minkowski）距離：

曼哈坦（Manhattan）距離：

歐幾里得（Euclidean）距離：

切比雪夫（Chebyshev）距離：

馬哈拉諾比斯（Mahalanobis）距離：

劃分方法簡介對于一個給定的n個對象或元組的數(shù)據(jù)庫，采用目標(biāo)函數(shù)最小化的策略，通過迭代把數(shù)據(jù)分成k個劃分塊，每個劃分塊為一個簇，這就是劃分方法。

劃分方法滿足兩個條件：（1）每個分組至少包含一個對象；（2）每個對象必屬于且僅屬于某一個分組。

常見的劃分方法有k-均值方法和k-中心點(diǎn)方法。其他方法大都是這兩種方法的變形。

k-均值算法

k-均值聚類算法的核心思想是通過迭代把數(shù)據(jù)對象劃分到不同的簇中，以求目標(biāo)函數(shù)最小化，從而使生成的簇盡可能地緊湊和獨(dú)立。首先，隨機(jī)選取k個對象作為初始的k個簇的質(zhì)心；然后，將其余對象根據(jù)其與各個簇質(zhì)心的距離分配到最近的簇；再求新形成的簇的質(zhì)心。這個迭代重定位過程不斷重復(fù)，直到目標(biāo)函數(shù)最小化為止。

k-均值算法

輸入期望得到的簇的數(shù)目k，n個對象的數(shù)據(jù)庫。輸出使得平方誤差準(zhǔn)則函數(shù)最小化的k個簇。方法選擇k個對象作為初始的簇的質(zhì)心；repeat計算對象與各個簇的質(zhì)心的距離，將對象劃分到距離其最近的簇；重新計算每個新簇的均值；until簇的質(zhì)心不再變化。K-均值算法

012345678910012345678910012345678910012345678910K=2ArbitrarilychooseKobjectasinitialclustercenterAssigneachobjectstomostsimilarcenterUpdatetheclustermeansUpdatetheclustermeansreassignreassign層次聚類層次聚類按數(shù)據(jù)分層建立簇，形成一棵以簇為節(jié)點(diǎn)的樹，稱為聚類圖。

按自底向上層次分解，則稱為凝聚的層次聚類。

按自頂向下層次分解，就稱為分裂的層次聚類。

凝聚的和分裂的層次聚類

凝聚的層次聚類采用自底向上的策略，開始時把每個對象作為一個單獨(dú)的簇，然后逐次對各個簇進(jìn)行適當(dāng)合并，直到滿足某個終止條件。

分裂的層次聚類采用自頂向下的策略，與凝聚的層次聚類相反，開始時將所有對象置于同一個簇中，然后逐次將簇分裂為更小的簇，直到滿足某個終止條件。

凝聚的和分裂的層次聚類

層次聚類方法的優(yōu)缺點(diǎn)層次聚類方法的優(yōu)點(diǎn)在于可以在不同粒度水平上對數(shù)據(jù)進(jìn)行探測，而且容易實(shí)現(xiàn)相似度量或距離度量。單純的層次聚類算法終止條件含糊，而且執(zhí)行合并或分裂簇的操作后不可修正，這很可能導(dǎo)致聚類結(jié)果質(zhì)量很低。由于需要檢查和估算大量的對象或簇才能決定簇的合并或分裂，所以這種方法的可擴(kuò)展性較差。通常考慮把層次聚類方法與其他方法（如迭代重定位方法）相結(jié)合來解決實(shí)際聚類問題。層次聚類和其他聚類方法的有效集成可以形成多階段聚類，能夠改善聚類質(zhì)量。這類方法包括BIRCH、CURE、ROCK、Chameleon等。

分類與預(yù)測簡介決策樹簡介分類預(yù)測分類分類的目的是提出一個分類函數(shù)或分類模型（即分類器），通過分類器將數(shù)據(jù)對象映射到某一個給定的類別中。數(shù)據(jù)分類可以分為兩步進(jìn)行。第一步建立模型，用于描述給定的數(shù)據(jù)集合。通過分析由屬性描述的數(shù)據(jù)集合來建立反映數(shù)據(jù)集合特性的模型。這一步也稱作有監(jiān)督的學(xué)習(xí)，導(dǎo)出模型是基于訓(xùn)練數(shù)據(jù)集的，訓(xùn)練數(shù)據(jù)集是已知類標(biāo)記的數(shù)據(jù)對象。第二步使用模型對數(shù)據(jù)對象進(jìn)行分類。首先應(yīng)該評估模型的分類準(zhǔn)確度，如果模型準(zhǔn)確度可以接受，就可以用它來對未知類標(biāo)記的對象進(jìn)行分類。訓(xùn)練集與測試集訓(xùn)練集：數(shù)據(jù)庫中為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練集。訓(xùn)練集中的單個元組稱為訓(xùn)練樣本,每個訓(xùn)練樣本有一個類別標(biāo)記。一個具體樣本的形式可為:(v1,v2,...,vn;c);其中vi表示屬性值,c表示類別。測試集：用于評估分類模型的準(zhǔn)確率。

分類的兩個階段a.模型訓(xùn)練階段

訓(xùn)練集b.使用模型分類階段評估準(zhǔn)確率（測試集）對類標(biāo)號未知的新數(shù)據(jù)分類

分類模型的構(gòu)造方法機(jī)器學(xué)習(xí)方法：決策樹法知識表示是決策樹規(guī)則歸納知識表示是產(chǎn)生式規(guī)則神經(jīng)網(wǎng)絡(luò)方法：BP算法,模型表示是前向反饋神經(jīng)網(wǎng)絡(luò)模型粗糙集(roughset)知識表示是產(chǎn)生式規(guī)則預(yù)測預(yù)測的目的是從歷史數(shù)據(jù)記錄中自動推導(dǎo)出對給定數(shù)據(jù)的推廣描述，從而能夠?qū)κ孪任粗臄?shù)據(jù)進(jìn)行預(yù)測。分類和回歸是兩類主要的預(yù)測問題。分類是預(yù)測離散的值，回歸是預(yù)測連續(xù)值。用預(yù)測法預(yù)測類標(biāo)號為分類用預(yù)測法預(yù)測連續(xù)值為預(yù)測評估分類和預(yù)測方法的五條標(biāo)準(zhǔn)預(yù)測的準(zhǔn)確率計算速度魯棒性可伸縮性可解釋性決策樹決策樹學(xué)習(xí)簡介決策樹實(shí)例決策樹學(xué)習(xí)的算法決策樹學(xué)習(xí)簡介決策樹（DecisionTree）學(xué)習(xí)是以樣本為基礎(chǔ)的歸納學(xué)習(xí)方法。決策樹的表現(xiàn)形式是類似于流程圖的樹結(jié)構(gòu)，在決策樹的內(nèi)部節(jié)點(diǎn)進(jìn)行屬性值測試，并根據(jù)屬性值判斷由該節(jié)點(diǎn)引出的分支，在決策樹的葉節(jié)點(diǎn)得到結(jié)論。內(nèi)部節(jié)點(diǎn)是屬性或?qū)傩缘募?，葉節(jié)點(diǎn)代表樣本所屬的類或類分布。經(jīng)由訓(xùn)練樣本集產(chǎn)生一棵決策樹后，為了對未知樣本集分類，需要在決策樹上測試未知樣本的屬性值。測試路徑由根節(jié)點(diǎn)到某個葉節(jié)點(diǎn)，葉節(jié)點(diǎn)代表的類就是該樣本所屬的類。決策樹實(shí)例關(guān)于PlayTennis的決策樹如圖所示：決策樹學(xué)習(xí)的算法決策樹學(xué)習(xí)的基本算法是貪心算法，采用自頂向下的遞歸方式構(gòu)造決策樹。Hunt等人于1966年提出的概念學(xué)習(xí)系統(tǒng)CLS是最早的決策樹算法，以后的許多決策樹算法都是對CLS算法的改進(jìn)或由CLS衍生而來。Quinlan于1979年提出了著名的ID3方法。以ID3為藍(lán)本的C4.5是一個能處理連續(xù)屬性的算法。其他決策樹方法還有ID3的增量版本ID4和ID5等。強(qiáng)調(diào)在數(shù)據(jù)挖掘中有伸縮性的決策樹算法有SLIQ、SPRINT、RainForest算法等。Web

挖掘KnowledgeWWW目錄Web挖掘簡介Web日志挖掘WebMining簡介產(chǎn)生原因應(yīng)用分類過程產(chǎn)生原因網(wǎng)絡(luò)信息搜集的需求與收集結(jié)果低效性的矛盾迫切需要對網(wǎng)絡(luò)資源的整序與檢索。傳統(tǒng)數(shù)據(jù)挖掘和文本挖掘技術(shù)的不斷完善和應(yīng)用。應(yīng)用查詢相關(guān)信息從Web數(shù)據(jù)發(fā)現(xiàn)潛在的未知信息了解用戶的興趣愛好信息個性化Web挖掘分類WebMiningWebContentMiningWebUsageMiningWebStructureMiningWeb內(nèi)容挖掘Web內(nèi)容挖掘是從文檔內(nèi)容或其描述中抽取知識的過程。Web內(nèi)容挖掘策略直接挖掘文檔的內(nèi)容在其它工具搜索的基礎(chǔ)上進(jìn)行改進(jìn)Web內(nèi)容挖掘（續(xù)）提取文字、圖片或者其他組成網(wǎng)頁內(nèi)容成分的信息，即通過有效的內(nèi)容挖掘能告訴我們哪些頁面是德文或者法文的？哪些站點(diǎn)賣我們喜歡的東西？哪些頁面介紹了我們感興趣的知識？搜索引擎、智能代理和一些推薦引擎都使用內(nèi)容挖掘來幫助客戶在浩瀚的網(wǎng)絡(luò)空間中尋找所需的內(nèi)容。Web結(jié)構(gòu)挖掘Web結(jié)構(gòu)挖掘研究的是Web文檔的鏈接結(jié)構(gòu)，揭示蘊(yùn)含在這些文檔結(jié)構(gòu)中的有用模式，處理的數(shù)據(jù)是Web結(jié)構(gòu)數(shù)據(jù)。是從WWW的組織結(jié)構(gòu)和鏈接關(guān)系中推導(dǎo)知識。由于文檔之間的互連，WWW能夠提供除文檔內(nèi)容之外的有用信息。利用這些信息，可以對頁面進(jìn)行排序，發(fā)現(xiàn)重要的頁面。Web結(jié)構(gòu)挖掘（續(xù)）提取網(wǎng)絡(luò)的拓?fù)湫畔ⅷD―網(wǎng)頁之間的鏈接信息，即通過有效的結(jié)構(gòu)挖掘能告訴我們哪些頁面被其他頁面所鏈接？哪些頁面指向了其他頁面？哪些頁面的集合構(gòu)成了一個獨(dú)立的整體？Web日志挖掘Web日志挖掘的主要目標(biāo)則是從Web的訪問記錄中（Web服務(wù)器log日志）抽取感興趣的模式。WWW中的每個服務(wù)器都保留了訪問日志（Webaccesslog），記錄了用戶訪問和交互的信息。分析這些數(shù)據(jù)可以幫助理解用戶的行為，從而改進(jìn)站點(diǎn)的結(jié)構(gòu)，或?yàn)橛脩籼峁﹤€性化的服務(wù)。Web日志挖掘（續(xù)）一般的訪問模式跟蹤通過分析日志數(shù)據(jù)來了解用戶的訪問模式和傾向，以改進(jìn)站點(diǎn)的組織結(jié)構(gòu)個性化的使用記錄跟蹤傾向于分析單個用戶的偏好，其目的是根據(jù)不同用戶的訪問模式，為每個用戶提供定制的站點(diǎn)。Web日志挖掘（續(xù)）提取關(guān)于客戶如何運(yùn)用瀏覽器瀏覽和使用這些鏈接的信息，即通過有效的日志挖掘能告訴我們那些客戶訪問了哪些頁面？在每一頁上待了多長時間？下一步單擊了什么？在站點(diǎn)中是按照怎樣的訪問路線通向檢查計數(shù)器，又是通過怎樣的路線直接退出的？Web內(nèi)容挖掘Web結(jié)構(gòu)挖掘Web日志挖掘處理數(shù)據(jù)類型IR方法：無結(jié)構(gòu)數(shù)據(jù)、半結(jié)構(gòu)數(shù)據(jù)數(shù)據(jù)庫方法：半結(jié)構(gòu)化數(shù)據(jù)Web結(jié)構(gòu)數(shù)據(jù)用戶訪問Web數(shù)據(jù)主要數(shù)據(jù)自由化文本、HTML標(biāo)記的超文本HTML標(biāo)記的超文本W(wǎng)eb文檔內(nèi)及文檔間的超鏈Serverlog,Proxyserverlog,Clientlog表示方法詞集、段落、概念、IR的三種經(jīng)典模型對象關(guān)系模型圖關(guān)系表、圖處理方法統(tǒng)計、機(jī)器學(xué)習(xí)、自然語言理解數(shù)據(jù)庫技術(shù)機(jī)器學(xué)習(xí)、專有算法統(tǒng)計、機(jī)器學(xué)習(xí)、關(guān)聯(lián)規(guī)則主要應(yīng)用分類、聚類、模式發(fā)現(xiàn)模式發(fā)現(xiàn)、數(shù)據(jù)向?qū)А⒍鄬訑?shù)據(jù)庫、站點(diǎn)創(chuàng)建與維護(hù)頁面權(quán)重分類聚類模式發(fā)現(xiàn)Web站點(diǎn)重建，商業(yè)決策Web挖掘過程資源發(fā)現(xiàn)：在線或離線檢索Web的過程，例如用爬蟲（crawler）或（spider）在線收集Web頁面信息選擇與預(yù)處理：對檢索到的Web資源的任何變換都屬于此過程。詞干提取高低頻詞的過濾漢語詞的切分綜合過程：自動發(fā)現(xiàn)Web站點(diǎn)的共有模式分析過程：對挖掘到的模式進(jìn)行驗(yàn)證和可視化處理Web日志挖掘Web日志挖掘數(shù)據(jù)類型Web日志挖掘應(yīng)用Web日志挖掘過程服務(wù)器日志數(shù)據(jù)類型ClientIP:AuthenticatedUserID:--Time/Date:[10/Nov/1999:10:16:39-0600]Request:"GET/HTTP/1.0"Status:200Bytes:-Referrer:“-”Agent:"Mozilla/4.61[en](WinNT;I)"Web日志挖掘應(yīng)用Applications電子商務(wù)中發(fā)現(xiàn)潛在客戶增強(qiáng)終端用戶信息獲取的質(zhì)量提高Web服務(wù)器的性能合理放置廣告提高站點(diǎn)設(shè)計欺詐和入侵檢測預(yù)測用戶行為Web日志挖掘過程Web日志挖掘過程預(yù)處理數(shù)據(jù)挖掘模式分析數(shù)據(jù)預(yù)處理數(shù)據(jù)清理用戶對話識別頁面視圖識別路徑完整數(shù)據(jù)清理根據(jù)一組原始的日志項(xiàng)，完成一系列基本任務(wù)，如歸并日志、解析日志等。對于一些網(wǎng)站，需要過濾掉圖象文件，這可以通過檢查文件后綴實(shí)現(xiàn)。一般地，我們需要對日志中的狀態(tài)碼（statuscode）進(jìn)行檢查。清理后的SampleLogIPAddressTime/DateMethod/URIReferrerAgent15:30:01/2-Jan-01GETIndex.htmMozilla/4.0(IE5.0W98)15:30:01/2-Jan-01GET1.htmMozilla/4.0(IE5.0W98)15:30:01/2-Jan-01GETA.htmMozilla/4.0(IE5.0W98)15:37:09/2-Jan-01GETE.htmMozilla/4.0(IE5.0W98)15:33:04/2-Jan-01GETIndex.htmMozilla/4.0(IE4.0NT)15:33:04/2-Jan-01GET1.htmMozilla/4.0(IE4.0NT)15:33:04/2-Jan-01GETA.htmMozilla/4.0(IE4.0NT)15:35:11/2-Jan-01GETB.htmMozilla/4.0(IE4.0NT)15:35:11/2-Jan-01GETC.htmMozilla/4.0(IE5.0W98)用戶對話識別1.IPAddress&Agent2.EmbeddedSessionID3.Registration(UserProfile)4.Cookie5.SoftwareAgent(Applet&Scrtipt)6.ModifiedBrowser用戶對話識別（續(xù)）方法說明隱私性保護(hù)優(yōu)點(diǎn)缺點(diǎn)IP地址/代理服務(wù)器假定每個獨(dú)立IP地址/代理服務(wù)器組是獨(dú)立用戶低通?？捎?，無需附加技術(shù)。無法保證唯一性，在隨機(jī)或者輪換IP情況下失效嵌入式對話ID通過動態(tài)形成頁面將ID加入每個鏈接低/中等通?？捎?，不需依賴于IP地址無法了解重復(fù)訪問，需要完全動態(tài)站點(diǎn)。注冊用戶確切地登陸站點(diǎn)中等可以跟蹤單個用戶，而不僅僅是瀏覽器不是全部用戶都愿意注冊Cookie在客戶端機(jī)器上保留標(biāo)識符中等/高可以跟蹤重復(fù)訪問能被禁止。不為大眾接收軟件代理服務(wù)器程序載入瀏覽器從而將日志數(shù)據(jù)返回高可以得到單個Web站點(diǎn)的確切日志數(shù)據(jù)很可能被拒絕。不為大眾接收改進(jìn)型瀏覽器瀏覽器記錄日志數(shù)據(jù)非常高可以得到關(guān)于整個Web的日志數(shù)據(jù)用戶必須確切地得到軟件用戶對話識別15:33:04/2-Jan-01GETIndex.htm15:33:04/2-Jan-01GET1.htm15:33:04/2-Jan-01GETA.htm15:35:11/2-Jan-01GETB.htm15:30:01/2-Jan-01GETIndex.htm15:30:01/2-Jan-01GET1.htm15:30:01/2-Jan-01GETA.htm15:37:09/2-Jan-01GETE.htm15:35:11/2-Jan-01GETC.htmMozilla/4.0(IE5.0W98)User1:Mozilla/4.0(IE4.0NT)User2:頁面視圖識別1-ABA.htm1-AEC.htm1-CA.htmMozilla/4.0(IE5.0W98)User1:Mozilla/4.0(IE4.0NT)User2:路徑補(bǔ)全解決由于Cache帶來的問題路徑不全的問題數(shù)據(jù)挖掘統(tǒng)計分析頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則聚類分析和分類序列模式統(tǒng)計分析主要用于改進(jìn)系統(tǒng)的性能、設(shè)計等包括：

1)最頻繁訪問的頁面

2)每個頁面的平均訪問時間

3)通過一個站點(diǎn)的平均時間頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則可以尋找出經(jīng)常頻繁訪問的page組，可用于修改Web站點(diǎn)的設(shè)計或提前緩沖頁面，改進(jìn)系統(tǒng)的性能。包括兩方面的應(yīng)用：*user用于Marketsegmentation(市場分割)和個人內(nèi)容定制*page(content)后者主要用于IR和沖浪輔助聚類和分類序列模式可用于用戶的visitpattern.包括：1.趨勢分析2.拐點(diǎn)檢測模式分析目的是根據(jù)實(shí)際應(yīng)用，通過用戶的選擇和觀察，把發(fā)現(xiàn)的規(guī)則、模式和統(tǒng)計規(guī)律轉(zhuǎn)換為知識。Visualization流數(shù)據(jù)挖掘流數(shù)據(jù)簡介流數(shù)據(jù)頻繁模式挖掘簡介流數(shù)據(jù)頻繁模式挖掘算法數(shù)據(jù)流簡介概念一系列連續(xù)且有序的點(diǎn)組成的序列x1,…,xi,…,xn,稱為數(shù)據(jù)流；按照固定的次序，這些點(diǎn)只能被讀取一次或者幾次特點(diǎn)大數(shù)據(jù)量，甚至無限頻繁的變化和快速的響應(yīng)線性掃描算法，查詢次數(shù)有限r(nóng)andomaccessisexpensiveDBMS與DSMS持久的關(guān)系One-timequeries隨機(jī)的訪問“無限”的磁盤空間當(dāng)前狀態(tài)有效相對較低的更新率很少“實(shí)時服務(wù)”假定數(shù)據(jù)精確無誤訪問策略由查詢處理器在數(shù)據(jù)庫設(shè)計時確定瞬間的流連續(xù)的查詢序列化的訪問有限的主存數(shù)據(jù)的到達(dá)順序是關(guān)鍵數(shù)據(jù)傳輸率未知實(shí)時響應(yīng)過時/模糊的數(shù)據(jù)變化的數(shù)據(jù)及數(shù)據(jù)量ScratchSpace(Mainmemoryand/orDisk)User/ApplicationContinuousQueryStreamQueryProcessorResultsMultiplestreamsDSMSDSMSScratchStoreDSMSInputstreamsRegisterQueryStreamedResultStoredResultArchiveStoredRelations目前的DSMS項(xiàng)目STREAM(Stanford):Ageneral-purposeDSMSCougar(Cornell):sensorsAurora(Brown/MIT):sensormonitoring,dataflowHancock(AT&T):telecomstreamsNiagara(OGI/Wisconsin):InternetXMLdatabasesOpenCQ(GeorgiaTech):triggers,incr.viewmaintenanceTapestry(Xerox):pub/subcontent-basedfilteringTelegraph(Berkeley):adaptiveengineforsensorsTradebot():stocktickers&streamsTribeca(Bellcore):networkmonitoringStreaminer(UIUC):newprojectforstreamdatamining應(yīng)用領(lǐng)域新的應(yīng)用領(lǐng)域–以連續(xù)的、有序的“流”的形式輸入數(shù)據(jù)網(wǎng)絡(luò)監(jiān)聽和流量控制(Networkmonitoringandtrafficengineering)通信(Telecomcallrecords)網(wǎng)絡(luò)安全(Networksecurity)金融領(lǐng)域(FinancialApplication)工業(yè)生產(chǎn)(ManufacturingProcesses)網(wǎng)頁日志與點(diǎn)擊流(Weblogsandclickstreams)應(yīng)用實(shí)例網(wǎng)絡(luò)安全數(shù)據(jù)包流，用戶的會話信息查詢:URL過濾，異常監(jiān)測，網(wǎng)絡(luò)攻擊和病毒來源金融領(lǐng)域交易數(shù)據(jù)流，股票行情，消息反饋查詢:套匯可能性分析，模式現(xiàn)有的研究方向流數(shù)據(jù)建模(Streamdatamodel)STanfordstREamdatAManager(STREAM)DataStreamManagementSystem(DSMS)流檢索/查詢建模(Streamquerymodel)ContinuousQueriesSlidingwindows流數(shù)據(jù)挖掘(Streamdatamining)Clustering&summarization(Guha,Motwanietal.)Correlationofdatastreams(Gehrkeetal.)Classificationofstreamdata(Domingosetal.)流數(shù)據(jù)頻繁模式挖掘簡介靜態(tài)數(shù)據(jù)流數(shù)據(jù)關(guān)系特點(diǎn)靜態(tài)穩(wěn)固短暫易失查詢方式一次完成連續(xù)查詢存取方式隨機(jī)訪問序列訪問存儲容量無限的輔存有限的主存響應(yīng)速度無要求或盡量快必須快存儲特點(diǎn)被動存儲主動存儲更新速度低不可預(yù)測響應(yīng)特點(diǎn)較少“實(shí)時服務(wù)”實(shí)時響應(yīng)流數(shù)據(jù)頻繁模式挖掘要求只能對數(shù)據(jù)流進(jìn)行一次掃描；處理的數(shù)據(jù)項(xiàng)是無窮的；實(shí)時響應(yīng)數(shù)據(jù)處理要求。數(shù)據(jù)流管理系統(tǒng)的抽象體系結(jié)構(gòu)流數(shù)據(jù)頻繁模式挖掘算法確定區(qū)間（deterministicbounds）近似算法：計算一個近似結(jié)果，但這個近似結(jié)果能夠落入由真實(shí)結(jié)果構(gòu)成的區(qū)間；概率區(qū)間（probabilisticbounds）近似算法：計算一個近似結(jié)果，但這個近似結(jié)果能夠以較高的概率落入由真實(shí)結(jié)果構(gòu)成的區(qū)間。算法比較滑動窗口技術(shù)自然滑動窗口31

days24hours4qtrs12monthsTimeNow24hrs4qtrs15minutes7daysTimeNow25sec.對數(shù)滑動窗口隱私保護(hù)數(shù)據(jù)挖掘隱私保護(hù)數(shù)據(jù)挖掘簡介隱私保護(hù)數(shù)據(jù)挖掘面向企業(yè)信用評估的分布式隱私保護(hù)數(shù)據(jù)挖掘研究一、隱私保護(hù)數(shù)據(jù)挖掘簡介WhatWhyWhoGoalHowAnExample什么是數(shù)據(jù)挖掘數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取或“挖掘”知識的過程。數(shù)據(jù)挖掘以客觀、有效的數(shù)據(jù)源為物質(zhì)基礎(chǔ)。數(shù)據(jù)挖掘得到的知識是一種數(shù)據(jù)歸納的結(jié)果，是一種統(tǒng)計的知識。什么是隱私針對不同的應(yīng)用環(huán)境，隱私定義不同。在信息時代，隱私指用戶隱藏個人信息的權(quán)利和控制自己的信息給其他人的能力。什么是隱私保護(hù)數(shù)據(jù)挖掘“gettingvaliddataminingresultswithoutlearningtheunderlyingdatavalues”噪聲背景的數(shù)據(jù)挖掘受限制的數(shù)據(jù)挖掘數(shù)據(jù)挖掘可能會違反用戶的隱私數(shù)據(jù)挖掘以準(zhǔn)確的數(shù)據(jù)為數(shù)據(jù)源，進(jìn)行數(shù)據(jù)歸納分析。個體隱私記錄級和屬性級上的隱私組織隱私結(jié)果級上的隱私，統(tǒng)計分析后的結(jié)果什么人需要隱私保護(hù)數(shù)據(jù)挖掘？政府和公用事業(yè)部門疾病控制中心保險公司工商業(yè)組織跨國公司每個國家的法律是不同的軍事情報分析犯罪行為分析反恐分析隱私的限制不會阻止數(shù)據(jù)挖掘數(shù)據(jù)挖掘的目標(biāo)是結(jié)果的總結(jié)關(guān)聯(lián)規(guī)則分類聚類結(jié)果本身不會違反隱私不包含個人身份信息反映的是整個數(shù)據(jù)的歸納統(tǒng)計結(jié)果，而不是針對每個單位Theproblemiscomputingtheresultswithoutaccesstothedata!隱私保護(hù)數(shù)據(jù)挖掘的目標(biāo)PPDMencompassesthedualgoalofmeetingprivacyrequirementsandprovidingvaliddataminingresults.保護(hù)隱私和滿足安全性要求（安全性）產(chǎn)生正確的數(shù)據(jù)挖掘歸納結(jié)果（準(zhǔn)確性）提供高效的數(shù)據(jù)挖掘算法（高效性）AccuracyEfficiencyPrivacy如何進(jìn)行隱私保護(hù)數(shù)據(jù)挖掘計算頻繁項(xiàng)集：ABC≥5%?2ABC=9DBSize=2001ABC=18DBSize=3003ABC=5DBSize=100ABC:R+count-freq.*DBSizeR=17ABC:17+5-.05*100ABC:17ABC:17+9-.05*200ABC:12ABC:12+18-.05*300ABC:19ABC:19≥R?ABC:YES!計算頻繁項(xiàng)集：ABC≥5%?2ABC=9DBSize=2001ABC=18DBSize=3003ABC=5DBSize=100ABC:R+count-freq.*DBSizeR=17ABC:17+9-.05*200ABC:12+18-.05*300ABC:19≥R?ABC:YES!二、隱私保護(hù)數(shù)據(jù)挖掘隱私保護(hù)數(shù)據(jù)挖掘分類保護(hù)個體用戶隱私保護(hù)組織用戶隱私研究方法數(shù)據(jù)隱藏安全多方計算保護(hù)個體用戶隱私這是一種記錄和屬性級上的隱私保護(hù)。在原始數(shù)據(jù)庫中，類似于標(biāo)識符、姓名、地址和喜好等用戶數(shù)據(jù)作為用戶的隱私應(yīng)該被保護(hù)。保護(hù)敏感的原始數(shù)據(jù)的隱私保護(hù)數(shù)據(jù)挖掘方法應(yīng)該能夠使得用戶的敏感的原始數(shù)據(jù)被修改，以便數(shù)據(jù)的使用者不能對用戶的原始數(shù)據(jù)進(jìn)行直接存儲，不能查看用戶的隱私，以此保護(hù)用戶的私有數(shù)據(jù)。個體隱私:保護(hù)記錄每個項(xiàng)都不允許泄漏記錄的一部分是可以泄漏的個人身份信息個人身份信息刪除標(biāo)識符但是我們無法保證身份不能被推斷候選碼一些個體特有的屬性DataMiningenablessuchtracing!保護(hù)組織用戶隱私這是一種結(jié)果級上的隱私保護(hù)，這里的目標(biāo)不僅是保護(hù)個體用戶的不被泄漏，而且一些重要的策略模式和數(shù)據(jù)挖掘之后的結(jié)果同樣不能泄漏，在商業(yè)領(lǐng)域，這些模式被認(rèn)為是能夠提供有競爭力好處的知識，隱私必須被很好地保護(hù)。在