問 題 背 景 頁 面 質(zhì) 量 評 估 的 相 關(guān) 工 作 概 述 高 質(zhì) 量 頁 面 的 查 詢 無 關(guān) 特 征 分 析 基 于 學(xué) 習(xí) 的 頁 面 質(zhì) 量 評 估 算 法 應(yīng) 用 展 望 問 題 背 景 頁 面 質(zhì) 量 評 估 的 相 關(guān) 工 作 概 述 高 質(zhì) 量 頁 面 的 查 詢 無 關(guān) 特 征 分 析 基 于 學(xué) 習(xí) 的 頁 面 質(zhì) 量 評 估 算 法 應(yīng) 用 展 望 World Wide Web的 出 現(xiàn) 與 發(fā) 展 38年13年4年 1994年 個(gè) 人 瀏 覽 器 誕 生 ， 到1998年 用 戶 超 過 5000萬 人 Web蘊(yùn) 含 著 多 少 信 息 ？How Much Info 工 程 由 Intel, Microsoft, HP, EMC等 公 司 贊 助 ， UC Berkeley大 學(xué) 完 成2002年 世 界 上 共 產(chǎn) 生 了 5Exabyte的 數(shù) 據(jù) ， 其 中92%的 信 息 存 儲(chǔ) 于 電 子 介 質(zhì) 相 當(dāng) 于 人 類 歷 史 上 所 有 說 過 的 話 語所 包 含 的 信 息 量 的 總 和 大 部 分 存 儲(chǔ) 于 Web中 ， 構(gòu) 成 了 Web中 超 過 150Billion的 網(wǎng) 絡(luò) 頁 面 Web的 發(fā) 展 帶 來 了 什 么 ？ 信 息 數(shù) 量 的 急 劇 膨 脹 知 識(shí) 的 獲 取 空 前 簡 單 與 繁 榮 I nformation is no longer a scarce resource - attention is. (注 意 力 ， 而 不 是 信 息 ， 才 是 這 個(gè) 時(shí) 代 所 稀 缺 的 資 源 ) (紐 約 時(shí) 報(bào) ， 2005年 10月 16日 ) 在 信 息 化 時(shí) 代 ， 知 識(shí) 實(shí) 際 上 已 經(jīng) 不 是 資 源 ， 智 慧 才是 資 源 。 （ 清 華 大 學(xué) 經(jīng) 管 學(xué) 院 魏 杰 教 授 ） 從 Web中 有 效 的 獲 取 知 識(shí) 正 在 成 為 人 們 生 活 與工 作 的 必 須 技 能 高 科 技 企 業(yè) 員 工 1/3的 時(shí) 間 用 于 查 找 資 料 由 于 無 法 找 到 有 效 信 息 而 浪 費(fèi) 的 產(chǎn) 值 占 企 業(yè) 收 入 1/5 2005年 搜 索 引 擎 市 場 的 激 烈 競 爭Google市 值 的 變 化 舉 世 關(guān) 注Baidu上 市 造 就 數(shù) 以 百 計(jì) 的 百 萬 富 翁MSN推 出 新 版 搜 索 ， MSRA建 立 搜 索 研 究 中 心Yahoo中 國 重 組 主 要 門 戶 網(wǎng) 站 Sohu, Sina, Netease, 騰 訊 紛 紛推 出 搜 索 引 擎 產(chǎn) 品 最 早 的 網(wǎng) 絡(luò) 搜 索 引 擎 索 引 系 統(tǒng) 誕 生 ： Stanford大 學(xué) , 1995 pictures by Admit Singhal, Google Inc. SIGIR05 keynote speech google.stanford.edu： google前 身 Google服 務(wù) 器 機(jī) 群 ： 1999 Google數(shù) 據(jù) 中 心 ： 2005 當(dāng) 前 面 臨 的 存 儲(chǔ) 與 運(yùn) 算 需 求 每 天 處 理 超 過 2億 用 戶 查 詢 近 80億 頁 面 索 引 Data by Admit Singhal, Google Inc. SIGIR05 keynote speech 搜 索 引 擎 索 引 規(guī) 模 的 競 爭Search Engine 索 引 量 頁 面 最 大 大 小Google 8.1 billion(Dec. 2004) 101KMSN 5.0 billion 150KYahoo 4.2 billion (estimate) 500KAsk Jeeves 2.5 billion 101K+All the Web 152 billion 605KAll the Surface Web 10 billion 8K 2002.1219.2 bilion(Aug. 2005) From Danny Sullivan, SearchEngineWatch web site 搜 索 引 擎 索 引 規(guī) 模 競 爭 的 終 結(jié) ？ 沒 有 任 何 一 個(gè) 搜 索 引 擎 可 以 覆 蓋 互 聯(lián) 網(wǎng) 上 的 所 有 資 源 2005年 9月 , Google從 首 頁 去 除 了 頁 面 索 引 數(shù) 量 的 信息 ， 并 解 釋 說 ： “ 絕 對 的 數(shù) 量 已 經(jīng) 不 再 重 要 ”Google Yahoo! MSN TeomaRound 1 76.30% 69.28% 62.03% 57.58%Round 2 76.09% 69.29% 61.90% 57.69%Round 3 76.27% 69.37% 61.87% 57.70%Round 4 76.05% 69.30% 61.73% 57.57%Round 5 76.11% 69.26% 61.96% 57.56%Average 76.16% 69.32% 61.90% 57.62% 對 中 文 搜 索 引 擎 而 言 搜 索 引 擎 里 每 天 有 400多 萬 被 檢 索 的 關(guān) 鍵 詞 一 般 而 言 不 重 復(fù) 的 關(guān) 鍵 詞 會(huì) 占 總 數(shù) 的 30%以 內(nèi)（ 根 據(jù) 李 彥 宏 報(bào) 告 的 百 度 狀 況 ） 對 于 每 個(gè) 關(guān) 鍵 詞 ， 用 戶 平 均 點(diǎn) 擊 的 頁 面 數(shù) 在 2頁 以 內(nèi) 則 可 以 估 算 如 下 : 用 戶 每 天 使 用 到 的 被 索 引 的 頁 面 數(shù) 為 2400萬 個(gè) 左 右 在 百 度 的 平 均 更 新 周 期 （ 1個(gè) 月 ） 內(nèi) ， 用 戶 共 可 能 訪 問 到的 頁 面 總 數(shù) 為 7.2億 個(gè) ， 少 于 百 度 聲 稱 的 索 引 量 （ 8億 ） 更 少 于 中 文 網(wǎng) 頁 總 數(shù) （ 20億 ） 搜 索 引 擎 應(yīng) 當(dāng) 處 理 (存 儲(chǔ) 、 評 價(jià) 、 預(yù) 處 理 與 后 處 理 )所 有 的 Web頁 面 么 ? 數(shù) 據(jù) 數(shù) 量 已 然 非 常 龐 大 網(wǎng) 絡(luò) 環(huán) 境 數(shù) 據(jù) 質(zhì) 量 堪 憂 ： 不 可 靠 、 Spam、 過 時(shí) ， 重 復(fù) 不 需 要 ， 也 不 可 能 ! 利 用 頁 面 質(zhì) 量 評 估 定 位 高 質(zhì) 量 頁 面 在 用 戶 查 詢 之 前 進(jìn) 行 數(shù) 據(jù) 預(yù) 處 理 階 段 使 用 查 詢 無 關(guān) 特 征 進(jìn) 行 頁 面 質(zhì) 量 評 估 的 過 程 應(yīng) 當(dāng)是 查 詢 無 關(guān) 完 成 的 問 題 背 景 頁 面 質(zhì) 量 評 估 的 相 關(guān) 工 作 概 述 高 質(zhì) 量 頁 面 的 查 詢 無 關(guān) 特 征 分 析 基 于 學(xué) 習(xí) 的 頁 面 質(zhì) 量 評 估 算 法 應(yīng) 用 展 望 按 照 粒 度 不 同 宏 觀 粒 度 的 質(zhì) 量 評 估 去 除 無 用 頁 面 / 定 位 有 用 頁 面 清 理 “ 全 局 垃 圾 ” 微 觀 粒 度 的 質(zhì) 量 評 估 去 除 頁 面 中 的 無 用 部 分 / 找 出 頁 面 中 最 有 用 的 部 分 清 理 “ 局 部 垃 圾 ” 宏 觀 粒 度 的 頁 面 質(zhì) 量 評 估 目 的 ： 找 出 對 用 戶 檢 索 信 息 有 用 的 頁 面 當(dāng) 前 的 研 究 重 點(diǎn) ： Web鏈 接 結(jié) 構(gòu) 分 析 如 果 存 在 超 鏈 接 L從 頁 面 P(source)指 向 頁 面 P(destiny)，則 P(source)與 P(destiny)之 間 滿 足 ：假 設(shè) 1： （ 內(nèi) 容 推 薦 假 設(shè) ） 頁 面 P(source)的 作 者 推 薦 頁 面P(destiny)的 內(nèi) 容 ， 且 利 用 L的 鏈 接 文 本 內(nèi) 容 對 P(destiny)進(jìn) 行 描 述 。假 設(shè) 2： （ 主 題 相 關(guān) 假 設(shè) ） 被 超 鏈 接 連 接 的 兩 個(gè) 頁 面 P(source)與P(destiny)比 隨 機(jī) 抽 取 的 兩 個(gè) 頁 面 有 更 大 的 概 率 有 內(nèi) 容 相 關(guān) 性 。 PageRank（ Google） , HITS（ Kleinberg.） 及 眾 多 的改 進(jìn) 算 法 微 觀 粒 度 的 頁 面 質(zhì) 量 評 估 目 的 ： 找 出 對 用 戶 檢 索 信 息 有 用 的 頁 面 的 某 個(gè) 部 分 去 除 特 定 垃 圾 信 息 （ 利 用 機(jī) 器 學(xué) 習(xí) 方 法 和 一 定 量 的 訓(xùn)練 ） 去 除 廣 告 條 （ Davison et. al.） 去 除 頁 面 中 的 無 關(guān) 鏈 接 與 垃 圾 鏈 接 （ Kushmerick et. al.） 頁 面 分 塊 模 型 依 據(jù) 語 料 統(tǒng) 計(jì) 信 息 計(jì) 算 頁 面 塊 的 信 息 量 （ Lin et. al.） 基 于 模 板 頻 度 檢 測 構(gòu) 建 站 點(diǎn) 模 板 （ Yossef et. al. Yi et. al.） 基 于 頁 面 塊 的 絕 對 位 置 和 機(jī) 器 學(xué) 習(xí) 方 法 計(jì) 算 塊 的 重 要 性（ VIsion Based Page Segmentation, VIPS, MSRA） 微 觀 粒 度 的 質(zhì) 量 評 估 示 例 （ 頁 面 分 塊 ） 頁 面 質(zhì) 量 評 估 的 研 究 現(xiàn) 狀 微 觀 粒 度 具 有 數(shù) 據(jù) 挖 掘 方 面 研 究 的 積 累 （ 數(shù) 據(jù) 預(yù) 處 理 、 數(shù) 據(jù) 清 理 等 ） 相 對 比 較 成 熟 完 善 宏 觀 粒 度 搜 索 引 擎 競 價(jià) 排 名 機(jī) 制 的 引 入 ， 帶 來 了 大 量 的 鏈 接 垃 圾 內(nèi) 容 推 薦 和 主 題 相 關(guān) 假 設(shè) 受 到 挑 戰(zhàn) 過 多 關(guān) 注 頁 面 自 身 的 特 性 ， 忽 略 用 戶 的 實(shí) 際 需 求 只 重 視 鏈 接 結(jié) 構(gòu) 特 征 ， 忽 略 頁 面 其 他 類 型 的 查 詢 無 關(guān) 特 征 是 我 們 研 究 的 重 點(diǎn) 頁 面 質(zhì) 量 評 估 應(yīng) 當(dāng) 涉 及 到 鏈 接 關(guān) 系 之 外 的 特 征 信 息PageRank only uses the link structure of the web to estimate page quality. It seems to us that a better estimate of the quality of a page requires additional sources of information. Monika R. Henzinger, Research Director of Google 我 們 的 理 解 ：對 于 檢 索 系 統(tǒng) 而 言 ， 頁 面 質(zhì) 量 的 最 根 本 評 價(jià) 不 是 由 諸 如 頁 面 在 鏈接 結(jié) 構(gòu) 圖 中 的 重 要 程 度 這 樣 的 特 征 來 決 定 的 。能 否 滿 足 用 戶 獲 取 信 息 的 需 要 是 頁 面 質(zhì) 量 評 價(jià) 的 根 本 出 發(fā) 點(diǎn) 。 研 究 用 戶 需 要 什 么 ， 而 非 假 設(shè) 用 戶 需 要 什 么 有 可 能 成 為 用 戶 檢 索 目 標(biāo) 的 頁 面 才 是 高 質(zhì) 量 的 用 戶 需 要 什 么 ？ 反 映 在 用 戶 查 詢 的 目 標(biāo) 頁 面 中 高 質(zhì) 量 頁 面 ： 可 能 成 為 用 戶 檢 索 目 標(biāo) 的 Web頁 面 矛 盾 ： 查 詢 目 標(biāo) 頁 面 是 與 查 詢 相 關(guān) 的 頁 面 質(zhì) 量 評 估 是 查 詢 無 關(guān) 的 過 程 必 須 使 用 查 詢 無 關(guān) 特 征 宏 觀 上 來 講 ， 與 查 詢 相 關(guān) 的 查 詢 目 標(biāo) 頁 面 是 否 存 在 與 查 詢無 關(guān) 的 特 征 呢 ？ 問 題 背 景 頁 面 質(zhì) 量 評 估 的 相 關(guān) 工 作 概 述 高 質(zhì) 量 頁 面 的 查 詢 無 關(guān) 特 征 分 析 基 于 學(xué) 習(xí) 的 頁 面 質(zhì) 量 評 估 算 法 應(yīng) 用 展 望 基 于 真 實(shí) 網(wǎng) 絡(luò) 語 料 庫 進(jìn) 行 查 詢 目 標(biāo) 頁 面的 查 詢 無 關(guān) 特 征 分 析 語 料 庫 2005.11月 采 集 的 超 過 3700萬 中 文 網(wǎng) 頁 占 用 空 間 超 過 0.5 Terabyte. 自 S獲 得 高 質(zhì) 量 頁 面 采 樣 訓(xùn) 練 集 : 1600頁 面 測 試 集 : 17000頁 面 由 Sogou工 程 師 手 工 標(biāo) 注 基 于 超 鏈 接 結(jié) 構(gòu) 分 析 的 特 征PageRank 入 鏈 接 個(gè) 數(shù) 入 鏈 接 文 本 長 度 其 他 特 征 文 檔 長 度 /大 小 完 全 鏡 像 個(gè) 數(shù)URL長 度 與 類 型 頁 面 編 碼 PageRank 入 鏈 接 個(gè) 數(shù) 入 鏈 接 文 本 長 度 文 檔 長 度 頁 面 鏡 像 個(gè) 數(shù) URL 長 度 /類 型 其 他 部 分 特 征 查 詢 無 關(guān) 特 征 能 夠 有 效 地 區(qū) 分 目 標(biāo) 頁 面 與 普 通 頁面 ， 亦 即 查 詢 目 標(biāo) 頁 面 具 有 查 詢 無 關(guān) 特 征普 通 頁 面 查 詢 目 標(biāo) 頁 面動(dòng) 態(tài) 頁 面 13.06% 1.87%編 碼 非 GBK 14.04% 1.39%是 否 是 Hub類 型 3.78% 24.77% 問 題 背 景 頁 面 質(zhì) 量 評 估 的 相 關(guān) 工 作 概 述 高 質(zhì) 量 頁 面 的 查 詢 無 關(guān) 特 征 分 析 基 于 學(xué) 習(xí) 的 頁 面 質(zhì) 量 評 估 算 法 應(yīng) 用 展 望 根 據(jù) 查 詢 無 關(guān) 特 征 計(jì) 算 頁 面 成 為 查 詢 目 標(biāo) 頁 面 的可 能 性 ， 用 這 種 可 能 性 表 示 頁 面 質(zhì) 量 的 高 低 形 式 化 的 表 述 為 ：具 有 查 詢 無 關(guān) 特 征 A1, A2, A3, , An的 頁 面 P成 為查 詢 目 標(biāo) 頁 面 的 可 能 性 ),.,|( 21 nAAAfeaturehasppageTargetpP 算 法 描 述1 單 特 征 分 析 )()( )|( )|( pageTargetpPAfeaturehaspP pageTargetpAfeaturehaspP AfeaturehasppageTargetpP （ 貝 葉 斯 公 式 ）（ 先 驗(yàn) 概 率 定 義 ）)(# )(#)(# )(# )( )|( CORPUS AfeaturehasppageTarget pageTargetpAfeaturehasp AfeaturehaspP pageTargetpAfeaturehaspP )(# )(#)(# )(# )|( CORPUS AfeaturehaspsetsamplepageTarget setsamplepageTargetpAfeaturehasp AfeaturehasppageTargetpP 算 法 描 述2 多 特 征 分 析在 合 理 選 取 的 基 礎(chǔ) 上 ， 可 以 發(fā) 現(xiàn) 特 征 之 間 的 近 似 獨(dú) 立 性 關(guān) 系URL Format Encode PageRank Cluster DocLength URL Length IndegreeURL Format 1.00 0.05 0.05 0.01 0.04 0.10 0.00Encode 1.00 0.20 0.00 0.06 0.30 0.00PageRank 1.00 0.01 0.06 0.03 0.05Cluster 1.00 0.01 0.10 0.00DocLength 1.00 0.04 0.00URL Length 1.00 0.02 Indegree 1.00 算 法 描 述2 多 特 征 分 析 （ 續(xù) ） n1i in21 )|()|,.,( pageTargetpAfeaturehaspPpageTargetpAAAfeaturehaspP （ 樸 素 貝 葉 斯 假 設(shè) ） n1i in21 )(),.,( AfeaturehaspPAAAfeaturehaspP （ 特 征 近 似 獨(dú) 立 ） n1i in1i ii n21n21 n21 )|()( )()|( ),.,( )()|,.,( ),.,|( pageTargetpAfeaturehaspPAfeaturehaspP pageTargetpPpageTargetpAfeaturehaspP AAAfeaturehaspP pageTargetpPpageTargetpAAAfeaturehaspP AAAfeaturehasppageTargetpP 比 較 的 相 對 大 小 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 1 2 4 8 16 32 64 128 256 other Ordinary HighQuality ni ii CORPUS AfeaturehaspsetsamplepageTarget setsamplepageTargetpAfeaturehasp1 )(# )(#)(# )(#( 高 質(zhì) 量 頁 面 的 概 率 分 布 情 況 測 試 效 果 測 試 集 合 ： 17000多 個(gè) 查 詢 目 標(biāo) 頁 面 （ 訓(xùn) 練 集 的 10倍 ） 算 法 判 定 出 的 高 質(zhì) 量 頁 面 僅 占 數(shù) 據(jù) 總 量 的 5%， 但 能 夠滿 足 超 過 92%以 上 的 用 戶 查 詢 需 求普 通 頁 面 查 詢 目 標(biāo) 頁 面訓(xùn) 練 集 合 查 詢 目 標(biāo) 頁 面測 試 集 合算 法 判 定 出 的低 質(zhì) 量 頁 面 95.04% 7.27% 7.63%算 法 判 定 出 的高 質(zhì) 量 頁 面 4.96% 92.73% 92.37% 質(zhì) 量 評 估 算 法 效 果 的 評 價(jià) 指 標(biāo) 高 質(zhì) 量 頁 面 平 均 召 回 率 （ High Quality Page Average Recall, AR） )(#)()(# 1 DocumentiRecallAR Documenti High Quality Recall 與 直 接 應(yīng) 用 PageRank作 為 頁 面 質(zhì) 量 評 估 指標(biāo) 的 比 較 High Quality Page Average Recall 0.905 0.910 0.915 0.920 0.925 0.930 0.935 0.940 0.945 0.950 0.955 PageRank Only Without PageRank Without Inlink All Feature比 僅 使 用 PageRank特 征 取 得 更 好 的 效 果 并 不 單 獨(dú) 依 靠 某 個(gè) 特 征實(shí) 現(xiàn) 評 估 任 務(wù) 算 法 分 辨 垃 圾 /低 質(zhì) 量 頁 面 的 能 力 同 時(shí) 具 有 較 好 的 篩 選 作 弊 頁 面 和 低 質(zhì) 量 頁 面 的 作 用 0% 5% 10% 15% 20% 25% 30% 35% Page Quality Estimation PageRank Only Inlink Only Spam Reduced Low Quality Reduced 問 題 背 景 頁 面 質(zhì) 量 評 估 的 相 關(guān) 工 作 概 述 高 質(zhì) 量 頁 面 的 查 詢 無 關(guān) 特 征 分 析 基 于 學(xué) 習(xí) 的 頁 面 質(zhì) 量 評 估 算 法 應(yīng) 用 展 望 利 用 頁 面 質(zhì) 量 評 估 算 法 作 為 搜 索 引 擎 層 次索 引 機(jī) 制 的 基 礎(chǔ)普 通 頁 面 高 質(zhì) 量索 引質(zhì) 量 評 價(jià) 算 法搜 索 引 擎 系 統(tǒng) 結(jié) 果查 詢反 饋 同 PageRank一 樣 作 為 Ranking算 法 的 依 據(jù) PageRank： 用 戶 隨 機(jī) 訪 問 到 某 個(gè) 頁 面 的 可 能 性 頁 面 質(zhì) 量 ： 某 個(gè) 頁 面 成 為 用 戶 查 詢 目 標(biāo) 的 普 適 可 能 性 具 有 明 確 的 物 理 含 義 利 用 類 似 方 法 進(jìn) 行 垃 圾 頁 面 清 理 工 作 統(tǒng) 計(jì) 垃 圾 頁 面 的 查 詢 無 關(guān) 特 征 比 較 查 詢 目 標(biāo) 頁 面 而 言 ， 這 種 特 征 應(yīng) 當(dāng) 更 加 明 顯 利 用 機(jī) 器 學(xué) 習(xí) 方 法 構(gòu) 建 分 類 器 計(jì) 算 某 個(gè) 頁 面 成 為 垃 圾 頁 面 的 概 率 其 它 的 可 能 應(yīng) 用 方 向 用 于 提 高 搜 索 引 擎 Spider的 頁 面 抓 取 效 率 提 高 個(gè) 人 化 搜 索 （ personalized search） 質(zhì) 量 更 好 的 理 解 用 戶 使 用 搜 索 引 擎 的 行 為 特 點(diǎn)摘 自 http:/ 連 續(xù) 幾 天 ， 定 時(shí) 被 百 度 的 抓 取 機(jī) 器 人 抓 到系 統(tǒng) 停 止 響 應(yīng) 。 拜 托 百 度 ， 不 要 這 樣 抓 內(nèi) 容 了 。 就 算 抓 ， 也 應(yīng) 該 用 1個(gè) 線 程來 抓 ， 只 抓 更 新 的 內(nèi) 容 ， 何 必 每 天 抓 一 次 ， 而 且 用 無 數(shù) 個(gè) 線 程 ， 而且 每 次 都 要 抓 全 部 內(nèi) 容 ， 還 不 放 過 任 何 wiki的 歷 史 頁 面 ， 甚 至 連錯(cuò) 誤 信 息 都 要 原 樣 搬 走 。 這 種 抓 取 方 法 ， 誰 受 得 了 ？ Thank you!Questions or comments?