大數(shù)據(jù)互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘

1、Mining of Massive Datasets,大數(shù)據(jù)：互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘與分布式處理,,,聚類(lèi),7,,Part,Clustering,聚類(lèi)是對(duì)點(diǎn)集進(jìn)行考察并按照某種距離測(cè)度將它們聚成多個(gè)“簇”的過(guò)程。聚類(lèi)的目標(biāo)是同一簇內(nèi)的點(diǎn)之間的距離較短，而不同簇中點(diǎn)之間的距離較大。如圖，不同種類(lèi)的犬在某種程度上形成一種簇。三種不同犬類(lèi)的身高體重分布圖，可以知道這些犬可以分到三個(gè)簇中，每個(gè)簇恰好對(duì)應(yīng)一種犬類(lèi)。,而聚類(lèi)分析則是根據(jù)最大化簇內(nèi)的相

2、似性、最小化簇間的相似性的原則將數(shù)據(jù)對(duì)象聚類(lèi)或分組，所形成的每個(gè)簇可以看作一個(gè)數(shù)據(jù)對(duì)象類(lèi)，用顯式或隱式的方法描述它們。,,,,,,,,,,,,,,,,,,最大化簇內(nèi)的相似性,最小化簇間的相似性,01,02,03,04,05,06,,能夠適用于大數(shù)據(jù)量（可伸縮性）,能夠處理不同類(lèi)型數(shù)據(jù)（距離定義）,能夠發(fā)現(xiàn)任意形狀的簇（結(jié)果特點(diǎn)）,能夠處理高維數(shù)據(jù),具有處理噪聲的能力,聚類(lèi)結(jié)果可解易使用,,,Web廣告,8,,Part,Advert

3、ising on the Web,目前，許多WEB應(yīng)用通過(guò)廣告而維持生計(jì)，從在線(xiàn)廣告中獲益最多的是搜索應(yīng)用，而搜索廣告的有效性主要源于將搜索查詢(xún)和廣告進(jìn)行匹配的一個(gè)稱(chēng)為Adwords模型。 本章將主要關(guān)注廣告匹配的優(yōu)化算法。這里使用的算法屬于一種特殊的類(lèi)型，他們屬于一種特殊的類(lèi)型，它們屬于貪心算法且從特定技術(shù)角度來(lái)說(shuō)是在線(xiàn)算法，重點(diǎn)討論在線(xiàn)廣告的相關(guān)問(wèn)題、在線(xiàn)算法、Adwords實(shí)現(xiàn)和問(wèn)題等。,二部圖,最大匹配,完美匹配,最大匹

4、配的貪心算法,貪心匹配算法的競(jìng)爭(zhēng)率為1/2,01,02,03,04,05,,,推薦系統(tǒng),9,,Part,Recommendation Systems,,舉例1，在淘寶上多次瀏覽某類(lèi)商品時(shí)，淘寶網(wǎng)站會(huì)出現(xiàn)該類(lèi)產(chǎn)品的推薦，諸如：您可能感興趣…。舉例2，某些門(mén)戶(hù)網(wǎng)站會(huì)基于您的瀏覽足跡，推薦您感興趣的新聞內(nèi)容。沒(méi)錯(cuò)，這就是推薦系統(tǒng)的巨大魅力，大數(shù)據(jù)環(huán)境之下，Web應(yīng)用可以對(duì)涉及用戶(hù)喜好進(jìn)行預(yù)測(cè)，而這種系統(tǒng)稱(chēng)為推薦系統(tǒng)。,不知道大家有沒(méi)有

5、這樣的經(jīng)驗(yàn)，反正我是經(jīng)常碰到。,這類(lèi)系統(tǒng)通過(guò)計(jì)算用戶(hù)或/和項(xiàng)之間的相似度來(lái)推薦項(xiàng)。與某用戶(hù)相似的用戶(hù)所喜歡的項(xiàng)會(huì)推薦給該用戶(hù)。,這類(lèi)系統(tǒng)主要考察的是推薦項(xiàng)的性質(zhì)。用戶(hù)計(jì)算機(jī)用戶(hù)以往的瀏覽歷史來(lái)預(yù)測(cè)用戶(hù)將來(lái)的行為，也就是基于內(nèi)容的推薦。,推薦系統(tǒng),基于內(nèi)容的系統(tǒng),協(xié)同過(guò)濾系統(tǒng),基于內(nèi)容的推薦（Content-based Recommendation）是信息過(guò)濾技術(shù)的延續(xù)與發(fā)展，它是建立在項(xiàng)目的內(nèi)容信息上作出推薦的，而不需要依據(jù)用戶(hù)對(duì)項(xiàng)目的

6、評(píng)價(jià)意見(jiàn)，更多地需要用機(jī)器學(xué)習(xí)的方法從關(guān)于內(nèi)容的特征描述的事例中得到用戶(hù)的興趣資料。在基于內(nèi)容的推薦系統(tǒng)中，項(xiàng)目或?qū)ο笫峭ㄟ^(guò)相關(guān)的特征的屬性來(lái)定義，系統(tǒng)基于用戶(hù)評(píng)價(jià)對(duì)象的特征，學(xué)習(xí)用戶(hù)的興趣，考察用戶(hù)資料與待預(yù)測(cè)項(xiàng)目的相匹配程度。用戶(hù)的資料模型取決于所用學(xué)習(xí)方法，常用的有決策樹(shù)、神經(jīng)網(wǎng)絡(luò)和基于向量的表示方法等?；趦?nèi)容的用戶(hù)資料是需要有用戶(hù)的歷史數(shù)據(jù)，用戶(hù)資料模型可能隨著用戶(hù)的偏好改變而發(fā)生變化。,,,不需要其它用戶(hù)的數(shù)據(jù)，沒(méi)有冷開(kāi)始問(wèn)

7、題和稀疏,能為具有特殊興趣愛(ài)好的用戶(hù)進(jìn)行推薦,能推薦新的或不是很流行的項(xiàng)目，沒(méi)有新項(xiàng)目問(wèn)題,通過(guò)流出推薦項(xiàng)目?jī)?nèi)容特征，解釋推薦那些項(xiàng)目的原因,已有比較好的技術(shù)，如關(guān)于分類(lèi)學(xué)習(xí)的技術(shù)已趨成熟,,,,,,,,,優(yōu)點(diǎn),缺點(diǎn)是要求內(nèi)容能容易抽取成有意義的特征，要求特征內(nèi)容有良好的結(jié)構(gòu)性，并且用戶(hù)的口味必須能夠用內(nèi)容特征形式來(lái)表達(dá)，不能顯式地得到其它用戶(hù)的判斷情況。,,,,分析數(shù)據(jù),輸出結(jié)果,過(guò)濾數(shù)據(jù),數(shù)據(jù)收集,利用分類(lèi)聚類(lèi)技術(shù)分析出這些

8、日志數(shù)據(jù)之間的關(guān)聯(lián)性，以及這些日志數(shù)據(jù)和用戶(hù)之間的關(guān)聯(lián)性，這也是最重要的一步。,Web日志中有很多無(wú)用的信息，我們要把這些無(wú)用的信息排除掉，而且要區(qū)分出用戶(hù)和日志數(shù)據(jù)之間的聯(lián)系。,即搜集用戶(hù)的行為資料，其中也包括很多方法，根據(jù)我找到的資料與以往的經(jīng)驗(yàn)來(lái)看，web日志可以作為我們的切入點(diǎn)，即我們的數(shù)據(jù)來(lái)源。,基于用戶(hù)的協(xié)同過(guò)濾推薦的基本原理是，根據(jù)所有用戶(hù)對(duì)物品或者信息的偏好，發(fā)現(xiàn)與當(dāng)前用戶(hù)口味和偏好相似的“鄰居”用戶(hù)群，在一般的應(yīng)用中是

9、采用計(jì)算“K- 鄰居”的算法；然后，基于這 K 個(gè)鄰居的歷史偏好信息，為當(dāng)前用戶(hù)進(jìn)行推薦。,上圖示意出基于用戶(hù)的協(xié)同過(guò)濾推薦機(jī)制的基本原理，假設(shè)用戶(hù) A 喜歡物品 A，物品 C，用戶(hù) B 喜歡物品 B，用戶(hù) C 喜歡物品 A ，物品 C 和物品 D；從這些用戶(hù)的歷史喜好信息中，我們可以發(fā)現(xiàn)用戶(hù) A 和用戶(hù) C 的口味和偏好是比較類(lèi)似的，同時(shí)用戶(hù) C 還喜歡物品 D，那么我們可以推斷用戶(hù) A 可能也喜歡物品 D，因此可以將物品 D 推薦給