一个借助查询历史改善结果排序的文件检索系统的设计与实现 硕士毕业论文.doc

北京大学硕士研究生学位论文 题目：一个借助查询历史改善结果排序的文件检索系统的 设计与实现 姓 名 ： 学 号 ： 院 系 ： 信 息 科 学 技 术 学 院 专 业 ： 计 算 机 系 统 结 构 研 究 方 向 ： 计 算 机 网 络 与 分 布 式 系 统 导 师 ： 1 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本 论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作 者著作权之问题，将可能承担法律责任。 2 摘 要 随 着 网 络 的 发 展 ， 网 络 上 提 供 文 件 共 享 服 务 的 服 务 器 越 来 越 多 ， 共 享 的 文 件 数 量 也 随 之 增 加 。 如 何 更 好 的 检 索 、 利 用 这 些 共 享 文 件 成 为 一 个 重 要 的 问 题 。 针 对 用 户 对 文 件 检 索 的 需 求 ， 本 文 在 文 件 检 索 技 术 领 域 有 如 下 贡 献 。 1. 本 文 首 先 提 出 了 一 个 文 件 检 索 的 模 型 ， 明 确 了 在 文 件 检 索 模 型 中 检 索 对 象 、 查 询 串 、 查 询 与 检 索 对 象 的 匹 配 方 式 三 部 分 的 含 义 。 检 索 对 象 ， 即 文 件 条 目 表 示 为 六 元 组 name, ext, size, date, site, path的 形 式 ， 查 询 串 表 示 为 以 空 格 分 隔 的 字 符 串 的 集 合 ， 查 询 与 检 索 对 象 的 匹 配 则 表 示 为 查 询 串 与 文 件 条 目 的 匹 配 串 之 间 的 匹 配 。 2. 提 出 了 对 文 件 检 索 系 统 进 行 评 测 的 指 标 。 将 查 询 结 果 视 作 集 合 时 以 查 全 率 、 查 准 率 为 评 测 指 标 。 将 查 询 结 果 视 作 有 序 序 列 时 ， 分 析 了 查 询 结 果 的 相 关 性 、 连 接 下 载 速 度 以 及 结 果 的 可 用 性 等 因 素 对 排 序 的 影 响 ， 并 提 出 了 对 排 序 进 行 评 测 的 指 标 排 序 指 数 。 作 者 还 提 出 对 于 两 个 排 序 策 略 进 行 比 较 时 ， 应 当 在 结 果 的 每 个 页 面 内 部 应 用 排 序 策 略 ， 而 不 是 在 全 体 结 果 集 合 上 应 用 排 序 策 略 ， 并 比 较 平 均 用 户 选 取 条 目 的 页 内 排 名 。 3. 通 过 统 计 、 分 析 用 户 对 文 件 搜 索 引 擎 的 检 索 和 对 检 索 结 果 中 下 载 地 址 条 目 的 选 取 ， 作 者 发 现 了 用 户 行 为 习 惯 中 的 两 个 重 要 规 律 ： 一 、 少 数 查 询 串 占 据 了 全 部 查 询 请 求 的 大 多 数 ， 具 体 而 言 ， 前 20%的 热 门 查 询 串 占 据 了 全 部 查 询 请 求 的 80%； 二 、 对 全 体 用 户 而 言 ， 假 设 有 n 次 不 同 的 查 询 请 求 使 用 了 同 一 个 查 询 串 ， 并 且 它 们 代 表 k 类 不 同 的 查 询 意 图 。 那 么 通 常 k 3， 因 而 在 n 较 大 的 情 况 下 ， 则 n/k 的 值 较 大 ， 即 大 量 的 来 自 不 同 用 户 的 请 求 代 表 了 相 同 的 查 询 意 图 。 4. 基 于 上 文 所 述 ， 作 者 设 计 并 实 现 了 一 个 真 实 的 系 统 。 该 系 统 借 助 查 询 历 史 改 善 结 果 的 排 序 。 与 一 般 基 于 用 户 历 史 信 息 的 检 索 系 统 不 同 的 是 ， 本 系 统 借 助 的 历 史 信 息 不 局 限 于 当 前 用 户 的 历 史 信 息 ， 还 包 含 提 交 了 相 同 查 询 串 的 其 他 用 户 的 查 询 信 息 。 或 者 说 ， 即 使 当 前 用 户 是 第 一 次 使 用 本 系 统 ， 本 系 统 也 能 利 用 其 他 用 户 的 历 史 记 录 来 改 进 结 果 的 排 序 和 筛 选 。 作 者 最 后 还 验 证 了 其 实 际 的 效 果 。 应 用 本 方 法 后 ， 平 均 用 户 选 取 条 目 的 页 内 排 名 从 原 来 的 13.70 名 前 进 到 了 8.93 名 。 试 验 结 果 表 明 文 中 所 做 的 分 析 是 正 确 的 。 关键词：文件检索系统，查询历史，检索模型 3 the design and implementation of a file index system which improve the order by query history abstract with the rapid expansion of the internet, there are more sharing file servers. and the number of sharing files is increasing rapidly too. so its more important to retrieve these files easily. for the requirement of file retrieving of the users, we did the following jobs: 1. we proposed a file index model. the model is composed of the expression of an index object, the expression of a query, and how the query word matches the index object. the index object can be expressed as name, ext, size, date, site, path, the query string is expressed as strings separated by space, and the matching between query and index object is realized by matching the query string and the matching strings of the file item. 2. we also proposed the evaluation indicator for the file index evaluation. the precision and recall are useful when we evaluate the query result. but the result is not a set, but an ordered list. so we indicated the factors in order: the relativity of the item, the connecting and download speed and the availability of the site. we proposed how to evaluate the order: average rank of chosen items. if we just want to compare two ranking strategy, we should not reorder all items in the result set but only reorder the items within each page and compare the average rank of chosen items within page. 3. by analyzing the records of users queries and the file items that users chosen from a real file search engine, we discovered two lows. 1). most query strings are repeating hot query strings. 80% query words are the top 20% hot query strings. 2) if there are n times of queries using the same query strings, and the total number of different intensions is k. then k should be a very small number (usually, k5 对 应 的 查 询 串 的 个 数 33 157 81 0 1 0 从 上 表 可 见 ， 查 询 意 图 只 有 1 3 个 的 查 询 串 占 全 部 记 录 数 据 的 绝 大 部 分 ， 超 过 5 种 不 同 意 图 的 查 询 串 在 统 计 的 日 志 中 根 本 就 没 有 出 现 。 我 们 再 来 看 一 下 n 和 k 的 比 例 的 分 布 ， 统 计 结 果 如 下 图 。 图 中 横 坐 标 表 示 查 询 串 被 查 询 的 次 数 n， 综 坐 标 为 n/k 的 比 值 。 要 说 明 一 点 就 是 为 了 使 图 像 中 的 点 线 显 示 清 晰 ， 我 们 忽 略 了 很 少 量 的 查 询 次 数 非 常 高 的 词 （ 这 些 点 对 应 的 横 坐 标 值 非 常 大 ） ， 但 事 后 的 手 工 验 证 仍 然 证 明 了 它 们 符 合 本 文 的 规 律 。 26 1 10 10 100 0 10 20 30 40 50 60 70 80 90 100 图 4-3 查询串与查询意图种类比值分析 其中横坐标为查询串查询次数 n， 综坐标为 n/k 比值（为指数标度） 从 图 中 可 以 看 到 ， 当 n100 时 ， n/k 的 值 都 在 30 以 上 。 由 上 面 的 分 析 我 们 能 够 知 道 ， 尽 管 查 询 串 不 同 ， 但 一 般 说 来 ， 它 们 所 代 表 的 查 询 意 图 的 数 量 并 不 是 太 多 的 ， 通 常 在 1-3 种 ， 并 且 在 n 较 大 的 情 况 下 （ 如 n100） ， 通 常 n/k 的 比 值 较 大 （ 本 例 中 大 于 30） 。 因 此 我 们 得 到 了 第 二 个 重 要 的 规 律 ： 规 律 二 ： 假 设 有 n 次 不 同 的 请 求 查 询 了 同 一 个 查 询 串 ， 并 且 它 们 代 表 k 种 不 同 的 查 询 意 图 。 在 n 较 大 的 情 况 下 （ n100） ， n/k 的 值 较 大 （ n/k30） 。 4.3 用 户 行 为 特 点 的 启 发 利 用 上 面 的 用 户 行 为 特 点 中 的 两 个 规 律 ， 以 及 前 面 关 于 相 关 反 馈 方 法 的 思 路 ， 可 以 考 虑 采 用 如 下 思 路 来 实 现 一 个 借 助 查 询 历 史 信 息 改 善 结 果 排 序 的 文 件 检 索 系 统 。 从 上 面 的 特 征 我 们 知 道 ， 大 多 数 的 查 询 请 求 不 仅 其 查 询 串 本 身 是 重 复 的 ， 而 且 其 所 代 表 的 查 询 意 图 也 是 重 复 的 。 这 样 我 们 就 可 以 由 “较 早 的 相 同 的 查 询 串 的 结 果 选 取 记 录 ”作 为 用 户 的 反 馈 信 号 。 这 样 一 来 ， 后 来 提 交 同 样 查 询 串 的 用 户 不 需 要 27 任 何 主 动 干 预 ， 就 可 以 得 到 经 过 反 馈 信 号 处 理 过 的 重 新 排 序 的 查 询 结 果 了 。 当 然 ， 由 于 用 户 意 图 并 不 唯 一 ， 我 们 并 不 能 确 定 究 竟 本 次 查 询 的 用 户 是 哪 种 查 询 意 图 ， 但 因 为 k 值 通 常 都 相 当 小 （ 小 于 等 于 3） ， 因 此 对 用 户 而 言 ， 很 容 易 从 这 为 数 极 少 的 查 询 意 图 中 找 到 满 足 自 己 意 图 的 结 果 。 具 体 而 言 ， 我 们 可 以 考 虑 如 下 的 思 路 。 首 先 记 录 下 每 次 用 户 对 查 询 结 果 的 选 取 。 我 们 认 为 ， 用 户 在 查 询 结 果 中 点 击 的 下 载 地 址 ， 就 是 用 户 认 为 比 较 理 想 的 下 载 地 址 。 通 过 一 段 时 间 的 记 录 ， 我 们 就 得 到 了 对 于 大 量 查 询 串 的 较 理 想 的 匹 配 结 果 。 对 于 一 个 查 询 串 q， 我 们 有 一 个 用 户 认 为 较 好 的 文 件 条 目 的 集 合 s， 我 们 将 其 表 示 为 一 个 二 元 组 (q,s)。 这 样 ， 我 们 就 得 到 了 大 量 的 这 样 的 二 元 组 。 依 据 规 律 2， 我 们 知 道 每 个 查 询 串 可 能 代 表 几 个 不 同 的 查 询 意 图 ， 那 么 不 同 的 查 询 意 图 对 应 的 理 想 下 载 地 址 肯 定 不 同 （ 否 则 就 是 相 同 的 查 询 意 图 了 ） ， 我 们 可 以 采 用 聚 类 的 方 法 对 每 个 s 中 的 文 件 条 目 进 行 聚 类 。 聚 类 后 ， 对 于 每 个 q， 我 们 会 得 到 k 种 不 同 的 类 别 ， 这 k 个 类 别 就 也 就 反 映 了 不 同 的 查 询 意 图 ， 而 每 个 类 别 中 的 文 件 条 目 ， 就 可 以 看 作 这 个 类 别 的 训 练 集 。 每 个 类 别 中 的 条 目 个 数 ， 也 直 接 反 映 了 这 个 类 别 的 权 重 。 当 再 次 有 用 户 查 询 同 样 的 查 询 串 q 时 ， 我 们 首 先 采 用 原 始 的 检 索 方 法 ， 得 到 一 个 结 果 集 合 ， 然 后 用 聚 类 得 到 的 k 个 类 别 和 训 练 集 对 其 进 行 分 类 处 理 。 一 些 条 目 被 分 到 这 k 个 类 别 中 ， 另 外 一 些 可 能 不 属 于 任 何 类 别 。 不 属 于 任 何 类 别 的 条 目 往 往 也 是 用 户 不 太 需 要 的 条 目 ， 可 以 考 虑 抛 弃 或 排 在 结 果 的 最 后 输 出 。 28 第 5章 系 统 体 系 结 构 与 主 要 算 法 5.1 系 统 体 系 结 构 基 于 以 上 分 析 ， 我 们 设 计 了 如 下 的 检 索 系 统 来 改 善 文 件 检 索 系 统 的 排 序 。query string (q)normal index syst() index rsult (s0) fedback dta dtbse site list datbsequeryclusteringthe traing sfoqueryitm items not blgay rupresult afer cagoiztin (s)categorization, odgfiletms tha user cliked 图 5-1 系统结构图 下 面 我 们 来 详 细 介 绍 这 个 模 型 。 我 们 首 先 查 看 模 型 中 的 各 个 组 成 部 分 。 query string (q)： 用 户 输 入 的 查 询 串 ； normal index system(i)： 常 规 的 文 件 检 索 系 统 ； index result(s0)： 初 始 查 询 结 果 集 ； feedback data db(f)： 该 数 据 库 中 记 录 了 已 有 的 每 个 查 询 请 求 和 它 对 应 的 不 同 的 k 种 查 询 意 图 ， 以 及 每 种 意 图 的 作 为 训 练 集 的 文 件 条 目 。 fileitem db(d)： 该 数 据 库 中 保 存 了 每 次 用 户 进 行 检 索 后 对 查 询 结 果 的 选 取 情 况 。 具 体 而 言 ， 当 用 户 进 行 查 询 后 ， 检 索 系 统 返 回 结 果 ， 当 用 户 在 结 果 页 面 中 对 文 件 条 目 进 行 点 击 并 下 载 时 ， 本 模 型 会 记 录 用 户 的 点 击 选 取 行 为 。 库 中 的 每 条 记 录 含 有 当 前 的 查 询 串 和 用 户 点 击 的 这 条 记 录 的 具 体 文 件 信 息 ： 文 件 名 称 、 扩 展 名 称 、 最 后 修 改 日 期 、 文 件 大 小 、 文 件 所 在 站 点 和 文 件 所 在 的 路 径 。 29 本 检 索 系 统 的 工 作 流 程 如 下 ： 数 据 库 f 中 需 要 足 够 的 数 据 记 录 系 统 才 能 够 进 行 工 作 。 因 此 在 系 统 运 行 之 初 ， 系 统 便 开 始 自 动 记 录 用 户 的 点 击 ， 并 将 记 录 填 充 进 数 据 库 d。 数 据 库 d 每 隔 一 段 时 间 ， 对 每 个 查 询 串 q 进 行 一 次 聚 类 操 作 ， 这 样 便 得 到 了 每 个 查 询 串 所 代 表 的 k 种 查 询 意 图 。 现 在 我 们 假 设 f 中 已 经 包 含 有 了 足 够 的 记 录 信 息 。 当 用 户 输 入 查 询 串 q 后 ， 一 方 面 ， 模 型 中 最 上 面 的 流 程 开 始 工 作 ， 常 规 的 检 索 系 统 进 行 检 索 ， 得 到 一 个 原 始 的 查 询 结 果 s0。 另 一 方 面 ， 如 模 型 图 示 中 的 中 层 的 流 程 ， q 被 送 入 数 据 库 f。 数 据 库 f 返 回 对 应 的 k 种 意 图 和 其 点 击 记 录 集 合 。 这 些 记 录 将 作 为 下 一 步 分 类 工 作 的 训 练 集 。 有 了 s0 和 这 k 种 类 别 ， 下 面 将 利 用 这 k 种 类 别 的 训 练 集 对 s0 进 行 分 类 。 分 类 后 我 们 将 s0 分 成 了 k+1 类 ， 其 中 新 增 加 的 这 个 类 别 是 那 些 不 属 于 任 何 类 别 的 文 件 条 目 item 集 合 。 对 于 不 属 于 任 何 类 别 的 条 目 ， 我 们 认 为 它 是 用 户 不 太 关 心 的 结 果 ， 可 以 把 它 抛 弃 或 放 入 输 出 结 果 的 最 后 。 这 里 有 一 点 要 注 意 ， 就 是 k 种 类 别 的 地 位 是 不 同 的 ， 类 别 本 身 也 是 有 权 重 的 ， 权 重 可 以 由 聚 类 时 每 个 类 别 中 的 条 目 数 量 来 决 定 。 这 样 在 最 后 输 出 时 可 以 按 照 权 重 本 身 对 类 别 进 行 排 序 。 由 于 k 的 取 值 通 常 都 比 较 小 （ 小 于 等 于 3） ， 用 户 最 终 看 到 的 结 果 往 往 是 接 近 用 户 的 真 实 查 询 意 图 的 。 然 后 就 可 以 按 照 一 般 的 条 目 列 表 方 式 或 者 聚 类 的 树 型 结 构 将 结 果 输 出 给 最 终 用 户 。 5.2 主 要 算 法 5.2.1 用户点击日志的表示 用 户 点 击 日 志 就 是 用 户 所 点 击 的 文 件 条 目 item。 由 前 面 的 对 文 件 检 索 的 建 模 ， 我 们 知 道 可 以 表 示 为 ： item = name, ext, size, date, site, path 我 们 将 其 改 写 为 如 下 格 式 ： pathsitedatesizeextnam xxx 有 时 候 为 了 简 便 ， 我 们 也 会 表 述 为 如 下 形 式 ： 30 654321 xxx 对 于 查 询 串 q， 价 格 共 有 n 个 记 录 ， 因 此 我 们 得 到 如 下 的 矩 阵 ：1,1,21,31,41,51,6,1,2,3,4,5,6,1,2,3,4,5,6iiiiiinnnnnnxxxxxx 5.2.2 计算文件条目之间的距离 不 论 是 进 行 聚 类 处 理 还 是 进 行 分 类 处 理 ， 都 需 要 进 行 大 量 的 对 两 个 文 件 条 目 (item)之 间 的 距 离 d 的 计 算 。 或 者 说 ， 需 要 通 过 上 文 中 的 二 模 矩 阵 ， 得 到 下 面 的 表 示 条 目 之 间 距 离 的 单 模 矩 阵 ：0(2,1)3(,)04,(4,3)(5),5(,)06,1(2)6,(6,5)7,(7),7(,)0.(,)(,),3(,4)(,),(,ddd dndnndn1)0 图 中 我 们 用 d(i,j)表 示 项 xi 和 xj 之 间 的 距 离 ， 有 d(i,j) 0。 当 d(i,j)=0 时 表 示 二 者 完 全 相 同 ； 当 d(i,j)0 时 表 示 二 者 不 同 ， 并 且 d 的 值 越 大 表 示 文 件 条 目 xi 和 xj 之 间 的 差 异 越 大 。 对 于 条 目 i 和 j 之 间 距 离 的 d(i,j)的 计 算 ， 我 们 采 用 如 下 加 权 公 式 ： 31 (,)1(,)ifjpxfddxij 由 前 文 文 件 检 索 模 型 可 知 ， 此 处 p=6。 我 们 分 别 计 算 文 件 条 目 i 和 j 的 6 项 对 应 属 性 的 距 离 ， 再 进 行 加 权 求 和 最 后 再 进 行 标 准 化 处 理 。 由 于 文 件 条 目 的 6 项 属 性 的 数 据 类 型 和 含 义 不 完 全 相 同 ， 因 此 具 体 的 计 算 方 法 区 别 较 大 ， 在 计 算 时 需 要 分 别 考 虑 。 下 图 为 各 个 属 性 的 数 据 类 型 和 计 算 方 法 。 表格 5-1 文件条目各个属性数据类型 属 性 数 据 类 型 距 离 计 算 方 法 name string minimal edit distance ext string nominal variables size integer interval-scaled variables date integer interval-scaled variables site string n/a path string subsection string 具 体 方 法 为 ： 5.2.2.1 name 属性距离的计算方法 name 表 示 文 件 的 不 包 含 扩 展 名 的 主 名 的 名 称 ， 数 据 类 型 为 字 符 串 型 。 对 于 这 种 字 符 串 类 型 数 据 的 处 理 ， 一 般 情 况 下 可 以 按 照 文 档 的 相 似 度 的 方 式 进 行 。 但 由 于 文 件 名 通 常 都 比 较 短 小 ， 命 名 多 数 情 况 下 也 不 规 范 。 这 里 并 不 建 议 按 照 文 档 的 形 式 来 处 理 。 我 们 这 里 采 用 的 处 理 方 法 是 按 照 最 小 编 辑 距 离 的 方 法 来 处 理 。 编 辑 距 离 是 指 两 个 字 符 串 通 过 插 入 字 符 、 删 除 字 符 、 改 写 字 符 而 变 为 相 同 字 符 串 所 需 要 的 操 作 次 数 。 比 如 ： d(“abc”,”abd”) = 1 d(“abc”,”ab”) = 1 d(“abc”, “abcdf”) = 2 d(“serveru”,” ser-u”) = 4 利 用 动 态 规 划 的 方 法 计 算 编 辑 距 离 ， 时 间 复 杂 性 可 以 达 到 o(n2)， 空 间 复 杂 性 32 为 o（ n2） 。 计 算 方 法 为 一 个 递 归 算 法 ： d(, ) = 0 d(s, ) = d(, s) = |s| （ |s|表 示 s 的 长 度 ） d(s1+ch1, s2+ch2) = min( d(s1, s2) + （ if ch1=ch2 then 0 else 1） , d(s1+ch1, s2) + 1, d(s1, s2+ch2) + 1 ) 5.2.2.2 ext 属性距离的计算方法 ext 指 文 件 的 扩 展 名 ， 虽 然 数 据 类 型 为 字 符 串 ， 但 因 此 常 见 的 文 件 类 型 是 有 限 的 ， 因 此 可 以 看 成 是 枚 举 类 型 ， 在 聚 类 算 法 中 则 称 为 标 称 变 量 。 在 进 行 距 离 计 算 时 可 以 按 照 聚 类 算 法 中 对 于 此 类 数 据 类 型 的 标 准 处 理 方 法 进 行 处 理 ， 即 其 距 离 只 是 一 个 二 值 函 数 ： 取 值 相 同 则 距 离 为 0； 否 则 距 离 为 1。 但 考 虑 到 文 件 扩 展 名 是 有 实 际 含 义 的 ， 而 且 很 多 时 候 这 些 不 同 的 扩 展 名 之 间 还 有 着 丰 富 的 联 系 ， 因 此 我 们 能 够 将 其 处 理 的 更 加 精 确 。 一 般 的 ， 我 们 可 以 按 照 文 件 的 扩 展 名 对 文 件 类 型 进 行 分 类 。 比 如 可 以 将 文 件 分 成 ： 程 序 、 图 片 、 音 乐 、 影 视 、 源 码 等 类 别 。 在 每 个 类 别 内 部 ， 可 能 又 有 更 深 的 层 次 ， 比 如 源 码 可 能 又 分 为 c/c+源 码 ， java 源 码 等 ， 而 c/c+源 码 又 可 以 进 一 步 分 为 头 文 件 和 实 现 文 件 等 这 样 就 形 成 了 一 棵 树 。 不 过 要 注 意 的 是 ， 这 棵 树 不 是 平 衡 的 ， 某 些 叶 节 点 可 能 比 较 深 ， 另 外 一 些 可 能 比 较 浅 。 为 了 形 成 这 棵 树 ， 我 们 还 需 要 说 明 如 下 。 首 先 ， 我 们 假 设 每 种 扩 展 名 只 对 应 于 树 中 的 一 个 节 点 ； 其 次 ， 我 们 设 置 一 个 根 节 点 ， 根 节 点 本 身 不 包 含 如 何 任 何 文 件 类 型 ； 再 有 ， 对 于 没 有 扩 展 名 的 文 件 ， 我 们 为 其 赋 予 一 个 特 殊 的 值 ， 并 且 直 接 位 于 根 节 点 之 下 ； 对 于 不 能 识 别 的 扩 展 名 我 们 也 做 同 样 处 理 。 这 样 ， 最 后 形 成 了 一 棵 类 似 下 图 的 树 ： 33 rotprogamvideomusicpicturesourceother real formt .avi.rm.rmvb c/+ langue .jav.himplentaio .c .cp 图 5-2 文件扩展名属性距离计算 这 样 ， 计 算 任 意 两 个 文 件 条 目 类 型 属 性 的 距 离 演 变 成 了 计 算 树 中 任 意 两 个 叶 节 点 之 间 的 关 系 。 对 于 树 中 任 意 两 个 叶 节 点 的 距 离 ， 则 表 示 为 其 相 似 程 度 的 倒 数 。 而 相 似 程 度 的 计 算 ， 可 以 按 照 如 下 算 法 。 树 中 每 个 节 点 均 存 在 一 条 从 根 节 点 到 达 它 所 在 位 置 的 唯 一 路 径 p。 两 个 节 点 的 相 似 程 度 可 以 表 示 为 它 们 各 自 路 径 p 中 公 共 节 点 的 个 数 的 函 数 。 在 实 现 上 ， 我 们 选 取 如 下 的 函 数 ： 假 设 需 要 计 算 两 个 ext 值 分 别 为 e1 和 e2 的 点 xi、 xj 在 此 属 性 上 的 距 离 。 设 e1 对 应 的 路 径 为 p1， e2 对 应 的 路 径 为 p2。 p1 和 p2 的 公 共 节 点 个 数 为 k（ 根 节 点 除 外 ） ， 则 我 们 取 ：2,21()ijkdx 34 5.2.2.3 size 属性距离的计算方法 size 属 性 表 示 文 件 条 目 的 文 件 大 小 ， 以 字 节 为 单 位 ， 数 据 类 型 为 整 数 。 由 于 文 件 大 小 的 取 值 范 围 跨 度 很 大 ， 一 般 能 够 从 几 十 字 节 到 几 十 亿 字 节 ， 因 此 不 适 合 按 照 一 般 区 间 标 度 变 量 的 方 法 来 计 算 ， 可 以 按 照 比 例 标 度 型 变 量 来 处 理 。 首 先 对 size 的 值 取 对 数 ：,3,3log()iiyx 不 过 在 实 际 应 用 中 要 注 意 的 是 ， 因 为 size 的 取 值 范 围 是 非 负 整 数 ， 可 能 取 0， 因 此 不 能 直 接 取 log， 可 以 考 虑 首 先 将 x 1 再 取 log。,3,3l(1)iiyx 然 后 将 yi3 转 化 为 对 应 的 z-score 值 zi3,imz s 其 中 )31,32,3n (yyn, 3|)ns m 进 行 标 准 化 处 理 之 后 ， 再 求 二 者 之 差 ： 3,3,3,3()ijijdxz 5.2.2.4 date 属性距离的计算方法 date 属 性 表 示 文 件 的 最 后 修 改 日 期 ， 前 面 已 经 说 过 ， 我 们 将 原 来 的 字 符 串 格 式 统 一 转 化 为 整 数 ， 比 如 按 照 距 离 公 元 元 年 元 旦 的 日 期 数 。 对 于 整 数 ， 属 于 区 间 标 度 变 量 。 为 了 更 好 的 计 算 各 个 项 目 该 属 性 之 间 的 距 离 ， 我 们 并 不 直 接 计 算 各 个 条 目 的 差 ， 而 是 先 对 其 进 行 标 准 化 处 理 。 将 xi4 转 化 为 对 应 的 z-score 值 zi4,4,iixmz s 35 其中 )41,42,4nm (xxn, ,4|)nsm 进行标准化处理之后，再求二者之差： 44,4,4(,)ijijdxz 5.2.2.5 site 属性距离的计算方法 由 于 在 实 际 文 件 共 享 系 统 中 ， site 值 最 常 见 的 情 况 就 是 ip 地 址 ， 而 两 个 ip 地 址 之 间 的 距 离 的 比 较 是 没 有 实 际 意 义 的 ， 因 此 我 们 忽 略 两 个 site 属 性 的 之 间 的 距 离 ， 或 者 可 以 表 示 为 ：5,5()0ijdx 5.2.2.6 path 属性距离的计算方法 path 表 示 文 件 从 根 目 录 开 始 到 其 节 点 所 经 过 的 路 径 。 其 重 要 特 点 就 是 路 径 是 分 段 的 ， 是 由 多 个 字 符 串 连 接 而 成 的 。 比 如 路 径 ： /resource/software/tools/network/ 可 以 看 成 是 由 分 段 的 子 字 符 串 resource， software， tools 和 network 构 成 的 。 在 对 path 进 行 比 较 的 时 候 ， 我 们 将 每 个 路 径 拆 分 成 多 个 子 字 符 串 ， 然 后 比 较 其 中 公 共 子 字 符 串 的 个 数 占 全 部 子 字 符 串 的 比 例 。6,6()comijijsdx 公 式 中 si 和 sj 分 别 表 示 xi 和 xj 的 path 属 性 的 分 段 的 个 数 ， scom 为 公 共 子 字 符 串 的 个 数 。 5.2.3 对用户点击记录进行聚类 在 本 体 系 中 需 要 对 用 户 的 点 击 日 志 进 行 聚 类 ， 以 便 能 够 得 到 这 k 个 不 同 的 用 户 查 询 意 图 。 聚 类 常 用 的 方 法 有 partitioning 方 法 ， hierarchical 方 法 和 density-based 方 法 。 根 据 我 们 的 具 体 情 况 ， 这 里 选 用 自 底 向 上 的 hierarchical 方 法 。 36 对 本 方 法 的 图 示 说 明 如 下 ： ab cde a,bstep 0 step 1 step 2 step 3 step 4d,e c,dea,bc,deaglomerative(agnes) 图 5-3 聚类示意图 假 设 共 有 5 个 对 象 a,b,c,d,e， 我 们 将 其 根 据 彼 此 的 相 关 程 度 进 行 聚 类 。 首 先 ， 将 每 个 待 聚 类 的 元 素 独 立 划 分 为 一 个 自 己 的 类 别 ， 如 果 有 n 个 元 素 ， 则 开 始 时 共 有 n 类 。 然 后 将 距 离 最 近 的 两 个 元 素 归 为 一 类 ， 此 时 有 n-1 类 ； 此 后 再 将 距 离 次 近 的 归 为 一 类 ， 类 别 共 n-2 类 ； 如 此 不 断 重 复 如 果 没 有 结 束 标 志 ， 则 最 终 将 会 把 所 有 类 别 都 归 为 一 类 。 所 以 必 须 要 设 置 结 束 标 志 。 这 其 中 有 几 点 要 说 明 ： 5.2.3.1 结束标志的设定 结 束 标 志 可 以 从 几 个 方 面 来 综 合 考 虑 。 首 先 是 距 离 因 素 ， 设 定 当 距 离 最 近 的 两 个 类 的 距 离 大 于 某 个 类 别 间 的 距 离 阀 值 d 时 不 再 进 行 合 并 操 作 ， 设 置 距 离 标 志 d 可 以 防 止 最 后 生 成 的 类 别 过 少 。 另 外 由 规 律 2 可 知 相 同 的 查 询 串 通 常 只 表 示 很 少 的 查 询 意 图 ， 因 此 可 以 设 定 一 个 最 大 类 别 数 g， 这 个 表 示 可 以 防 止 最 后 生 成 的 类 别 数 过 多 。 通 过 这 两 个 结 束 标 志 的 综 合 运 用 ， 可 以 使 最 终 的 类 别 数 量 控 制 在 较 理 想 的 范 围 中 。 5.2.3.2 具有多个元素的类别之间距离的计算 当 类 别 包 含 多 个 元 素 时 ， 计 算 它 们 之 间 的 距 离 有 三 种 不 同 的 方 法 ： 计 算 距 离 最 近 的 两 点 之 间 的 距 离 、 最 远 的 两 点 之 间 的 距 离 、 或 者 用 中 心 点 来 计 算 距 离 。 我 们 这 里 选 用 中 心 点 来 计 算 二 者 的 距 离 。 这 个 中 心 点 可 能 是 类 别 中 真 实 存 在 的 一 个 元 素 ， 37 但 也 可 能 是 一 个 并 不 真 正 包 含 的 虚 拟 的 元 素 。 5.2.3.3 孤立点的处理 事 实 上 ， 一 些 查 询 串 可 能 会 对 应 一 两 个 或 很 少 的 孤 立 查 询 记 录 ， 这 些 查 询 记 录 和 其 余 大 量 的 查 询 记 录 的 相 似 度 很 低 。 通 过 人 工 查 看 的 方 法 ， 我 们 发 现 很 多 这 些 孤 立 查 询 记 录 其 实 都 是 看 上 去 不 太 正 常 的 记 录 ， 比 如 对 于 一 些 大 小 为 0 的 文 件 进 行 下 载 ， 或 者 下 载 一 些 快 捷 方 式 文 件 等 。 我 们 认 为 这 些 孤 立 点 是 因 为 用 户 不 小 心 或 不 了 解 所 致 。 而 这 些 文 件 条 目 实 际 上 并 不 应 该 被 下 载 ， 而 应 该 被 抛 弃 。 因 此 我 们 需 要 对 这 些 孤 立 点 进 行 丢 弃 。 5.2.3.4 训练集的生成 由 于 在 进 行 完 聚 类 后 我 们 会 对 查 询 再 进 行 分 类 ， 因 此 我 们 考 虑 利 用 聚 类 中 的 文 件 条 目 作 为 分 类 时 的 训 练 集 。 在 聚 类 完 成 后 我 们 将 保 留 每 个 查 询 串 的 每 个 类 别 足 够 的 文 件 条 目 。 5.2.4 对查询结果集合进行分类 常 用 的 分 类 算 法 有 k nearest neighbor(knn), nave bayes, 还 有 support vector machines 等 。 我 们 采 用 knn 算 法 。 其 具 体 步 骤 为 ： 首 先 需 要 有 一 个 训 练 集 。 对 于 每 个 可 能 的 类 别 ， 各 自 有 一 些 属 于 该 类 别 的 对 象 。 给 定 一 个 待 分 类 的 对 象 ， 系 统 在 训 练 集 中 查 找 与 其 最 相 似 的 k 个 对 象 (称 为 邻 居 )， 并 根 据 这 些 邻 居 所 属 的 类 别 情 况 来 给 该 对 象 的 候 选 类 别 评 分 ， 最 后 按 照 分 值 来 确 定 待 分 类 对 象 的 类 别 。 38 第 6章 系 统 实 现 与 评 测 6.1 系 统 设 计 体 系 结 构 图 实 际 系 统 的 体 系 结 构 图 如 下 。 考 虑 到 一 些 实 现 问 题 ， 和 上 一 章 的 系 统 模 型 略 有 区 别 。 index part clustering part colection part clicklog datbse traing set dtbas clicklog serv clustering query q normal index syst items categorization filter categoris click log items traing set click log 图 6-1 体系结构图 下 面 我 们 来 详 细 介 绍 此 系 统 设 计 。 6.1.1 用户行为收集部分 collection part 部 分 为 用 户 点 击 记 录 收 集 部 分 ， 是 实 时 运 行 的 。 在 用 户 进 行 查 询 后 ， 文 件 检 索 系 统 返 回 包 含 查 询 串 的 结 果 。 用 户 从 中 选 取 自 己 认 为 正 确 的 文 件 条 目 。 用 户 的 选 取 操 作 就 是 一 次 鼠 标 的 点 击 操 作 。 这 个 点 击 动 作 自 动 触 发 到 我 们 的 后 台 cgi 程 序 ， 程 序 先 将 用 户 的 下 载 请 求 转 向 到 真 正 的 下 载 地 址 ， 后 台 再 发 送 一 个 记 录 点 击 操 作 的 服 务 请 求 。 该 服 务 请 求 由 clicklog server 接 收 ， 并 记 录 到 clicklog database 中 。 我 们 称 用 户 的 每 次 点 击 对 应 的 文 件 条 目 为 39 clicklog。 经 过 这 样 反 复 多 次 后 ， clicklog database 中 记 录 了 大 量 的 clicklog， 每 个 clicklog 包 含 一 个 查 询 串 和 对 应 的 文 件 条 目 item。 6.1.2 聚类部分 此 部 分 为 聚 类 操 作 部 分 ， 每 隔 一 段 时 间 运 行 一 次 。 在 实 际 系 统 中 可 以 根 据 用 户 数 量 来 设 定 为 每 小 时 或 每 天 一 次 。 这 部 分 首 先 从 clicklog database 中 读 取 全 部 的 clicklog 条 目 ， 然 后 对 每 个 查 询 串 依 次 进 行 处 理 。 取 出 每 个 查 询 串 对 应 的 clicklog 记 录 ， 进 行 聚 类 ， 聚 类 后 得 到 k 个 类 别 。 如 前 文 所 述 ， 其 中 可 能 存 在 一 些 孤 立 点 ， 然 后 按 照 标 准 对 这 些 孤 立 点 进 行 考 察 ， 需 要 的 话 要 抛 弃 掉 其 对 应 的 孤 立 类 别 。 聚 类 操 作 完 成 后 ， 将 聚 类 的 结 果 存 入 training set database 中 。 至 此 ， 我 们 就 得 到 了 实 现 免 用 户 干 预 的 、 基 于 反 馈 信 息 的 检 索 系 统 所 需 要 的 反 馈 数 据 。 6.1.3 索引部分 完 成 了 上 面 两 个 部 分 的 工 作 ， 就 可 以 进 行 真 正 的 反 馈 了 。 对 于 用 户 的 查 询 串 q， 首 先 使 用 常 规 检 索 系 统 进 行 检 索 ， 就 可 得 到 一 个 文 件 条 目 item 的 集 合 。 然 后 在 training set database 中 取 出 对 应 于 查 询 串 q 的 k 个 类 别 的 训 练 集 。 利 用 这 些 训 练 集 条 目 为 刚 刚 通 过 常 规 查 询 得 到 的 item 集 合 进 行 分 类 。 此 处 我 们 限 定 每 个 文 件 条 目 至 多 属 于 1 个 类 别 。 分 类 后 可 能 得 到 k+1 个 类 别 （ 某 些 item 可 能 不 属 于 任 何 类 别 ） ， 以 及 每 个 条 目 和 其 所 属 类 别 的 相 似 程 度 。 利 用 分 类 的 类 别 和 相 似 度 ， 系 统 可 以 重 新 根 据 此 信 息 进 行 输 出 。 对 于 那 些 不 属 于 任 何 类 别 的 文 件 条 目 ， 通 常 也 是 用 户 所 不 太 关 心 的 结 果 ， 可 以 选 择 抛 弃 或 排 在 结 果 页 面 的 最 后 。 6.2 其 它 实 现 中 的