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

《大數(shù)據(jù)互聯(lián)網(wǎng)大規(guī)模數(shù)據(jù)挖掘ppt課件.pptx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

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

2、成的每個(gè)簇可以看作一個(gè)數(shù)據(jù)對(duì)象類，用顯式或隱式的方法描述它們。最大化簇內(nèi)的相似性最小化簇間的相似性聚類的操作聚類算法基于劃分的K-meansK-medoids基于層次的凝聚的分裂的基于密度的DBSCANOPTICS基于網(wǎng)格的STINGCLIQUE基于模型的StatisticsNeuralNetwork聚類分析算法的分類010203040506能夠適用于大數(shù)據(jù)量（可伸縮性）能夠處理不同類型數(shù)據(jù)（距離定義）能夠發(fā)現(xiàn)任意形狀的簇（結(jié)果特點(diǎn)）能夠處理高維數(shù)據(jù)具有處理噪聲的能力聚類結(jié)果可解易使用聚類算法需要考慮的因素We

3、b廣告8PartAdvertisingontheWeb目前，許多WEB應(yīng)用通過(guò)廣告而維持生計(jì)，從在線廣告中獲益最多的是搜索應(yīng)用，而搜索廣告的有效性主要源于將搜索查詢和廣告進(jìn)行匹配的一個(gè)稱為Adwords模型。本章將主要關(guān)注廣告匹配的優(yōu)化算法。這里使用的算法屬于一種特殊的類型，他們屬于一種特殊的類型，它們屬于貪心算法且從特定技術(shù)角度來(lái)說(shuō)是在線算法，重點(diǎn)討論在線廣告的相關(guān)問(wèn)題、在線算法、Adwords實(shí)現(xiàn)和問(wèn)題等。Web廣告背景Web廣告Adwords實(shí)現(xiàn)投標(biāo)和搜索查詢的匹配更復(fù)雜問(wèn)題的匹配問(wèn)題文檔和投標(biāo)之間的匹配

4、算法Adwords問(wèn)題搜索廣告的歷史Adwords問(wèn)題的定義Adwords問(wèn)題的貪心算法Balance算法Balance算法競(jìng)爭(zhēng)的一個(gè)下界多投標(biāo)者的Balance算法一般性的Balance算法Adwords問(wèn)題的最后論述在線廣告相關(guān)問(wèn)題廣告機(jī)會(huì)直接廣告展示廣告的相關(guān)問(wèn)題在線算法在線和離線算法貪心算法競(jìng)爭(zhēng)率廣告匹配問(wèn)題匹配及完美匹配最大匹配貪心算法貪心匹配算法的競(jìng)爭(zhēng)率章節(jié)具體框架在線算法分類1離線算法將算法所需的所有數(shù)據(jù)準(zhǔn)備好才產(chǎn)生答案的傳統(tǒng)算法在線算法只能保存有限的流數(shù)據(jù)，但是需要在某個(gè)流元素到達(dá)之后就以輸出的

5、方式對(duì)查詢進(jìn)行應(yīng)答，此時(shí)是在對(duì)未來(lái)的數(shù)據(jù)一無(wú)所知的情況下對(duì)當(dāng)前元素進(jìn)行決策的過(guò)程2算法現(xiàn)象一般情況下會(huì)尋找搜索引擎收益和廣告上顯示次數(shù)同時(shí)的最大化，因?yàn)闊o(wú)法保證在線算法與離線算法一樣有效3貪心算法采用貪心策略，綜合考慮關(guān)鍵詞與廣告的匹配程度、廣告商競(jìng)價(jià)、廣告商剩余預(yù)算等因素，通過(guò)最大化當(dāng)前輸入元素信息的某個(gè)函數(shù)得到當(dāng)前的最優(yōu)值。4競(jìng)爭(zhēng)率存在某個(gè)小于1的常數(shù)c,使得對(duì)于任意輸入，一個(gè)具體的在線算法的結(jié)果至少是最優(yōu)離線算法結(jié)果的c倍。廣告的匹配問(wèn)題1二部圖設(shè)G=(V,E）是一個(gè)無(wú)向圖，如果頂點(diǎn)V可分割為兩個(gè)互不相交

6、的子集(A,B），并且圖中的每條邊（i，j）所關(guān)聯(lián)的兩個(gè)頂點(diǎn)i和j分別屬于這兩個(gè)不同的頂點(diǎn)集，則稱圖G為一個(gè)二分圖。2最大匹配一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問(wèn)題。3完美匹配在一個(gè)匹配中，所有的節(jié)點(diǎn)都不會(huì)同時(shí)是兩條或者多條邊對(duì)的端點(diǎn)且所有的節(jié)點(diǎn)都出現(xiàn)，則匹配是完美的。4最大匹配的貪心算法按照任意次序來(lái)考慮邊，當(dāng)考慮邊（x,y）時(shí)，如果x和y都不是已有匹配中邊的端點(diǎn)則加入，否則跳過(guò)。貪心算法產(chǎn)生的匹配不一定是最大匹配，很可能結(jié)果

7、會(huì)不盡人意。5貪心匹配算法的競(jìng)爭(zhēng)率為1/2。因?yàn)樗惴ǖ母?jìng)爭(zhēng)率是算法所有可能的輸入下所得到最小值和最優(yōu)結(jié)果的比值，因此1/2是競(jìng)爭(zhēng)率的上界。又設(shè)Mo是最大匹配、Mg是貪心算法匹配，L為在Mo中匹配但在Mg中不匹配的左節(jié)點(diǎn)結(jié)合，R為L(zhǎng)中所有節(jié)點(diǎn)連接的邊右節(jié)點(diǎn)的集合。由于

8、M0

9、<=

10、M0

11、+

12、L

13、,

14、L

15、<=

16、R

17、，

18、R

19、<=

20、Mg

21、，可以推導(dǎo)得到

22、M0

23、<=2

24、Mg

25、，競(jìng)爭(zhēng)率至少為1/2。因此競(jìng)爭(zhēng)率為1/2。廣告的匹配問(wèn)題二部圖最大匹配完美匹配最大匹配的貪心算法貪心匹配算法的競(jìng)爭(zhēng)率為1/20102030405推薦

26、系統(tǒng)9PartRecommendationSystems舉例1，在淘寶上多次瀏覽某類商品時(shí)，淘寶網(wǎng)站會(huì)出現(xiàn)該類產(chǎn)品的推薦，諸如：您可能感興趣…。舉例2，某些門戶網(wǎng)站會(huì)基于您的瀏覽足跡，推薦您感興趣的新聞內(nèi)容。沒(méi)錯(cuò)，這就是推薦系統(tǒng)的巨大魅力，大數(shù)據(jù)環(huán)境之下，Web應(yīng)用可以對(duì)涉及用戶喜好進(jìn)行預(yù)測(cè)，而這種系統(tǒng)稱為推薦系統(tǒng)。推薦系統(tǒng)的概念不知道大家有沒(méi)有這樣的經(jīng)驗(yàn)，反正我是經(jīng)常碰到。這類系統(tǒng)通