數(shù)據(jù)挖掘第一講

數(shù)據(jù)挖掘和數(shù)據(jù)倉庫孟大志北京工業(yè)大學dzhmeng07@Tel:(010)69755596137013771081、二十一世紀的社會特征：數(shù)字化生活精確化，社會管理精確化（ISO9000），生產(chǎn)精確化，等等。全面數(shù)字化進程導至：海量數(shù)據(jù)是社會最普遍的特征。海量數(shù)據(jù)導致計算是世界上最普遍的社會行為。數(shù)學模型是最普適的方法，不僅是數(shù)學方法，而且是思維方法，是文化素質(zhì)。第一講緒論一、背景社會文明的標志不是吃、穿、行，而是信息化水平。精確水平的信息化——數(shù)字化。2、計算機的巨大驅(qū)動計算科學和計算機緊密的結(jié)合形成了新的計算領(lǐng)域的更強有力的生力軍。其中不僅使用概率統(tǒng)計方法、傳統(tǒng)的組合計算和動力學計算，而且大量使用了全新的方法：仿生計算分別代表是模仿生物進化（遺傳算法），模仿大腦的智能結(jié)構(gòu)（神經(jīng)網(wǎng)絡(luò)）和模仿生物群體智能行為（蟻群算法和粒子群計算），這三類生物智能特點的計算；機器學習與數(shù)據(jù)挖掘方法和以及冠名以‘普適計算’的現(xiàn)代計算方法；非線性計算混沌計算和分形計算。當然還有改進的計算機技術(shù)：分布式計算和并行計算。1）、網(wǎng)絡(luò)引發(fā)海量數(shù)據(jù)計算機與網(wǎng)絡(luò)對人類的影響：工業(yè)革命以后的信息革命！1961年11月21日，ARPANET連接了四個單位：UCLA，加州大學，斯坦福研究院和狄他州大學。當時沒有人預見到這種NET將導致影響全人類的因特網(wǎng)?。ˋRPA：五角大樓高級研究計劃暑）1971年發(fā)展到24個站點；1981年突破200個；1990年ARPANET完成使命，指揮權(quán)轉(zhuǎn)移到國家科學基金會。開始了因特網(wǎng)。每季度網(wǎng)站以20%增長，完全超越了摩爾定律。網(wǎng)絡(luò)數(shù)據(jù)的增長遠遠超過網(wǎng)絡(luò)本身，第一海量！3、海量數(shù)據(jù)來源2）經(jīng)濟發(fā)展的必然現(xiàn)象：數(shù)據(jù)爆炸國家統(tǒng)計局公布或可查閱數(shù)據(jù)；政府部門統(tǒng)計部門可查閱數(shù)據(jù)；國家部門專有數(shù)據(jù)（銀行，保險，證卷業(yè)，稅務(wù)，工商，人口，環(huán)保等）；非國營企事業(yè)單位可采集數(shù)據(jù)（生產(chǎn)，經(jīng)營，納稅及財務(wù)）；商業(yè)系統(tǒng)數(shù)據(jù)（超市票據(jù)）；公用事業(yè)數(shù)據(jù)（地鐵，工交票務(wù)或IC卡數(shù)據(jù)）；個人資料與經(jīng)濟數(shù)據(jù)…等。DNA的堿基數(shù)目，在GenBank中每十四個月增加1倍。還不包括Bioinformation中所使用的關(guān)于核酸、蛋白質(zhì)，基因組等更大量的信息。數(shù)據(jù)處理與分析是更大量的計算：DNA序列結(jié)構(gòu)，致病基因識別，蛋白質(zhì)空間結(jié)構(gòu)的描述與分析，藥物設(shè)計等等。3）生物與醫(yī)學信息4）科學研究數(shù)據(jù)美國國家航天局（NASA）的對地觀測系統(tǒng)（EOS）:地球物理、氣象、生物化學、水文四大學科的數(shù)據(jù)，每天發(fā)出1000G數(shù)據(jù)；Fortune500公司收集行業(yè)數(shù)據(jù)，已經(jīng)擁有3814萬G數(shù)據(jù)（1016字節(jié)）；對比：宇宙中原子個數(shù)，1080!巨量的信息是最危險的殺手。（天氣預報，網(wǎng)上犯罪與黑客）

決策與理解危機。DataMining是解決問題的方法。信息爆炸是一把雙刃劍：巨量的信息是最重要的財富；（30億個字符的DNA序列，計算機產(chǎn)業(yè)和數(shù)據(jù)信息產(chǎn)業(yè)）二、2020年計算會變成什么樣？Nature,Vol.440/23/March2006發(fā)表7篇文章，討論今后15年，計算的發(fā)展。1、電子傳感器將“everything,everywhere”微型傳感器將象“smartdust”,無處不在，而且在世界上所有地方形成“sensorwebs”。眾多的自然科學需要象“dust”那樣的傳感器網(wǎng)絡(luò)。傳感器網(wǎng)絡(luò)的計算（通訊與控制）將最廣泛需要！無處不在的傳感器網(wǎng)絡(luò)將記錄和處理隨時間累積的巨量的數(shù)據(jù)流，提供給人們巨量的信息，科學研究只是從數(shù)據(jù)中發(fā)現(xiàn)規(guī)則。KatalinSzlavecz，霍浦金斯大學的生態(tài)學家，從事土壤生物和營養(yǎng)循環(huán)的工作。她因為努力用有限的數(shù)據(jù)解決復雜的問題而受挫敗，這迫使她從事傳感器網(wǎng)絡(luò)。在大學校園外的一條小河流邊緣配置了十個微粒。每一個微粒在每分鐘都在測量土壤的濕度與溫度，并且網(wǎng)絡(luò)將它得到的數(shù)據(jù)周期性的傳送到她辦公室的計算機。2、由于傳感器網(wǎng)絡(luò)的普遍化，數(shù)據(jù)將指數(shù)增長：指數(shù)的世界。其中第一個問題是數(shù)據(jù)的存儲和處理，構(gòu)建連接整個世界的網(wǎng)絡(luò)數(shù)據(jù)庫：強大的處理能力和統(tǒng)一的數(shù)據(jù)標準成為首要的計算問題。在數(shù)據(jù)挖掘中成為數(shù)據(jù)立方體的數(shù)據(jù)倉庫的網(wǎng)絡(luò)：3、自動計算、自動推理和自動控制成為計算的主要任務(wù)和特點。自動化：數(shù)據(jù)的收集、存儲、處理；由數(shù)據(jù)產(chǎn)生，模式、模型和產(chǎn)生規(guī)律和知識；并且自動測試模型、改進、假定和驗證等等。使用自動化傳統(tǒng)科學的改變傳統(tǒng)科學自動化科學假設(shè)化學知識實驗實驗設(shè)計機器-編碼的邏輯假設(shè)機器-編碼化學代數(shù)化學圖靈機程序設(shè)計理論微流體機器人的化學家：4、網(wǎng)絡(luò)不僅是生活方式！網(wǎng)絡(luò)將成為科學與技術(shù)研究的工具、實驗室和方式：將不僅利用網(wǎng)絡(luò)的數(shù)據(jù)，而且利用網(wǎng)絡(luò)上的人的群體智慧與知識，可以自動進行“創(chuàng)造”；將利用網(wǎng)絡(luò)，象設(shè)計游戲一樣，設(shè)計群體實驗：心理學、社會學、生態(tài)學和人類學，等等。億萬計算機+網(wǎng)絡(luò)+人群=超級生物：超越人類的極限！TheCreativityMachine三.數(shù)據(jù)挖掘概念1995年美國計算機學會（ACM）的會議上提出了數(shù)據(jù)挖掘的概念（datamining）。一般理解：從巨量數(shù)據(jù)集合(不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù))中挖掘出隱含的、未知的、具有應(yīng)用價值的信息的過程，通常這種信息具有一般化意義時又稱為知識。相類似的用語：知識抽?。╧nowledgeextraction）、數(shù)據(jù)捕撈（datadredgine）及知識發(fā)現(xiàn)（KDD）等。數(shù)據(jù)挖掘目前還不是一種系統(tǒng)化的獨立的體系性理論，只是一個概念與框架，將數(shù)據(jù)庫技術(shù)、數(shù)據(jù)處理技術(shù)和知識發(fā)現(xiàn)技術(shù)堆放與按目標整合的結(jié)構(gòu)。未來？理論？1）數(shù)據(jù)挖掘內(nèi)容：知識發(fā)現(xiàn)“查詢是數(shù)據(jù)庫的奴隸，發(fā)現(xiàn)才是數(shù)據(jù)庫的主人。”關(guān)系數(shù)據(jù)庫的結(jié)構(gòu)就是為了查詢的：字段1字段2字段3記錄1記錄1數(shù)據(jù)的隱含的關(guān)聯(lián)、模式等結(jié)構(gòu)是沒有表現(xiàn)的：什么數(shù)據(jù)結(jié)構(gòu)可以表現(xiàn)？數(shù)據(jù)挖掘能發(fā)現(xiàn)的知識類型：廣義型知識，反映事物共同性質(zhì)的知識；特征型知識，反映事物各種特征的知識；差異型知識，反映事物的屬性差別的知識；關(guān)聯(lián)型知識，反映事物之間的依賴和關(guān)聯(lián)的知識；預測型知識，根據(jù)歷史和當前的知識預測未來的知識；偏離型知識，揭示事物偏離常規(guī)的異常現(xiàn)象的知識（腐敗可以挖掘嗎？）；在不同概念層次上發(fā)現(xiàn)：微觀，中觀，宏觀，…分類.分類是理解的基礎(chǔ)?!分類器構(gòu)造方法:機器學習,神經(jīng)網(wǎng)絡(luò),統(tǒng)計…評價和比較尺度:預測準確性,計算復雜度,模型簡潔度.聚類.發(fā)現(xiàn)共性,概念與規(guī)律,創(chuàng)造！動態(tài)聚類法,有序樣品聚類,有重復聚類,模糊聚類…關(guān)聯(lián)規(guī)則發(fā)現(xiàn).最普遍的、最基礎(chǔ)的挖掘！例.“在購買面包和黃油的顧客中,90%的也買了牛奶”超市中的尿布和啤酒關(guān)聯(lián)??？2）數(shù)據(jù)挖掘功能分類分析數(shù)據(jù)的功能可以是數(shù)學的，也可以是非數(shù)學的；可以是演繹的，也可以是歸納的，數(shù)據(jù)庫的等。概念生成與分析：從數(shù)據(jù)到概念、層次結(jié)構(gòu)；決策方法和決策模型（直覺到數(shù)據(jù)?。?；時間序列分析的數(shù)據(jù)挖掘方法；應(yīng)用模型的數(shù)據(jù)分析方法，等等。系統(tǒng)的基本結(jié)構(gòu)：網(wǎng)絡(luò)模型的數(shù)據(jù)挖掘構(gòu)建——反向網(wǎng)絡(luò)工程。文本自動分類:理解文本的類屬性,子空間分類.(SVM的微分幾何方法)文本自動聚類:發(fā)現(xiàn)文本集合中的新模式,新概念.文本向量:由文本的實意詞的特征值或特征模式為分量的向量.以信息熵的形式構(gòu)造.特征子空間:具有某種共同意義的分量組成的子空間.主義自由科學一個成功的例子.---自動文本分析文本向量空間:全部文本向量的高維線性空間.3）數(shù)據(jù)挖掘過程：涉及技術(shù)領(lǐng)域：數(shù)據(jù)庫技術(shù)、機器學習、大規(guī)模計算、模式識別、神經(jīng)網(wǎng)絡(luò)、可視化、圖象與信號處理、信息檢索等?？商幚矶喾N數(shù)據(jù)源：關(guān)系數(shù)據(jù)庫、文本數(shù)據(jù)、網(wǎng)絡(luò)數(shù)據(jù)、多媒體數(shù)據(jù)等。挖掘水平取決于：目標構(gòu)思、數(shù)據(jù)處理水平、數(shù)據(jù)倉庫構(gòu)建的科學性、挖掘工具類型適用性、模式評估和知識表達方式。數(shù)據(jù)挖掘是綜合的高合作的研究！關(guān)系數(shù)據(jù)庫或各種數(shù)據(jù)源數(shù)據(jù)倉庫數(shù)據(jù)挖掘模式評估知識表示清理集成四、數(shù)據(jù)挖掘的意義1、數(shù)據(jù)挖掘與數(shù)據(jù)信息產(chǎn)業(yè)中國青年報2003/4/3：泰農(nóng)銀行總裁來京特別想了解北京的潛在客戶群情況，看看與泰國進行貿(mào)易往來有哪些企業(yè)？在德國摩根建福投資銀行作國外金融機構(gòu)的中國事物投資顧問：“是否在京投資？要投多少？什么方式？盈利情況如何？”他們在北京經(jīng)過調(diào)查，得到的結(jié)論是：“兩眼一摸黑！”這樣的結(jié)果可能解決問題嗎？……企業(yè)界?商業(yè)界？各行各業(yè)都需要資料和數(shù)據(jù)咨詢！數(shù)據(jù)的商業(yè)價值數(shù)據(jù)是有價原料；加工后的商品是信息；再加工后的商品是知識，是更有價值的商品。計算機網(wǎng)絡(luò)造就了信息業(yè)，信息業(yè)的主要價值卻不在存儲器、處理器和傳輸工具----網(wǎng)絡(luò)，而在信息本身。車和乘客，哪個更重要？哪個更有價值？！數(shù)據(jù)信息產(chǎn)業(yè)是比今天的IT業(yè)更有發(fā)展的產(chǎn)業(yè)。

數(shù)據(jù)信息產(chǎn)業(yè)是利用數(shù)據(jù)信息本身的商業(yè)價值來創(chuàng)造利潤的行業(yè).數(shù)據(jù)信息產(chǎn)業(yè)

數(shù)據(jù)信息產(chǎn)業(yè)在市場經(jīng)濟中的必要性和重要性:.利用數(shù)據(jù)信息拓展多種銷售渠道是企業(yè)經(jīng)營活動的重心;.完整準確的信息是廣泛市場到目標市場轉(zhuǎn)型的首要條件;.什么是目標市場;.目標市場在顧客關(guān)系管理(CRM)中的重要性;.目標市場在市場商業(yè)活動中將發(fā)揮重要作用并成為主要發(fā)展趨勢；.數(shù)據(jù)信息產(chǎn)業(yè)的發(fā)展是經(jīng)濟高度完善和成熟的標志。提出你理解的數(shù)據(jù)信息產(chǎn)業(yè)？龍頭產(chǎn)業(yè)的更迭：工業(yè)革命催生的能源產(chǎn)業(yè)——石油大王；催生材料需求——鋼鐵大王；新技術(shù)革命催生制造業(yè)——汽車大王；半導體發(fā)明催生電子行業(yè)——電器大王；計算機、PC機技術(shù)催生軟件業(yè)——蓋茲！下一個龍頭產(chǎn)業(yè)是什么？？數(shù)據(jù)信息產(chǎn)業(yè)在金融業(yè)中的重大作用.聯(lián)合誠信體系(CreditBureau)是信息產(chǎn)業(yè)的一個極好實例;.信用卡在發(fā)達國家已成為普遍使用的支付手段;.在美國和全世界最為流行的四種信用卡:最早發(fā)行的快捷卡(AmericanExpress)世界發(fā)行量最大的簽證卡(Visa)富有首創(chuàng)精神的百事達卡(Master)發(fā)現(xiàn)卡(Discover).信用卡市場的開發(fā)和誠信體系的完善緊密相關(guān).美國聯(lián)合誠信體經(jīng)歷了從小到大的發(fā)展歷程.全世界最大的三家聯(lián)合誠信體系（CreditBureau)公司歷史最長的EFX(EquiFax)公司業(yè)務(wù)范圍最大的Experian公司Transunion公司e)外延價值：城市超市整體數(shù)據(jù)庫的長期積累可以提供超市分布與再投資分析與風險預測，甚至經(jīng)濟發(fā)展分析與預測。對政府的經(jīng)濟政策提供資信。數(shù)據(jù)挖掘例：超市數(shù)據(jù)處理與分析.a)數(shù)據(jù)資源:銷售原始清單,采購清單,商品配放三維位置數(shù)據(jù)庫,導購員位置,采購推車損耗率,停車場使用密度,…等；b)構(gòu)造數(shù)據(jù)倉庫：相對完整的歷史數(shù)據(jù)，形成動態(tài)數(shù)據(jù)庫，賦予信息處理的數(shù)據(jù)結(jié)構(gòu)；c)DataMining技術(shù)：動態(tài)數(shù)學模型，分類，聚類，相關(guān)性，規(guī)則提取，…（OLAP、統(tǒng)計、機器學習、SVM等）；d)產(chǎn)生有價值信息與商業(yè)知識：“人-商品-商場”三位相關(guān)性分析，動態(tài)關(guān)系分析，可以提供與時間相關(guān)的商品采購計劃，安全庫存量模型，商品搭配與貨柜設(shè)計策略，以至商場改造與再設(shè)計等有重大商業(yè)價值的信息與知識；數(shù)據(jù)信息產(chǎn)業(yè)---數(shù)據(jù)信息市場---物質(zhì)市場的催化劑沒有酶生命不能存在一分鐘；沒有數(shù)據(jù)信息產(chǎn)業(yè)和市場，物質(zhì)商品市場將不能發(fā)展到高級的水平：市場將萎縮，經(jīng)濟將衰退。以分析為主的方法轉(zhuǎn)變到分析加上關(guān)聯(lián)、整合的系統(tǒng)化的方法；以精確的邏輯推定為主轉(zhuǎn)換為以統(tǒng)計和演化為主的非確定性推斷等等。問題：計算與分析應(yīng)該是什么樣的呢？二十一世紀與前比較，無論在科學技術(shù)領(lǐng)域的重心的轉(zhuǎn)移還是在方法上的更新，都對數(shù)值計算提出了新的需求：以物理學為中心到以生物學、經(jīng)濟學為中心的多中心。生物學發(fā)展是物理的傳承。2.科學技術(shù)中的數(shù)據(jù)挖掘1）新世紀的科學技術(shù)特點2）反問題方法科學技術(shù)的反問題成為研究的主題：已知交通流量問阻塞原因；已知人流密度分布問傳染病傳染路徑；已知基因表達譜數(shù)據(jù)問基因組的結(jié)構(gòu)；已知粒子散射圖象問粒子結(jié)構(gòu)；已知Web節(jié)點的信息流量問用戶行為；已知網(wǎng)絡(luò)游戲中的玩家的操作問心理學問題；等等。數(shù)據(jù)挖掘特別適合反問題求解！3、量化社會決策1）不確定性決策問題的建模與分析技術(shù)；2）隨機決策模型求解；3）風險度量與管理；4）期望效用評價（綜合評價問題）；5）網(wǎng)絡(luò)環(huán)境下的決策理論與方法；多數(shù)問題需要數(shù)據(jù)挖掘發(fā)現(xiàn)規(guī)則，并用計算機模擬算法。五、幾個最基本概念1、數(shù)據(jù)、信息與知識數(shù)據(jù)≠信息≠知識理解信息知識理解是核心，是創(chuàng)造，是科學。理解的中心問題是：結(jié)構(gòu)！

數(shù)據(jù)庫=數(shù)據(jù)+結(jié)構(gòu)+存儲空間

結(jié)構(gòu)是中心！數(shù)據(jù)：字符集上的字符串的集合(同語言的定義）。

（英文字母，十進數(shù)字，漢字，圖象，聲音…）數(shù)據(jù)→信息→知識

信息：數(shù)據(jù)+結(jié)構(gòu)，減少不確定性；知識：可重復、有規(guī)律的信息并被理解的產(chǎn)物。信息和知識都可以當作數(shù)據(jù)：產(chǎn)生更高級的信息和知識下雨天留客天留我不留。數(shù)據(jù)結(jié)構(gòu)：理解，發(fā)現(xiàn)，表達，應(yīng)用。

結(jié)構(gòu)是從數(shù)據(jù)構(gòu)成信息的核心，相同的數(shù)據(jù)賦予不同的結(jié)構(gòu)，得到不同的信息。例.下雨天留客天留我不留？例.語言的不同結(jié)構(gòu)產(chǎn)生不同的文學信息

唐詩清明時節(jié)雨紛紛，路上行人欲斷魂。借問酒家何處有？牧童遙指杏花村。

宋詞清明時節(jié)雨紛紛路上行人欲斷魂。借問酒家何處有牧童遙指杏花村。劇本(元曲)[清明時節(jié)][雨紛紛][路上]行人（欲斷魂）：借問酒家何處有？牧童（遙指）:杏花村。劇本(元曲)[清明時節(jié)][雨紛紛][路上]行人（欲斷魂）：借問酒家何處有？牧童（遙指）:杏花村。時間環(huán)境地點人物語言另人物動作語言抽象出結(jié)構(gòu):

七言唐詩××××××××××××××××××××××××××××比較規(guī)整,適于言志“詩言志”宋詞××××××××××××××××××××××××××××錯落有序,用語活躍,適于抒情“詞抒情”元曲時間、地點、情景、人物、動作、言語等。用語白話，易懂。百姓故事結(jié)構(gòu)的不同表示可以表現(xiàn)出文學基調(diào)不同：專業(yè)模型數(shù)學模型？喬姆斯基的形式語言？七言唐詩****************************用音高表示：唏唏唏唏唏啦嫂發(fā)米來斗宋詞****************************嫂啦米啦嫂米規(guī)則變化數(shù)據(jù)挖掘的核心是挖掘結(jié)構(gòu)！結(jié)構(gòu)是什么？獨立結(jié)構(gòu)：關(guān)系、關(guān)聯(lián)；局部結(jié)構(gòu)：關(guān)系、關(guān)聯(lián)的群體；系統(tǒng)結(jié)構(gòu)：關(guān)系、關(guān)聯(lián)的全體，具有整體性、轉(zhuǎn)換性、守恒性和可以數(shù)學形式化表達（皮亞杰）。2、數(shù)據(jù)與整合1）數(shù)據(jù)的屬性一切源于實際的數(shù)據(jù)必然有“屬性”商業(yè)發(fā)生數(shù)據(jù)：銷售量、銷售額、產(chǎn)量、投入資金、市場份額，屬性數(shù)據(jù)：市場容量、客戶數(shù)據(jù)、商品數(shù)據(jù)，等等；科學研究數(shù)據(jù)：實驗測試數(shù)據(jù)、參數(shù)、誤差、函數(shù)、比率、表達量、時間序列、統(tǒng)計數(shù)據(jù)、樣本數(shù)據(jù)、概率值，屬性：研究對象數(shù)據(jù)，實驗人員數(shù)據(jù)，一般理論依據(jù)，等等；管理數(shù)據(jù)：工作記錄、績效值、庫存數(shù)據(jù)、質(zhì)量評價數(shù)據(jù)、事務(wù)記錄，屬性數(shù)據(jù)：人員名單、部門結(jié)構(gòu)數(shù)據(jù)、質(zhì)量指標體系、統(tǒng)計指標體系，等等。2）多維數(shù)據(jù)模型由表到數(shù)據(jù)立方體（datacube）。數(shù)據(jù)立方體由“維”與“事實”來定義。

維：time（按季或月劃分的實體）item（商品項目劃分的實體）location（地區(qū)或城市為實體）Supplier（供應(yīng)商為實體）Q4timeQ3Q2Q1ilemlocation每個維都由一個表定義：time：Q1，Q2，Q3，Q4，季度。item：計算機、家庭娛樂、電話、安全。Location:Chicago、NewYork、Toronto、Vancourer?！笆聦崱笔菙?shù)據(jù)(dollars_sold)，由維的表中交叉點的值描述。這種用“維”和“事實”表達一個主題的全部內(nèi)容，匯總方式多式多樣，但可以由匯總級來定義。“維”