海量數(shù)據(jù)聚類文獻

名目

聚類算法討論..............................................................2

面對中文自然語言文檔的自動學問抽取方法...................................8

學問抽取技術綜述*........................................................10

當前學問抽取的主要技術方法解析*..........................................11

基于本體的專利摘要學問抽取*..............................................13

一種基于網(wǎng)格的改進的K-Means聚類算法.....................................15

基于初始點選取的K-Means聚類近似常數(shù)算法.................................17

一種半監(jiān)督K均值多關系數(shù)據(jù)聚類算法.......................................19

基于單元區(qū)域的高維數(shù)據(jù)聚類算法...........................................21

一種層次化的檢索結(jié)果聚類方法.............................................23

面對信息檢索的快速聚類算法...............................................25

基于MapReduce的分布式近鄰傳播聚類算法..................................27

一種基于層次距離計算的聚類算法...........................................30

聚類算法討論

題目：孫吉貴，劉杰，趙連宇等.聚類算法討論[J].軟件學

JU,2022,19（1）:48-61.DOI:10.3724/SPJ.1001.2022.00048.

基本學問儲備與理解：

01、聚類過程與定義：

1）數(shù)據(jù)預備：包括特征標準化和降維。

2）特征選擇：從最初的特征中選擇最有效的特征，并將其存儲于向量中。

3）特征提?。和ㄟ^對所選擇的特征進行轉(zhuǎn)換形成新的突出特征。

4）聚類（或分組）：首先選擇合適特征類型的某種距離函數(shù)（或構造新的距離函數(shù)）進行

接近程度的度量；而后執(zhí)行聚類或分組。

5）聚類結(jié)果評估：是指對聚類結(jié)果進行評估.評估主要有3種：外部有效性評估、內(nèi)部

有效性評估和相關性測試評估。

聚類的定義：一個類簇內(nèi)的實體是相像的，不同類簇的實體是不相像的；一個類簇是測

試空間中點會聚，同一類簇的任意兩個點間的距離小于不同類簇的任意兩個點間的距離。

所謂聚類，就是把大量的d維數(shù)據(jù)對象（N個）聚集成K個類（K<N）,使同一個類內(nèi)對象

的相像性盡可能最大，而不同類內(nèi)的對象的相像性盡量達到最小，也就是說，形成類之

后，同一個類內(nèi)對象具有很高的相像性，而且與不屬于該類的對象有迥然的差異。

劃分的方法：k均值，k中心點燈；

層次的方法：分散法和分裂法，BIRCH,CURE,變色龍法；

基于密度的方法：DBSCAN,OPTICS,DENCLUE（基于對象的聚類只能發(fā)覺球狀的簇，基于

密度可以發(fā)覺任意的簇）

基于網(wǎng)格的方法：將一個網(wǎng)格內(nèi)的數(shù)據(jù)當成一個對象來處理，STING、WaveCluster.

CLIQUE

基于模型的方法：統(tǒng)計學方法（COBWEB）和神經(jīng)網(wǎng)絡方法（競爭學習、自組織特征映射），

數(shù)據(jù)是依據(jù)潛在的概率分布生成的。

02、層次聚合算法：

又叫做樹聚類算法，使用數(shù)據(jù)的聯(lián)接規(guī)章，透過一種層次架構方式，反復將數(shù)據(jù)進行分

裂和聚合，以形成一個層次序列的聚類問題解。

層次聚類算法：類似于樹形結(jié)構，自底向上逐層聚合，直至全部樣本都屬于同一個類。

Binary-Positive方法（正二進制法）：該方法把待分類數(shù)據(jù)以正的二進制形式存儲于

一個二維矩陣中，其中，行表示紀錄（對象），列表示其屬性的可能取值。紀錄對應的取

值為1或者0,分別表示此紀錄有對應的屬性值或者不存在對應屬性值。因此，相像性距

離計算只在被比較的二進制向量中的正比特位上進行，即只在取值為1的紀錄（對象）之

間進行。將原始數(shù)據(jù)轉(zhuǎn)換成正二進制會改善聚類結(jié)果的正確性和聚類的魯棒性，對于層

次聚類算法尤其適用。

連續(xù)數(shù)據(jù)的粗聚類算法（roughclusteringofsequentialdata,簡稱RCOSD）：關鍵思

想是查找能捕獲數(shù)據(jù)序列的連續(xù)信息及內(nèi)容信息的一個特征集，并把這些特征集映射到

一個上近似空間，應用約束相像性上近似技術獲得粗類簇的上近似，其中一個元素可以

屬于多個類簇.該算法引入S3M作為Web數(shù)據(jù)的相像性度量方法，S3M既考慮了項的消失次

序又考慮了集合內(nèi)容。該算法每一次迭代可以合并兩個或多個類，所以加快了層次聚類

速度。該算法能夠有效挖掘連續(xù)數(shù)據(jù)，并刻畫類簇的主要特性，關心呢b挖掘者描述潛

在的新的Web用戶組的特性。

03、劃分式聚類算法：需要預先指定聚類數(shù)據(jù)或者聚類中心，通過反復迭代運算，逐步

降低目標函數(shù)的誤差值，當目標函數(shù)收斂時，得到最終的聚類結(jié)果。

K均值聚類：

第一步：選擇K個點作為初始的質(zhì)心；

其次步：repeat

第三步：將每個點指派到最近的質(zhì)心，形成k個簇；

第四步：重新計算每個簇的質(zhì)心；

第五步；until質(zhì)心不再發(fā)生變化。

優(yōu)點：能對大型數(shù)據(jù)集進行高效分類，其計算簡單性為O（tKmn）,其中，t為迭代次數(shù)，

K為聚類數(shù)，加為特征屬性數(shù)，n為待分類的對象數(shù)，通常，K,m,t?n.在對大型數(shù)據(jù)

集聚類時,K-means算法比層次聚類算法快得多。

不足：通常會在獲得一個局部最優(yōu)值時終止；僅適合對數(shù)值型數(shù)據(jù)聚類；只適用于聚類

結(jié)果為凸形（即類簇為凸形）的數(shù)據(jù)集。

K-modes算法：該算法對K-means進行了3點擴展：引入了處理分類對象的新的相異性度

量方法（簡潔的相異性度量匹配模式），使用modes代替means,并在聚類過程中使用基于

頻度的方法修正modes,以使聚類代價函數(shù)值最小化。K-modes算法的另一-個優(yōu)點是modes

能給出類的特性描述。

缺點是會產(chǎn)生局部最優(yōu)解，依靠于初始化modes的選擇和數(shù)據(jù)集中數(shù)據(jù)對象的次序。初

始化modes的選擇策略尚需進一步討論。

迭代初始點集求精K-modes算法，由于k-modes算法需要通過預先打算或者隨機選擇類的

初始modes才能夠聚類分類數(shù)據(jù)，并且初始modes的差異經(jīng)常會導致截然不同的聚類結(jié)果,

可通過迭代初始點求精算法予以解決。

全都性保留k均值算法：對于一個類中的任意數(shù)據(jù)點，要求它的K最近鄰和K互最近鄰都

必需在該類中。

模糊聚類算法（FCM）：主要適用于圖像分割，勝利之處在于為解決每個圖像像素的隸

屬需要引入了模糊性，可以保留更多的圖像的信息。缺點是沒有考慮圖像上下文中的任

何空間信息，對于噪聲比較敏感。

圖論算法：構造一顆最小生成樹（MST）,通過刪除最小生成樹的最長邊來形成類。

04、基于網(wǎng)格和密度聚類：基于密度，通過數(shù)據(jù)密度來發(fā)覺任意外形的類簇；基于網(wǎng)格，

使用一個網(wǎng)格結(jié)構，圍繞模式組織由矩陣塊劃分的值空間，基于塊的分布信息實現(xiàn)模式

聚類。

DBSCAN算法：

第一步：將全部點標記為核心點、邊界點、噪聲點

其次步：刪除噪聲點；

第三步：為距離在Eps（半徑）之內(nèi)的全部核心點之間賜予一條邊；

第四步：每組連通的核心點形成一個簇；

第五步：將每個邊界點指派到一個與之關聯(lián)的核心點的簇中。

09、AC0DF聚類算法：不需要求任何硬子問題，但能給出近似最優(yōu)解的聚類算法。

第一步：應用蟻群算法，規(guī)定每個螞蟻只需要訪問全部城市數(shù)量的特別之一，并且訪問

城市數(shù)目漸漸削減；循環(huán)幾次，兩點之間的相對較短的路徑的信息素濃度會增大，兩點

之間相對長的路徑的信息素會削減。因此，螞蟻會選擇訪問近距離的節(jié)點，并用自己的

信息加強次路徑，最終形成具有較高濃度的路徑，聚類完畢。

其次步：應用模擬退火策略來解決局部最優(yōu)解的問題。

ns(t+l)=ns(t)XT其中ns是蟻群在T。函數(shù)期間訪問的節(jié)點數(shù),ns(t+l)表示當前蟻群

的訪問的節(jié)點數(shù),ns(t)表示上一次循環(huán)蟻群訪問的節(jié)點數(shù)，r是一個常數(shù)(T=0.95)。

nf(t+l)=2ns(t)/3-ins(t)/(run*3)其中,nf是蟻群在Ti函數(shù)期間訪問的節(jié)點數(shù),

nf(t+1)表示蟻群當前訪問的節(jié)點數(shù)，nf(t)表示上一次循環(huán)蟻群訪問的節(jié)點數(shù)，run=2,

ie{1,2}。

第三步：使用錦標賽選擇策略，即從N條路徑中隨機選擇K條路徑，再從K條路徑中選擇

最短路徑。

算法類型算法名稱算法描述算法優(yōu)缺點

針對大型數(shù)據(jù)庫的高效的聚類算優(yōu)點：對孤立點的處理更加健壯，能夠

法，采納固定數(shù)目有代表性的點代識別外形簡單，大小不一的聚類。

CURE算法

表一個簇，處理大數(shù)據(jù)量時采納隨缺點：代表點是來自一組隨機抽取的樣

機取樣。本集，它的最初數(shù)目需要人為確定。

優(yōu)點：簡潔聚類，并適用于類別屬性的

對CURE算法的改進，采納基于元組

數(shù)據(jù)。

分散層次聚類ROCK算法之間的連接數(shù)目來計算相像形。

缺點：該算法的相像度函式sim是基于

算法

領域?qū)＜业闹庇X。

在層次聚類中采用了動態(tài)建模技優(yōu)點：在發(fā)覺高質(zhì)量的任意外形簇方面

術，通過圖劃分算法將數(shù)據(jù)對象劃有更強的力量。

CHAMELEON

分為相對較小的子集，然后用一個缺點：聚類結(jié)果的精確性和

算法

分散的層次聚類算法通過反復合并有效性有待提高，時間效率需進?步優(yōu)

子類來找到結(jié)果簇?；?/p>

采納自頂向下的策略，先將全部對

優(yōu)點：適用于任意外形和任意屬性的數(shù)

象置于一個簇中，然后漸漸細分為

據(jù)集，敏捷掌握不同層次的聚類粒度，

越來越小的簇，直到每個對象自成

DIANA算法聚類力量強。

分裂層次聚類一簇，或者達到了某個終結(jié)條件。

缺點：大大延長了算法的執(zhí)行時間，不

算法其主要思想是將那些成員之間不是

能回溯處理。

特別緊密的簇進行分裂。

基于密度的空間聚類算法，它將簇優(yōu)點：在處理空間數(shù)據(jù)時能快速、有效

定義為密度相連的點的最大集合，和發(fā)覺任意外形聚類。

DBSCAN算法能夠把具有足夠高密度的區(qū)域劃分缺點：對用戶定義的參數(shù)是敏感的，參數(shù)

為簇，并可在空間數(shù)據(jù)庫中發(fā)覺任難以確定，全局密度參數(shù)不能刻畫內(nèi)在

意外形的聚類。的聚類結(jié)構。

優(yōu)點：有良好的聚類特征，算法速度快，

可以有效揭示數(shù)據(jù)分布的內(nèi)在層次，可

基于密度的分基于一組密度分布函數(shù)的算法，依

以發(fā)覺任意外形的聚類，對噪聲數(shù)據(jù)不

割聚類算法DENCLU算法據(jù)數(shù)據(jù)點在屬性空間中的密度進行

敏感。

聚類，得到的是全局最優(yōu)化分。

缺點：聚類結(jié)果嚴峻依靠于用戶參數(shù)的

合理選取。

通過對象排序識別聚類結(jié)果，為聚優(yōu)點：具有良好的聚類想能，具有較高

類分析生成一個增廣的簇排序，這的敏捷性。

OPTICS算法

個排序代表了各樣本點基于密度的缺點：需要額外的存儲空間，處理稀疏

聚類結(jié)構。點具有局限性。

基于網(wǎng)格的多辨別率聚類技術，將優(yōu)點:不依靠于查詢，有利于并行處理和

空間劃分為矩陣單元，形成一個層增量更新，效率高。

STING算法

次結(jié)構，關于每個網(wǎng)格單元屬性的缺點:全部聚類邊界都是水平或者平衡

統(tǒng)計信息被預先計算和存儲，這些的，沒有對角的邊界，可能降低簇的質(zhì)

基于網(wǎng)格的分信息用于回答查詢。量和精確性。

割聚類算法

優(yōu)點：自動的發(fā)覺最高維的子空間，對

結(jié)合網(wǎng)格和密度聚類的思想，區(qū)分于輸入挨次不敏感，無須假設任何法律

空間中的稀疏和擁擠的單元，以發(fā)規(guī)范的數(shù)據(jù)分布，與輸入數(shù)據(jù)的大小呈

CLIQUE算法覺數(shù)據(jù)集合的全局分布模式，假如線性關系，當數(shù)據(jù)維數(shù)增加時具有良好

一個單元中包含的數(shù)據(jù)超過了某個的擴展性。

輸入模型參數(shù)，則該單元是密集的缺點：隨著方法的簡化，精度可能大大

降低。

采納小波變換聚類，是一種多辨別優(yōu)點：能有效地處理大數(shù)據(jù)集合，發(fā)覺

WaveCluster率的聚類算法，通過在數(shù)據(jù)空間上任意外形的簇集，勝利處理孤立點，對噪

算法加一個多維網(wǎng)格結(jié)構來匯總數(shù)據(jù)，聲和輸入數(shù)據(jù)的挨次不敏感。

然后采納小波變化找到密集區(qū)域。缺點：對數(shù)學和建模的學問要求較高。

優(yōu)點：具有較強的發(fā)覺任意外形和任意

通過在合并兩類時用更高的標準來大小簇的力量，可以得到較好的聚類質(zhì)

CHAMELEON

提高聚類質(zhì)量的聚類算法既考慮r量。

算法

交互性，又考慮了近似度。缺點：不適合大型數(shù)據(jù)庫中的數(shù)據(jù)聚

類。

基于圖論的分

點集自動聚類的算法，使用特別的

割聚類算法優(yōu)點：能夠發(fā)覺任意外形的類簇，需要

圖結(jié)構來描述對象的空間近鄰，然

AUTOCLUST很少的輸入?yún)?shù)，聚類精度高。

后刪除不全都的邊來形成一組子

算法缺點：算法不行靠，計算量較大，不考

圖，該算法基于Delaunay三角網(wǎng)進

慮空間對象的屬性。

行計算

優(yōu)點：期望最大化、能夠處理異構數(shù)據(jù)、

逐步對聚類結(jié)果進行優(yōu)化、不斷將

概率聚類算能夠處理具有簡單結(jié)構的紀錄、能夠連

目標數(shù)據(jù)集向各個聚類中心進行重

法續(xù)處理成批的數(shù)據(jù)、具有在線處理力

新安排。

量、產(chǎn)生的聚類結(jié)果易于解釋。

最近鄰聚類

優(yōu)點：在處理大小不同、外形不同以及

算法一一共

密度不同的數(shù)據(jù)集上具有很好的聚類

享最近鄰算結(jié)合基于密度方法和ROCK思想，保

效果。

基于劃分的聚法SNN留K最近鄰簡化相像矩陣和個數(shù)。

缺點：時間簡單度提高，不適合處理大

類算法

規(guī)模數(shù)據(jù)集。

選擇k個對象，每個對象代表一個聚

類，把其余的對象分別安排給最相

K-Medioids算優(yōu)點：能處理任意類型的屬性，對特別

像的聚類，然后嘗試把每個中心分

法數(shù)據(jù)不敏感。

別用其他非中心來代替，檢查聚類

缺點：執(zhí)行代價高。

的質(zhì)量是否有所提高，若是，則保

留替換，直到不再發(fā)生變化。

選擇k個對象，每個對象代表一個聚優(yōu)點：應用最為廣泛，收斂速度快，能

K-Means算法

類的質(zhì)心，對于其余的每一個對象，擴展以用于大規(guī)模的數(shù)據(jù)集，具有很好

依據(jù)該對象與各聚類質(zhì)心之間的距的收縮性。

高，把它安排到與之最相像的聚類缺點：要多次掃描數(shù)據(jù)庫，只能找出球

中，計算每個聚類的新質(zhì)心，通常形的類，初始質(zhì)心的選擇對聚類結(jié)果有

采納的準則函數(shù)是平方誤差準則函較大的影響，對噪聲很敏感。

數(shù)。

過濾不行能包含任何愛好度子空間優(yōu)點：含有大量的局部信息，算法的效

中的屬性，計算得到由非冗余屬性率高。

用于高維數(shù)據(jù)ENCLUS算法的相關度函數(shù)值所組成的關系矩缺點：不行避開地帶來了原始數(shù)據(jù)信息

的聚類算法陣，將屬性聚類，產(chǎn)生子空間聚類。的損失和聚類精確性的降

低。

自組織映射，向量化方法，遞增逐優(yōu)點：采用相應的啟發(fā)式算法獲得較高

神經(jīng)網(wǎng)絡聚i處理，映射至二維平面，實現(xiàn)可質(zhì)量的聚類結(jié)果。

類方法視化缺點：計算簡單度較高，結(jié)果依靠于對

某些閱歷參數(shù)的選擇。

基于模型的方輸入對象用分類屬性-值來描述，以優(yōu)點：不需要用戶輸入?yún)?shù)來確定類的

法一個分類樹的形式創(chuàng)建層次聚類，個數(shù)，可以自動修正劃分中類的個數(shù)。

COBWEB算法分類樹的每個節(jié)點對應一個概念，缺點：分類樹對于偏斜的輸入數(shù)據(jù)是不

包含該概念下的一個概率描述，概平衡的，可能導致時間空間簡單性的猛

述被分在該節(jié)點下的對象.烈變化。

面對中文自然語言文檔的自動學問抽取方

法

題目：車海燕，馮鐵，張家晨等.面對中文自然語言文檔的自動學問抽取方法[J].

計算機討論與進展,2022,50(4):834-842.

作者思路：提出了基于語義web理論和中文自然語言處理(NPL)技術的自動學問抽取新方

法AKE,并用相應試驗賜予證明。

基本定義：

01,聚集體學問概念(AKC),是領域本體中的一類概念，它將N元關系所對應的結(jié)構化信息

聚集而成一個獨立的資源，并用自身的屬性刻畫N元關系的各個元。

02、外部聚集體學問概念(Outer-AKC),是聚集體學問結(jié)構中最外層的AKG,只能作為非AKG

實例的屬性值。

03、內(nèi)部聚集體學問概念(Inner-AKC),只能作為Outer-AKC和Inner-AKC的實例的屬性值，刻

畫該屬性值的聚集體學問結(jié)構。

04、有效性，在一個三元組集合中，一個RDF節(jié)點是有效的，假如它是RDF文字或命名實體

類型概念的實例或者它是AKC類概念的實例并且在三元組集合中該實例滿意領域本體對其

所屬概念定義的全部屬性約束。

05、完整性：在三元組集合中，一個RDF節(jié)點是完整的，假如它是RDF文字或命名實體類型

概念的實例或者它是有效的AKC類概念的實例并且該實例在三元組集合中的全部屬性嗾使

有效的。

核心思想：

01、學問三元組的構造：〈主體s,謂詞p,客體o>

1)按序原則：構建三元組是以屬性為核心為其選擇合適的主體和客體，顯示屬性優(yōu)先

于隱式屬性；選擇主體和客體是，依據(jù)實例被識別的挨次狗仔三元組。

2)局部最新優(yōu)先原則：為三元組選擇主體或客體時優(yōu)先從局部概念實例集合中選擇，

假如沒有，再從全局概念實例集合中選擇，并且優(yōu)先選擇最新被識別或被創(chuàng)建的。

02、學問清洗：

對從一篇文檔中抽取出的事實學問三元組集合進行有效性和完整性檢查,刪除無效節(jié)點

以及相關的三元組和有效節(jié)點的不完整部分。

基本學問儲備與理解：

01、學問抽取討論如何依據(jù)本體識別并抽取無語義標注的信息中與本體匹配的事實學問。

學問抽取的討論意義在于：1、抽取出的事實學問可以用來構建各種基于學問的服務，

如基于語義的智能學問搜尋；2、識別出的語義信息可以為現(xiàn)有的web數(shù)據(jù)進行語義標

注，從而促進語義web遠景的真正實現(xiàn)。

02、目前自動學問抽取中存在的問題：1、依靠于大規(guī)模的通用語言學問庫或同義詞表，例

如目前存在的中文的通用語言學問庫“知網(wǎng)”，但是通用語言學問庫無法為特定領域的

詞匯供應精確的解釋；2、沒有對常見的N元關系簡單學問給出系統(tǒng)化的處

理方法。文章中就是對于這兩點進行了討論。

03、學問抽取處理的對象依據(jù)其結(jié)構化的程度可以分為結(jié)構化、半結(jié)構化和自然語言文檔。

04、定義領域本體時要為本體概念指定必要的屬性約束：對于Outer-AKC要確定關鍵屬性集

合并為該集合中的屬性定義基數(shù)為1的基數(shù)約束，其他非關鍵屬性則依據(jù)具體學問特點

指定必要的屬性約束；對于其他類型的本體概念也要依據(jù)具體學問特點指定必要的屬

性約束。

學問抽取技術綜述*

基本學問儲備與理解：

01、學問抽取討論如何依據(jù)本體識別并抽取無語義標注的信息中與本體匹配的事實學問。

02、本體(Ontology)是共享概念模型的明確形式化的法律規(guī)范說明。概念模型是指抽象客

觀世界中的一些現(xiàn)象的相關概念而得到的模型，即概念系統(tǒng)所蘊含的語義結(jié)構，是對

某一種事實結(jié)構的一組非正式的約束規(guī)章，可以理解和表達為一組概念(包括實體、屬

性和過程)、定義和關系；明確(explicit)是指所使用的概念及使用這些概念的約束都有明

確的定義；形式化(formal)是指本體是計算機可讀的；共享(share)是指本體中體現(xiàn)的是

共同認可的學問，反映的是相關領域中公認的概念集，即本體針對的是社會范疇而非

個體之間的共識。

03、W3C提出的用于描述Web資源的資源描述框架語言(resourcesdescriptionframework,

RDF)o不僅是Web數(shù)據(jù)集成的元數(shù)據(jù)解決方案，而且是一個能對結(jié)構化的元數(shù)據(jù)進行

編碼、交換和重用的體系框架。RDF使用統(tǒng)一資源標志符(universalresourceidentifier,

URI)作為標志機制的基礎，采用URI引用(URIreferences)描述任何事物及事物之間的關

系。RDF基本數(shù)據(jù)模型包含資源(resource)、屬性(property)和陳述(statement)三種對象模

型。

04、面對中文的學問抽取技術：

對結(jié)構化和半結(jié)構化文檔的學問抽?。篿ASA語義標注方法(包括規(guī)章學習模塊、標注

模塊和解釋模塊)、OMKast框架描述語言-NKI本體語言，表示領域本體和獵取到的目標

學問。

05、面對自由文檔的學問抽取：

對于中文自然語言文檔進行有效學問抽取需要結(jié)合多方面的工作，包括中文分詞、中

文命名實體識別和中文實體關系抽取等，同時還要依靠于對中文內(nèi)容部分元素的語義

識別。

06、基于主題的本體屬性識別方法不再試圖將自然語言句子中的詞語與本體中的概念和屬

性進行直接匹配，而是先依據(jù)已經(jīng)識別出的信息，包括概念實例和屬性，判定當前句

子的描述主題，然后采用本體中定義的與該主題相關的本體屬性查找文字中可能蘊含

的屬性。

07、iOkra框架借助本體和NLP技術首先對輸入文本執(zhí)行語形分析，分詞是通過將文中詞匯

與本體中元素進行對應為該詞供應語法和語義信息；然后進行淺層的句法分析，對分

詞結(jié)果執(zhí)行短語合并操作，并采用基于信息的全部格文法識別文中詞匯的主題角色(即

通用本體中定義的關系)；最終進行語義分析，采用通用語言本體和領域本體對ICG的

標記結(jié)果進行消歧并構造RDF語句，同時采用語言的局部依靠性特性識別那些沒有被

ICG識別出的角色。

當前學問抽取的主要技術方法解析*

題目：張智雄,吳振新,劉建華等.當前學問抽取的主要技術方法解析[J].現(xiàn)代圖

書情報技術,2022,(8):2-11.D01:10.3969/j.issn.1003-3513.2022.08.002.

基本學問儲備與理解：

01、狹義的學問抽取基本上屬于文本挖掘的范疇，其處理的對象是自由文本，目標是分

析文本內(nèi)容，通過識別出文本中的學問片段，促進對文本內(nèi)容的理解。

02、學問抽取系統(tǒng)中目前分為兩種思路，機器學習和自然語言處理，兩種技術思路目前

正在相互融合、相互借鑒，各自都得到了較大的進展?；跈C器學習的學問抽取系統(tǒng),

提出了自適應的信息抽取(AdaptiveIE)、開放信息抽取(OpenIE)等新的技術思路，并向著

自動本體學習(OntologyLearning)的方向進展；而基于自然語言分析的學問抽取系統(tǒng)，則

提出了基于模式標注(Pattern-BasedAnnotation)、語義標注(SemanticAnnotation)等新的

技術思路，并且都在向著基于Ontology的信息抽取(OBIE)的方向進展。

03、自適應的信息抽取需要借助肯定數(shù)量的手工標注語料，以適應新的應用領域。

04、開放信息抽取的目的在于促進領域無關的學問抽取應用，它能從文本中抽取出大量

關系對，并可被應用到各種類型和規(guī)模的web信息抽取任務中。

05、本體學習就是自動或半自動地從各類數(shù)據(jù)資源中獵取期望本體的方法和技術集合，

類似概念還有本體生成、本體挖掘、本體抽取等。

06、基于模式標注的學問抽取更加注意采用自然語言分析技術?；谀Ｊ綐俗⒌膶W問抽

取可分為兩種類型：一種通過模式的自動發(fā)覺，進而實現(xiàn)對相關內(nèi)容的標注：另--種通

過人工定義的模式實現(xiàn)內(nèi)容標注。

07、語義標注除采用自然語言的語法模式和規(guī)章外，更重要的是對語義內(nèi)容的挖掘?；?/p>

于Ontology的信息抽取(OBIE)方法可以認為是當前語義標注討論的一種主流方法，也被

稱作基于本體的標注和基于本體的語義標注。OBIE是語義標注的進一步進展，它不但

要將抽取出的內(nèi)容納入到學問庫中，還要求在抽取過程中始終得到Ontology的支持。

OBIE通過Ontology定義的類、屬性、層次結(jié)構抽取非結(jié)構化或半結(jié)構化文本中對應的

實例，進行歧義消解，進而識別文本中的實體及關系，將結(jié)果存儲于對應的Ontology

中。

08、于受控語言的信息抽取(CLIE)方法是一種很特別的技術方法，它以某些受掌握語言撰

寫的文本為處理對象，從這些受控語言的文本中構建Ontology。它可以降低Ontology構建

的門檻，提高Ontology構建效率。

09、學問抽取的5個特點：

1、學問抽取強調(diào)語義的抽取。抽取出的內(nèi)容是有肯定意義的、能被其它上下文所解釋

的語義學問片段(如概念及概念間的關系等)。2、學問抽取普遍將機器學習技術和自然語

言分析技術相結(jié)合。與傳統(tǒng)的基于學習或規(guī)章的信息抽取不同，由于面對更為簡單的任

務，許多學問抽取的系統(tǒng)都采納機器學習技術和自然語言分析技術相結(jié)合的方法。3、

學問抽取需要0ntology的支持。Ontology^學問抽取不行或缺的組件。在學問抽取前，

Ontology定義需要抽取的學問類型：命名實體識別過程中，Ontology除了能夠起到詞表

和辭典的幫助標識作用外，還可為學問抽取供應推理機制；在語義標注中，Ontology可

以對抽取結(jié)果進行語義識別和消退歧義；處理抽取結(jié)果，抽取結(jié)果被關聯(lián)到Ontology中，

形成學問庫。4、學問抽取關注實體間關系的識別和抽取。學問抽取除了要識別出命名

實體的類型外，還需要識別出這一命名實體與其它命名實體之間的各種關系，通過關系

將識別出來的新實體納入到相應的學問庫之中。5、學問抽取的結(jié)果為學問庫建設供應

了內(nèi)容。依據(jù)預先定義的Ontology框架，學問抽取系統(tǒng)從一系列文獻中抽取出相應實體

和關系，并將這些文獻和抽取出的實體和關系組織到學問庫中，實現(xiàn)本體填充(Ontology

Population),,所建設的學問庫是進一步實現(xiàn)數(shù)據(jù)挖掘、學問發(fā)覺的基礎。

基于本體的專利摘要學問抽取*

題目：姜彩紅，喬曉東，朱禮軍等.基于本體的專利摘要學問抽?。跩］.現(xiàn)代圖書情

報技術,2022,（2）:23-28.D0I:10.3969/j.issn.1003-3513.2022.02.004.

基本學問儲備與理解：

01、專利摘要的內(nèi)容可以分為如下5個部分：對專利的全局推斷（包括所屬技術領域的

推斷、用途或目的等）、專利采納或舍棄的方法或技術、專利的工作原理（包括鏈接接

觸。驅(qū)動掌握或自動工作等）、專利的組成結(jié)構以及專利人對專利的評價（包括正面性

能的增加，負面性能的削減或優(yōu)秀性能的保持等）。

02、抽取流程：數(shù)據(jù)轉(zhuǎn)換模塊、中文分詞模塊、本體構建模塊、學問抽取模塊。

本體

構

|中文分聞模塊］建

模

塊

中文專利摘

要文檔集

知

|數(shù)據(jù)轉(zhuǎn)換模塊］識

抽

取

模

塊

中文專利

專利知識庫KB

數(shù)據(jù)庫

03、數(shù)據(jù)轉(zhuǎn)換模塊的主要功能是用于對于語料的收集。

04、中文分詞模塊應用中科院分詞軟件ICTCLAS,對其進行了二次開發(fā)，實現(xiàn)對整個文

檔集進行批量分詞的功能。

05、本體構建模塊的任務是將專利摘要中的五項內(nèi)容抽取出來，并且以肯定的語義關系

組織起來存放入學問庫中。

在專利這個大類下面創(chuàng)建兩個子類，專利外部信息和專利內(nèi)部信息。在文本中，專

利外部信息指的是專利數(shù)據(jù)庫中的專利名稱，申請日，申請專利人，申請人地址，公開

號公開日等信息，在構建專利學問庫的時候，這些信息都可以從專利數(shù)據(jù)庫中直接獵取;

將專利摘要內(nèi)容判別原則中的5項內(nèi)容歸為專利內(nèi)部信息的五個子類，在構建專利學問

庫時，這些信息需要先從文本中抽取出來，并通過本體進行組織后存入學問庫中

06、學問抽取工具GATE,詞表的收集步驟如下所示：

1）全局推斷部分。這部分內(nèi)容基本上由以下三種動詞引導表達:表示專利所屬領域的動

詞（如:屬于、屬、所屬、涉及等）、表示專采用途或目的的動詞（如:用于、周作、作為、

適用于、有助于等）以及對專利進行解釋說明的動詞（如:在于、具有、稱為、兼有等）；

2）取舍替代部分。這部分內(nèi)容基本上由以下三種動詞引導表達:引出專利選取對象的

動詞（如:選擇、選取、采納、任選等）、專利舍棄對象的動詞（如:省去、省摔、取消、撤

銷等）以及引出專利代替對象的動詞（如:轉(zhuǎn)換、變換、切換、替代等）；

3）評價內(nèi)容部分。這部分內(nèi)容基本上由以下三種動詞引導表達:表示專利正面性能增

加的動詢（如:提高、增高、增大、延長等）、表示專利負面性能削減的動詞（如:降低、

削減、縮短、簡化、節(jié)約等）以及表示專利良好性能保持的動祠（如:保持、維持、保留

等）。

4）組成結(jié)構和作用原理部分。二者往往嵌套消失，因此放在一起處理。不但要收集

相關的動坷，還需妥收集其中的名詞。名詞部分主要有如下幾個方面:新能源汽車

名稱術語、汽車材料、燃料、動力設施、設施工藝以及動力傳遞方式等;動飼部分

主要可以分為如下幾種:引導組成結(jié)構的動詞（如:組成、構成、包含、包括等）、表示

連接作用的動詞（如：連接、鄰接、連接、結(jié)合、接觸等）、表示驅(qū)動掌握的動詞（如：掌

握、驅(qū)動、產(chǎn)生、傳輸、啟動等）以及表示自動反應的動詞（如:旋轉(zhuǎn)、運轉(zhuǎn)、伸縮、

分流、滑動等）。

規(guī)章撰寫：Java標注模式引擎（JavaAnnotationPatternsEngine,JAPE）供應了基于

正則表達式的標注有限狀態(tài)轉(zhuǎn)換，是CPSL（CommonPatternSpecificationLanguage）的一

個版本。通過JAPE語言可以編寫GATE能夠識別的規(guī)章，采用這些規(guī)章來對文檔進行

抽取。

抽取的結(jié)構存儲在xml文件中，然后通過對GATEAPI的調(diào)用對文檔進行批量抽取。

最終通過從xml文件中提取相關字段，并依據(jù)本體中抽象出的語義標注集，自動生成學

問庫。

一種基于網(wǎng)格的改進的K-Means聚類算法

題目：任家東，孟麗麗，張冬梅等.一種基于網(wǎng)格的改進的K-Means聚類算法［J］.

計算機討論與進展,2022,46(z2):828-833.

基本定義：

01、單元密度聚合度(U)：一個網(wǎng)格單元c中所包含的全部數(shù)據(jù)點x與c的幾何中心點

mean(c)之間的距離之和再除以網(wǎng)格單元c的密度Density?與網(wǎng)格單元長度d的乘積。

02、對于密集單元c,-?般U=<0.5的網(wǎng)格單元作為密集中心網(wǎng)格單元，其中U<=0.25的

密集中心網(wǎng)格單元為緊密集中心網(wǎng)格單元；0.25<U<-0.5的密集中心網(wǎng)格單元為松密集中

心網(wǎng)格單元。U>0.5的網(wǎng)格單元稱為非密集中心網(wǎng)格單元。

03、偏單元網(wǎng)格：密度大于閾值的非密集中心網(wǎng)格。

核心算法：

輸入：數(shù)據(jù)點數(shù)n,網(wǎng)格單元寬度d,網(wǎng)格密度閾值s;

輸出：聚類結(jié)果

Stepl:對輸入空間進行預處理。依據(jù)d劃分單元格，并且統(tǒng)計每個單元格的密度，獲得全部

非空單元格的信息，依據(jù)非空單元格對象的密度大小依次排序并保存在向量隊列Desc(m)中；

Step2:選取初始聚類網(wǎng)格。在向量隊列選取初始聚類網(wǎng)格.從向量隊列Desc(m)中依次取密度

最大的單元格，若是偏網(wǎng)格，則給該單元格作一個待定處理的標識，等全部聚類基本完成后

再打算其的歸屬：假如它是松密集中心網(wǎng)格，并且若它的鄰居單元是一棵聚類樹的節(jié)點，則

將其作為這個鄰居單元的子節(jié)點加入該類；假如其四周沒有聚類，則將它作為一個類的根節(jié)

點建立聚類樹；假如它是緊密集中心網(wǎng)格，則將其作為一個獨立的類，并且是最終類，以后

不參與聚類過程。這樣從向量隊列Desc(m)中最多?。踁n］或［2lnn］個單元格作為聚類樹的根

節(jié)點。

Step3:構建網(wǎng)格聚類樹，依據(jù)上步確定的根節(jié)點，將沒有處理過的鄰近單元格并且是松密集

中心網(wǎng)格作為它的子節(jié)點，假如鄰近單元格是非密集中心網(wǎng)格則等全部聚類基本完成后再打

算其的歸屬，遞歸循環(huán)至沒有鄰近網(wǎng)格的加入。

Step4:依據(jù)上步的結(jié)果，一棵樹即為一個類，假如兩棵樹在聚類過程中有公共的葉子單元

格并且這個單元格是松密集中心網(wǎng)格或偏單元格，則將這兩棵樹合并在一起作為一個類，并

更新類的標示。

Step5:對于待處理的非密集中心網(wǎng)絡，檢測與其相鄰的網(wǎng)格是否屬于同一個類，假如是同一

個類，則將該單元格中的數(shù)據(jù)并入該類；假如不是，則依據(jù)上述對偏單元格的處理方法并入

所屬類。

Step6:檢測零散類，對于沒有標示過和沒有處理過的單元格，為其建立聚類樹，假如樹的層

次在三層以上，則將這些零散節(jié)點作為一個類，賜予一個類標示，否則將其視為離群節(jié)點刪

除。設置此步驟的目的是為了避開遺漏密度較小的聚類。

算法簡單度：

該算法只需掃描一遍數(shù)據(jù)集，假設具有以個數(shù)據(jù)的空間域經(jīng)過網(wǎng)格化預處理后，存在非

奪數(shù)據(jù)單元格數(shù)目為Cne。密集中心網(wǎng)格單元數(shù)為Cden，偏單元格數(shù)為Cdep，則IKMG算法的總

體時間簡單度為O(n)+8O(Cden)+3X4O(Cdep)。

試驗結(jié)果展現(xiàn):

m耕費就

TestDBl5002

TestDB210002

TestDB350002

KddCupl100002

KddCup2500002

KddCupS1000002

算法理解：

IKMG采用網(wǎng)格連通性原理，借助樹形結(jié)構，將多個密集網(wǎng)格單元作為初始根節(jié)點，四

周網(wǎng)格作為它的子節(jié)點，為此類推。試驗結(jié)果也表明白IKMG在數(shù)據(jù)集較大時對比K-Means

大大縮短了處理時間，作者還認為IKMG有效消退了聚類結(jié)果對初始聚類中心的敏感性，而

且無需認為指定K值，能找出不同大小，不同外形的聚類。我的理解是IKMG在肯定程度上優(yōu)

化了k均值算法，但是在算法的輸入中又引入了網(wǎng)格邊長以及網(wǎng)格密度閾值這兩個憑借閱歷

值設定的量，增加的了算法的不穩(wěn)定性；對于聚類數(shù)量的選取并沒有給出合理的數(shù)值，僅僅

是用根號下數(shù)據(jù)集數(shù)量或者是2倍的In數(shù)據(jù)集數(shù)量；此外，試驗也僅僅是驗證了維數(shù)為2的時

候的聚類狀況，并沒有驗證多維數(shù)據(jù)下的IKMG算法的聚類效果。

基于初始點選取的K-Means聚類近似常數(shù)

算法

題目：王守強，朱大銘，韓愛麗等.基于初始點選取的k-means聚類近似常數(shù)算法

[J].計算機討論與進展,2007,44(z2):69-74.

問題描述：

在原始的k-means算法中，選取k個點作為聚類中心，依據(jù)這K個點進行聚類，而在劃分過

程中沒有考察這K個中心點的有效性，即這k個點的代表性。當這K個點恰好是分別屬于k

個不同最優(yōu)聚類簇時，該算法能夠很快收斂；假如這k個點中存在屬于同一簇的狀況，則很

簡潔將本屬于同一簇的數(shù)據(jù)硬性的劃分到其他簇中，從而陷入局部微小，即它依靠于初始化

分?，F(xiàn)在的問題就是如何找出這K個點。

核心算法：

初始點獵取算法：

輸入：點擊P

輸出：初始K個點

Stepl：從集合P中隨機勻稱地選擇一個點c,將其當如集合C中。

Step2:從集合P中選擇下一個點cl,依據(jù)相應的概率選擇某一點作為第i個初始點，使得

點ci距離它最近的中心點的距離最小。

Step3:重復step2,直到選擇K個點為止。

假如從集合P中隨機取k個點，要求這k個點分別屬于不同的最優(yōu)聚類中的點，可采納上述算

法，該算法假如運行1/(1—09)戶次，則以較高概率取得這K個點，使其分別屬于不同的最

優(yōu)聚類簇PI,P2,...PK中的一個點。

局部搜尋算法：

Stepl:從集合P中任選k個點集合作為初始中心點進行K-means聚類劃分，設劃分后的K-means

聚類的解值為t；

Step2:對于一個確定的整數(shù)p,從集合P中選擇p，個點與中心點C中p，個點進行替換，新求得中

心點集合為C:設新的K-means聚類的劃分值為匕假如t，＜t,則置C=C"t=f;

Step3:重復step2,直至t的值不再變化。

K-means聚類局部搜尋算法：

輸入：k個初始中心點

輸出：最小聚類解及相應的K-means聚類劃分

Stepl：設k個初始點為C-以這k個點作為中心點求得一個初始解值t；

對于每一個初始劃分測試全部中的執(zhí)行一個點交換，求得一個新劃分，設對

SteP2：P,Px,

應的解值為匕假如t小于上次運算的解值t,則1=匕C=C\

Step3：重復上述步驟，直到t的值不再變化。

試驗結(jié)果分析與算法理解:

表與傳統(tǒng)聚類相結(jié)合實驗結(jié)果

表2時然版新崩H軸版3hmeans

局部搜索結(jié)合

實嬲麻K色近微短數(shù)歌K值最優(yōu)值近做It

m轆獻Mmeans結(jié)果

Iris2152.347157.6299901.034677348Iris2152,347152.3687291.000142628

378,851483.9600141.064787867378.851478,9408341.001134209

457.228460.4399951.056118903457.228457.3550301.002212713

546.446150.9699861.097400772546,446146,7820931.007234041

639.039943,9199941.125002728639.039939,177475L003523959

734.298238,6899991.128047507734.298234.3880001.002618213

Rusplni289337.8097298.00001.089102261Rusplni289337.8089337.8203131.000000227

351063.4$3390.00001.045562967351063.451155.3906251.001801498

410126.713169.00001.300423633410126.712281.0527341.212739859

58575.4010575.0000,1.23317862758575.4010149.270508L183533189

67126.198945.00001.25522895167126.198597.9560551.206529163

76149.637599.00i.23568409876149.637249.8549801.178909134

85)81.656540.0000001.26214622885181.656272.0698241.210438726

SpathPostal2602546000000703093145600.001.166870489SpathPostal2602546000000649245622272,001.077503829

ZoneData3294506000000294506463232.001.000001573

ZoneData3294506000000318W9024.001.081076409

4104474000000104474689536.001.0000066

4104474000000128375177216.001.22877632

55976150000059761520640.001.000000345