第一章 緒論

數(shù)據(jù)：網(wǎng)絡(luò)空間的任何事物。

結(jié)構(gòu)化數(shù)據(jù)、半結(jié)構(gòu)化數(shù)據(jù)與無(wú)結(jié)構(gòu)數(shù)據(jù)：后兩者是研究的主要內(nèi)容。

大數(shù)據(jù)定義:狹義指無(wú)法在一定時(shí)間內(nèi)用常規(guī)軟件工具對(duì)其內(nèi)容進(jìn)行抓取、管理和處理的數(shù)據(jù)集合，廣義上指基于多源異構(gòu)、跨域關(guān)聯(lián)的海量數(shù)據(jù)分析所產(chǎn)生的決策流程、商業(yè)模式、科學(xué)范式、生活方式和觀念形態(tài)上的顛覆性變化的總和。

數(shù)據(jù)挖掘是統(tǒng)計(jì)模型的構(gòu)建過(guò)程。

人工智能：究重心在機(jī)器學(xué)習(xí)和推理機(jī)制。算法的理論性強(qiáng)，追求理論的正確性。

數(shù)據(jù)挖掘： 強(qiáng)調(diào)算法的實(shí)用性，不關(guān)心理論問(wèn)題的解決，而是關(guān)心實(shí)際問(wèn)題的解決

第二章：數(shù)據(jù)與處理

數(shù)據(jù)集的類型：記錄數(shù)據(jù)，圖和網(wǎng)絡(luò)數(shù)據(jù)，有序數(shù)據(jù)，多媒體數(shù)據(jù)。

數(shù)據(jù)預(yù)處理任務(wù)：是為了提高數(shù)據(jù)挖掘效率與質(zhì)量進(jìn)行的預(yù)處理工作，包括數(shù)據(jù)清理，數(shù)據(jù)集成，數(shù)據(jù)變換，數(shù)據(jù)規(guī)約，數(shù)據(jù)離散化等。

處理噪聲數(shù)據(jù)的方法：分箱---用臨近數(shù)據(jù)進(jìn)行光滑，如箱均值，中位數(shù)，箱邊界；回歸---將缺失值通過(guò)回歸函數(shù)進(jìn)行預(yù)測(cè)。

處理離群點(diǎn)數(shù)據(jù)：通過(guò)聚類進(jìn)行檢測(cè)，數(shù)據(jù)光滑處理，通過(guò)外部手段糾正等，有時(shí)根據(jù)具體情況不需要處理。

數(shù)據(jù)集成：合并來(lái)自多個(gè)數(shù)據(jù)源的數(shù)據(jù)。

相關(guān)系數(shù)：線性相關(guān)程度

圖片: https://uploader.shimo.im/f/KCTf39hcJLM9It7m.png

卡方檢驗(yàn)（相關(guān)分析）：

圖片: https://uploader.shimo.im/f/TboWeCcY5fgfg9Xa.png

數(shù)據(jù)變換：數(shù)據(jù)的光滑、聚集、泛5化（離散化與分層）、規(guī)范化、特征構(gòu)造等。

第三章 鏈接分析

PageRank算法（網(wǎng)頁(yè)的重要程度僅由指向它的網(wǎng)頁(yè)決定）：

轉(zhuǎn)移矩陣是個(gè)n*n列的方陣，用來(lái)描述隨機(jī)沖浪者的下一步訪問(wèn)行為

? 如果網(wǎng)頁(yè)j有k條出鏈，那么對(duì)每條出邊鏈向的網(wǎng)頁(yè)i，m_ij=1/k

? 其他網(wǎng)頁(yè)的i對(duì)應(yīng)的矩陣元素mij=0

隨機(jī)沖浪的過(guò)程：

基本算法思想

隨機(jī)沖浪者位置的概率分布可以用一個(gè)n維列向量表示，其中分量j代表位于網(wǎng)頁(yè)j的概率。該概率即PageRank值，初始n個(gè)網(wǎng)頁(yè)的初始概率都為V_0。

Web的轉(zhuǎn)移矩陣為M。第一步之后，沖浪者的概率分布向量是Mv0，第二步為M^2v0，i步后為M^iv_0.

收斂前提條件：1.圖為強(qiáng)連通圖 2.不存在終止節(jié)點(diǎn)

算法終止條件：M^（i+1）v_0 = M^iv_0 ----迭代前后結(jié)果差異足夠小，一般50~75次即可收斂

算法優(yōu)化

處理終止點(diǎn)問(wèn)題：

將其行列從圖中剔除，若產(chǎn)生新的終止點(diǎn)，則迭代刪除，直至無(wú)終止點(diǎn)。

修改隨機(jī)沖浪者在Web上的沖浪過(guò)程

終止點(diǎn)的PageRank值：

對(duì)刪除終止點(diǎn)之后的圖G，計(jì)算出各節(jié)點(diǎn)的PageRank值

恢復(fù)到原圖，但仍然保留G中各節(jié)點(diǎn)的PageRank值

對(duì)不在G中的終止點(diǎn)及偽終止點(diǎn)：

若所有指向它的網(wǎng)頁(yè)P(yáng)ageRank都已算出，則它的PageRank=∑這些網(wǎng)頁(yè)的PageRank/出鏈數(shù)，否則等待其他終止點(diǎn)網(wǎng)頁(yè)計(jì)算PageRank。即按照終止點(diǎn)刪除順序的逆序進(jìn)行節(jié)點(diǎn)的PageRank計(jì)算。

采集器陷阱及“抽稅法”：采集器陷阱指的是一系列節(jié)點(diǎn)，它們可能互相鏈接，但是卻不會(huì)鏈接集合以外的節(jié)點(diǎn)，即沒(méi)有出鏈指向集合之外。當(dāng)采集器（爬蟲(chóng)程序）一旦進(jìn)入采集器陷阱，將無(wú)法跳出。

solution：抽稅機(jī)制--進(jìn)行隨機(jī)跳轉(zhuǎn)：允許隨機(jī)沖浪者以一個(gè)較小的概率隨機(jī)跳轉(zhuǎn)到一個(gè)隨機(jī)網(wǎng)頁(yè)，而不一定沿著當(dāng)前網(wǎng)頁(yè)的出鏈前進(jìn)。

圖片: https://uploader.shimo.im/f/jHWyyeqxeqkCT1f5.png

其中，β是選定的常數(shù)，通常取值在0.8到0.9之間。e是一個(gè)所有分量都為1、維數(shù)為n的向量，n是Web圖中所有節(jié)點(diǎn)的數(shù)目。

PageRank優(yōu)點(diǎn)：由于M的稀疏性計(jì)算快速，且避免了磁盤(pán)的大量使用?？梢詫⑾∈杈仃噳嚎s表示（方法如下，轉(zhuǎn)移矩陣是特殊的稀疏矩陣）

圖片: https://uploader.shimo.im/f/ydit1i6wJrgo4lx4.png

圖片: https://uploader.shimo.im/f/gjdVDmaSf80NM8bC.png

面向主題的Page Rank

有偏的隨機(jī)游走模型：識(shí)別特定主題的網(wǎng)頁(yè)集合，作為隨機(jī)跳轉(zhuǎn)集合的范圍，只有該集合中的網(wǎng)頁(yè)才能共享抽稅部分所占的PageRank值。

假定整數(shù)集合S由已知屬于某個(gè)主題的網(wǎng)頁(yè)，e_s是一個(gè)向量，若其分量對(duì)應(yīng)的網(wǎng)頁(yè)屬于S，則該分量置為1，否則為0，面向主題S的PageRank值是圖片: https://uploader.shimo.im/f/th4Ni0EDHxkUACgA.png的極限。其中，︱S︱是集合S的大小

鏈接作弊及應(yīng)對(duì)

人工增加某個(gè)特定網(wǎng)頁(yè)P(yáng)ageRank的方法稱為鏈接作弊，由此得到的信息統(tǒng)稱為垃圾

不可達(dá)網(wǎng)頁(yè)（Inaccessible pages），作弊者無(wú)法影響的網(wǎng)頁(yè)，Web中的絕大多數(shù)網(wǎng)頁(yè)

可達(dá)網(wǎng)頁(yè)（Accessible pages），不受作弊者控制，但可以影響的網(wǎng)頁(yè)

如評(píng)論網(wǎng)頁(yè)，作弊者可以在其上粘貼指向自有網(wǎng)頁(yè)的鏈接

自有網(wǎng)頁(yè)（Own pages），被作弊者完全控制的網(wǎng)頁(yè)

可能跨越多個(gè)域名

垃圾農(nóng)場(chǎng)：目標(biāo)是最大化目標(biāo)網(wǎng)頁(yè)的PageRank值，技術(shù)：在可達(dá)網(wǎng)頁(yè)上盡可能多的構(gòu)造指向目標(biāo)網(wǎng)頁(yè)的鏈接、構(gòu)造“鏈接農(nóng)場(chǎng)”來(lái)形成PageRank值的倍增效應(yīng)

垃圾農(nóng)場(chǎng)放大效果計(jì)算：令X為所有可達(dá)網(wǎng)頁(yè)為垃圾農(nóng)場(chǎng)提供的PageRank總量，m為自由網(wǎng)頁(yè)數(shù)量，則目標(biāo)網(wǎng)頁(yè)P(yáng)ageRank值y為圖片: https://uploader.shimo.im/f/fhCCyQHyzfkF5wtE.png

Solution：

Trust Rank和垃圾質(zhì)量： 思想是可靠網(wǎng)頁(yè)不太可能指向垃圾網(wǎng)頁(yè)。

垃圾質(zhì)量=（PageRank-TrustRank）/PageRank, 越大越可能是垃圾網(wǎng)頁(yè)，負(fù)數(shù)或小正數(shù)可能是正常網(wǎng)頁(yè)

Timed-PageRank:? ? PageRank算法+時(shí)效性，引入時(shí)間函數(shù)f(t)∈[0,1], t為距上次更新的時(shí)間，表示沖浪者沿所在網(wǎng)頁(yè)的鏈接繼續(xù)沖浪的概率，1-f(t) 為跳轉(zhuǎn)到隨機(jī)網(wǎng)頁(yè)的概率。

HITS算法（網(wǎng)頁(yè)的重要程度由與它關(guān)聯(lián)的所有網(wǎng)頁(yè)共同決定，包含出鏈和入鏈）

權(quán)威頁(yè)（authority）：某些網(wǎng)頁(yè)提供了有關(guān)某個(gè)主題的信息，因此它們具有非常重要的價(jià)值，這些網(wǎng)頁(yè)被稱為權(quán)威頁(yè)? 例如：課程主頁(yè)、汽車(chē)制造商的網(wǎng)頁(yè)等

權(quán)威度(a=authority)：該網(wǎng)頁(yè)充當(dāng)權(quán)威頁(yè)的良好程度，通過(guò)累加所有鏈入網(wǎng)頁(yè)的導(dǎo)航度來(lái)估算當(dāng)前頁(yè)的權(quán)威度。

導(dǎo)航頁(yè)（h=hub）：鏈向權(quán)威頁(yè)的網(wǎng)頁(yè)，它們雖然并不提供有關(guān)任何主題的信息，但是卻可以給出找到關(guān)于該主題的網(wǎng)頁(yè)的信息，因此它們也具有重要價(jià)值? 例如：院系門(mén)戶網(wǎng)頁(yè)、汽車(chē)制造商列表等

導(dǎo)航度：該網(wǎng)頁(yè)充當(dāng)導(dǎo)航頁(yè)的良好程度，通過(guò)累加所有鏈出網(wǎng)頁(yè)的權(quán)威度來(lái)估算當(dāng)前頁(yè)的導(dǎo)航度

Web鏈接矩陣L：若有n個(gè)網(wǎng)頁(yè)，那么L就是一個(gè)n*n的矩陣，如果網(wǎng)頁(yè)i到j(luò)存在一個(gè)鏈接，則Lij=1，否則Lij=0

導(dǎo)航度 h = λLa ，權(quán)威度a = μL^Th ,其中λ和μ是代表歸一化因子的常數(shù)，兩個(gè)式子通過(guò)迭代進(jìn)行計(jì)算，并將每次結(jié)果進(jìn)行最大分量歸一化，直至收斂。

第四章 發(fā)現(xiàn)相似項(xiàng)

近鄰搜索的應(yīng)用（尋找相似的集合）

如檢測(cè)抄襲文檔，Web鏡像檢測(cè)

集合的Jaccard相似度圖片: https://uploader.shimo.im/f/APHprmWnxO0JYd4k.png? 計(jì)算時(shí)注意包和集合的區(qū)分? https://www.cnblogs.com/chenxiangzhen/p/10648503.html? 鏈接為各種距離度量

如果數(shù)據(jù)存在“分?jǐn)?shù)膨脹“問(wèn)題，就使用皮爾遜相關(guān)系數(shù)

如果數(shù)據(jù)比較密集，變量之間基本都存在共有值，且這些距離數(shù)據(jù)都是非常重要的，那就使用歐幾里得或者曼哈頓距離

如果數(shù)據(jù)是稀疏的，就使用余弦相似度

TF.IDF---- 詞項(xiàng)頻率乘以逆文檔頻率

-是對(duì)給定詞語(yǔ)在少數(shù)文檔中反復(fù)出現(xiàn)程度的形式化度量，正相關(guān)于某詞在該篇文檔的出現(xiàn)頻率 和 該詞在其他文檔的未出現(xiàn)次數(shù)。

圖片: https://uploader.shimo.im/f/PUQwGlgfwd4AtNQ5.png

K-shingling 算法 （將文檔看成一個(gè)字符串，K表示劃分粒度，可以是k長(zhǎng)的子串，也可以是k個(gè)單詞 等，將文檔都用一個(gè)或多個(gè)k-Shingle集合表示）

k的選擇：5-9.太小會(huì)造成文檔相似性太高，太大也會(huì)造成不準(zhǔn)確。

shingle的壓縮處理：可以將k長(zhǎng)字符串通過(guò)哈希映射到定長(zhǎng)（如四字節(jié)）桶編號(hào)，將桶編號(hào)作為最終的shingle，文檔即被表示成桶編號(hào)的集合。

將9-shingles映射到4字節(jié)整數(shù)進(jìn)行處理，與直接使用4-shingles來(lái)表示文檔的區(qū)別？

答：從適用范圍看，4字節(jié)的桶編號(hào)范圍為[0,2^32-1], 9shingles映射到四字節(jié)桶編號(hào)能夠比較充分地保留較長(zhǎng)shingles的差異性，即能夠較好地進(jìn)行長(zhǎng)文本相似性對(duì)比，而4-shingles更適合短文本的差異性比較。但從存儲(chǔ)角度來(lái)看，由于桶編號(hào)是4字節(jié)，單篇文本用第一種方法存儲(chǔ)shingles約需要四倍文檔大小的存儲(chǔ)空間，與4shingles的存儲(chǔ)大約相同。

基于詞的shingle

最小哈希Minhashing：映射到四個(gè)字節(jié)的shingle集合約為文檔4倍大小，還是很大。當(dāng)文檔數(shù)增大時(shí)不能直接裝入內(nèi)存。該技術(shù)用較小的“簽名”表示shingle集合，可以較好地估計(jì)集合相似度。

集合構(gòu)造簽名包含大量計(jì)算，每次計(jì)算是特征矩陣的minhashing過(guò)程：– 首先選擇行號(hào)的一個(gè)排列進(jìn)行行變換，每列的最小哈希值為變換后的1所在行的最小行號(hào)。

經(jīng)過(guò)隨機(jī)行打亂后，兩個(gè)集合的最小哈希值相等的概率等于這兩個(gè)集合的Jaccard相似度

最小哈希簽名：對(duì)于表示集合S的特征矩陣M，隨機(jī)選擇n（幾百個(gè)）個(gè)排列轉(zhuǎn)換用于行排列，則每列對(duì)應(yīng)有各自的n個(gè)最小哈希值，每列的這些值作為該列的最小哈希簽名向量，這些向量構(gòu)成了一個(gè)n行*M的列數(shù) 列的簽名矩陣，空間更小。

計(jì)算過(guò)程：顯式的排列轉(zhuǎn)換不適用大規(guī)模矩陣，通過(guò)哈希函數(shù)模擬排列的效果。將行號(hào)映射到與行數(shù)目大致相等數(shù)量的桶中，數(shù)量很大且哈希結(jié)果沖突不頻繁時(shí)，可以假設(shè)r行放在H（r）位置。這樣選擇n個(gè)哈希函數(shù)模擬行排列。

具體算法過(guò)程參考ppt，簽名向量的相似度一定程度上能反映特征向量的相似度。

局部敏感哈希算法（LSH）或近鄰搜索：只關(guān)注相似的文檔，不用分析所有文檔時(shí)使用。

算法思路：使用函數(shù)f（x，y）判斷文檔相似度，將哈希矩陣中每一列哈希映射到桶中，對(duì)每個(gè)桶中文檔進(jìn)行相似判斷。進(jìn)行多次哈希操作，盡可能使只有最相似的列在一個(gè)桶，將桶中集合作為候選對(duì)進(jìn)行相似判斷。目標(biāo)是盡可能減小偽正例和偽反例

計(jì)算過(guò)程：

M劃分為b個(gè)行條，每個(gè)r行

行條中每一列哈希映射到k個(gè)桶中（k足夠大）

候選列對(duì)為至少在一個(gè)行條中被映射到同一桶中的列對(duì)

調(diào)整b和r，獲得盡可能多的相似對(duì)與盡可能少的非相似對(duì)

第五章 頻繁模式挖掘、關(guān)聯(lián)和相關(guān)性

頻繁模式：數(shù)據(jù)集中頻繁出現(xiàn)的模式。

k項(xiàng)集：包含k個(gè)項(xiàng)的集合。

項(xiàng)的支持頻度（支持度計(jì)數(shù)或計(jì)數(shù)），項(xiàng)的相對(duì)支持度（支持度/全體事務(wù)）

頻繁項(xiàng)集：項(xiàng)集支持度滿足預(yù)定義的最小支持度閾值

圖片: https://uploader.shimo.im/f/BkbRUd2ClasT4HEV.png

關(guān)聯(lián)規(guī)則挖掘：找出頻繁項(xiàng)集（滿足最小支持度），產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則（同時(shí)滿足最小置信度）

X在D中是閉的：不存在真超項(xiàng)集Y，使Y與X在D中具有相同的支持度計(jì)數(shù)

閉頻繁項(xiàng)集：X是閉的和頻繁的

極大頻繁項(xiàng)集：X在D中頻繁，且不存在超項(xiàng)集Y且Y在D中也是頻繁的。稱X是極大頻繁項(xiàng)集。

圖片: https://uploader.shimo.im/f/Hvjc16cxMYQiXlSM.png

頻繁項(xiàng)集的挖掘策略：

減少候選集的數(shù)量（減小M）（剪枝策略）

減少事務(wù)的數(shù)量（減小N）（不包含任何k項(xiàng)集的事務(wù)在候選k+1時(shí)刪除）

減少比較的數(shù)量（減小NM）

先驗(yàn)性質(zhì)：頻繁項(xiàng)集的所有非空子集也一定頻繁，即非頻繁項(xiàng)的所有超集都是非頻繁的。

Apriori算法（思想）：

連接步：通過(guò)將Lk與自身連接，產(chǎn)生候選（k+1）項(xiàng)集Ck+1

剪枝：掃描數(shù)據(jù)庫(kù),確定Ck+1中每個(gè)項(xiàng)的計(jì)數(shù)，從而確定Lk+1

當(dāng)沒(méi)有頻繁項(xiàng)集L或候選項(xiàng)集產(chǎn)生時(shí)算法終止。

圖片: https://uploader.shimo.im/f/51D61kUzgKcbUJBI.png

圖片: https://uploader.shimo.im/f/8IrWuOtOa8kGWhyE.png

圖片: https://uploader.shimo.im/f/2JgmCbCQNHExTJRD.png

項(xiàng)的表示優(yōu)化：

將字符串項(xiàng)哈希轉(zhuǎn)化為整數(shù)

三角矩陣：用一位數(shù)組存儲(chǔ)作為二項(xiàng)集的映射（ij映射為數(shù)組下標(biāo)）

用三元組存儲(chǔ)項(xiàng)對(duì)

2-項(xiàng)集計(jì)數(shù)內(nèi)存優(yōu)化：無(wú)法在內(nèi)存中對(duì)所有項(xiàng)集計(jì)數(shù)，減少需要計(jì)數(shù)的2-項(xiàng)集數(shù)目，掃描兩遍

第一遍掃描：建立項(xiàng)名與整數(shù)映射表，建立計(jì)數(shù)數(shù)組，下標(biāo)為對(duì)應(yīng)的項(xiàng)集映射整數(shù)，掃描并計(jì)數(shù)。

第一遍掃描后：檢查項(xiàng)的計(jì)數(shù)值，確定頻繁1項(xiàng)集，將其按照數(shù)量m進(jìn)行1-m編號(hào)，在計(jì)數(shù)數(shù)組中將對(duì)應(yīng)值改為編號(hào)。

第二遍掃描：用三角矩陣法，空間為2m^2，也可用三元組方法

PCY算法：第一次掃描時(shí)，將每個(gè)事務(wù)產(chǎn)生的二項(xiàng)集散列到不同桶中，并增加桶計(jì)數(shù)，掃描結(jié)束后用bitmap來(lái)記錄哪個(gè)是頻繁桶，生成候選項(xiàng)集選擇時(shí)，留下在頻繁桶中的候選集，不在候選集的則刪除。

效果： 如果大部分桶都是非頻繁的，那么第二次掃描需要計(jì)數(shù)的項(xiàng)對(duì)數(shù)目會(huì)顯著降低。與Apriori相比，項(xiàng)對(duì)的表示只能采用三元組法，只減少了2-項(xiàng)集的計(jì)算，如果不能減少至少2/3的頻繁對(duì)，則PCY并不比Apriori算法更好。

多階段算法：第一遍掃描同SPY，在第二次掃描時(shí)用里一個(gè)哈希函數(shù)建立第二張哈希表，第二張哈希表與第一張桶數(shù)目接近，進(jìn)行第二次掃描時(shí)進(jìn)行哈希的項(xiàng)對(duì){i，j}：i，j都是頻繁項(xiàng)，且{i，j}

在第一遍掃描中被哈希到一個(gè)頻繁桶。兩個(gè)bitmap。

候選二項(xiàng)集的條件：i和j都是頻繁項(xiàng)，{i,j}哈希到第一張表的某個(gè)頻繁桶中，同時(shí)也哈希到第二張表的某個(gè)頻繁桶中

效果：第二張哈希表的計(jì)數(shù)值之和，顯著低于第一張哈希表的計(jì)數(shù)值之和，期望第二張表中頻繁桶的數(shù)目遠(yuǎn)低于第一張表。

多哈希算法：在第一次掃描時(shí)同時(shí)使用兩個(gè)哈希函數(shù)和兩張獨(dú)立的哈希表，就得到了多階段掃描的好處。

風(fēng)險(xiǎn)：使用兩張哈希表，但每張表的桶只有PCY的一半。

期望：只要PCY中每個(gè)桶的平均計(jì)數(shù)值遠(yuǎn)小于支持度閾值，就可以使用兩張一半大小的表并期望大部分桶都是非頻繁的。

Apriori的進(jìn)一步改進(jìn)：

較少比較次數(shù)，不再將每個(gè)事務(wù)與每個(gè)候選項(xiàng)集進(jìn)行比較，而是將事務(wù)與存在哈希桶中的候選項(xiàng)進(jìn)行比較

構(gòu)造哈希樹(shù)，可以明顯減少比較次數(shù)

頻繁模式增長(zhǎng)：

? 將代表頻繁項(xiàng)集的數(shù)據(jù)壓縮到一棵頻繁模式樹(shù)（FP-樹(shù)），? 建立頻繁模式樹(shù)之后，采用遞歸的分治方法直接挖掘頻繁項(xiàng)集

方法：掃描第一次并計(jì)數(shù)，由長(zhǎng)度為1的頻繁模式開(kāi)始，構(gòu)造條件模式基并排序。

掃描第二次，將事務(wù)也同序排序并構(gòu)建FP樹(shù)。。。。。

保持了用于頻繁模式挖掘的全部信息，沒(méi)有打斷任何事務(wù)中的長(zhǎng)模式。簡(jiǎn)潔性。

垂直數(shù)據(jù)格式：? 確定k-項(xiàng)集的支持度：對(duì)它的任意（k-1)子集求交集

圖片: https://uploader.shimo.im/f/BLUHHjw79O81Jm9h.png圖片: https://uploader.shimo.im/f/BQCT63MEf4QTWMzg.png

優(yōu)點(diǎn)：計(jì)算快，無(wú)需掃描數(shù)據(jù)庫(kù)

缺點(diǎn)：不適合大規(guī)模TID列表

圖片: https://uploader.shimo.im/f/9UfE6ImUgekTg1o5.png

有限掃描算法：只選擇購(gòu)物籃的隨機(jī)子集看做數(shù)據(jù)集。

偽正例：再做一次掃描去除。

偽反例：放松支持度閾值減小數(shù)量。

SON算法：兩次掃描去掉所有偽正例和偽反例。

方法：先分塊，計(jì)算后將各塊的頻繁項(xiàng)集合并，第二遍掃描確定最終的頻繁項(xiàng)集。

產(chǎn)生關(guān)聯(lián)規(guī)則：? 給定頻繁項(xiàng)集L，找出L的所有非空子集f（f?L） ，且滿足規(guī)則f→{L–f}滿?足最小置信度閾值要求

圖片: https://uploader.shimo.im/f/Y9jdC9K2v34JBWUf.png

按照該原則可以優(yōu)化剪枝方法。

候選規(guī)則的生成：

合并兩條在規(guī)則的后件中有共享前綴的規(guī)則。連接(CD=>AB,BD=>AC)可以生成候選規(guī)則D => ABC，

刪除規(guī)則D=>ABC，若其子集CD=>AB不不具有高置信度的話

模式評(píng)價(jià)：

置信度的局限性。各種度量都有其局限性。

度量的對(duì)稱性與非對(duì)稱性。

序列數(shù)據(jù)：

子序列：序列列 <a1 a2 … an>包含于另一個(gè)序列列 <b1 b2 … bm> (m ≥ n) ，如果i

存在整數(shù)i1 < i2 < … < in 使得 a1 ? bi1 , a2 ? bi2, …, an ? bin

GSP算法

第六章 聚類分析

無(wú)監(jiān)督學(xué)習(xí)，即無(wú)先驗(yàn)類劃分。可以單獨(dú)用來(lái)了解數(shù)據(jù)分布，也可以作為其他數(shù)據(jù)挖掘任務(wù)的與處理過(guò)程。

簇的中心：

質(zhì)心點(diǎn)：平均。

中心點(diǎn)：最有代表性的點(diǎn)。

評(píng)價(jià)聚類的質(zhì)量：

相異/相似矩陣 ，距離函數(shù)的定義

聚類方法：層次聚類和劃分聚類。

層次聚類：–創(chuàng)建給定數(shù)據(jù)集的層次分解。 形成一系列嵌套的簇，組合成層次樹(shù)。

劃分聚類：– 將數(shù)據(jù)對(duì)象分解為不重疊的子集（簇）。 每個(gè)數(shù)據(jù)對(duì)象都在唯一的子集中。

簇間的距離

? 單鏈：一個(gè)簇中的對(duì)象與另一個(gè)簇中對(duì)象距離的最小值

? 全鏈：一個(gè)簇中的對(duì)象與另一個(gè)簇中對(duì)象距離的最?大值

? 均值：一個(gè)簇中的對(duì)象與另一個(gè)簇中對(duì)象距離的平均值

基于質(zhì)心的距離或基于中心（主觀選擇）的距離

簇的半徑：簇中成員對(duì)象到質(zhì)心的平均距離

簇的直徑：簇中逐對(duì)對(duì)象的平均距離

層次聚類的優(yōu)點(diǎn)：不需假設(shè)簇的數(shù)量，數(shù)量由樹(shù)狀圖的切割方式得到

缺點(diǎn)：不不同的方法都會(huì)遇到下列列的?一個(gè)或多個(gè)問(wèn)題：

–對(duì)噪聲和離群點(diǎn)比較敏敏感

–難以處理理不不同規(guī)模的簇或者凸形狀的簇

–將較大的簇分開(kāi)了了

凝聚聚類算法：

計(jì)算相似矩陣

每個(gè)點(diǎn)看做獨(dú)立的簇

重復(fù)以下過(guò)程：合并最近的兩個(gè)類，更新相似矩陣，直到只有一個(gè)類

空間復(fù)雜度為O（N方），相似度矩陣存儲(chǔ)為n方大小，時(shí)間復(fù)雜度是O(n3）或O（n2logn）相似矩陣進(jìn)行n步查詢。

距離度量方法：

使用單鏈（MIN）度量方法的優(yōu)點(diǎn)與缺點(diǎn)：能夠處理非橢圓形狀的簇，但對(duì)噪聲和孤立點(diǎn)非常敏感.

使用全鏈（MAX）度量方法的優(yōu)點(diǎn)與缺點(diǎn)：對(duì)噪聲和離群點(diǎn)不敏感，但可能使較大的簇破裂，偏好形成球形的簇

使用均值度量：兩個(gè)簇的相似度是兩個(gè)簇間所有點(diǎn)對(duì)相似度的平均值。是全鏈和單鏈的折中，對(duì)噪聲和離群點(diǎn)不敏感，但也傾向于形成規(guī)則的圖形。

birth算法

是一種能夠高效處理大數(shù)據(jù)聚類的基于樹(shù)的層次聚類算法

線性擴(kuò)展：通過(guò)一次掃描發(fā)現(xiàn)較好的簇結(jié)構(gòu)，并且通過(guò)少數(shù)幾次新的掃描提?高簇的質(zhì)量量

缺點(diǎn)：對(duì)插?入數(shù)據(jù)順序是敏敏感的

– 限制了了葉節(jié)點(diǎn)的規(guī)模，?生成的簇不夠?自然

– 傾向于形成球形的簇

– 只適合于數(shù)值數(shù)據(jù)

K-means聚類

圖片: https://uploader.shimo.im/f/wfzsOSiUclE5Jo68.png

質(zhì)心初始隨機(jī)化，通常在計(jì)算中將簇中點(diǎn)的均值作為下次迭代的質(zhì)心

評(píng)價(jià)標(biāo)準(zhǔn)為SSE：每個(gè)點(diǎn)到最近簇的距離的平方和

圖片: https://uploader.shimo.im/f/polmcnnAT2sG48Wf.png

K-means對(duì)初始點(diǎn)選擇十分敏感

解決方法：

多運(yùn)行幾次

抽樣，使用層次聚類確定初始質(zhì)心

選擇多于K個(gè)初始質(zhì)心，從中選擇合適的質(zhì)心

二分K-means

空簇的處理：

選取一個(gè)新的質(zhì)心點(diǎn)替代，可以是對(duì)SSE貢獻(xiàn)最大的點(diǎn)，即離質(zhì)心最遠(yuǎn)的點(diǎn)，也可以在具有最大SSE的簇中選擇點(diǎn)，這可以導(dǎo)致簇的分裂從而降低SSE。

預(yù)處理與后處理

預(yù)處理：數(shù)據(jù)規(guī)范化，刪除離群點(diǎn)

后處理：排除可能代表離群點(diǎn)的小簇，分裂松散的簇與合并較近的簇

二分K-means

首先將所有點(diǎn)作為一個(gè)簇，然后將該簇一分為二。之后選擇一個(gè)簇繼續(xù)進(jìn)行劃分，選擇哪一個(gè)簇進(jìn)行劃分取決于對(duì)其劃分是否可以最大程度降低SSE的值。而劃分就是上面提到的K-均值的思想了，利用上面的函數(shù)k設(shè)為2來(lái)劃分。通過(guò)不斷重復(fù)的操作，直到達(dá)到需要的簇?cái)?shù)量。

通過(guò)測(cè)量量不不同k值情況下聚類結(jié)果的質(zhì)量，通常可以分析出正確的k值

K-means的缺點(diǎn)：

當(dāng)簇有著不不同的 規(guī)模? 密度? 不不規(guī)則形狀，數(shù)據(jù)包括離群點(diǎn)時(shí)，k-means可能出現(xiàn)問(wèn)題

BFR算法：

在高位空間進(jìn)行聚類，思想是假設(shè)簇的行狀滿足以質(zhì)心為期望的正態(tài)分布。

CURE算法（歐式空間）：可以處理不同形狀的類

點(diǎn)分配的大規(guī)模聚類算法，

1.抽取一部分?jǐn)?shù)據(jù)在內(nèi)存中進(jìn)?行行聚類

- 理理論上，可以采?任何的內(nèi)存聚類算法

- 由于簇可以是任意形狀，通常采用層次聚類的?方法

- CURE算法的特點(diǎn)是能夠處理理形狀古怪的簇

2.從每個(gè)簇中，選擇一小部分點(diǎn)作為簇的代表點(diǎn)，選出的點(diǎn)之間盡量量相距較遠(yuǎn)

3.將每個(gè)代表點(diǎn)移動(dòng)一段距離

- 距離其位置到簇質(zhì)心的距離乘以一定比例，如20%

- 這一步必須在歐式空間下進(jìn)行，否則“兩點(diǎn)間線段”沒(méi)有定義

1.當(dāng)兩個(gè)簇的某對(duì)代表點(diǎn)（分別來(lái)自不不同的簇）之間足夠接近，就將兩個(gè)簇合并；

- “接近”的距離可以自行定義；

- 重復(fù)該過(guò)程，直到?jīng)]有?夠接近的簇為止；

2.進(jìn)行點(diǎn)分配。

費(fèi)歐式空間的聚類：

基于密度的聚類方法：

兩個(gè)參數(shù)：

Eps：每個(gè)對(duì)象鄰域的半徑

MinPts 稠密區(qū)域的密度閾值，一個(gè)對(duì)象鄰域內(nèi)點(diǎn)的最小數(shù)量。

圖片: https://uploader.shimo.im/f/q0202pMDPnExujTz.png

? 核心點(diǎn)：一個(gè)數(shù)據(jù)點(diǎn)的??-鄰域中至少包含MinPts個(gè)數(shù)據(jù)點(diǎn)

? 邊界點(diǎn)：一個(gè)數(shù)據(jù)點(diǎn)的??-鄰域中包含的數(shù)據(jù)點(diǎn)的數(shù)量量少于MinPts，但是數(shù)據(jù)點(diǎn)位于某個(gè)核心點(diǎn)的??-鄰域中

噪聲點(diǎn)：既不是核心點(diǎn)，也不是邊界點(diǎn)的數(shù)據(jù)點(diǎn)

直接密度可達(dá)：對(duì)于核心點(diǎn)q和數(shù)據(jù)點(diǎn)p，p是從q直接密度可達(dá)的，如果p在q的??-鄰域內(nèi)。

密度可達(dá)：數(shù)據(jù)點(diǎn)p是從q（關(guān)于??和MinPts）密度可達(dá)的，如果存在一個(gè)對(duì)象鏈，p1, …, pn, p1 = q, pn = p ，并且對(duì)于pi ，pi+1 是從pi 直接密度可達(dá)的。圖左圖片: https://uploader.shimo.im/f/lGSKBE3mWhs0KpQT.png圖片: https://uploader.shimo.im/f/ci9RPy1pHKsA51Yi.png

密度相連：數(shù)據(jù)點(diǎn)p和q是（關(guān)于??和MinPts）密度相連的，如果存在一個(gè)數(shù)據(jù)點(diǎn)o，使得p和q都是從o（關(guān)于??和MinPts）密度可達(dá)的。

依靠與基于密度的簇的定義：一個(gè)簇是密度相連的數(shù)據(jù)點(diǎn)的最大集合

這樣的定義可以在有噪聲的空間中發(fā)現(xiàn)任意形狀的簇

DBSCAN算法：

能有效的處理理噪聲數(shù)據(jù)

? 能有效處理理不不同形狀和規(guī)模的簇

不適合同簇密度不同的數(shù)據(jù)與高維數(shù)據(jù)

去除噪聲點(diǎn)：

圖片: https://uploader.shimo.im/f/n0QbSJeaRoUm6tM5.png

聚類評(píng)估的主要任務(wù)：估計(jì)聚類趨勢(shì)，確定簇的數(shù)量，評(píng)價(jià)聚類質(zhì)量。

深度學(xué)習(xí)兩章

圖片: https://uploader.shimo.im/f/RmlzM0SAxaY9MDLq.png

? ? ? ? ? ? ? ? 圖片: https://uploader.shimo.im/f/mh10DAcZpzoDZfpM.png? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

圖片: https://uploader.shimo.im/f/6Zgj2WzbI4sBOH4K.png

通用逼近定理：神經(jīng)網(wǎng)絡(luò)能以任意精度逼近功的連續(xù)函數(shù)，即使對(duì)于只有一個(gè)隱藏層的神經(jīng)網(wǎng)絡(luò)，這結(jié)論依然成立。

損失函數(shù)：如平方誤差SSE，交叉熵等

梯度下降圖片: https://uploader.shimo.im/f/osA2n3zBKQAOnysH.png，達(dá)到局部最小值

可采用自適應(yīng)學(xué)習(xí)率，如隨迭代次數(shù)不斷減小學(xué)習(xí)率

AdaGrad算法? 每個(gè)參數(shù)在各自維度上收斂速度不相同，根據(jù)不同收斂情況分別設(shè)置學(xué)習(xí)率，即每次迭代自適應(yīng)地調(diào)整每個(gè)參數(shù)的學(xué)習(xí)率。

反向傳播算法：利用輸出誤差估 計(jì)層的直接前導(dǎo)，再其利用其估計(jì)更前一層誤差，逐反傳下去直至獲得所有其他各層的誤差估計(jì)，基于此修正權(quán)值。

收斂判定：誤差最小，一般取誤差函數(shù)局部梯度零點(diǎn)。

數(shù)據(jù)集拆分：留出法，k-折交叉驗(yàn)證

CNN三大特點(diǎn)：局部連接，權(quán)值共享，池化算法（maxpooling或meanpooling）

通過(guò)kernel近似卷積的計(jì)算，CNN具有參數(shù)更少，收斂更快，能進(jìn)行區(qū)域特征識(shí)別的優(yōu)勢(shì)。

第二部分

第一章? 多元數(shù)據(jù)的數(shù)學(xué)表達(dá)與統(tǒng)計(jì)描述

隨機(jī)變量與隨機(jī)（變量）向量 參見(jiàn)隨機(jī)過(guò)程

總體期望與方差，協(xié)方差矩陣圖片: https://uploader.shimo.im/f/kpJD7RfyajUpNDxe.png

二階距存在才有方差哦

圖片: https://uploader.shimo.im/f/Ld1x5emyudEPvBlT.png

圖片: https://uploader.shimo.im/f/P09cCzkiFU4FnCpR.png

相互獨(dú)立：聯(lián)合分布等于邊緣分布乘積，密度函數(shù)同理圖片: https://uploader.shimo.im/f/HzyxJ1k35AIZzaPP.png

不相關(guān)：相關(guān)系數(shù)為0

圖片: https://uploader.shimo.im/f/M82godBiRR0ZKviY.png

圖片: https://uploader.shimo.im/f/XusevrfvKygmFPeD.png

圖片: https://uploader.shimo.im/f/TBcHGkI81Co3lrG4.png

圖片: https://uploader.shimo.im/f/YIVXbchsa5c3jGot.png

圖片: https://uploader.shimo.im/f/TOjsx1QzeTourYKA.png

圖片: https://uploader.shimo.im/f/oNQkGn5AoTMbs6iV.png

樣本協(xié)方差與樣本協(xié)方陣

圖片: https://uploader.shimo.im/f/5inoqF4EFWsRVImD.png

圖片: https://uploader.shimo.im/f/h2MxcondUtI5zIjL.png

圖片: https://uploader.shimo.im/f/fqwoaX0QoBsQ80mk.png

圖片: https://uploader.shimo.im/f/JFAcPMPwMGM8vbM8.png

數(shù)據(jù)的基本統(tǒng)計(jì)描述：

中心趨勢(shì)度量：均值、中位數(shù)、眾數(shù)、中列數(shù)

數(shù)據(jù)的散布：極差、四分位極差（Q3-Q1）、方差、標(biāo)準(zhǔn)差d

圖形化表示：盒圖（五數(shù)概括）、分位圖、直方圖、分位數(shù)分位數(shù)圖、散點(diǎn)圖

均值與加權(quán)平均：對(duì)極端值敏感，可以丟棄極端值

數(shù)據(jù)的相似性與相異性：

相異性矩陣

標(biāo)稱屬性比較：

圖片: https://uploader.shimo.im/f/6Qlj0cprdT0WqyEn.png

二元相異性：

圖片: https://uploader.shimo.im/f/liTCkUEUG84jr4bt.png距離度量：

圖片: https://uploader.shimo.im/f/qckc5tbXJa4MY9r0.png