基于多項式回歸的預取技術的研究

摘 要：Web預取技術和緩存技術對緩解訪問延遲有一定的作用，但各有利弊。這里將預取技術與語義緩存技術相結合，對用戶查詢的訪問頻率進行實時監測，并通過多項式回歸算法對用戶的下一周期訪問概率進行預測。采用基于多項式回歸預取技術構建的預測模型，可以實現動態在線預測，既可避免興趣漂移引起的預取不確定性，又可以減少歷史信息的存儲量，科學合理地解決Web訪問延遲的問題。

關鍵詞：多項式回歸； 預取技術； 緩存技術； 訪問延遲

中圖分類號：TN91134； TP311 文獻標識碼：A 文章編號：1004373X（2012）22008403

目前互聯網已經成為人們生活中不可缺少的一部分，由于搜素引擎是獲得信息的主要手段，這使得網絡負載增大，不斷出現網絡擁塞的現象。如何減少Web訪問延遲，以提高訪問Web頁面的速度是學者們關心的問題。目前緩解網絡延遲的有效手段主要有Web緩存技術和預取技術［1］。

Web緩存技術是根據Web訪問的時間局部性原理，將訪問過的內容以副本的形式存放在Cache中，待該內容再次被訪問時，則由Cache中保留的副本提供。但是對于未曾訪問過的內容卻無法緩沖，即用戶的興趣漂移可以引起不確定性， 因此Web緩存技術具有一定的局限性。隨著WWW上動態內容的增加以及個性化服務需求的加巨，利用緩存技術來改善網絡性能已不再顯著［1］，由此可見，減少Web訪問延遲只利用Web緩存技術已經遠遠不夠。

1 預取技術

1.1 預取技術概述

預取技術是根據時間局部性向空間局部性進行擴展的原理，是在服務器處理用戶請求時，利用預取算法預測用戶接下來可能訪問的內容，并利用網絡空閑時間段將預測內容取回至緩存內［2］。因此這種技術可以擬補緩存技術的不足，可以較好地減少網絡的訪問延遲，提高響應速度［3］。

1.2 常用預取技術

目前比較流行的預取算法主要有基于流行度的算法、基于交互的算法、基于訪問概率的算法和基于數據挖掘的算法四類。常用的預取模型有基于PPM預取模型、基于Markov鏈預取模型和基于數據挖掘的預取模型等。由于預取算法主要是利用用戶訪問的歷史信息來進行預測的，所以要保留大量的歷史信息。正是由于這些特點，使得目前的預取技術有一定的不足之處，例如網絡用戶的興趣漂移現象，導致歷史訪問數據不能準確表達用戶的最新興趣方向；為了使預取結果準確、命中率高，歷史訪問數據就必須有足夠的空間和時間進行采集；對于龐大的數據預取算法的實施需要一定的系統開銷；算法得到的預取頁面數量很多，而滿足用戶即將訪問需求的卻數量很少，所以根據歷史訪問信息的預取技術并不能很好地、準確地、迅速地使訪問者得到查詢結果，充分達到減少網絡的訪問延遲的目標。

1.3 性能評價標準

衡量Web預取性能的度量最主要的有兩個，即準確率和查全率。若不考慮緩存、網絡或時間等物理限制的情況，正確預測對象數目和總預測數目比值即為準確率，也可以稱之為正確率或命中率；正確預測對象數目和用戶請求對象數目的比值即為查全率，也可以稱之為有用性［4］。

假設有N個請求序列，由預測模型產生共P個預測結果，其中P+個預測是正確的，則準確率為 P+/P；查全率［5］為P+/N。

這兩種性能評價標準主要側重于預測效率和有效性兩個方面的性能評價。準確率主要用來衡量預測算法正確性，而查全率主要用來衡量預測模型的適用性［6］。研究一個科學合理的Web預取技術，需要依據這兩個重要的評價標準。

2 關鍵技術實現

2.1 技術原理

預取技術是對Web緩存技術的有力補充，其目的是使有限的網絡資源得到合理的利用［7］。目前已經存在利用隨機Petri網使Web緩存和預取技術相結合的技術［8］，而且證明了緩存與預取結合技術比單純的緩存技術或預取技術更能有效減少平均延遲、提高服務器的吞吐量［910］。緩存技術是數據庫優化方法之一，尤其語義緩存技術很好地彌補了頁緩存和元組緩存對支持關系數據庫方面不夠完美的缺陷，語義緩存是將用戶的查詢信息及相應結果保存到緩存中，重用緩存數據主要是利用查詢之間語義的相關性，根據與其對應的語義描述來進行。

2.2 基本思想

多項式回歸預取技術基本思想是把Web預取技術與語義緩存技術相結合，根據用戶訪問興趣度來進行預取，主要是通過建立多項式回歸模型對用戶訪問頻率進行預測，既而將用戶興趣度高的內容取回至本地緩存中供用戶訪問。

2.3 預測模型的建立

首先設定統計周期，一般以24 h為一個統計周期。對各周期的各條語義緩存項訪問概率進行統計，利用最近N個周期內各語義緩存項的訪問概率來建立多項式回歸模型，在緩存中存儲語義緩存項{K，P，T，Z}i最近N個周期的訪問頻率pij（j=1～N），及其在下一周期的訪問概率預測值POP。語義緩存項中K為用戶提交的查詢關鍵字集合，p為訪問概率預測值，t為該查詢語句有效期，z為查詢語句是否被預取。

假設某一訪問周期內，Count為語義緩存項總訪問數量， Counti為每條語義緩存項的訪問數量，由此可定義第i個訪問周期內各語義緩存項訪問概率為pi，pi為Counti與Count的比值。

2.4 訪問概率值預測

回歸預測法常用在市場預測方面。這種預測方法是把對因果關系的影響因素作為自變量，把預測對象作為因變量，用數學方法找出自變量與因變量之間近似的函數關系表達，利用樣本數據對模型參數進行估計。其中具有多個自變量的稱為多元回歸分析。不管因變量與自變量存在何種關系，采用多項式回歸均可以接近某一函數。

計算緩存中各語義緩存項在下一周期的訪問概率預測值POP，首先建立多項式回歸模型，利用已經統計的N個訪問周期的概率值對下一個周期的訪問概率進行預測。假設在n個試驗點x1，x2，…，xn獲得y的n個觀測值，建立模型如式（1）所示：yi = β0 + β1xi + β2x2i+…+ βpxpi + ei

i=1，2，…，n

（1） 假設誤差項為獨立、N（0，δ2）分布的，模型（1）用最小二乘法對參數進行估計得到式（2）：fi＝0+1xN+1+...+pxpN+1

j=0，1，…p

（2）式中：j為βj的無偏估計；f即為某一語義緩存項第N+1周期訪問概率預測值。

2.5 預取隊列的生成

若第N+1周期預測的訪問概率POP大于閾值α，則可根據數據存儲標識、數據有效期標識來判斷哪些語義緩存項需要預取，從而生成預取隊列。

若數據有效期在有效范圍內，如果語義緩存項是存儲在內緩存的有效語義緩存區內，且結果集存儲在外緩存有效數據區，則不需要重新預取；如果語義緩存項是存儲在外緩存的臨時語義緩存區內，且結果集存儲在臨時數據區，則將語義緩存項移動至內緩存有效語義緩存項存儲區內，結果集移動至外緩存有效數據區內。

若數據有效期不在有效范圍內，且語義緩存項滿足預取條件，如果數據已經失效則需要重新預取，即將語義緩存項填加至預取隊列中；如果數據保存在臨時數據區且數據失效則需要重新預取，即將語義緩存項填加至預取隊列表中。

2.6 預取技術的實施

當用戶提交查詢請求時，同時在內緩存和外緩存中進行查詢匹配，若匹配結果為相交匹配，根據情況從有效或臨時數據區或是Web數據庫得到的查詢結果合并后返回給用戶，并把生成的新語義緩存項及其結果集保存到臨時數據區。當外緩存的臨時語義緩存區滿時，則需要進行替換。統計各語義緩存項在各周期的訪問量，建立預測模型并采用多項式回歸預測算法，預測下一周期各語義緩存項訪問概率并生成預取隊列，并訪問Web數據庫，由此獲取的結果集保存至外緩存有效數據區內。

3 結 語

在Web數據集成環境下采用基于多項式回歸預取技術，根據用戶訪問的興趣度來進行預取，可以實現動態在線預測。對網絡銷售管理系統進行商品查詢，從查詢響應時間和預取準確率兩方面進行測試。實驗表明基于多項式的預取技術，可有效提高用戶查詢響應速度，減少網絡延遲，在性能評價的準確率和查全率兩個方面達到了理想的標準值。

參 考 文 獻

［1］ XU Huanqing， WANG Yongcheng.A Web prefetching model based on analyzing user access pattern［J］.Journal of Software， 2003， 14（6）： 11421147.

［2］ 王世克，吳集，金士堯．Web預取模型分析＼[J＼]．微機發展，2005，15（8）：13.

［3］ NANOPOULO S A， KAT SARO S D， MANOLOPOULOS Y. A data mining algorithm for generalized Web prefetching ＼[J＼]. IEEE Trans. on Knowledge and Data Engineering， 2003， 15（5）： 11551169.

［4］ CHRISTOS B. Predictive prefetching on the Web and its potential impact in the wide area ＼[J＼]. World Wide Web， 2004， 7（2）： 143179.

［5］ 韓英杰，石磊，劉楊.Web 預取性能指標準確率與查全率的關系＼[J＼].計算機工程，2010，36（3）：6162.

［6］ SHI Lei， HAN Yingjie， DING Xiaoguang， et al. An SPNbased integrated model for Web prefetching and caching ＼[J＼]. Journal of Computer Science and Technology， 2006， 21（4）： 482489.

［7］ XU Baowen ， ZHANG Weifeng. Applying data mining to Web prefetching ＼[J＼]. Chinese Journal of Computers， 2001， 24（4）： 430436.

［8］ SHI L， HAN Y， DING X， et al. An SPN based integrated model for Web prefetching and caching ＼[J＼]. Journal of Computer Science and Technology， 2006， 21（4）： 482489.

［9］ 班志杰，古志民，金瑜.Web預取技術綜述＼[J＼].計算機研究與發展，2009，46（2）：202210.

［10］ DOMENECH J， GIL J A， SAHUQUILLO J， et al. Web prefetching performance metrics： a survey ＼[J＼]. Performance Evaluation， 2006， 63（9）： 9881004.

作者簡介： 李春潔 女，1977年出生，黑龍江佳木斯人，講師，在讀碩士研究生。研究方向為數據庫與知識庫。

王 銳 女，1974年出生，黑龍江佳木斯人，副教授，碩士。研究方向為數據庫應用。

李美珊 女，1982年出生，黑龍江七臺河人，講師，碩士。研究方向為軟件工程。