博客數(shù)據(jù)的屬性拓撲分析

張　濤，李　慧，任宏雷(.燕山大學信息科學與工程學院，河北秦皇島066004; .唐山啟奧科技股份有限公司系統(tǒng)測試部，河北唐山063000)

博客數(shù)據(jù)的屬性拓撲分析

張濤1，*，李慧1，任宏雷2
(1.燕山大學信息科學與工程學院，河北秦皇島066004; 2.唐山啟奧科技股份有限公司系統(tǒng)測試部，河北唐山063000)

摘要:近些年博客逐漸呈現(xiàn)蓬勃發(fā)展趨勢，但由于零門檻和缺少監(jiān)管，博客信息斑駁繁雜，信息垃圾層出不窮。形式概念分析是數(shù)據(jù)分析與知識處理的有力工具，而屬性拓撲作為形式背景的新型的表示方法，在背景表示可視化和概念計算可視化方面尤其有效。本文在子拓撲并行計算形式概念的理論基礎上，加入一些條件約束，通過對博客數(shù)據(jù)的形式概念計算，對博主及其博客主題內(nèi)容的相關信息進行合理的整合和深層次的挖掘，有利于摒棄無用信息，為博客使用者迅速發(fā)現(xiàn)對自己有利和感興趣的博客內(nèi)容以及了解博客作者的相關信息提供了理論依據(jù)。

關鍵詞:形式概念分析;屬性拓撲;全路徑搜索;博客

0　引言

博客是以自由、開放和共享為文化特征，通過圖文音象等表現(xiàn)形式，圍繞個人網(wǎng)絡存在的五大功能，提供存取讀寫、組織溝通、評價交換等服務的一種社會化個人服務模式。它并不是純粹的技術創(chuàng)新，而是一種逐漸演變的網(wǎng)絡應用，一種形式的變化。博客的全民性，讓它的傳播方式成為所有人對所有人的傳播。然而，博客并不如表面般繁榮，當博客毫不掩飾地在大眾面前喧鬧的時候，接踵而來的問題使得博客亂了方寸。博客參與者的盲目性導致了博客行為過程中的迷茫與厭倦;由于進入的零門檻和缺少監(jiān)管，徹底顛覆互聯(lián)網(wǎng)既有模式的博客，變成了新的信息垃圾場。博客正遭受低俗膚淺成風、網(wǎng)絡侵權等因素的困擾。

作為數(shù)據(jù)分析與知識處理的有力工具，形式概念分析［1］以數(shù)學化的概念和概念層次為基礎，已經(jīng)應用在眾多領域，如數(shù)據(jù)挖掘［2-3］、網(wǎng)絡搜索［4-5］、軟件工程［6-7］、本體分析［8-9］等，并仍然具有很大的潛在應用價值。

屬性拓撲［10-12］作為一種新型的形式背景表示方法，可以有效地生成形式概念，本文在子拓撲計算形式概念［12］的基礎上，加入一些條件約束，通過對博客數(shù)據(jù)的形式概念計算，對博客信息資源進行了科學的整合和發(fā)掘，對斑駁繁雜的博客信息進行了“過濾”，為博客使用者迅速發(fā)現(xiàn)對自己有利和感興趣的博客內(nèi)容以及了解博客作者的相關信息提供了理論依據(jù)，有利于摒棄無用信息，可以促進博客文化的科學管理和博客健康、有序的發(fā)展。

1　屬性拓撲及形式概念計算

1.1屬性拓撲的表示

在形式背景K = (G，M，I)中，定義T = (V，E)為屬性拓撲的鄰接矩陣表示［10-12］。其中，V = M為拓撲的頂點集合，E為拓撲中邊的集合。則可以得到屬性拓撲的表達式:其他

定義T = (V，E')為屬性拓撲的關聯(lián)矩陣表示［12］。同樣，V = M為拓撲中的頂點集合，E'為拓撲中邊的集合。由此得到屬性拓撲的另一個表達式為

由形式背景所對應的鄰接矩陣和關聯(lián)矩陣，即可得到以所有屬性為頂點的形式背景的屬性拓撲［12］。

1.2屬性拓撲的分解與子拓撲的構造

依文獻［12］可知，根據(jù)屬性拓撲中各屬性類別及其之間的關系情況，可判斷拓撲是否可分解為若干子拓撲。將拓撲判定為可分解后，便可以進行下一步，即拓撲的分解與子拓撲的構造。

假設形式背景K = (G，M，I)可分解，其屬性拓撲中的頂層屬性的個數(shù)為n，則子拓撲數(shù)也為n。拓撲的分解與子拓撲的構造流程圖如圖1。

圖1　子拓撲的分解流程圖Fig.1　Flow chart of decomposition of sub-topologies

1.3基于子拓撲的形式概念計算算法

利用上述得到的子拓撲進行概念的計算，假設得到子拓撲分別為subT(V1，E1)，subT(V2，E2)，…，subT(Vn，En)。

文獻［12］通過對分解后的屬性子拓撲分別進行全路徑搜索實現(xiàn)概念的計算。為了將算法應用到實際數(shù)據(jù)的分析中，需要在文獻［12］提出的算法實現(xiàn)的理論基礎上加入一些約束條件，修改后的算法流程圖如圖2所示。

依照圖2所示算法流程圖，分別對子拓撲subT(V1，E1)，subT(V2，E2)，…，subT(Vn，En)進行全路徑搜索，對每個子圖的所有路徑進行遍歷后，可以得到各子圖中對應所有的形式概念集β(subT(V1，E1))，β(subT(V2，E2))，…，β(subT(Vn，En))。

圖2　子拓撲計算形式概念算法流程圖Fig.2　Flow chart of calculation of formal concepts by sub-topology

2　基于屬性拓撲的博客數(shù)據(jù)分析

2.1拓撲的生成

經(jīng)過二十多年的不斷發(fā)展，目前的UCI數(shù)據(jù)庫已經(jīng)包含了264個不同種類的數(shù)據(jù)集。其中，在這些數(shù)據(jù)集中，大部分來自于各個領域?qū)＜艺鎸嵉膶嶒灁?shù)據(jù)，涉及到生命科學、物理科學、工程學、社會科學等多個領域。為了測試和驗證屬性拓撲算法表示形式背景和計算形式概念的可行性，本文選取UCI機器學習數(shù)據(jù)庫(UCI Machine Learning Repository)中的最近更新的博客數(shù)據(jù)集進行測試，其包含了6個屬性和100個對象，這些屬性和對象的關系包括了形式背景中可能出現(xiàn)的所有關系，并且凈化后的背景直觀明確，適合本文中的實驗。在實驗中，本文研究的屬性拓撲算法均在凈化背景的基礎上［10-12］，因此需要先對樣本數(shù)據(jù)進行背景的凈化和處理，將重復的對象合并整理，多值屬性進行單值化，凈化后的測試數(shù)據(jù)集包含14個屬性和41個對象，如表1所示。

表1　凈化后的測試數(shù)據(jù)集Tab.1　Test data set after purification

表1中的各字母代表的含義分別如下: a:博主為高學歷; b:博主為中等學歷; c:博主學歷較低; d:政治立場為左派; e:政治立場為中立; f:政治立場為右派; g:博客主題為感想; h:博客主題為政治; i:博客主題為旅游; j:博客主題為新聞; k:博客主題為科學; l:博客被當?shù)孛襟w轉(zhuǎn)載; m:地方，政治和社會空間; n:該博主為臨博主。

由第2節(jié)的鄰接矩陣和關聯(lián)矩陣計算公式，可以得到表1所示。形式背景的鄰接矩陣和關聯(lián)矩陣分別如下:

鄰接矩陣:

由關聯(lián)矩陣確定圖中各邊的走向，即關聯(lián)矩陣中若兩個屬性所在位置交叉處對應的兩個值均為0，則這兩個屬性無關聯(lián)，若值為1和－1，則這兩個屬性為包含關系［10］，用單向邊連接，若兩個值均為1，則這兩個屬性為相容關系［10］，拓撲中用雙向邊連接;鄰接矩陣確定圖中邊的權值，可以得到表1的屬性拓撲如圖3所示，圖中包含了形式背景中的所有屬性以及屬性間的關聯(lián)方式和關聯(lián)強度，其為帶權值的有向圖。為表示方便，圖中將各邊的權值省略。

圖3　表1的屬性拓撲圖Fig.3　The attribute topology for Tab.1

依文獻［10］中頂層屬性和文獻［12］中伴生屬性的定義可知，圖3中，頂層屬性為: a，b，c，d，e，f，j，h，j，l，m，n，伴生屬性為: j，k，且屬性i，k均為屬性l的伴生屬性。與伴生屬性i，k相連的雙向邊用虛線連接，表示該雙向邊連接的兩個屬性在概念計算時不能直接關聯(lián)，需要通過伴生屬性的父屬性產(chǎn)生關聯(lián)［12］。

圖4為表1所示背景的其中一種概念格。顯然，相對于概念格，從屬性拓撲圖中可以更明顯的看出各個屬性間是否有關聯(lián)，及其產(chǎn)生關聯(lián)的對象集合，具有更強的可視性，使得屬性間的關系一目了然。

圖4　表1的概念格Fig.4　The concept lattice of Tab.1

2.2形式概念計算

屬性拓撲是形式概念分析理論的一種突破，因為該方法既做到了形式背景的表示，同時還可用于計算，其優(yōu)勢就在于背景表示的可視性和概念計算的可視性。

下面將以分析實驗的方式分析基于屬性拓撲的概念計算方法，并結(jié)合實際情況對本組數(shù)據(jù)進行分析。

分析圖3可知，該屬性拓撲顯然是可分解的。采用文獻［12］中給出的子拓撲構造算法，將圖3所示拓撲中的12個頂層屬性進行出度大小排序并以這些頂層屬性為中心構造子拓撲。其中這12個頂層屬性的順序為: h，a，g，e，j，b，d，c，f，l，m，n，對應做出各頂層屬性的子拓撲如圖5～15所示，n的子拓撲只包含n一個屬性，在此不做畫圖表示，并依據(jù)這些子拓撲進行概念的計算。為表示方便，子圖中將各邊的權值省略，圖中的虛線表示與伴生屬性相連的雙向邊。顯然，子圖的結(jié)構要更簡化，更便于屬性關系的觀察和概念的計算。

下面以屬性h的子拓撲圖5為例進行計算和分析，分析子拓撲的概念計算算法。該算法利用了圖的全路徑搜索原理，首先將子拓撲中中心屬性以外的所有屬性進行隨機排序(本文中采用了字母表順序)，再按順序進行遍歷，可實現(xiàn)在搜索過程中省略掉偽概念，只保留概念，因此減小了計算步驟。下圖16是子圖h的全路徑搜索示意圖。

圖16中的虛線表示遍歷過程中產(chǎn)生的偽概念直接忽略掉不做存儲，由此遍歷過程即可直接得到全部的概念并且避免了偽概念的產(chǎn)生，提高了計算的效率，并且遍歷過程實現(xiàn)了可視化，便于觀察和分析。

圖6～15子拓撲的概念計算過程與屬性h的子拓撲計算過程類似，同樣是將與其直接相關聯(lián)的屬性進行排序，再按順序進行全路徑搜索，在偽概念產(chǎn)生條件下，遍歷路徑用虛線表示，并不做存儲，直至路徑遍歷完全。由于過程類似，文中將不再做詳細計算分析。

圖5　頂層屬性h的子拓撲Fig.5　The sub-topology of top-attribute h

圖6　頂層屬性a的子拓撲Fig.6　The sub-topology of top-attribute a

圖7　頂層屬性g的子拓撲Fig.7　The sub-topology of top-attribute g

圖8　頂層屬性e的子拓撲Fig.8　The sub-topology of top-attribute e

圖9　頂層屬性j的子拓撲Fig.9　The sub-topology of top-attribute j

圖10　頂層屬性b的子拓撲Fig.10　The sub-topology of top-attribute b

圖11　頂層屬性d的子拓撲Fig.11　The sub-topology of top-attribute d

圖12　頂層屬性c的子拓撲Fig.12　The sub-topology of top-attribute c

圖13　頂層屬性f的子拓撲Fig.13　The sub-topology of top-attribute f

2.3數(shù)據(jù)分析

前面分析了屬性拓撲關于概念計算的算法，而概念的計算目的則是為了分析數(shù)據(jù)中屬性之間實際存在的聯(lián)系。在屬性拓撲計算形式概念的同時，可直觀的看到每個頂層屬性與其他所有屬性的關聯(lián)與關聯(lián)強度，而根據(jù)這個關聯(lián)強度的大小就可以提取其對應的類別，從而達到屬性規(guī)整的效果。

圖14　頂層屬性l的子拓撲Fig.14　The sub-topology of top-attribute l

圖15　頂層屬性m的子拓撲Fig.15　The sub-topology of top-attribute m

依舊以圖16為例進行說明。圖16是以屬性h為中心的子拓撲的遍歷過程，其中虛線代表過程中產(chǎn)生了偽概念，計算時該二元組不做存儲，例如二元組({ 2，10}，{ h，a，d，l})與二元組({ 2，10}，{ h，a，d，l，m})，而存儲直線后的二元組({ 2，10}，{ h，a，d，l，m})，這是因為相同的對象集{ 2，10}下，屬性集達到最大的{ h，a，d，l，m}時，該二元組才可稱為概念，結(jié)合圖16的遍歷過程反映到數(shù)據(jù)中即為，在同時滿足了博客的主題為政治和博主為高學歷前提下的2和10這兩篇博客中，該博客政治立場為左派以及博客被當?shù)孛襟w轉(zhuǎn)載和該博客反映了地方，政治和社會空間這3條屬性將并列同時出現(xiàn)，可以稱這3個屬性為屬性集{ h，a}下的綁定屬性，即可以認為當一篇博客滿足博客政治立場為左派以及博客被當?shù)孛襟w轉(zhuǎn)載兩個條件時，這篇博客很有可能也反映了地方，政治和社會空間。而對于連接實線的屬性h和屬性a而言，表示二元組({ 2，5，6，10，14，17}，{ h，a})即為一個概念，運算過程中可直接存儲，結(jié)合屬性代表的含義分析可知，2，5，6，10，14和17這幾篇博客同時滿足了博客的主題為政治和博主為高學歷兩個條件。特別的，如圖16所示，當前路徑中若存在伴生屬性，則必然存在其父屬性，在實驗中表現(xiàn)為，當博客主題為旅游或者科學時，則該博客均會被當?shù)孛襟w轉(zhuǎn)載。

圖16　圖5的全路徑搜索示意圖Fig.16　The full path searching of Fig.5

3　結(jié)束語

本文在子拓撲計算形式概念的基礎上，加入一些約束條件，將博客數(shù)據(jù)背景下的屬性拓撲分解為子拓撲，利用全路徑搜索計算博客數(shù)據(jù)的形式概念。通過博客數(shù)據(jù)形式概念的計算，深入分析了各個博主相關信息及其博客主題相關信息之間實際存在的聯(lián)系，有利于博客使用者快速了解博主及其博客的相關主題，摒棄無用信息。

參考文獻

［1］Ganter B，Wille R.Formal concept analysis: mathematical foundations［M］.New York: Springer-Verlag，1999.

［2］Mehdi Kaytoue，Sergei O Kuznetsov，Amedeo Napoli，et al.Mining gene expression data with pattern structures in formal concept analysis［J］.Information Sciences，2011，181(10) : 1989-2001.

［3］Tarek Abudawood.Improving Predictions of Multiple Binary Models in ILP［J］.The Scientific World Journal，2014，739062.

［4］Du Ya-jun，Hai Yu-feng.Semantic ranking of web pages based on formal concept analysis［J］.The Journal of Systems and Software，2013，86(1) : 187-197.

［5］Anna Formica.Semantic Web search based on rough sets and Fuzzy Formal Concept Analysis［J］.Knowledge-Based Systems，2012，26: 40-47.

［6］Li Bi-xin，Sun Xiao-bing，Leung Hareton.Combining concept lattice with call graph for impact analysis［J］.Advances in Engineering Software，2012，53: 1-13.

［7］LI Bi-xin，SUN Xiao-bing，Jacky Keung.FCA-CIA: An approach of using FCA to support cross-level change impact analysis for object oriented Java programs［J］.Information and Software Technology，2013，55(8) : 1437-1449.

［8］Lambrini Seremeti，Ioannis Kougias.Yoneda Philosophy in Engineering［J］.International Journal of Engineering Mathematics，2013，758729.

［9］Kang Xiangping，Li Deyu，Wang Suge.Research on domain ontology in different granulations based on concept lattice［J］.Knowledge-Based Systems，2012，27: 152-161.

［10］張濤，任宏雷.形式背景的屬性拓撲表示［J］.小型微型計算機系統(tǒng)，2014，35(3) : 590-593.

［11］Zhang Tao，Ren Hong-lei，Wang Xiao-min.A calculation of formal concept by attribute topology［J］.ICIC Express Letters，Part B: Applications，2013，4(3) : 793-800.

［12］張濤，任宏雷，洪文學，等.基于屬性拓撲的可視化形式概念計算［J］.電子學報，2014，42(5) : 925-932.

Attribute topology analysis of blogger data

ZHANG Tao1，LI Hui1，REN Hong-lei2
(1.College of Information Science and Engineering，Yanshan University，Qinhuangdao，Hebei 066004，China; 2.System Testing Department，Tangshan Qiao Technology Company Limited，Tangshan，Hebei 063000，China)

Abstract:Blog has gradually showed vigorous development trend in recent years，but blog information presents mottled and multifarious，and information garbage emerge in endlessly due to the zero threshold and lack of regulation.Formal concept analysis is a powerful tool for data analysis and knowledge processing，and attribute topology，a new representation method of formal context，is especially effective in the visual representation of context and computational visualization.Based on the theory of computing formal concepts in parallel，this paper presents the reasonable integration and deep-seated mining of the related information of the bloggers and the themes of blog by adding some constrains and computing the formal concepts of blog data.It is beneficial to abandon the useless information and it provides a theoretical basis for the blog users to find useful and interesting bolg content for himself and the related information of bloggers quickly.

Key words:formal concept analysis; attribute topology; full path searching; blog

作者簡介:*張濤(1979-)，男，河北唐山人，博士，副教授，主要研究方向為信息融合、可視化模式識別、圖像處理，Email: zhtao@ ysu.edu.cn。

基金項目:國家自然科學基金資助項目(61273019，61201111，81273740，81373767) ;河北省自然科學基金資助項目(F2013203368，F(xiàn)2015203013)

收稿日期:2014-06-25

文章編號:1007-791X(2015) 01-0042-09

DOI:10.3969/j.issn.1007-791X.2015.01.007

文獻標識碼:A

中圖分類號:TP182