BBS信息挖掘系統(tǒng)

1、BBS信息挖掘系統(tǒng)信息挖掘系統(tǒng)第21組朱嘉奇 劉丹星李希婷 田 楓主要內(nèi)容n系統(tǒng)概述n系統(tǒng)功能n關(guān)鍵技術(shù)n拓展與展望系統(tǒng)概述n北大未名BBS共有ID87375個(gè)，而這些用戶并不是孤立存在的，他們相互之間有聯(lián)系! (認(rèn)識(shí)?熟悉?好友?)n以這種“認(rèn)識(shí)關(guān)系”為基礎(chǔ)，構(gòu)建BBS虛擬社會(huì)的用戶關(guān)系網(wǎng)(有向帶權(quán)圖)n在此基礎(chǔ)上進(jìn)行各種分析挖掘，為BBS管理員和用戶提供更多的信息和方便。 系統(tǒng)功能n建立及更新關(guān)系圖n將ID分類 n查看兩個(gè)ID之間的最短路徑n查看某ID直接認(rèn)識(shí)(被認(rèn)識(shí))的IDn查看某ID間接認(rèn)識(shí)(被認(rèn)識(shí))的IDnTop 10(十大活躍ID)n演示圖關(guān)鍵技術(shù)n用戶間認(rèn)識(shí)程度信息的獲取抓取文集

2、抓取討論區(qū)n關(guān)系圖中邊的權(quán)值的計(jì)算n對(duì)關(guān)系圖的分析抓取文集n文集的留言簿是用戶間信息往來的主要場(chǎng)所之一,保留大量有價(jià)值信息.l留言簿常常有多個(gè)名字,不容易直接找到.l逐層分析每個(gè)目錄,尋找文章署名不是文集主人和guest的IDn連目也是一個(gè)重要的信息來源.l需要判斷連目是的確連向其他好友的文集,還是連向討論區(qū).抓取討論區(qū)n如果ID A回復(fù)了ID B的某篇文章,那么他們可能認(rèn)識(shí).且回復(fù)的文章數(shù)越多,他們 “認(rèn)識(shí)”的可能性越大! 對(duì)所有討論區(qū)的文章依次分析 對(duì)篇數(shù)大于1的文章提取所有“發(fā)信人”n間隔較長(zhǎng)時(shí)間的文章的回復(fù)通常都被刪掉.所以, 較早文章的文章數(shù)一般都是1. 利用這個(gè)特點(diǎn),對(duì)每個(gè)討論區(qū)進(jìn)

3、行分析時(shí),不需要一直找到第一篇文章。若發(fā)現(xiàn)當(dāng)前頁的所有文章的文章數(shù)都是1, 就不再對(duì)上一頁進(jìn)行分析。權(quán)值的計(jì)算n綜合兩個(gè)結(jié)果計(jì)算ID之間的認(rèn)識(shí)程度lID A在ID B的文集里留言的文章數(shù)lID A對(duì)ID B的文章進(jìn)行回復(fù)的總數(shù)n兩種信息的重要性不同!l文集中的信息比回復(fù)文章中的信息更重要,能更準(zhǔn)確的反映用戶間的關(guān)系!加權(quán)求和n方法l給文集中留言的文章數(shù)賦一個(gè)較大的權(quán)重l給進(jìn)行回復(fù)的文章數(shù)賦一個(gè)較小的權(quán)重n發(fā)現(xiàn) 留言次數(shù)分布在0,1000)之間 回復(fù)文章數(shù)分布在0,100)之間如果再給留言次數(shù)一個(gè)較大的權(quán)值，回復(fù)文章數(shù)就更加微不足道了！分布區(qū)間規(guī)格化n考慮造成上述問題的原因是分布區(qū)間的不一致n將

4、文集留言數(shù)與文章回復(fù)數(shù)映射到同一區(qū)間 或者放大文章回復(fù)數(shù)分布的區(qū)間 或者縮小文集留言數(shù)分布的區(qū)間相當(dāng)于給文章回復(fù)數(shù)一個(gè)較大的權(quán)值，給文集留言數(shù)一個(gè)較小的權(quán)值。與兩種信息的重要性不符！區(qū)間分段映射n不能簡(jiǎn)單的放大或縮小整個(gè)區(qū)間n把文集留言數(shù)和回復(fù)文章數(shù)分成四段，分段映射， 每個(gè)段分別對(duì)應(yīng)一種熟悉程度： 不認(rèn)識(shí)，認(rèn)識(shí)，熟悉，好友n用映射函數(shù)反映兩種信息的重要性的不同 映射函數(shù)圖020406080100141030100weight_re標(biāo)準(zhǔn)值映射函數(shù)圖020406080100129201000weight_corpus標(biāo)準(zhǔn)值分段映射函數(shù)（續(xù)）n閾值的選取 最后級(jí)別至少不低于各自判斷出的級(jí)別的較高值

5、 最后級(jí)別不高于各自判斷出的級(jí)別的較高值加1 max(c1,c2) c max(c1,c2)+1 20 40 80 100 不認(rèn)識(shí) 認(rèn)識(shí) 熟悉 好友 1 2 3 4 對(duì)關(guān)系圖的分析n將ID分類把關(guān)系圖看成無向圖 把關(guān)系圖中權(quán)值小于閾值的邊去掉，問題轉(zhuǎn)化為求圖中的連通分支的問題采取不嚴(yán)格的廣度優(yōu)先搜索的算法 兩個(gè)map結(jié)構(gòu)，map2包括所有已分好類的id，map1則只包括已分好類且以它為根節(jié)點(diǎn)的樹尚未遍歷的id 由于此分類過程需要時(shí)間很長(zhǎng)，故把結(jié)果都輸入到class數(shù)據(jù)庫表中 對(duì)關(guān)系圖的分析（續(xù)）nTop10 只需對(duì)每個(gè)id查詢數(shù)據(jù)庫表，計(jì)算與它之間的權(quán)值不小于相應(yīng)閾值的id個(gè)數(shù)，選出排在前10

6、位的id n某id間接認(rèn)識(shí)(被認(rèn)識(shí))的所有id 嚴(yán)格的廣度優(yōu)先搜索算法n兩個(gè)id之間的最短路徑拓展和展望n邊的權(quán)值的計(jì)算v發(fā)文和回復(fù)文章次數(shù) 文集中短時(shí)間的多次發(fā)文 討論區(qū)中對(duì)同一問題re多篇文章v分析re文內(nèi)容，確定不同的初始權(quán)值u改進(jìn)映射函數(shù)v映射區(qū)間的選取v非線性的映射函數(shù)拓展和展望（續(xù)）n分析算法的改進(jìn) 有針對(duì)性的比較快的算法，以滿足大數(shù)據(jù)量的要求 n對(duì)圖中隱藏信息的挖掘n通過對(duì)id的分類分析版面的性質(zhì) 一大類id經(jīng)常訪問的版面 幾大類id經(jīng)常訪問的版面 許多類id經(jīng)常訪問的版面 許多分散在不同類的id經(jīng)常訪問的版面 少數(shù)幾個(gè)分散在不同類的id經(jīng)常訪問的版面拓展和展望（續(xù)）n擴(kuò)展系統(tǒng)的適用范圍 v校園bbs：兩全其