RANSAC 算法在網(wǎng)頁(yè)關(guān)鍵信息智能篩選中的應(yīng)用研究

曾光輝 何 波

（廣州工程技術(shù)職業(yè)學(xué)院 信息工程學(xué)院，廣東 廣州510900）

RANSAC 算法，其全稱是RANdom SAmple Consensus，指的是隨機(jī)抽樣一致性，是模型參數(shù)估計(jì)算法的一種[1]。通常情況下，可以在一組數(shù)據(jù)中通過數(shù)學(xué)模型的計(jì)算，提出異常數(shù)據(jù)，獲得有效樣本數(shù)據(jù)。在應(yīng)用RANSAC 算法的過程中，準(zhǔn)確來說是一個(gè)迭代的、不斷尋求更優(yōu)的模型參數(shù)的過程[2]。計(jì)算過程中主要包含三個(gè)參數(shù)，分別是誤差容忍度、迭代次數(shù)和一致集大小。這個(gè)過程中，決定著模型參數(shù)的精度是迭代的次數(shù)，而樣本一致集大小，也代表著模型參數(shù)精確程度。

大數(shù)據(jù)包含了各種類型的原始信息，例如文本信息、圖像信息等[3]。但是，隨著信息的快速發(fā)展。面對(duì)著浩瀚無際的信息海，人們?nèi)绾慰焖佾@取所需信息成為一個(gè)難題。隨著信息迷航、負(fù)載的不斷發(fā)生，網(wǎng)頁(yè)關(guān)鍵信息智能篩選，開始成為一項(xiàng)受到關(guān)注的技術(shù)。本文通過對(duì)RANSAC 算法為核心的研究，將其應(yīng)用于網(wǎng)頁(yè)關(guān)鍵信息智能篩選中，有利于信息智能篩選的更快發(fā)展。

1 基于RANSAC 算法網(wǎng)頁(yè)關(guān)鍵信息智能篩選方法設(shè)計(jì)

1.1 網(wǎng)站信息采集與處理

想要實(shí)現(xiàn)基于RANSAC 算法的，網(wǎng)頁(yè)關(guān)鍵信息智能篩選。那么前期需要完成一個(gè)工作，就是對(duì)網(wǎng)站信息的采集與處理，以此作為接下來信息篩選的基礎(chǔ)。首先，對(duì)網(wǎng)站數(shù)據(jù)進(jìn)行采集抓取。

對(duì)于網(wǎng)站中包含數(shù)據(jù)，利用初始隊(duì)列中的URL 地址，取得網(wǎng)頁(yè)內(nèi)容信息后，將其返回給爬蟲。通過獲取爬蟲分析，將需要進(jìn)一步抓取的數(shù)據(jù)放回鏈接。將需要保存的進(jìn)行數(shù)據(jù)清洗。將網(wǎng)頁(yè)解析過后，將網(wǎng)頁(yè)信息提取出來，保存至數(shù)據(jù)庫(kù)。數(shù)據(jù)的存儲(chǔ)采用MySQL 數(shù)據(jù)庫(kù)，將處理后的數(shù)據(jù)實(shí)現(xiàn)結(jié)構(gòu)化存儲(chǔ)。在信息存儲(chǔ)過程中，可以采用文章標(biāo)題、發(fā)布時(shí)間、關(guān)鍵字等等作為定義存儲(chǔ)的文章。使得收集的信息，每一條可以進(jìn)行關(guān)鍵詞的自動(dòng)辨認(rèn)。

此外，利用機(jī)器學(xué)習(xí)算法，將收集存儲(chǔ)的信息，轉(zhuǎn)換為數(shù)值數(shù)據(jù)集。對(duì)于文本利用中文分詞技術(shù)，將文本內(nèi)容向字符串列表轉(zhuǎn)換。輔助之后的信息智能篩選工作。

1.2 基于RANSAC 算法提取網(wǎng)頁(yè)關(guān)鍵信息

完成網(wǎng)站信息的前期采集與處理后，就可以應(yīng)用RANSAC算法，進(jìn)行網(wǎng)頁(yè)關(guān)鍵信息智能篩選的設(shè)計(jì)。網(wǎng)頁(yè)的關(guān)鍵信息智能篩選，需要在數(shù)據(jù)庫(kù)中提取與用戶輸入的關(guān)鍵信息相匹配的網(wǎng)頁(yè)信息。獲取相關(guān)內(nèi)容后，對(duì)信息的特征點(diǎn)進(jìn)行匹配，所提取的特征點(diǎn)和用戶所需信息特征點(diǎn)匹配與否，需要通過兩個(gè)特征點(diǎn)之間的歐氏距離進(jìn)行判斷。將兩個(gè)特征點(diǎn)表示為A=｛x1,x2,…,xn},B=｛y1,y2,…,yn},因此，兩個(gè)特征點(diǎn)之間的歐氏距離，可以采用以下公式計(jì)算。

公式中，n 表示特征描述子維度，d 代表特征點(diǎn)之間歐氏距離。當(dāng)兩條信息進(jìn)行匹配時(shí)，在用戶輸入信息中進(jìn)行特征描述子選擇，以此為依據(jù)，計(jì)算第二條信息特征描述子，與第一條特征描述子之間的歐氏距離。并分析最小歐氏距離與次小歐氏距離之間的比值，當(dāng)比值小于閾值時(shí)，表示兩者之間匹配。一般情況下，閾值為0.6-0.8 之間。RANSAC 算法主要采用最小子樣本集，對(duì)網(wǎng)頁(yè)關(guān)鍵信息進(jìn)行估計(jì)的迭代算法，其具體計(jì)算流程如下：第一步，面向包含無數(shù)信息樣本的數(shù)據(jù)集U，在進(jìn)行信息篩選之前，以計(jì)算模型中，未知量的個(gè)數(shù)作為依據(jù)，確定算法計(jì)算過程中所需的最小數(shù)據(jù)個(gè)數(shù)，獲取樣本集。并且要保證樣本集中數(shù)據(jù)總量，大于采樣所需最小數(shù)據(jù)個(gè)數(shù)。第二步，最小樣本數(shù)確定后，將其從數(shù)據(jù)集中提取出來，使用該數(shù)據(jù)對(duì)模型進(jìn)行估計(jì)。第三步，面向其他未被提取樣本，計(jì)算其與模型之間的誤差，根據(jù)誤差與閾值之間的比較，確定其為內(nèi)點(diǎn)還是外點(diǎn)。第四步，計(jì)算數(shù)據(jù)元素的總個(gè)數(shù)。若模型正確，為了保證準(zhǔn)確性采用去除一部分外點(diǎn)后的更準(zhǔn)確的集合，否則，循環(huán)一到三步，直到選取合適的最小樣本集合。上述迭代流程中，RANSAC 算法的取樣次數(shù)，取決于隨機(jī)選取的數(shù)據(jù)點(diǎn)是否為內(nèi)點(diǎn)。

為了快速篩選網(wǎng)頁(yè)關(guān)鍵信息，內(nèi)點(diǎn)比例少于30%的情況很少出現(xiàn)。大于30%后，迭代次數(shù)與內(nèi)點(diǎn)比例呈現(xiàn)反比例增長(zhǎng)。最后，通過RANSAC 算法的迭代，將提取的網(wǎng)頁(yè)關(guān)鍵信息與用戶所需信息進(jìn)行匹配，實(shí)現(xiàn)網(wǎng)頁(yè)關(guān)鍵信息篩選。

1.3 檢測(cè)篩選信息

網(wǎng)頁(yè)的關(guān)鍵信息篩選，定然會(huì)有一小部分的誤差存在。因此，在完成信息篩選后，可以再對(duì)RANSAC 算法進(jìn)行改進(jìn)，完成篩選信息的再檢測(cè)。文中關(guān)于篩選信息的檢測(cè)過程，同樣需要進(jìn)行M 次樣本選取，經(jīng)過檢測(cè)沒有被剔除的是正確對(duì)應(yīng)信息，這種信息所占的百分比，可以用通過率來表示。倘若將Pf設(shè)為樣本的通過率。則通過該算法獲取的關(guān)鍵信息篩選正確概率可以用（1-ε）mPf來表示。這個(gè)過程中，一部分篩選信息被過濾掉，所以產(chǎn)生的結(jié)果數(shù)量稍有降低，準(zhǔn)確度卻大幅提升。篩選信息在檢測(cè)中是否通過，需要進(jìn)行方法設(shè)計(jì)。首先選擇d 個(gè)正確數(shù)據(jù)作為固定，然后對(duì)篩選信息進(jìn)行對(duì)比，當(dāng)有c 個(gè)及以上數(shù)據(jù)通過，證明該信息無誤。

1.4 展示網(wǎng)頁(yè)關(guān)鍵信息智能篩選結(jié)果

以RANSAC 算法為基礎(chǔ)，完成網(wǎng)頁(yè)關(guān)鍵信息的篩選，并且確定篩選信息無誤后，需要對(duì)這些信息進(jìn)行分類顯示，完成整體的網(wǎng)頁(yè)關(guān)鍵信息智能篩選流程。根據(jù)一些算法構(gòu)建分類器，對(duì)篩選出來的信息實(shí)現(xiàn)精確歸類。分類器對(duì)訓(xùn)練樣本集進(jìn)行訓(xùn)練，調(diào)整樣本權(quán)重。隨著懸鏈次數(shù)的增加，分類錯(cuò)誤樣本權(quán)重逐漸升高，根據(jù)設(shè)定的權(quán)重值，進(jìn)行分類器分類錯(cuò)誤率的計(jì)算。以權(quán)重值為依據(jù)，對(duì)權(quán)重向量進(jìn)行更改，降低正確分類的樣本權(quán)重，提高錯(cuò)分樣本的權(quán)重。權(quán)值公式如下所示。

公式（2）中，a 表示權(quán)重值，D 表示向量，xi表示x 中第i 個(gè)元素，yi表示y 中第i 個(gè)元素。將計(jì)算結(jié)果重新代入，直至訓(xùn)練錯(cuò)誤率為0。篩選后的信息作為訓(xùn)練函數(shù)，進(jìn)行輸入。經(jīng)過訓(xùn)練，最終得到篩選器模型。之后，可以利用此篩選器模型，對(duì)篩選信息進(jìn)行分類。在這個(gè)過程中，為了最大程度保證模型分類結(jié)果準(zhǔn)確，可以通過設(shè)置不同數(shù)量的分類器，進(jìn)行分類精度的測(cè)試。

通過測(cè)試，發(fā)現(xiàn)該模型中最佳分類器數(shù)量為8 個(gè)，此時(shí)分類精度保持在98.5%左右。通過對(duì)網(wǎng)頁(yè)關(guān)鍵信息篩選結(jié)果的準(zhǔn)確分類，將最終信息篩選結(jié)果向用戶進(jìn)行展示，實(shí)現(xiàn)網(wǎng)頁(yè)關(guān)鍵信息智能篩選。

2 實(shí)驗(yàn)論證分析

為了保證本文提出信息智能篩選方法，在實(shí)際應(yīng)用中具有良好的效果，特進(jìn)行實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。根據(jù)統(tǒng)計(jì)數(shù)據(jù)顯示，網(wǎng)民訪問頻率最高的是新浪、搜狐、人民網(wǎng)、新華網(wǎng)四大網(wǎng)站，實(shí)驗(yàn)選取四大網(wǎng)站中的800 篇文章。這些文章對(duì)應(yīng)四種分類，分別是娛樂、教育、財(cái)經(jīng)、體育，每種分類選擇200 篇文章，將其綜合整理。以體育、財(cái)經(jīng)兩種分類，作為網(wǎng)頁(yè)關(guān)鍵信息進(jìn)行搜索，分析智能篩選結(jié)果。由于在信息檢索領(lǐng)域，面對(duì)信息智能篩選性能時(shí)，常用查準(zhǔn)率與查全率進(jìn)行判斷。其中查準(zhǔn)率指的是篩選的信息中心，正確信息所占比例。而查全率代表篩選結(jié)果中的正確信息，占實(shí)際所有滿足要求信息的比例。以本文提出方法為實(shí)驗(yàn)組，選取兩種傳統(tǒng)的信息智能篩選方法，作為對(duì)照組進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖1 所示。

根據(jù)圖1 我們可以發(fā)現(xiàn)，在三種網(wǎng)頁(yè)關(guān)鍵信息智能篩選方法中，文中所提出的應(yīng)用RANSAC 算法的智能篩選方法性能明顯更優(yōu)。在圖中，我們將[0,1]這個(gè)區(qū)間劃分為10 個(gè)等份。選擇每個(gè)邊界點(diǎn)值的查全率作為固定條件，計(jì)算相同查全率下，不同方法的信息查準(zhǔn)率對(duì)比。通過圖1，對(duì)體育與財(cái)經(jīng)兩個(gè)關(guān)鍵詞進(jìn)行信息篩選，三種方法的篩選結(jié)果顯示，查準(zhǔn)率都在隨著查全率的上升而下降。以體育為例，本文方法的查準(zhǔn)率從一開始的0.95，下降到了最后的0.76。兩種傳統(tǒng)方法也分別降到了0.64、0.50。顯而易見，本文方法相比傳統(tǒng)方法查準(zhǔn)率有所上升，財(cái)經(jīng)方面也與之相似。綜上所述，在網(wǎng)頁(yè)關(guān)鍵信息智能篩選中，RANSAC 算法的應(yīng)用，提升了信息智能篩選的查準(zhǔn)率。

圖1 實(shí)驗(yàn)論證結(jié)果曲線

結(jié)束語(yǔ)

本文以網(wǎng)頁(yè)關(guān)鍵信息智能篩選為重點(diǎn)，分析RANSAC 算法在信息篩選中的應(yīng)用。通過本文研究，明確了RANSAC 算法，在網(wǎng)頁(yè)關(guān)鍵信息智能篩選中，以此為基礎(chǔ)，設(shè)計(jì)信息智能篩選方法擁有較高的查準(zhǔn)率，可以加快網(wǎng)絡(luò)信息的發(fā)展，提升人們對(duì)于關(guān)鍵信息查找的速度。