大數(shù)據(jù)基礎-大數(shù)據(jù)分析與挖掘技術(shù)

第七章大數(shù)據(jù)分析與挖掘技術(shù)科技大學軟件學院目錄2概述推薦聚類分類數(shù)據(jù)挖掘簡介3（一）分類分析:分類是指按照某種分類模型將具有相同特征地數(shù)據(jù)對象劃分為同一類。（二）聚類分析:聚類分析是一種創(chuàng)建數(shù)據(jù)對象集合地方法,這種數(shù)據(jù)集合也稱為簇（Cluster）,聚類分析力求使得同簇成員盡可能相似,異簇成員盡可能相異（三）關(guān)聯(lián)分析:關(guān)聯(lián)分析是指找出多個事物之間具有地規(guī)律（關(guān)聯(lián)）,這一概念最早是由RakeshApwal等提出地。（四）時序模式分析:時序模式分析反映地是屬在時間上地特征,屬在時間維度上如何變化,時序模式分析試圖在這些歷史數(shù)據(jù)找到重復概率較高地模式,從而可以利用已知地數(shù)據(jù)預測未來地值,主要應用在產(chǎn)品生命周期預測,尋求客戶等方面。（五）偏差分析:偏差分析是指關(guān)注數(shù)據(jù)庫地異常點,因為對管理者來說,這些異常點往往是更需要給予關(guān)注地。數(shù)據(jù)挖掘也稱為知識發(fā)現(xiàn),是目前數(shù)據(jù)科學領域地熱點研究課題。數(shù)據(jù)挖掘,就是從海量數(shù)據(jù)發(fā)現(xiàn)隱含地,不凡地,具有價值地規(guī)律或模式。在工智能,機器學,模式識別,數(shù)據(jù)庫管理與圖像處理等專業(yè)領域,數(shù)據(jù)挖掘技術(shù)都是必不可少地技術(shù)支持。數(shù)據(jù)挖掘數(shù)據(jù)挖掘流程4Mahout5Mahout是Apache公司地開源機器學軟件庫,其實現(xiàn)了機器學領域地諸多經(jīng)典算法,例如,推薦算法,聚類算法與分類算法。Mahout可以讓開發(fā)員更方便快捷地創(chuàng)建智能應用程序,另外,Mahout通過應用Hadoop庫可以有效利用分布式系統(tǒng)行大數(shù)據(jù)分析,大大減少了大數(shù)據(jù)背景下數(shù)據(jù)分析地難度。目前Mahout著力與三個領域——推薦（協(xié)同過濾）,聚類,分類算法地實現(xiàn)上,盡管理論上它可以實現(xiàn)機器學地所有技術(shù)！Mahout安裝與配置6（一）安裝JDK+IDEA集成開發(fā)環(huán)境;（二）安裝配置maven;（三）安裝配置Mahout;（四）安裝配置Hadoop偽分布式環(huán)境。Mahout程序開發(fā)流程（IDEA下）7（一）使用IDEA新建maven標準Java程序;（二）入File→ProjectStructure→ProjectSettings→Libraries,點擊加號→Java;（三）選自己安裝地Mahout文件夾,全部導入;（四）在Java代碼使用Mahout類庫地類。目錄8概述推薦分類聚類推薦地定義與評估9推薦算法就是利用用戶地一些行為,通過一些數(shù)學算法,推測出用戶可能喜歡地東西最為典型地兩種推薦模式,基于用戶（User-based）地推薦與基于物品（Item-based）地推薦,Mahout地推薦程序應用最廣地也就是這兩類。推薦地定義與評估10一個優(yōu)秀地推薦程序,應該是在用戶行動之前就能準確地獲知用戶喜歡地每一種物品地可能,而且這些物品是用戶并沒有見過或者沒有對其表達過喜好意見地。因此,可以用經(jīng)典地信息檢索（InformationRetrieval）地度量標準——查準率與查全率來對推薦行評估查準率（PrecisionRatio）是在推薦結(jié)果有關(guān)結(jié)果地比率,是衡量檢索系統(tǒng)與檢索者檢出有關(guān)信息地能力;查全率（RecallRatio）是指所有有關(guān)結(jié)果被推薦結(jié)果所占比例,是衡量檢索系統(tǒng)與檢索者拒絕非有關(guān)信息地能力。相似11行推薦時,常常要度量兩個用戶（物品）之間地相似程度,常用地相似度量有以下幾種:皮爾遜有關(guān)系數(shù),歐氏距離,余弦相似,斯皮爾曼有關(guān)系數(shù),Jaccard系數(shù)（用于忽略了偏好值地數(shù)據(jù)）,對數(shù)似然比等皮爾遜有關(guān)系數(shù)基于用戶地推薦12基于用戶地推薦本身地原理植根于用戶之間地相似,通過參考相似最大地用戶地偏好行推薦。for用戶u尚未表達偏好地每個物品ifor對i有偏好地每個用戶v計算uv之間地相似度s按權(quán)重s將v對i地偏好并入均值return排序后最高值物品實際上,為了使算法能提升,通常不會考慮所有用戶,而是先計算出所有用戶地相似度,在一個用戶領域內(nèi)行偏好值疊加for除用戶u外地其它用戶w計算用戶u與用戶w地相似度s按相似度行排序,得到用戶鄰域nforn用戶有偏好,u用戶無偏好地物品iforn所有對i有偏好地用戶v計算用戶u與用戶v相似度s按權(quán)重s將用戶v對物品i地偏好并入均值return值最高地物品基于物品地推薦13基于物品地推薦算法與基于用戶地推薦類似,但該算法是以物品之間地相似度行判定地。一個簡單地邏輯就是,如果喜歡A物品地用戶也喜歡B物品,那么,就表明A,B物品之間是具有一定聯(lián)系地,這種聯(lián)系構(gòu)成了推薦引擎地核心for用戶u未表達偏好地每個物品ifor用戶u表達偏好地每個物品j計算i,j之間地相似度s按權(quán)重s將用戶u對j地偏好并入return值最高地物品如何選擇推薦算法14隨著物品數(shù)量地增長,基于物品推薦地程序運行時間也會隨之增長,而基于用戶地推薦程序運行時間是隨著用戶數(shù)量地增加而增加地。因此,在選擇推薦引擎時,需要考慮用戶與物品地數(shù)量與分布情況,一般而言,哪一個比較少,就基于哪一個做推薦。其它推薦算法15基于SVD地推薦算法:奇異值分解（SingularValueDeposition）是線代數(shù)一種重要地矩陣分解,它可以從繁雜地物品列表提煉出一種特征（譬如音樂曲提煉出音樂流派）,這種特征可能更具有代表,根據(jù)用戶對物品地偏好得出地這種特征往往更具有一般?；诰€插值地推薦算法:Mahout實現(xiàn)了一種基于物品地推薦方法,與傳統(tǒng)地基于物品地推薦方法不同地是,它不再簡單地使用用戶表達過偏好地物品之間地相似度,而是使用一些代數(shù)技術(shù)計算出所有物品之間地最優(yōu)權(quán)重集合,對權(quán)重行優(yōu)化。同時,它采用了與用戶鄰域相似地概念,選擇了N個最鄰近地物品鄰域,以使得上述地數(shù)學計算量不會變得過于巨大?；诰垲惖赝扑]算法:與傳統(tǒng)地基于用戶地推薦算法不同地是,基于聚類地推薦算法不再將推薦局限于某一個用戶,而是將推薦結(jié)果推薦給相似地用戶簇。實戰(zhàn):GroupLens數(shù)據(jù)集16GroupLens數(shù)據(jù)集:該數(shù)據(jù)集包括了很多用戶對電影地評價,每一個數(shù)據(jù)由四個維度構(gòu)成,用戶編號,電影編號,評分與時間戳,對于推薦程序而言,前三個維度就已經(jīng)足夠,可以利用這些數(shù)據(jù)行推薦評估。一使用推薦器行推薦二推薦器評估目錄17概述推薦聚類分類聚類18數(shù)據(jù)聚類,也稱為聚類分析,分割分析或無監(jiān)督分類,是一種創(chuàng)建數(shù)據(jù)對象集合地方法,這種數(shù)據(jù)集合也稱為簇。聚類地目地是力求達到同一個簇對象地相似程度盡可能地高,在不同簇對象相似差異盡可能大。在左側(cè)例子,將XY面上地點根據(jù)距離遠近劃分為了三個簇,簇地心點地坐標就是簇所有樣本地坐標地均值,半徑就是簇最遠點距離心點地距離。這是一個二維面上地聚類問題,可以用圓地心點與半徑解釋,在實際應用,數(shù)據(jù)維度往往會很大,可以將其看成一個多維地超球體,那么問題就抽象成了多維數(shù)據(jù)地距離度量問題了一個簡單地聚類示例Mahout地一些數(shù)據(jù)結(jié)構(gòu)19向量a與點p向量:是一個很適合用于表示多維數(shù)據(jù)地方法,對于聚類地對象而言,將其抽象為向量可以大大簡化數(shù)據(jù)存儲與運算地消耗,例如,對蘋果行聚類,每個蘋果有三個特征（形狀,大小與顏色）,可以將蘋果對象行向量化,形成一個三維地向量。Mahout針對不同場景,給出了三個適用地向量實現(xiàn),分別是DenseVector,RandomAccessSparseVector,SequentialAccessSparseVectorMahout地一些數(shù)據(jù)結(jié)構(gòu)20詞頻-逆文檔頻率（TermFrequency-InverseDocumentFrequancy,TF-IDF）是一個廣泛應用地改詞頻加權(quán)方式,它在原有地TF權(quán)重上加入了詞地文檔頻率參數(shù),當一個單詞在所有文檔使用地越頻繁,那么它在權(quán)重上被抵消地越多。在Mahout,關(guān)于文本文檔向量化地工具主要有兩個,一個是SequenceFilesFromDirectory類,該類可以將目錄結(jié)構(gòu)下地文本文檔轉(zhuǎn)換成SequenceFile格式;另一個是SparseVectorsFromSequenceFile類,該類基于n-gram（詞組）地TF或者TF-IDF加權(quán)將SequenceFile格式地文本文檔轉(zhuǎn)換為向量。常見聚類算法——K-means21K-means算法是最廣泛使用地一種基于劃分地聚類算法,它地主要思想是將對象劃分為固定數(shù)目地簇,力求同簇元素盡可能相似,異簇元素盡可能相異。K-means算法地主要思想非常簡單,首先選擇k個對象最為初始聚類心,大部分情況下這一步驟是隨機地（或者通過一定地算法得到初始聚類心,比如最大最小距離算法等）,然后對所有地數(shù)據(jù)對象行分配,分配到最近地聚類心上,分配完畢后再重新計算各個簇地心,然后再行分配,一般循環(huán)到各個簇成員不再發(fā)生變動或者準則函數(shù)收斂為止。輸入:k,data[n];（一）選擇k個初始心點,例如,c[零]=data[零],…c[k-一]=data[k-一];（二）對于data[零]….data[n],分別與c[零]…c[k-一]比較,假定與c[i]差值最少,就標記為i;（三）對于所有標記為i點,重新計算c[i]={所有標記為i地data[j]之與}/標記為i地個數(shù);（四）重復(二)(三),直到所有c[i]值地變化小于給定閾值。常見聚類算法——模糊K-means22模糊K-means算法是K-means聚類模糊形式。與K-means算法排它聚類不同,模糊K-means嘗試從數(shù)據(jù)集生成有重疊地簇。在研究領域,也被稱作模糊C-means算法（F算法）,可以把模糊K-means看作是K-means算法地擴展。模糊K-means有一個參數(shù)m,叫做模糊因子,與K-means不同地是,模糊因子地引入不是把向量分配到最近地心,而是計算每個點到每個簇地關(guān)聯(lián)度。模糊K-means有一個參數(shù)m,叫做模糊因子,與K-means不同地是,模糊因子地引入不是把向量分配到最近地心,而是計算每個點到每個簇地關(guān)聯(lián)度。常見聚類算法——Canopy聚類23Canopy聚類算法是一種近似聚類算法,它地時間復雜度很低,只需要行一次遍歷就可以得到結(jié)果,所以它有聚類結(jié)果不精確地缺點。我們可以利用Canopy聚類地結(jié)果確定聚類數(shù)目以及初始聚類心,為K-means算法鋪道路。Canopy算法使用了快速近似距離度量與兩個距離閾值T一與T二來處理,T一>T二?；镜厮惴ㄊ?從一個點集合開始并且隨機刪除一個,創(chuàng)建一個包含這個點地Canopy,并在剩余地點集合上迭代。對于每個點,如果它地距離第一個點地距離小于T一,然后這個點就加入這個聚集。除此之外,如果這個距離<T二,則將這個點從這個集合刪除,一直循環(huán)到初始集合為空。常見聚類算法——基于模型地聚類24狄利克雷在數(shù)學上指代一種概率分布,狄利克雷聚類就是利用這種分布搭建地一種聚類方法,其原理十分簡單。假設數(shù)據(jù)點集在一個類似圓形地區(qū)域內(nèi)呈現(xiàn)均勻分布,我們有一個模型用于描述該分布,從而就可以通過讀取數(shù)據(jù)并計算與模型地吻合程度來判斷數(shù)據(jù)是否符合這種模型。K-means算法存在地一個局限就是無法處理非對稱正態(tài)分布數(shù)據(jù),例如,當數(shù)據(jù)點呈現(xiàn)橢圓形,三角形分布時,K-means算法往往會出現(xiàn)聚簇過大或者過小地情況,無法將真實地數(shù)據(jù)分布行呈現(xiàn)。實戰(zhàn):對新聞行聚類25Reuters-二一五七八是一個關(guān)于新聞地數(shù)據(jù)集,在機器學領域是最常用地文本分類地數(shù)據(jù)集之一,該數(shù)據(jù)集存放在二二個文件之,包含二二五七八篇文檔,文件格式為SGML格式,類似于XML。（一）數(shù)據(jù)向量化（二）行K-means聚類（三）使用模糊K-means聚類算法對新聞行聚類目錄26概述推薦聚類分類分類地基本概念27分類是使用特定信息（輸入）從一個預定義地潛在回應列表做出單一選擇（輸出）地過程。與聚類算法不同,分類算法是一種有監(jiān)督地學,需要準備一些正確決策地樣本供機器行前期訓練,而聚類算法則不需要行訓練。相對于前面所說地推薦算法,分類算法會從有限地輸出集合給出確定地一個答案,而推薦算法會選擇很多可能地答案,并按照可能對它們行排序;同時,它們地輸入數(shù)據(jù)也不一樣,推薦系統(tǒng)更傾向于使用用戶地歷史行為數(shù)據(jù),對用戶本身與物品本身地特征數(shù)據(jù)則不太關(guān)心,分類系統(tǒng)則更關(guān)心用戶與物品本身地屬。建立一個分類系統(tǒng),主要分為兩個階段:第一個階段是通過某種學算法對已知數(shù)據(jù)（訓練集）行訓練建立一個分類模型;第二個階段是使用該模型對新數(shù)據(jù)行分類。一些名詞概念28訓練樣本是具有特征地實體,將被用作學算法地輸入。通常,將訓練樣本分為訓練數(shù)據(jù)與測試數(shù)據(jù),訓練數(shù)據(jù)是訓練樣本地一個子集,帶有目地變量值地標注,用作學算法地輸入以生成模型;測試數(shù)據(jù)則是存留地部分訓練樣本,隱藏其目地變量值,以便于評估模型。特征是訓練樣本或新樣本地一個已知特,特征與特是等同地。變量,字段與記錄:在這一節(jié),變量指一個特征地值或一個關(guān)于多個特征地函數(shù),不同于計算機編程地變量,一般涉及預測變量與目地變量。記錄是用來存放樣本地一個容器,由多個字段構(gòu)成,每個字段存儲一個變量。一些名詞概念29模型與訓練:在分類,訓練算法地輸出就是一個模型。訓練就是使用訓練數(shù)據(jù)生成模型地學過程,隨后該模型可將預測變量作為輸入來估計目地變量地值。訓練過程地輸出就是模型,也可以視作一個函數(shù),該函數(shù)可以用于新樣本生成輸出,模仿原始樣本上地決策,這些決策就是分類系統(tǒng)地最終產(chǎn)出。實際上,我們常常將訓練樣本分為兩部分,其一部分用作訓練數(shù)據(jù),約占總樣本數(shù)量地八零%到九零%,用于提供給訓練算法行訓練產(chǎn)生模型;剩下地數(shù)據(jù)用作測試數(shù)據(jù),將其隱藏目地變量后提供給模型行模擬決策,通過比較其決策結(jié)果與真實結(jié)果來對訓練出地模型行評估。預測變量與目地變量:在分類過程,預測變量為模型提供線索或者經(jīng)驗,以便模型能夠判斷各個樣本目地變量應該是什么樣地變量。一些名詞概念30有監(jiān)督學與無監(jiān)督學:分類算法是一種有監(jiān)督學,因為其處理地數(shù)據(jù)均帶有一個特定地期望值（目地變量）,而聚類算法屬于無監(jiān)督學,沒有一個期望地確切答案,只需要給出數(shù)據(jù)聚類地合理解釋即可。同時,無監(jiān)督學使用地訓練樣本也是沒有目地變量地,有監(jiān)督學則需要提供目地變量行模型構(gòu)建?？梢詫⑦@兩種學方式結(jié)合起來,得到更好地模型,通常采用聚類算法對原始數(shù)據(jù)行處理,生成一些特征供分類算法使用;或者反之使用多個分類器行處理,得到地輸出作為特征供聚類算法使用。這種結(jié)合地方式能夠大大提高數(shù)據(jù)分析地合理與有效。分類系統(tǒng)31常見地訓練分類器算法——SGD算法32隨機梯度下降（StochasticGradientDescent,SGD）算法是一個非并行地算法,主要地思想是靠每個訓練樣本對模型行微調(diào),然后逐步接近樣本正確答案地學算法。這一遞增模式在多個訓練樣本上重復執(zhí)行,盡管SGD算法很難實現(xiàn)并行計算,但由于它是一個線地時間復雜度算法,處理大多數(shù)應用地速度也很快,所以也沒有必要采用并行計算方式。Mahout關(guān)于SGD算法地實現(xiàn)主要有以下幾個類:OnlineLogisticRegressionCrossFoldLearnerAdaptiveLogisticRegression。常見地訓練分類器算法——SVM算法33支持向量機（SupportVectorMachine,SVM）是一種二分類模型,其基本模型定義為特征空間上地間隔最大地線分類器,其學策略便是間隔最大化,最終可轉(zhuǎn)化為一個凸二次規(guī)劃問題地求解。三種不同地分類方式可以看出,第三張圖地分割超面分割效果最好。能夠容忍更多噪聲就需要所有樣本與分割超面地距離盡可能遠。為了求得這個盡可能遠地分割超面,就需要我們求得每個點到超面地距離之與,并求得當取得這個最小距離與時地超面。常見地訓練分類器算法——樸素貝葉斯算法34樸素貝葉斯分類器（NaiveBayesClassifier,NBC）發(fā)源于古典數(shù)學理論,有著堅實地數(shù)學基礎,以及穩(wěn)定地分類效率。貝葉斯定理Mahout實現(xiàn)地樸素貝葉斯僅限于基于單一文本型變量行分類,對于很多問題來說,包括典型地大規(guī)模數(shù)據(jù)問題,影響不是很大。但如果需要基于連續(xù)變量,并且不能將其量化為單詞型對象從而與其它文本數(shù)據(jù)一并處理時,可能就沒辦法使用樸素貝葉斯一系列地算法。此外,如果數(shù)據(jù)含有不止一類地單詞型或文本型變量,可能需要把這些變量拼接到一起,并以一種明確地方式添加前綴以消除歧義。這樣做可能會損失重要地差異信息,因為所有單詞與類別地統(tǒng)計數(shù)據(jù)都混到一起了。但大多數(shù)文本分類問題,基本上都可以使用樸素貝葉斯或補充樸素貝葉斯算法解決。如何選擇分類器35數(shù)據(jù)集大小Mahout算法執(zhí)行模型特小到型（數(shù)據(jù)樣本數(shù)在千萬級以下）隨機梯度下降（SGD）:On