1、第七章用戶行為特征及緩存的應用,張宇 計算機科學與技術學院,研究用戶行為特征的目的,搜索引擎用戶輸入的查詢詞語和查詢過程中所點擊到的網頁URL均表現出明顯的局部性 可以用來指導查詢緩存的設計,主要內容,用戶查詢與點擊日志 用戶行為特征的統(tǒng)計分析 查詢緩存的使用 用戶行為與Web信息的分布特征,主要內容,用戶查詢與點擊日志 用戶行為特征的統(tǒng)計分析 查詢緩存的使用 用戶行為與Web信息的分布特征,用戶查詢與點擊日志,搜索引擎所維護的信息種類 搜集到的Web網頁相關的信息 網頁經過分析處理后得到的信息：摘要、關鍵詞、元信息、URL超鏈信息 這些都是提供給用戶看的信息 在服務過程中收集到的用戶行為信息

2、 用戶的查詢項、查詢時間、用戶的IP地址、用戶點擊的感興趣的頁面的URL,用戶查詢與點擊日志,天網日志文件 用戶查詢日志 用戶提交查詢請求時記錄的 用戶提交的關鍵詞、提交時間、用戶的IP、頁號、是否在緩存中命中 用戶點擊日志 在用戶瀏覽查詢結果時點擊頁面時記錄的 用戶點擊頁面的時間、點擊頁面的URL、用戶IP、點擊頁面的序號、該點擊對應的查詢詞等,Fri Mar 21 00:00:02 2003 /提交時間 218.24.100.77 /用戶IP Database /是否在緩存中命中 老歌 /查詢詞 3 /頁號,Fri Mar 21 00:00:02 2003 /點擊時間 202.206.10

3、2.169 /用戶IP 蟲兒飛 /查詢詞 /點擊的URL 16 /點擊頁面的排序,用戶查詢與點擊日志,統(tǒng)計分析了如下用戶行為的分布特征 用戶查詢詞的分布情況 雷同查詢詞的衰減統(tǒng)計 相鄰N項查詢項的偏差分析 用戶點擊URL的分布情況 用戶在輸出結果中的翻頁情況,主要內容,用戶查詢與點擊日志 用戶行為特征的統(tǒng)計分析 查詢緩存的使用 用戶行為與Web信息的分布特征,用戶行為特征的統(tǒng)計分析,用戶查詢詞的分布情況 天網1999年4月15日到1999年6月10日期間的日志記錄為分析對象 假設用戶的查詢詞序列為 其中，n個查詢中共有m個不同的查詢詞 按查詢次數降序排列，得到,用戶行為特征的統(tǒng)計分析,與S2對

4、應的查詢次數序列 S2中前某個百分比的查詢詞對應的查詢次數占總查詢次數的比率Y,用戶行為特征的統(tǒng)計分析,查詢詞的分布情況,X軸：用戶查詢詞占查詢詞總數的百分比 Y軸：查詢詞的查詢次數占總的查詢次數的百分比,查詢詞分布函數及其擬合函數,原函數,擬合函數,擬合函數：y=（-0.04103+1.01689x）0.1346,用戶行為特征的統(tǒng)計分析,雷同查詢詞的衰減統(tǒng)計 將序列S1進行分組（用戶的查詢詞序列） 每1000個一組 T1表示A1中不同的查詢項組成的集合，然后計算后面各組的查詢項中有多少個查詢項出現在T1中,用戶行為特征的統(tǒng)計分析,雷同查詢詞的衰減,用戶行為特征的統(tǒng)計分析,相鄰N項查詢的偏差分

5、析 將用戶查詢每1000項分為一組 對于相鄰的兩組A和B 假設A組中出現的不同的用戶查詢是 其中，前k項是A組和B組共有的，后n項是A中但B中沒有的 同理，B組中出現的不同的用戶查詢是,用戶行為特征的統(tǒng)計分析,A和B中的這些不同的查詢項構成一個向量空間 假設， 為某查詢詞qi在A中出現的次數，則可得到A組的特征向量 同樣，可得到B組的特征向量,用戶行為特征的統(tǒng)計分析,計算上兩種特征向量的差平方和,相鄰1000項查詢詞的頻率的差的平方和,用戶行為特征的統(tǒng)計分析,用戶在輸出結果中的翻頁情況統(tǒng)計表 統(tǒng)計相同頁號的頁面點擊次數占總點擊此書的百分比 假設系統(tǒng)能夠提供n個顯示頁面 實際系統(tǒng)中，n=2000

6、，每頁包括10個網頁信息 顯示頁面：P1,Pn 對應的點擊數：C1,Cn,用戶行為特征的統(tǒng)計分析,計算其點擊次數占總點擊此書的百分比,用戶在前5頁的翻頁情況統(tǒng)計,用戶行為特征的統(tǒng)計分析,用戶翻頁情況統(tǒng)計,用戶行為特征的統(tǒng)計分析,用戶點擊URL的分布情況 假設用戶點擊的URL序列為 其中，這n個點擊中有m個是不同的，按其被點擊次數進行降序排列，得到序列 與S2對應的點擊次數序列,用戶行為特征的統(tǒng)計分析,計算S2中前某個百分比的URL其對應點擊次數占總點擊次數的比率Y,用戶點擊URL的分布情況,橫坐標：所選URL的數目占用戶點擊的URL總數的比率 縱坐標：所選URL的被點擊數目占用戶點擊總數的比率

7、,用戶行為特征的統(tǒng)計分析,主要內容,用戶查詢與點擊日志 用戶行為特征的統(tǒng)計分析 查詢緩存的使用 用戶行為與Web信息的分布特征,查詢緩存的使用,基于用戶行為的啟示 用戶查詢分布的統(tǒng)計分析表明 用戶查詢詞是非常集中的 表明在查詢中使用緩存的可行性 用戶經常查詢的詞其實很少 把這些查詢次數較高的詞的查詢結果放在緩存中，可以用較小的空間取得較大的緩存命中率,假設 緩存中命中一個用戶查詢需要的延遲是Tm 磁盤文件中查找一個用戶查詢需要的時間是Td 緩存命中率是p 引入緩存后，用戶查詢的平均響應時間變?yōu)槲词褂镁彺娴谋?訪問一次硬盤的時間大約是訪問一次內存的幾十倍 1-p,查詢緩存的使用,用戶雷同查詢項的

8、統(tǒng)計分析表明 用戶查詢有一定的穩(wěn)定性 放在緩存中的查詢信息及其結果不僅在很短的時間內才有效，可能經過一段時間后還被用戶查詢,查詢緩存的使用,相鄰N項查詢項的統(tǒng)計分析表明 相鄰N項查詢項的查詢頻率偏差很小而且非常穩(wěn)定 緩存替換過程不會因為用戶查詢短期內的變化而產生顛簸現象,查詢緩存的使用,對用戶在輸出結果中翻頁情況的統(tǒng)計分析表明 用戶通常只瀏覽前幾頁的內容，說明了對輸出結果進行排序的重要性 一個URL被很多用戶點擊，表明該URL相對重要，提高其權值 不是在硬盤中修改的 使用熱點擊緩存，將用戶點擊過的URL放在里面，若再次被點擊，在內存中進行修改,查詢緩存的使用,緩存替換策略的研究 FIFO（fi

9、rst in first out） LRU（least recently used） 替換最近最少使用的對象 LFU（least frequently used） 替換緩存中最少被引用的對象,查詢緩存的使用,FIFO、LRU和LFU的緩存命中率比較,查詢緩存的使用,3種替換策略的局部比較,查詢緩存的使用,衰減因子 每次發(fā)生替換時，用某個衰減因子去衰減原來的查詢次數并累加新的查詢次數,調整后的LFU和LRU命中率的比較,查詢緩存的使用,主要內容,用戶查詢與點擊日志 用戶行為特征的統(tǒng)計分析 查詢緩存的使用 用戶行為與Web信息的分布特征,用戶行為與Web信息的分布特征,基本術語 網頁重要度的度量 用戶訪問越多的網頁越重要 網頁P的入度H(P) 整個網絡中指向網頁P的超鏈接數目 網頁P的鏡像度C(P) 整個網絡中網頁P的鏡像個數 域名深度：域名中包含子域的個數 目錄深度D(P)：域名中包含目錄的層數,海量Web信息的特征分析 URL序列：U1, U2, , U1000000 對應的用戶點擊次數為： V1, V2, , V1000000 對應的網頁入度為： H1, H2, , H1000000 網頁鏡像度為： C1, C2, , C1000000 URL目錄深度： D1, D2, , D1000000,用戶行為與We