Web信息處理與應(yīng)用復(fù)習(xí)筆記-GitHub

1、Web信息處理與應(yīng)用復(fù)習(xí)筆記? 2017-1 熊家靖 PB14011026PART 1：Web Search一、 Introduction1、 web 搜索的挑戰(zhàn)：數(shù)據(jù)規(guī)模大、分布散、不穩(wěn)定、質(zhì)量差、無(wú)結(jié)構(gòu)、異構(gòu)、價(jià)值低2、信息檢索：給定查詢和信息庫(kù)，找到相關(guān)的文檔3、 IR 與 DB 的區(qū)別：DB 數(shù)據(jù)結(jié)構(gòu)化、有明確語(yǔ)義，查詢結(jié)構(gòu)化、匹配要精確、次序不重要IR 數(shù)據(jù)半結(jié)構(gòu)化、無(wú)明確語(yǔ)義，查詢?yōu)槿我鈨?nèi)容、無(wú)需精確匹配、次序很重要4、 IR 的任務(wù)：基于用戶查詢的搜索、信息過(guò)濾、分類、問(wèn)答5、 IR 的基礎(chǔ)性問(wèn)題：相關(guān)性計(jì)算、檢索模型、評(píng)價(jià)、信息需求、檢索性能二、 Web Crawler1、網(wǎng)絡(luò)

2、爬蟲(chóng)的概念：從一個(gè)種子站點(diǎn)集合開(kāi)始，從web 中尋找并且下載網(wǎng)頁(yè)，獲取排序需要的相關(guān)信息，并且剔除低質(zhì)量的網(wǎng)頁(yè)2、網(wǎng)絡(luò)爬蟲(chóng)基本過(guò)程：種子裝入桶中、每次從桶中取出一個(gè)網(wǎng)頁(yè)、提取出網(wǎng)頁(yè)所有url 放入桶中、重復(fù)3、網(wǎng)絡(luò)爬蟲(chóng)的主要需求：快、可擴(kuò)展性、友好性、健壯、持續(xù)搜集、時(shí)新性4、網(wǎng)絡(luò)爬蟲(chóng)的常用策略：用棧深度優(yōu)先、用隊(duì)列廣度優(yōu)先5、網(wǎng)絡(luò)爬蟲(chóng)涉及的協(xié)議：HTTP/HTML、 DNS/URL、 Robots Exclusion（排斥協(xié)議）、 Sitemp（允許協(xié)議）6、 URL 規(guī)范化：協(xié)議 :/ 主機(jī)名 :端口 / 路徑 /: 參數(shù) ?查詢 #Fragment7、分布式爬蟲(chóng)的概念：如何有效地把N 個(gè)

3、網(wǎng)站的搜集任務(wù)分配到M 個(gè)機(jī)器上去使得分配比較均勻8、一致性Hash 的概念：將網(wǎng)頁(yè)和機(jī)器都映射到環(huán)路 Hash 空間，每個(gè)機(jī)器負(fù)責(zé)自身位置與后繼的網(wǎng)頁(yè)搜集三、 Text Processing1、文本處理的概念：將原始文檔轉(zhuǎn)換成詞項(xiàng)集以方便索引2、字符編碼的概念：ASCII：美國(guó)信息交換標(biāo)準(zhǔn)代碼Unicode： 統(tǒng)一碼，滿足跨語(yǔ)言、跨平臺(tái)的需求UTF-8 ：針對(duì)Unicode的可變長(zhǎng)度字符編碼3、分詞中的概念：- 1 -分詞：將文檔的字符串序列變成詞序列語(yǔ)素：最小的語(yǔ)音語(yǔ)義結(jié)合體，是最小的語(yǔ)言單位詞：代表一定的意義，具有固定的語(yǔ)音形式，可以獨(dú)立運(yùn)用的最小的語(yǔ)言單位交叉歧義：網(wǎng)球 /場(chǎng) / 網(wǎng)

4、/球場(chǎng) /組合歧義：我/ 個(gè)人 /三 /個(gè) /人 /未登錄詞： 未包括在分詞詞表中但必須切分出來(lái)的詞，包括各類專名、術(shù)語(yǔ)、 縮略語(yǔ)等停用詞：在文檔中頻繁出現(xiàn)或與語(yǔ)料庫(kù)特性有關(guān)的詞4、中文分詞的挑戰(zhàn)：漢語(yǔ)是字的集合而不是詞的集合漢字存在著不同的組詞方式漢語(yǔ)虛詞眾多，大多數(shù)漢字在不同的詞語(yǔ)中可能為關(guān)鍵字，也可能為停用詞分詞歧義新詞的頻繁出現(xiàn)5、常用的分詞方法：機(jī)械分詞：正向最大匹配分詞FMM反向最大匹配分詞BMM / RMM雙向最大匹配分詞BM: FMM + RMM最少切分分詞：圖中最短路徑ASM( d, a, m ) d為匹配方向，a 為失敗后增/減串長(zhǎng)， m 為最大 /小匹配理解分詞：分詞時(shí)進(jìn)

5、行句法、語(yǔ)義分析，從而減少歧義統(tǒng)計(jì)分詞：一元文法模型即最大概率分詞二元文法模型每個(gè)詞的概率為前一個(gè)詞出現(xiàn)后的條件概率N 元文法模型每個(gè)詞的概率為前N 個(gè)詞出現(xiàn)后的條件概率6、詞根化和編輯距離的概念：詞根化：使用一系列后綴變換規(guī)則對(duì)單詞進(jìn)行變換編輯距離：從s 轉(zhuǎn)換為 t 使用增加、刪除、替換三種操作的最小次數(shù)四、 Indexing1、布爾檢索的概念：利用 AND 、 OR 或者 NOT 操作符將詞項(xiàng)連接起來(lái)的查詢2、關(guān)聯(lián)矩陣的概念：行為詞項(xiàng)，列為文檔，詞項(xiàng)在文檔中出現(xiàn)為1 不出現(xiàn)為03、倒排索引的概念和結(jié)構(gòu)：以詞項(xiàng)為索引，每個(gè)詞項(xiàng)維護(hù)一個(gè)鏈表，表示其出現(xiàn)過(guò)的文檔集（從小到大）可以加入擴(kuò)展項(xiàng)：某詞

6、在某文檔中的出現(xiàn)詞頻TF 、某詞出現(xiàn)過(guò)的文檔頻數(shù)DF4、倒排索引的構(gòu)建：寫出每個(gè)文檔的詞項(xiàng)-> 文檔索引合并所有的索引，詞項(xiàng)和文檔號(hào)均從小到大排列5、倒排索引的存儲(chǔ)：詞項(xiàng)與鏈表存儲(chǔ)在同一個(gè)文件中/不同文件中6、詞匯表存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)、 Hash table、 B+- 樹(shù)、 Trie 樹(shù)7、 Zipf Law：任意一個(gè)詞項(xiàng)，其頻度和排名的乘積大致是一個(gè)常數(shù)- 2 -五、 Queries1、查詢表達(dá)的難點(diǎn)：一個(gè)查詢可以代表非常不同的信息需求一個(gè)查詢可能是其真正需求的一種非常差的表述2、查詢表達(dá)的優(yōu)化：局部?jī)?yōu)化：對(duì)用戶查詢進(jìn)行局部分析，如相關(guān)性反饋全局優(yōu)化：進(jìn)行全局分析來(lái)產(chǎn)生同/ 近義詞詞典

7、，如查詢擴(kuò)展3、相關(guān)性反饋的概念和過(guò)程：用戶在查詢后標(biāo)記相關(guān)/不相關(guān)文檔，然后迭代更新查詢以獲得更好的結(jié)果4、相關(guān)性反饋的分類及其各自的概念和特點(diǎn)：顯式反饋：定義：用戶顯式參加交互過(guò)程，即用戶反饋問(wèn)題：開(kāi)銷大、查詢長(zhǎng)、用戶不愿意、反饋邏輯難理解隱式反饋：定義：系統(tǒng)跟蹤用戶的行為來(lái)推測(cè)返回文檔的相關(guān)性，從而反饋好處：省卻了用戶的顯式參與過(guò)程問(wèn)題：對(duì)分析的要求高、準(zhǔn)確度難保證、可能需要額外設(shè)備偽相關(guān)反饋： 定義：對(duì)于真實(shí)相關(guān)反饋的人工部分進(jìn)行自動(dòng)化好處：不用考慮用戶因素，處理簡(jiǎn)單，平均效果也不錯(cuò)問(wèn)題：準(zhǔn)確率難以保證，可能出現(xiàn)查詢漂移5、 Ricchio算法：新查詢向量= ·原查詢向量+

8、·平均相關(guān)向量·平均不相關(guān)向量計(jì)算過(guò)程中出現(xiàn)負(fù)值，全部設(shè)為0基本假設(shè)：用戶知道使用文檔集中的詞項(xiàng)來(lái)表達(dá)初始查詢；相關(guān)文檔出現(xiàn)的詞項(xiàng)類似6、查詢擴(kuò)展的概念：相關(guān)性反饋中，用戶針對(duì)文檔提供附加信息，查詢擴(kuò)展中，用戶對(duì)詞項(xiàng)提供附加信息7、查詢擴(kuò)展的幾種方法：人工構(gòu)建同 / 近義詞詞典、自動(dòng)導(dǎo)出同 /近義詞詞典、基于查詢?nèi)罩就诰虿樵兊葍r(jià)類六、 Ranking1、 Ranking的難點(diǎn)：Web 網(wǎng)頁(yè)的質(zhì)量參差不齊，大量的網(wǎng)頁(yè)組織性、結(jié)構(gòu)性比較差大部分檢索用戶是沒(méi)有任何經(jīng)驗(yàn)的用戶的查詢需求存在著巨大差異2、信息檢索模型的概念：用來(lái)描述文檔和用戶查詢的標(biāo)識(shí)形式以及它們之間相關(guān)性的框架形式

9、化表示為： D, Q, F, R(Di,q) 即 文檔表達(dá) , 查詢表達(dá) , 匹配框架 , 相關(guān)性度量函數(shù)3、信息檢索的實(shí)質(zhì)問(wèn)題：對(duì)于所有文檔，根據(jù)其與用戶查詢的相關(guān)程度從大到小排序4、信息檢索模型與搜索引擎排序算法的關(guān)系：好的信息檢索模型在相關(guān)性上產(chǎn)生和人類決策非常相關(guān)的結(jié)果基于好的檢索模型的排序算法能夠在排序結(jié)果頂部返回相關(guān)的文檔5、信息檢索的分類：基于集合論的模型：布爾模型基于代數(shù)論的模型：向量空間模型基于概率論的模型：概率模型、語(yǔ)言模型、推理網(wǎng)絡(luò)6、相關(guān)系數(shù)的概念和計(jì)算：- 3 -Jaccard ： A 與 B 的交中元素的個(gè)數(shù)/A 與 B 的并中元素的個(gè)數(shù)# 未考慮詞頻、文檔長(zhǎng)度、罕

10、見(jiàn)詞信息量tf( t, d ) ： 詞項(xiàng) t 在文檔d 中出現(xiàn)的次數(shù)# 相關(guān)度不會(huì)正比于詞項(xiàng)頻率w( t, d ):當(dāng) tf > 0 時(shí)， 1 + lg( tf ) ； 否則， 0df( t ):出現(xiàn)詞項(xiàng) t 的文檔數(shù)目idf( t ):lg( N / df )其中 N 是文檔集中文檔的數(shù)目tf-idf:( 1 + lg tf )lg( N·/ df )# 隨著詞項(xiàng)頻率的增大而增大# 隨著詞項(xiàng)罕見(jiàn)度的增大而增大7、向量空間模型SMART ：D： 每個(gè)文檔是一個(gè)以詞項(xiàng)為維度的向量，每個(gè)維度的值為詞項(xiàng)的tf-idf 值Q： 每個(gè)查詢是一個(gè)以詞項(xiàng)為維度的向量，每個(gè)維度的值為詞項(xiàng)的tf

11、-idf 值F ： 非完全匹配R： 用文檔向量和查詢向量的相似度來(lái)估計(jì)相關(guān)性前提假設(shè)：檢索到的所有文檔相關(guān)性不等價(jià)、相關(guān)性多元、查詢關(guān)鍵字互相獨(dú)立8、余弦相似度：兩個(gè)向量夾角的余弦值，即：兩向量的點(diǎn)乘/ 各自模的積9、向量空間模型的操作過(guò)程：文檔和查詢表示成tf-idf 的權(quán)重向量計(jì)算兩向量余弦相似度將余弦相似度Top-K 的文檔返回給用戶10 、向量空間模型的缺點(diǎn)：用戶無(wú)法描述詞項(xiàng)之間的關(guān)系tf-idf 高的詞項(xiàng)可能會(huì)在檢索中影響過(guò)大詞項(xiàng)之間的獨(dú)立性假設(shè)與實(shí)際不符11 、概率模型：定義隨機(jī)變量R、Q、D，相關(guān)度R=0 或 1通過(guò)計(jì)算條件概率P( R = 1 | Q = q, D = d )來(lái)

12、度量文檔和查詢的相關(guān)度12 、 PageRank：PR(a) = ( 1d ) + dsigma(· PR(T) / C(T) )每個(gè)頁(yè)面的pagerank等于進(jìn)入它的邊的pagerank的函數(shù)計(jì)算過(guò)程：每個(gè)網(wǎng)頁(yè)賦初值，然后迭代計(jì)算，直到變化小于一個(gè)閾值優(yōu)點(diǎn)：給網(wǎng)頁(yè)提供重要性排序+ 可以離線完成+ 獨(dú)立于主題缺點(diǎn)：未區(qū)分鏈接種類+ 對(duì)新網(wǎng)頁(yè)不公平+ 不能單獨(dú)用于排序13 、 HITS ：入步驟：所有權(quán)威頁(yè)面的值等于鏈向它的中心頁(yè)面的值之和出步驟：所有中心頁(yè)面的值等于其鏈向的權(quán)威頁(yè)面的值之和計(jì)算過(guò)程：所有頁(yè)面初始為1 ，迭代使用入步驟和出步驟優(yōu)點(diǎn)：能更好描述互聯(lián)網(wǎng)的組織特點(diǎn)+ 主題相關(guān)

13、+ 查詢無(wú)關(guān)+ 可以單獨(dú)用于排序缺點(diǎn)：需要在線計(jì)算時(shí)間代價(jià)大+ 容易受到“鏈接作弊”的影響七、 Evaluation1、信息檢索評(píng)價(jià)概述：評(píng)價(jià)受主觀、情景、認(rèn)知、時(shí)間的影響，重點(diǎn)在于保持公平- 4 -2、信息檢索評(píng)價(jià)指標(biāo)：效率：時(shí)間開(kāi)銷、空間開(kāi)銷、響應(yīng)速度效果：準(zhǔn)確率、召回率、是否靠前其他：覆蓋率、訪問(wèn)量、數(shù)據(jù)更新速度3、效果評(píng)價(jià)指標(biāo)：基于集合：正確率 P ：返回的相關(guān)文檔占返回的總文檔的比比例召回率 R：返回的相關(guān)文檔占相關(guān)總文檔的比例F 值：召回率 R 和正確率 P 的調(diào)和平均F值：召回率 R 和正確率 P 的加權(quán)調(diào)和平均其中 R 的權(quán)為 2 ， P 的權(quán)為 1基于序：PN ：值考慮返回的

14、前 N 個(gè)文檔時(shí)的正確率R-Precision ： 即 P 相關(guān)文檔總數(shù)未插值 AP ：P 相關(guān)文檔出現(xiàn)位置的平均插值 AP：在召回率 0,0.1,0.21.0 上十一點(diǎn)的正確率平均不存在某召回率點(diǎn)時(shí)， 取該點(diǎn)到下一個(gè)點(diǎn)之間最大正確率簡(jiǎn)化 AP：在未插值 AP 中忽略未出現(xiàn)的相關(guān)文檔多個(gè)查詢：MAP ：所有查詢的 AP 的算術(shù)平均MRR ：第一個(gè)相關(guān)文檔返回的位置的倒數(shù)的算術(shù)平均其他：CGp ：位置 1 到位置 p 的檢索結(jié)果的相關(guān)度之和DCGp ：相關(guān)度要先除以 log2(i) 作為懲罰，其中 i 為出現(xiàn)的位置NDCGp ：DCG 的值除以理想化的 IDCG 的值，規(guī)范化為 0,1PART

15、2：Web Information Extraction一、 Named Entity Extraction1、信息抽取的概念：從語(yǔ)料中抽取指定的事件、事實(shí)等信息，形成結(jié)構(gòu)化的數(shù)據(jù)能作為一種淺層的文本理解，是信息檢索的進(jìn)一步深化2、信息抽取與信息檢索的關(guān)系：檢索是從文檔集合中找文檔子集，抽取是從文本中獲取用戶感興趣的事實(shí)信息檢索通常利用統(tǒng)計(jì)與關(guān)鍵詞等技術(shù)，抽取借助于自然語(yǔ)言處理技術(shù)檢索通常與領(lǐng)域無(wú)關(guān)，抽取通常與領(lǐng)域相關(guān)3、 MUC-7 定義的信息抽取任務(wù)：命名實(shí)體 NE：現(xiàn)實(shí)世界中具體或抽象的實(shí)體，還包括日期、時(shí)間、數(shù)量等模板元素 TE：實(shí)體屬性，通過(guò)槽描述命名實(shí)體的基本信息共指關(guān)系CR：命名

16、實(shí)體的等價(jià)關(guān)系模板關(guān)系TR：實(shí)體之間的各種關(guān)系，又稱為事實(shí)背景模板ST：實(shí)體發(fā)生的事件4、信息抽取的內(nèi)容：實(shí)體、屬性、關(guān)系、事件關(guān)鍵在于“抽取實(shí)體，確定關(guān)系”5、命名實(shí)體識(shí)別NER的概念：識(shí)別文本中的人名、地名等專有名稱和有意義的時(shí)間、日期等數(shù)量短語(yǔ)并加以歸類6、命名實(shí)體識(shí)別NER的難點(diǎn)：命名實(shí)體類型多樣、新命名實(shí)體不斷出現(xiàn)、命名實(shí)體歧義、命名實(shí)體結(jié)構(gòu)復(fù)雜- 5 -7、 MUC-7 中定義的NER內(nèi)容：實(shí)體類：人名、地名、機(jī)構(gòu)名時(shí)間類：日期、時(shí)間數(shù)值類：貨幣、百分比注意：人造物、重復(fù)指代的普通名詞、派生詞、以人命名的法律和獎(jiǎng)項(xiàng)等不算！8、命名實(shí)體識(shí)別NER的性能評(píng)價(jià)指標(biāo)：正確率 P：正確數(shù)/

17、總數(shù)( 正確數(shù)+ (1/2) 部分正確數(shù)) / 總數(shù)召回率 R：正確數(shù)/ 總正確數(shù)( 正確數(shù)+ (1/2) 部分正確數(shù)) / 總 (部分 )正確數(shù)F 值：P與 R 的調(diào)和平均9、命名實(shí)體識(shí)別NER的常用方法：基于詞典：詞典匹配；難以枚舉命名實(shí)體、構(gòu)建詞典代價(jià)大、難以處理歧義基于規(guī)則：自行構(gòu)造模板匹配；依賴性強(qiáng)、代價(jià)大、建設(shè)周期長(zhǎng)、可移植性差基于統(tǒng)計(jì)：隱馬爾可夫HMM 、最大熵ME、支持向量機(jī)SVM、條件隨機(jī)場(chǎng)CRF混合方法：混合使用詞典、規(guī)則和統(tǒng)計(jì)二、 Relation Extraction1、關(guān)系抽取的概念：從文本中識(shí)別出兩個(gè)實(shí)體或多個(gè)實(shí)體之間存在的事實(shí)上的關(guān)系2、關(guān)系抽取的意義：提高搜索引

18、擎發(fā)現(xiàn)知識(shí)的能力廣泛應(yīng)用于各種知識(shí)庫(kù)的構(gòu)建支持知識(shí)推理和問(wèn)答系統(tǒng)研究3、關(guān)系的表示方法：二元組、三元組、多元組4、關(guān)系抽取的常用方法：基于規(guī)則：針對(duì)特定領(lǐng)域的特定關(guān)系，設(shè)計(jì)針對(duì)性的抽取規(guī)則，代價(jià)大，難移植基于模式： 種子關(guān)系生成關(guān)系模式，基于關(guān)系模式抽取新的關(guān)系，再迭代生成新的模式和新的關(guān)系基于機(jī)器學(xué)習(xí)：特征向量、核函數(shù)5、 DIPRE系統(tǒng)：給定種子元組R在文檔中搜索元組R 的出現(xiàn) O從出現(xiàn) O 中提取模板P使用模板P 從文檔中獲取新的元組6、 Snowball 系統(tǒng)：只使用能匹配很多模板的元組只使用有多個(gè)元組支持的模板PART 3： Web Data Mining一、 Introductio

19、n1、網(wǎng)絡(luò)挖掘的概念：從 web 中挖掘有用的信息和有用的模式2、網(wǎng)絡(luò)挖掘的內(nèi)容與應(yīng)用：網(wǎng)絡(luò)內(nèi)容挖掘：數(shù)據(jù)挖掘、數(shù)據(jù)分類、數(shù)據(jù)聚類網(wǎng)絡(luò)結(jié)構(gòu)挖掘：社區(qū)分析、影響力分析- 6 -網(wǎng)絡(luò)用途挖掘：推薦系統(tǒng)二、 Data1、數(shù)據(jù)對(duì)象、屬性、維度、特征：數(shù)據(jù)對(duì)象是一個(gè)數(shù)據(jù)實(shí)例，其屬性、維度、 特征意思相同， 均為描述數(shù)據(jù)的一個(gè)域2、高維詛咒現(xiàn)象：數(shù)據(jù)分類的表現(xiàn)不會(huì)隨著維數(shù)的增加而一直上升，反而到了某個(gè)閾值后會(huì)下降因?yàn)殡S著維數(shù)上升，每個(gè)類的數(shù)據(jù)變得稀疏，很多測(cè)量手段都逐漸失去意義3、數(shù)據(jù)預(yù)處理的基本方法：采樣：使用有代表性的樣本，使得樣本與總體在屬性上有相似的性質(zhì)特征選擇：剔除冗余和無(wú)關(guān)特征降維：避免高維詛

20、咒、降低數(shù)據(jù)挖掘的代價(jià)、使數(shù)據(jù)更加清楚、消除噪聲三、 Classification1、監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)：監(jiān)督學(xué)習(xí)：使用訓(xùn)練樣本訓(xùn)練模型，再利用模型解析未知數(shù)據(jù)進(jìn)行分類無(wú)監(jiān)督學(xué)習(xí)：無(wú)訓(xùn)練樣本，直接按照未知數(shù)據(jù)的相似程度建模聚類2、分類的基本原理：選定模型后，使用訓(xùn)練數(shù)據(jù)訓(xùn)練模型參數(shù)，之后用模型解析輸入數(shù)據(jù)得到分類3、數(shù)據(jù)的向量表示：用數(shù)據(jù)的頻數(shù)或者tf-idf 表示4、 KNN 算法：找到與待分類數(shù)據(jù)距離最近的K 個(gè)數(shù)據(jù)，然后將其分入頻數(shù)最高的類中KNN 無(wú)法免疫高維詛咒現(xiàn)象，但是在高維特征獨(dú)立數(shù)較小時(shí)，KNN 也適用5、 Logistic regression 算法：6、如何評(píng)價(jià)分類效果：

21、訓(xùn)練誤差：訓(xùn)練數(shù)據(jù)的過(guò)程中造成的錯(cuò)誤測(cè)試誤差：測(cè)試的過(guò)程中造成的誤差accuracy 為測(cè)準(zhǔn)率泛化誤差：使用模型在未知記錄上造成的分布相同的期望誤差四、 Clustering1、聚類的概念：聚類是一個(gè)把現(xiàn)實(shí)或抽象的對(duì)象和與它相似的對(duì)象組織到一起的過(guò)程2、聚類的基本原理：聚類內(nèi)部相似性很高，聚類之間相似性很低3、層次式聚類算法流程：計(jì)算距離矩陣，默認(rèn)所有數(shù)據(jù)點(diǎn)都是一個(gè)類每次找到距離最近的兩個(gè)類，將其合并，并更新距離矩陣，重復(fù)直到只有一個(gè)類4、類的距離定義：Single-link：使用兩個(gè)聚類之間最近的點(diǎn)作為聚類的距離Complete-link ：使用兩個(gè)聚類之間最遠(yuǎn)的點(diǎn)作為聚類的距離Averag

22、e-link ：使用所有跨聚類的結(jié)點(diǎn)對(duì)的平均距離Centroid ：使用聚類重心之間的距離5、 K-means 算法流程：隨機(jī)產(chǎn)生k 個(gè)聚類中心點(diǎn)每個(gè)數(shù)據(jù)點(diǎn)歸類到與它最近的那個(gè)中心所代表的類- 7 -每個(gè)類重新計(jì)算中心點(diǎn)，返回第二步算法迭代到所有數(shù)據(jù)點(diǎn)的類歸屬不再改變6、 K-means 算法優(yōu)化目標(biāo)：每個(gè)數(shù)據(jù)點(diǎn)到它所屬的類中心距離的平方和最小7、 K-means 收斂性分析：均方差函數(shù)單調(diào)遞減而有界8、聚類算法的評(píng)價(jià)標(biāo)準(zhǔn)：凝聚度：計(jì)算各聚類的均方差的和分離度：不同聚類的重心要盡可能相互遠(yuǎn)離專家評(píng)判五、社區(qū)分析：1、圖的表示、組成部分以及相關(guān)性質(zhì)：點(diǎn)、邊（有向、無(wú)向）2、社區(qū)的概念：一組結(jié)點(diǎn)集

23、，集合內(nèi)的點(diǎn)之間有很多聯(lián)系，而集合內(nèi)的點(diǎn)與集合外的點(diǎn)聯(lián)系很少3、社區(qū)發(fā)現(xiàn)與聚類：基于結(jié)構(gòu)相似性通過(guò)使用層次式聚類或分割式聚類4、結(jié)構(gòu)相似度計(jì)算：結(jié)構(gòu)差異測(cè)度dij ：取兩點(diǎn)關(guān)聯(lián)向量的差，向量中兩點(diǎn)所在的位置清零，取模Jaccard相似度：兩點(diǎn)公共鄰居數(shù)/ 兩點(diǎn)無(wú)重總鄰居數(shù)余弦相似度：兩點(diǎn)關(guān)聯(lián)向量的余弦5、 GN 算法：一對(duì)結(jié)點(diǎn)之間的最短路徑為路上的邊貢獻(xiàn)一個(gè)流若最短路徑有多條，則均分每次切除一條流量最大的邊，然后重新計(jì)算流量，迭代進(jìn)行，直到無(wú)邊6、矩陣及性質(zhì)：鄰接矩陣：相鄰為1，不相鄰為0度數(shù)矩陣：對(duì)角線放每個(gè)結(jié)點(diǎn)的度數(shù)，其余地方為0拉普拉斯矩陣：度數(shù)矩陣減去鄰接矩陣，是半正定的7、 Cut

24、的性質(zhì)：Cut( A, B )表示 A 與 B 之間的邊數(shù)1?1?Cut( A, B ) = 4 ?( ?-?) ?= 4 ? ?；當(dāng) u A， y(u) = 1，當(dāng) u B， y(u) = -111RatioCut ( A,B) = cut(A, B)( |?| + |?|)NCut( A,B) =cut(A, B)(11)vol(A)表示 A 中結(jié)點(diǎn)度數(shù)之和+?(?)?(?)? ( ?-? )?RatioCut ( A,B) = ? ?st. ?= 0? -0.5-0.5?()?(?-? ) ? 0.5NCutA,B=?st. ? ?= 0?8、 modularity的概念：一種測(cè)量網(wǎng)絡(luò)劃

25、分為社區(qū)的好壞程度的指標(biāo)?，期望邊數(shù)為? ? ?兩結(jié)點(diǎn)間的實(shí)際邊數(shù)為，每個(gè)社區(qū)內(nèi)的邊數(shù)差為?2?- 2?- 8 -每個(gè)社區(qū)內(nèi)邊數(shù)差相加后除以總度數(shù)2m，即為 Q( G, S 屬)于 -1, 1六、影響力分析：1、度量結(jié)點(diǎn)中心性的標(biāo)準(zhǔn)：Degree centrality ：結(jié)點(diǎn)的度，可以除以n-1 標(biāo)準(zhǔn)化Closeness centrality：結(jié)點(diǎn)到其他結(jié)點(diǎn)的平均測(cè)地距離的倒數(shù)Betweenness centrality ：該結(jié)點(diǎn)通過(guò)的流量，可除以(n-1)(n-2)/2 標(biāo)準(zhǔn)化Eigenvector centrality ： Ax = x，其中 x 是所有結(jié)點(diǎn)的Eigenvector cen

26、trality2、關(guān)系強(qiáng)度：刪除后會(huì)造成結(jié)點(diǎn)對(duì)不連通的邊叫橋刪除后造成的結(jié)點(diǎn)對(duì)的距離增量越大，該關(guān)系越不牢固鄰居 overlap 函數(shù)：兩結(jié)點(diǎn)公共鄰居數(shù)/ ( 兩結(jié)點(diǎn)無(wú)重總鄰居數(shù)2 )s3、影響力傳播模型：線性閾值模型LTM：關(guān)聯(lián)到某結(jié)點(diǎn)的激發(fā)邊的總激發(fā)值大于閾值，則該結(jié)點(diǎn)被激發(fā)層級(jí)傳播模型ICM：激發(fā)結(jié)點(diǎn)按照邊權(quán)概率激發(fā)周圍的結(jié)點(diǎn)區(qū)別： LTM 是基于接收者的，ICM 是基于發(fā)送者的LTM 依賴于所有鄰居結(jié)點(diǎn)，ICM 影響到所有鄰居結(jié)點(diǎn)LTM 狀態(tài)只依賴于閾值，ICM 的狀態(tài)存在隨機(jī)性但是他們都具有子模性質(zhì)！4、最大影響結(jié)點(diǎn)集：f(S)是結(jié)點(diǎn)集S 最終能夠影響的結(jié)點(diǎn)集的大小最優(yōu)化問(wèn)題： max