名目

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

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

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

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

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

一種基于網格的改進的K-Means聚類算法.....................................15

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

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

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

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

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

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

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

聚類算法討論

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

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

基本學問儲備與理解：

01、聚類過程與定義：

1）數據預備：包括特征標準化和降維。

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

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

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

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

5）聚類結果評估：是指對聚類結果進行評估.評估主要有3種：外部有效性評估、內部

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

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

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

所謂聚類，就是把大量的d維數據對象（N個）聚集成K個類（K<N）,使同一個類內對象

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

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

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

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

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

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

基于網格的方法：將一個網格內的數據當成一個對象來處理，STING、WaveCluster.

CLIQUE

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

數據是依據潛在的概率分布生成的。

02、層次聚合算法：

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

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

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

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

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

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

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

間進行。將原始數據轉換成正二進制會改善聚類結果的正確性和聚類的魯棒性，對于層

次聚類算法尤其適用。

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

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

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

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

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

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

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

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

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

K均值聚類：

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

其次步：repeat

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

第四步：重新計算每個簇的質心；

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

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

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

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

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

結果為凸形（即類簇為凸形）的數據集。

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

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

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

能給出類的特性描述。

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

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

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

初始modes才能夠聚類分類數據，并且初始modes的差異經常會導致截然不同的聚類結果,

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

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

必需在該類中。

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

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

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

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

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

使用一個網格結構，圍繞模式組織由矩陣塊劃分的值空間，基于塊的分布信息實現模式

聚類。

DBSCAN算法：

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

其次步：刪除噪聲點；

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

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

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

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

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

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

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

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

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

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

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

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

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

ie{1,2}。

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

最短路徑。

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

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

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

CURE算法

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

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

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

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

數據。

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

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

算法

領域專家的直覺。

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

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

CHAMELEON

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

算法

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

子類來找到結果簇?；?/p>

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

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

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

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

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

DIANA算法聚類力量強。

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

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

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

能回溯處理。

特別緊密的簇進行分裂。

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

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

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

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

意外形的聚類。的聚類結構。

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

可以有效揭示數據分布的內在層次，可

基于密度的分基于一組密度分布函數的算法，依

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

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

敏感。

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

缺點：聚類結果嚴峻依靠于用戶參數的

合理選取。

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

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

OPTICS算法

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

聚類結構。點具有局限性。

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

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

STING算法

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

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

基于網格的分信息用于回答查詢。量和精確性。

割聚類算法

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

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

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

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

一個單元中包含的數據超過了某個的擴展性。

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

降低。

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

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

算法加一個多維網格結構來匯總數據，聲和輸入數據的挨次不敏感。

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

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

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

CHAMELEON

提高聚類質量的聚類算法既考慮r量。

算法

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

類。

基于圖論的分

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

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

圖結構來描述對象的空間近鄰，然

AUTOCLUST很少的輸入參數，聚類精度高。

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

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

圖，該算法基于Delaunay三角網進

慮空間對象的屬性。

行計算

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

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

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

目標數據集向各個聚類中心進行重

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

新安排。

量、產生的聚類結果易于解釋。

最近鄰聚類

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

算法一一共

密度不同的數據集上具有很好的聚類

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

效果。

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

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

類算法

規(guī)模數據集。

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

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

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

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

法數據不敏感。

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

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

的質量是否有所提高，若是，則保

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

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

K-Means算法

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

依據該對象與各聚類質心之間的距的收縮性。

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

中，計算每個聚類的新質心，通常形的類，初始質心的選擇對聚類結果有

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

數。

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

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

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

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

低。

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

神經網絡聚i處理，映射至二維平面，實現可質量的聚類結果。

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

某些閱歷參數的選擇。

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

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

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

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

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

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

法

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

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

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

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

基本定義：

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

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

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

實例的屬性值。

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

畫該屬性值的聚集體學問結構。

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

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

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

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

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

有效的。

核心思想：

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

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

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

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

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

02、學問清洗：

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

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

基本學問儲備與理解：

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

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

如基于語義的智能學問搜尋；2、識別出的語義信息可以為現有的web數據進行語義標

注，從而促進語義web遠景的真正實現。

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

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

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

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

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

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

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

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

性約束。

學問抽取技術綜述*

基本學問儲備與理解：

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

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

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

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

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

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

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

個體之間的共識。

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

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

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

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

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

型。

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

對結構化和半結構化文檔的學問抽取：iASA語義標注方法(包括規(guī)章學習模塊、標注

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

學問。

05、面對自由文檔的學問抽?。?/p>

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

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

識別。

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

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

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

的屬性。

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

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

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

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

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

ICG識別出的角色。

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

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

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

基本學問儲備與理解：

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

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

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

正在相互融合、相互借鑒，各自都得到了較大的進展。基于機器學習的學問抽取系統(tǒng),

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

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

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

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

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

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

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

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

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

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

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

過人工定義的模式實現內容標注。

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

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

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

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

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

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

中。

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

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

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

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

1、學問抽取強調語義的抽取。抽取出的內容是有肯定意義的、能被其它上下文所解釋

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

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

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

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

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

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

以對抽取結果進行語義識別和消退歧義；處理抽取結果，抽取結果被關聯到Ontology中，

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

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

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

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

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

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

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

題目：姜彩紅，喬曉東，朱禮軍等.基于本體的專利摘要學問抽取［J］.現代圖書情

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

基本學問儲備與理解：

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

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

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

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

02、抽取流程：數據轉換模塊、中文分詞模塊、本體構建模塊、學問抽取模塊。

本體

構

|中文分聞模塊］建

模

塊

中文專利摘

要文檔集

知

|數據轉換模塊］識

抽

取

模

塊

中文專利

專利知識庫KB

數據庫

03、數據轉換模塊的主要功能是用于對于語料的收集。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

等）。

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

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

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

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

連接作用的動詞（如：連接、鄰接、連接、結合、接觸等）、表示驅動掌握的動詞（如：掌

握、驅動、產生、傳輸、啟動等）以及表示自動反應的動詞（如:旋轉、運轉、伸縮、

分流、滑動等）。

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

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

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

抽取。

抽取的結構存儲在xml文件中，然后通過對GATEAPI的調用對文檔進行批量抽取。

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

問庫。

一種基于網格的改進的K-Means聚類算法

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

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

基本定義：

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

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

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

密集中心網格單元為緊密集中心網格單元；0.25<U<-0.5的密集中心網格單元為松密集中

心網格單元。U>0.5的網格單元稱為非密集中心網格單元。

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

核心算法：

輸入：數據點數n,網格單元寬度d,網格密度閾值s;

輸出：聚類結果

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

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

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

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

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

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

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

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

節(jié)點。

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

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

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

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

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

更新類的標示。

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

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

所屬類。

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

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

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

算法簡單度：

該算法只需掃描一遍數據集，假設具有以個數據的空間域經過網格化預處理后，存在非

奪數據單元格數目為Cne。密集中心網格單元數為Cden，偏單元格數為Cdep，則IKMG算法的總

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

試驗結果展現:

m耕費就

TestDBl5002

TestDB210002

TestDB350002

KddCupl100002

KddCup2500002

KddCupS1000002

算法理解：

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

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

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

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

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

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

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

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

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

算法

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

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

問題描述：

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

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

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

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

分?，F在的問題就是如何找出這K個點。

核心算法：

初始點獵取算法：

輸入：點擊P

輸出：初始K個點

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

Step2:從集合P中選擇下一個點cl,依據相應的概率選擇某一點作為第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:對于一個確定的整數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的值不再變化。

試驗結果分析與算法理解:

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

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

局部搜索結合

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

m轆獻Mmeans結果

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