宗傳玉，憲 超，夏秀峰

（沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽 110136）

0 引言

隨著數(shù)據(jù)源數(shù)量的增長(zhǎng)與數(shù)據(jù)庫技術(shù)的發(fā)展，數(shù)據(jù)可用性的研究得到了廣泛的關(guān)注。由于大部分用戶缺乏必要的專業(yè)知識(shí)，提交的查詢請(qǐng)求可能不能表達(dá)用戶真正的查詢意圖，無法從數(shù)據(jù)庫中得到想要的查詢結(jié)果；但是，這些用戶可以通過提供一些實(shí)例來表達(dá)自己的查詢意圖。因此，為了提高數(shù)據(jù)的可用性，數(shù)據(jù)庫系統(tǒng)應(yīng)該提供一種功能，即根據(jù)用戶提供的實(shí)例為用戶推薦合適的查詢參數(shù)，使用戶能夠根據(jù)推薦的查詢參數(shù)獲得所需的查詢結(jié)果，從而提高數(shù)據(jù)的可用性。

圖數(shù)據(jù)G=（V，E）能夠用于表示數(shù)據(jù)和數(shù)據(jù)間的關(guān)系，其中V用來保存表示實(shí)體的節(jié)點(diǎn)，E用來保存表示實(shí)體間關(guān)系的邊。隨著社交網(wǎng)絡(luò)、合作網(wǎng)絡(luò)、信息網(wǎng)絡(luò)、通信網(wǎng)絡(luò)等應(yīng)用的迅速發(fā)展，有效地對(duì)圖數(shù)據(jù)進(jìn)行管理和分析已經(jīng)成為眾多學(xué)者們研究的熱點(diǎn)?；趫D結(jié)構(gòu)的聚類（圖結(jié)構(gòu)聚類）得到了廣泛的研究。執(zhí)行圖結(jié)構(gòu)聚類后，圖中聯(lián)系緊密的節(jié)點(diǎn)被聚類到相同的簇中，聯(lián)系分散的節(jié)點(diǎn)被聚類到不同的簇中，剩余一些沒有被聚類到簇中的節(jié)點(diǎn)又被劃分為橋節(jié)點(diǎn)與離群節(jié)點(diǎn)。

pSCAN（pruned Structural Clustering Algorithm for Networks）算法［1］是一個(gè)快速且準(zhǔn)確的圖結(jié)構(gòu)聚類算法，該算法根據(jù)兩個(gè)聚類參數(shù)生成聚類結(jié)果，一個(gè)是密度約束μ，另一個(gè)是相似度閾值ε。給定一個(gè)社交網(wǎng)絡(luò)圖G=（V，E），x和y為圖G中的兩個(gè)節(jié)點(diǎn)，N［x］用來表示節(jié)點(diǎn)x的鄰居集合，集合中包含節(jié)點(diǎn)x本身。σ（x，y）用于表示兩個(gè)節(jié)點(diǎn)x和y之間的結(jié)構(gòu)相似度，這個(gè)值由x和y的各自鄰居數(shù)量與公共鄰居數(shù)量決定，結(jié)構(gòu)相似度越大，說明兩個(gè)節(jié)點(diǎn)的關(guān)系越密切，當(dāng)結(jié)構(gòu)相似度不小于ε時(shí)，x和y兩個(gè)節(jié)點(diǎn)互為ε-鄰居。

pSCAN 算法的聚類過程如下：計(jì)算每個(gè)節(jié)點(diǎn)的ε-鄰居數(shù)量，如果某個(gè)節(jié)點(diǎn)x的ε-鄰居數(shù)量不少于密度約束μ，x是一個(gè)核心節(jié)點(diǎn)。核心節(jié)點(diǎn)x將形成一個(gè)簇C，隨后C將迭代地吸收該簇中的核心節(jié)點(diǎn)的ε-鄰居中的核心節(jié)點(diǎn)，C將以這種機(jī)制持續(xù)擴(kuò)大，直到?jīng)]有新的核心節(jié)點(diǎn)加入為止。等到所有的核心節(jié)點(diǎn)都被聚類到不同的簇中后，最后將每一個(gè)簇中核心節(jié)點(diǎn)的ε-鄰居中的非核心節(jié)點(diǎn)聚類到相應(yīng)的簇中，直到處理完所有的節(jié)點(diǎn)。此外，對(duì)于不屬于任何一個(gè)簇的節(jié)點(diǎn)x，如果x的鄰居屬于兩個(gè)或以上的簇，那么x是一個(gè)橋節(jié)點(diǎn)；否則，x是一個(gè)離群節(jié)點(diǎn)。

如圖1 所示，當(dāng)參數(shù)ε=0.61、μ=4 時(shí)，可以得到一個(gè)簇C1=｛v1，v2，v3，v4，v5，v6，v7，v8，v9｝。因?yàn)関10、v11、v12不屬于任何一個(gè)簇，并且每個(gè)節(jié)點(diǎn)的鄰居不屬于兩個(gè)或兩個(gè)以上的簇，所以v10、v11、v12三個(gè)節(jié)點(diǎn)是離群節(jié)點(diǎn)。

圖1 圖結(jié)構(gòu)聚類實(shí)例Fig.1 Example of structural graph clustering

由于大部分用戶缺乏必要的專業(yè)知識(shí)，無法為pSCAN算法提供合適的參數(shù)，隨意設(shè)置參數(shù)很難得到想要的結(jié)果。然而，對(duì)于這些用戶來說，雖然不能提供合適的聚類參數(shù)，但是根據(jù)一些背景知識(shí)能夠提供一些實(shí)例簇，比如某一組技術(shù)人員的研究方向相同且屬于同一個(gè)部門，他們應(yīng)該屬于同一個(gè)簇。對(duì)于數(shù)據(jù)庫系統(tǒng)來說，提供根據(jù)用戶提供的實(shí)例為用戶推薦合適的查詢參數(shù)的功能是十分重要并且有用的［2］。目前，基于用戶實(shí)例來探究用戶查詢意圖已經(jīng)成為數(shù)據(jù)庫領(lǐng)域的一個(gè)研究熱點(diǎn)?；诿芏鹊膱D結(jié)構(gòu)聚類算法主要有SCAN（Structural Clustering Algorithm for Networks）算 法［3］、SCAN++（Structural Clustering Algorithm for Networks++）算法［4］以及pSCAN 算法等，pSCAN 算法是目前效率最高的圖結(jié)構(gòu)聚類算法，因此，本文以pSCAN 算法作為研究基礎(chǔ)。

如圖1 所示，假設(shè)用戶不能提供合理的聚類參數(shù)，但是根據(jù)一些已有的背景知識(shí)，用戶知道，｛v1，v2，v3，v4，v5，v6，v7，v8，v9｝應(yīng)該屬于同一個(gè)簇，那么如何根據(jù)這個(gè)實(shí)例簇為用戶返回合理的聚類參數(shù)是本文要研究的主要內(nèi)容。為了解決這類問題，本文提出了一種實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算算法，使得系統(tǒng)返回的聚類參數(shù)能夠?qū)⒂脩籼峁┑膶?shí)例簇節(jié)點(diǎn)聚類在同一個(gè)簇中，且不包含其他非實(shí)例簇的節(jié)點(diǎn)。用戶只需要向系統(tǒng)提交一些實(shí)例簇來表達(dá)自己的聚類需求，就可以獲得在該實(shí)例簇需求下的有效聚類參數(shù)。用戶再根據(jù)有效聚類參數(shù)執(zhí)行pSCAN 算法，便可以得到想要的聚類結(jié)果，這樣既可以幫助用戶更好地理解圖結(jié)構(gòu)聚類操作，又可以有效提高圖數(shù)據(jù)庫的可用性。

對(duì)于結(jié)構(gòu)龐大的圖結(jié)構(gòu)數(shù)據(jù)來說，得到有效的聚類參數(shù)來使得用戶提供的實(shí)例簇節(jié)點(diǎn)能夠聚類在同一個(gè)簇中的代價(jià)十分昂貴。因此，實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算算法的主要挑戰(zhàn)是如何基于實(shí)例簇快速且準(zhǔn)確地得到滿足實(shí)例簇需求的聚類參數(shù)。此外，滿足實(shí)例簇需求的有效聚類參數(shù)往往不止一個(gè)，如何得到滿足實(shí)例簇需求的最優(yōu)聚類參數(shù)也是本文研究的一個(gè)重點(diǎn)。

綜上，本文的主要工作如下：

1）構(gòu)建了一個(gè)實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算算法框架，該框架包含獲取子圖、劃分節(jié)點(diǎn)和計(jì)算并驗(yàn)證聚類參數(shù)3 個(gè)模塊。

2）為了使實(shí)例簇中的節(jié)點(diǎn)能夠形成一個(gè)簇，提出了兩個(gè)有效的實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算算法，為用戶返回滿足實(shí)例簇需求的最優(yōu)聚類參數(shù)。

3）在3 個(gè)真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了大量的實(shí)驗(yàn)，結(jié)果表明提出的算法能夠基于實(shí)例簇有效地返回滿足用戶需求的最優(yōu)聚類參數(shù)。

1 相關(guān)工作

1.1 圖結(jié)構(gòu)聚類

很多學(xué)者對(duì)于圖結(jié)構(gòu)聚類提出了不同的算法。Xu 等［3］提出了SCAN 算法，它是一種根據(jù)結(jié)構(gòu)相似度來將圖中節(jié)點(diǎn)進(jìn)行聚類的算法。Chang 等［1］提出了一種能夠減少結(jié)構(gòu)相似度計(jì)算次數(shù)的新方法pSCAN 算法，它是一種基于SCAN 算法的圖結(jié)構(gòu)聚類算法，性能要高于SCAN 算法。由于pSCAN 算法計(jì)算量巨大，學(xué)者們不斷在此基礎(chǔ)上進(jìn)行剪枝以減少計(jì)算量：Ruan 等［5］研究了具有 Jaccard 相似性和余弦相似性的邊緣插入和刪除的圖結(jié)構(gòu)聚類算法；Shiokawa 等［6］研究的DSCAN（Distributed Structural Clustering Algorithm for Networks）是一種采用邊緣修剪技術(shù)來減少分布式算法的通信和計(jì)算開銷的圖結(jié)構(gòu)聚類算法；Yu 等［7］研究了基于動(dòng)態(tài)規(guī)劃的穩(wěn)定結(jié)構(gòu)聚類算法，能夠在不確定圖中聚類；Tseng等［8］提出了一種基于并行索引的近似SCAN 算法，并行索引查詢比GS*-Index（Graph Structure Index）更快；Liang 等［9］研究 的 probSCAN（Prob Structural Clustering Algorithm for Networks）是一種基于分解的算法，它包含一個(gè)具有成本效益的索引結(jié)構(gòu)，以加快圖中結(jié)構(gòu)相似度計(jì)算；Zong 等［10］針對(duì)動(dòng)態(tài)變化的參數(shù)研究了兩種有效的增量聚類算法，避免SCAN 算法的重復(fù)執(zhí)行；Seo 等［11］研究了用于圖結(jié)構(gòu)聚類的高效算法，能夠?yàn)榉浅４蟮膱D提供可擴(kuò)展性能；Shiokawa等［4］研究的SCAN++算法是一種引入直接兩跳可達(dá)節(jié)點(diǎn)的圖聚類算法。

1.2 實(shí)例驅(qū)動(dòng)的查詢構(gòu)造方法

許多學(xué)者提出了不同的基于實(shí)例進(jìn)行查詢的方法：Shen等［2］提出了一種通過實(shí)例進(jìn)行查詢的方法，以用戶查詢作為用戶興趣數(shù)據(jù)的實(shí)例并加以實(shí)現(xiàn)；Fariha 等［12］提出了一種稱為SQuID（semantic Similarity-aware Query Intent Discovery）的算法，通過用戶提供的幾個(gè)例子來推斷用戶的意圖，從而完成用戶的查詢，這種查詢可以令沒有專業(yè)知識(shí)的用戶進(jìn)行專業(yè)查詢；Khwildi 等［13］提出了一種針對(duì)高動(dòng)態(tài)范圍（High-Dynamic Range，HDR）圖像的高效檢索系統(tǒng)；Sarwar 等［14］提出了一種基于語義角色標(biāo)簽的方法來識(shí)別事件跨度的無監(jiān)督查詢算法；Adamou 等［15］研究了針對(duì)未知數(shù)據(jù)集查詢時(shí)基于示例的星形查詢，可以通過用戶對(duì)其他數(shù)據(jù)的查詢推薦未知數(shù)據(jù)集的查詢；Rezig 等［16］研究了一個(gè)通過用戶提供的示例記錄的方法DICE（Data dIsCovery by Example），合成查詢捕獲用戶意圖，返回更多滿足用戶意圖的記錄；Qin 等［17］研究了一個(gè)數(shù)據(jù)探測(cè)系統(tǒng)，可以找到用戶想要的元組，并在交互中對(duì)所需元組進(jìn)行偏好排序；Jiang 等［18］提出了一種利用樣例影片對(duì)期望的拍攝方法進(jìn)行控制的運(yùn)動(dòng)控制器；Thakkar 等［19］提出的EGS（Example-Guided Synthesis）通過用戶提供的實(shí)例的潛在結(jié)構(gòu)生成關(guān)系查詢；Fariha 等［20］提出的SuDocu（Summarizing Documents）是一個(gè)由用戶提供示例摘要反映用戶摘要意圖的文檔摘要系統(tǒng)。本文的算法也是基于QBE（Query By Example）思想，通過少量的實(shí)例簇進(jìn)行計(jì)算，得到滿足用戶實(shí)例簇的最優(yōu)聚類參數(shù)。

2 預(yù)備知識(shí)與問題定義

在本章中，首先描述一些重要的符號(hào)和定義；然后，形式化定義了實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算。

2.1 相關(guān)定義

在說明實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算問題之前，首先介紹一些與圖結(jié)構(gòu)聚類參數(shù)計(jì)算有關(guān)的重要概念，例如結(jié)構(gòu)相似度、ε-鄰居、核心節(jié)點(diǎn)、結(jié)構(gòu)可達(dá)等。

定義1結(jié)構(gòu)相似度。給定圖G=（V，E）中的兩個(gè)節(jié)點(diǎn)u和v，則u和v的結(jié)構(gòu)相似度定義為σ（u，v）：

定義2ε-鄰居。給定一個(gè)相似度閾值ε、一個(gè)節(jié)點(diǎn)v以及它的一個(gè)鄰居u，如果v與u的結(jié)構(gòu)相似度大于或等于相似度閾值ε，那么u和v互稱為對(duì)方的ε-鄰居，v的ε-鄰居集合如式（2）所示：

定義3核心節(jié)點(diǎn)。給定相似度閾值ε，密度約束μ和一個(gè)節(jié)點(diǎn)v，如果v的ε-鄰居集合中節(jié)點(diǎn)個(gè)數(shù)大于μ，v被稱為核心節(jié)點(diǎn)；否則，v被稱為非核心節(jié)點(diǎn)。

定義4結(jié)構(gòu)可達(dá)。給定兩個(gè)節(jié)點(diǎn)u和v，相似度閾值ε和密度約束μ，如果存在一個(gè)節(jié)點(diǎn)序列x1，x2，…，xn(n≥2)，并且u=x1，v=xn，且滿足以下條件：

則稱節(jié)點(diǎn)v能夠從u結(jié)構(gòu)可達(dá)。

2.2 問題描述

通過分析pSCAN 算法的聚類原理可知，滿足用戶提交的實(shí)例簇需求的聚類參數(shù)可能有多個(gè)。如圖1 所示，假設(shè)用戶提交的實(shí)例簇為C1，滿足該實(shí)例簇的聚類參數(shù)有多個(gè)，聚類參數(shù)為μ1=4、ε1=0.58 時(shí)，得到的聚類結(jié)果為R1=｛v1，v2，v3，v4，v5，v6，v7，v8，v9｝；當(dāng)聚類參數(shù)為μ2=3、ε2=0.5 時(shí)，得到的聚類結(jié)果為R2=｛v1，v2，v3，v4，v5，v6，v7，v9，v10，v11，v12｝。通過比較可以發(fā)現(xiàn)，為用戶返回第一組聚類參數(shù)，用戶執(zhí)行該參數(shù)后得到的聚類結(jié)果更能滿足用戶的實(shí)例簇需求。此外，參數(shù)值越大，聚類條件也就越嚴(yán)格，返回的冗余節(jié)點(diǎn)和冗余簇也就越少。因此，為了提高聚類參數(shù)質(zhì)量，本文將能夠使得實(shí)例簇中節(jié)點(diǎn)成為一個(gè)簇的參數(shù)的最大值（即上限）稱為最優(yōu)聚類參數(shù)。而實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算算法是指根據(jù)用戶提交的實(shí)例簇，為用戶返回滿足實(shí)例簇需求的最優(yōu)聚類參數(shù)。綜上，本文的問題定義如下：

問題定義：給定一個(gè)圖數(shù)據(jù)集D，一個(gè)實(shí)例簇C=｛v1，v2，…，vn｝，實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算是指如何快速找到能夠使得C中節(jié)點(diǎn)成為一個(gè)簇的最優(yōu)聚類參數(shù)μopt，εopt，當(dāng)用戶在D上基于最優(yōu)參數(shù)執(zhí)行pSCAN 算法時(shí)能夠得到一個(gè)聚類結(jié)果R，且R應(yīng)滿足如下條件：

3 pSCAN結(jié)果的影響因素

在本章中，首先，介紹了實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算算法框架；然后，討論了聚類參數(shù)ε和μ對(duì)pSCAN 結(jié)果的影響。

3.1 算法框架

通過分析pSCAN 算法可知，pSCAN 算法的聚類結(jié)果中的每一個(gè)簇只可能包含兩類節(jié)點(diǎn)：核心節(jié)點(diǎn)和非核心節(jié)點(diǎn)。此外，密度約束μ是一個(gè)有限的整數(shù)。實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算算法的思路是首先根據(jù)實(shí)例簇獲得密度約束μ的可行區(qū)間；然后基于每一個(gè)可用的密度約束μ，計(jì)算滿足實(shí)例簇需求的相似度閾值參數(shù)ε的最大值（最優(yōu)值）并對(duì)獲得的參數(shù)進(jìn)行驗(yàn)證；最后返回滿足實(shí)例簇需求的最優(yōu)聚類參數(shù)。本文構(gòu)建了一個(gè)實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算算法框架，如圖2 所示。該框架包括獲取子圖、劃分節(jié)點(diǎn)和計(jì)算并驗(yàn)證聚類參數(shù)3 個(gè)模塊。

圖2 實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)參數(shù)計(jì)算算法框架Fig.2 Framework of instance-cluster-driven structural graph parameter calculation algorithm

1）獲取子圖：在該模塊中，根據(jù)給定的實(shí)例簇C從圖數(shù)據(jù)集D獲取與C相關(guān)的子圖H，H需滿足如下條件：

①子圖H包含C中所有節(jié)點(diǎn)及C中節(jié)點(diǎn)的鄰居。

②子圖H包含D中至少一個(gè)節(jié)點(diǎn)屬于C的邊。

2）劃分節(jié)點(diǎn)：首先根據(jù)子圖H計(jì)算出密度約束μ的可行區(qū)間。然后根據(jù)區(qū)間中每一個(gè)可行μ計(jì)算出對(duì)應(yīng)的最大相似度閾值ε。因?yàn)橐粋€(gè)簇是由互相結(jié)構(gòu)可達(dá)的核心節(jié)點(diǎn)和從這些核心節(jié)點(diǎn)結(jié)構(gòu)可達(dá)的非核心節(jié)點(diǎn)構(gòu)成的，為了得到每個(gè)μ對(duì)應(yīng)的最優(yōu)的ε，首先根據(jù)μ對(duì)實(shí)例簇中的節(jié)點(diǎn)進(jìn)行劃分并根據(jù)劃分后的節(jié)點(diǎn)計(jì)算ε，并不斷地優(yōu)化ε值來優(yōu)化對(duì)實(shí)例簇中節(jié)點(diǎn)的劃分，直到滿足以下條件：

①實(shí)例簇C中的所有核心節(jié)點(diǎn)互相結(jié)構(gòu)可達(dá)。

②實(shí)例簇C中所有的非核心節(jié)點(diǎn)都至少與一個(gè)核心節(jié)點(diǎn)結(jié)構(gòu)可達(dá)。

3）計(jì)算并驗(yàn)證聚類參數(shù)：通過劃分核心節(jié)點(diǎn)與非核心節(jié)點(diǎn)來獲得每一個(gè)密度約束μ下對(duì)應(yīng)的最優(yōu)相似度閾值ε。由于劃分節(jié)點(diǎn)可以獲得滿足實(shí)例簇的最大結(jié)構(gòu)相似度，并且在相同密度約束μ下，相似度閾值ε越大，聚類效果越好。因此，認(rèn)為滿足當(dāng)前節(jié)點(diǎn)劃分的最大ε時(shí)就是當(dāng)前μ所對(duì)應(yīng)的最優(yōu)ε。然后在H上驗(yàn)證當(dāng)前得到的參數(shù)μi和εi得到Hi。如果滿足實(shí)例簇需求，則計(jì)算終止，否則計(jì)算并驗(yàn)證下一個(gè)可用μi+1所對(duì)應(yīng)的最優(yōu)εi+1，直到滿足實(shí)例簇需求為止。

3.2 不同參數(shù)對(duì)查詢結(jié)果的影響

不同聚類參數(shù)會(huì)產(chǎn)生不同的聚類結(jié)果。在相同密度約束下，相似度閾值越大，聚類條件越嚴(yán)格，聚類結(jié)果越不可能包含冗余節(jié)點(diǎn)和冗余簇。如圖3（a）所示，當(dāng)聚類參數(shù)為μ=4、ε=0.61 時(shí)，得到聚類結(jié)果={v1，v2，v3，v4，v5，v6，v7，v8，v9}；當(dāng)聚類參數(shù)μ=4 不變，參數(shù)ε增大為ε=0.61時(shí)，得到聚類結(jié)果=｛v1，v2，v3，v4，v5，v6，v7，v9｝，如圖3（b）所示。類似地，在相同相似度閾值下，密度約束越大，聚類條件越嚴(yán)格，如圖3（c）和圖3（d）所示，當(dāng)聚類參數(shù)為μ=5、ε=0.58 時(shí)，得到聚類結(jié)果=｛v1，v2，v3，v4，v5，v6，v7，v8，v9｝；當(dāng)聚類參數(shù)ε=0.58 不變，參數(shù)μ減小為μ=5時(shí)，得到聚類結(jié)果=｛v1，v2，v3，v4，v5｝。上述分析進(jìn)一步說明了參數(shù)值越大，聚類條件越嚴(yán)格，得到的聚類參數(shù)越能滿足用戶實(shí)例簇的需求，執(zhí)行最優(yōu)聚類參數(shù)后得到的冗余簇就越少。

圖3 不同參數(shù)下的聚類結(jié)果Fig.3 Clustering results under different parameters

4 算法與定理

4.1 定理及證明

綜上所述，首先需要計(jì)算的是密度約束μ的可行區(qū)間，為了獲得更高的效率，在這一步應(yīng)盡可能縮小這個(gè)可行區(qū)間，一個(gè)重要的定理如下：

定理1如果一個(gè)節(jié)點(diǎn)x∈V，d[x]<μ，那么x一定不是核心節(jié)點(diǎn)。

證明x是一個(gè)核心節(jié)點(diǎn)需要滿足條件，|Nε(x) |≥μ，并且|Nε(x) |≤|N[x] |=d[x]，即d[x]≥μ，如果不滿足，則x不可能是一個(gè)核心節(jié)點(diǎn)。

如圖3（a）所示，d[v7]= |{v2，v6，v7} |=3 <4=μ，所以v7不可能是一個(gè)核心節(jié)點(diǎn)。

引理1如果實(shí)例簇C中的一個(gè)節(jié)點(diǎn)x是非核心節(jié)點(diǎn)，那么x的鄰居中至少有一個(gè)節(jié)點(diǎn)y是核心節(jié)點(diǎn)。

證明 pSCAN 聚類算法執(zhí)行后，核心節(jié)點(diǎn)會(huì)生成一個(gè)簇C，C中的核心節(jié)點(diǎn)迭代地吸收核心節(jié)點(diǎn)的ε-鄰居節(jié)點(diǎn)，如果有一個(gè)非核心節(jié)點(diǎn)x的鄰居中沒有核心節(jié)點(diǎn)，那么x將無法被聚類到簇中。也就是說非核心節(jié)點(diǎn)的鄰居中必然有一個(gè)是核心節(jié)點(diǎn)，該非核心節(jié)點(diǎn)才有可能出現(xiàn)在聚類結(jié)果中。

如圖3（a）所示，如果v7被劃分為非核心節(jié)點(diǎn)，那么v2和v6之中必定有一個(gè)是核心節(jié)點(diǎn)，這樣生成的簇才能夠包含v7。

在滿足引理1 后，可以保證實(shí)例簇C中所有節(jié)點(diǎn)被聚類到簇中，但是無法保證這些節(jié)點(diǎn)被聚類到同一個(gè)簇中，因?yàn)榭赡軙?huì)出現(xiàn)核心節(jié)點(diǎn)與非核心節(jié)點(diǎn)結(jié)構(gòu)不可達(dá)的情況，或者會(huì)出現(xiàn)核心節(jié)點(diǎn)之間結(jié)構(gòu)不可達(dá)的情況，會(huì)導(dǎo)致這些節(jié)點(diǎn)被聚類到兩個(gè)或者兩個(gè)以上的簇中。此時(shí)得到的ε值過大，可以再繼續(xù)減小ε的值，使這些節(jié)點(diǎn)被聚類到同一個(gè)簇中，一個(gè)重要的引理如下：

引理2如果實(shí)例簇C中的每個(gè)非核心節(jié)點(diǎn)都有一個(gè)核心節(jié)點(diǎn)的ε-鄰居，且C中的每個(gè)核心節(jié)點(diǎn)都相互結(jié)構(gòu)可達(dá)，那么C中的節(jié)點(diǎn)就能構(gòu)成一個(gè)簇。

此外，本文引入了以下定義：

定義5核心節(jié)點(diǎn)最大相似度閾值。給定一個(gè)節(jié)點(diǎn)v，密度約束μ，節(jié)點(diǎn)v的核心節(jié)點(diǎn)最大相似度閾值返回在當(dāng)前密度約束μ下，節(jié)點(diǎn)v能成為核心節(jié)點(diǎn)時(shí)相似度閾值ε的最大取值，形式化定義為Epμ(v)：

其中：maxμ表示向量中元素從大到小排列的第μ個(gè)值。如果當(dāng)前ε取值小于等于Epμ(v)時(shí)，v是一個(gè)核心節(jié)點(diǎn)；否則，v是一個(gè)非核心節(jié)點(diǎn)。

如圖4 所示，Ep4(v6)=σ(v1，v6)=0.73，當(dāng)ε≤0.73 時(shí)，v6是核心節(jié)點(diǎn)，當(dāng)ε>0.73 時(shí)，v6是非核心節(jié)點(diǎn)。

4.2 實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算的基本算法

根據(jù)上述定理和引理，將實(shí)例簇中的所有節(jié)點(diǎn)劃分為核心節(jié)點(diǎn)和非核心節(jié)點(diǎn)，針對(duì)可行區(qū)間內(nèi)的每一個(gè)μ計(jì)算得到一個(gè)對(duì)應(yīng)的最優(yōu)參數(shù)ε。算法1 的偽代碼如下：

算法1 實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算的基本算法（PART）。

首先通過輸入圖數(shù)據(jù)集D、實(shí)例簇Cs（第1）行）獲取Cs相關(guān)的子圖結(jié)構(gòu)。根據(jù)子圖結(jié)構(gòu)，可以得到密度約束μ的可行區(qū)間（第2）行），接下來對(duì)可能區(qū)間內(nèi)的最大μ進(jìn)行計(jì)算（第3）行）。根據(jù)定理1，將Cs中的部分節(jié)點(diǎn)劃分為非核心節(jié)點(diǎn)（第4）～8）行）。對(duì)Cs中未確定的節(jié)點(diǎn)，計(jì)算它們的核心節(jié)點(diǎn)最大相似度閾值（第9）～10）行）。在未確定的節(jié)點(diǎn)中，找到一個(gè)核心節(jié)點(diǎn)最大相似度閾值最小的節(jié)點(diǎn)作為非核心節(jié)點(diǎn)，并在該非核心節(jié)點(diǎn)的鄰居中找到一個(gè)核心節(jié)點(diǎn)最大相似度閾值最大的節(jié)點(diǎn)作為核心節(jié)點(diǎn)，如果當(dāng)前ε值大于該核心節(jié)點(diǎn)的最大相似度閾值，則更新ε為該核心節(jié)點(diǎn)的最大相似度閾值（第11）～19）行），然后將所有核心節(jié)點(diǎn)最大相似度閾值大于當(dāng)前ε的未確定節(jié)點(diǎn)劃分為核心節(jié)點(diǎn)（第20）～23）行），接下來，重復(fù)上述步驟，劃分非核心節(jié)點(diǎn)和核心節(jié)點(diǎn)并更新ε，直到所有節(jié)點(diǎn)均被劃分為核心節(jié)點(diǎn)或非核心節(jié)點(diǎn)（第11）～24）行）。接下來檢驗(yàn)當(dāng)前ε，如果成功聚類為同一個(gè)簇，并且簇中不包含Cs外的節(jié)點(diǎn)，則停止計(jì)算，輸出當(dāng)前μ和ε（第25）～27）行）；如果不能成功聚類為同一個(gè)簇，或者檢驗(yàn)時(shí)可以得到同一個(gè)簇，但簇中包含Cs以外的其他節(jié)點(diǎn)，或者計(jì)算得到的ε值為0，則認(rèn)為當(dāng)前μ值時(shí)無解，更新μ=μ-1（第28）～29）行），再重新進(jìn)行計(jì)算，直到能夠成功聚類為同一個(gè)簇為止（第3）～30）行）。最后輸出μopt，εopt（第31）行）。

如圖4 所示：首先找到μ可行區(qū)間［2，5］，對(duì)于最大值μ=5，首先將C中節(jié)點(diǎn)v5，v7，v8，v9劃分為非核心節(jié)點(diǎn)，然后計(jì)算v1，v2，v3，v4，v5，v6的核心節(jié)點(diǎn)最大相似度閾值，選擇最大核心節(jié)點(diǎn)最大相似度閾值的節(jié)點(diǎn)作為核心節(jié)點(diǎn)，將v1，v3，v4，v6劃為核心節(jié)點(diǎn)，此時(shí)得到ε=0.58；再選擇最小核心節(jié)點(diǎn)最大相似度閾值的節(jié)點(diǎn)作為非核心節(jié)點(diǎn)，將v2劃分為非核心節(jié)點(diǎn)，此時(shí)C中所有節(jié)點(diǎn)均被劃分為核心點(diǎn)或非核心點(diǎn)；檢驗(yàn)當(dāng)前參數(shù)下實(shí)例簇C中所有節(jié)點(diǎn)被聚到同一簇中，且不包含任何簇外節(jié)點(diǎn)。最后返回最優(yōu)參數(shù)為μopt=5，εopt=0.58。

圖4 算法1的實(shí)例Fig.4 Example of Algorithm 1

4.3 實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算的改進(jìn)算法

由于算法1 計(jì)算所需的時(shí)間較長(zhǎng)，對(duì)算法1 進(jìn)行了改進(jìn)和優(yōu)化，在保證精度的前提下，提高了計(jì)算效率。

根據(jù)以下引理能夠提高判斷一個(gè)節(jié)點(diǎn)是否是核心節(jié)點(diǎn)的效率。

引理3如果一個(gè)節(jié)點(diǎn)已被計(jì)算的ε-鄰居數(shù)量大于等于μ時(shí)，這個(gè)節(jié)點(diǎn)一定是核心節(jié)點(diǎn)。

如圖4 所示，根據(jù)引理1，假設(shè)當(dāng)前μ=4，當(dāng)計(jì)算出｛v1，v2，v3，v4｝為v1的ε-鄰居后，無論v5，v6與v1之間的結(jié)構(gòu)相似度為多少，v1都會(huì)是一個(gè)核心節(jié)點(diǎn)，因此，不需要再計(jì)算v5，v6與v1之間的結(jié)構(gòu)相似度，可以節(jié)省大量的計(jì)算。

算法1 中會(huì)出現(xiàn)核心節(jié)點(diǎn)與非核心節(jié)點(diǎn)結(jié)構(gòu)不可達(dá)的情況，因此引入以下定義來提高構(gòu)建核心節(jié)點(diǎn)與非核心節(jié)點(diǎn)結(jié)構(gòu)可達(dá)路徑的效率。

定義6最大結(jié)構(gòu)可達(dá)相似度閾值。給定兩個(gè)節(jié)點(diǎn)u和v，密度約束μ，u和v的最大結(jié)構(gòu)可達(dá)相似度閾值為u的核心節(jié)點(diǎn)最大相似度閾值和它與鄰居v的結(jié)構(gòu)相似度中的較小值，將其形式化定義為Mepμ（u，v）：

當(dāng)ε≤Mepμ(u，v)時(shí)，u是一個(gè)核心節(jié)點(diǎn)，并且v是u的ε-鄰居，u可以將v聚類到自己所在的簇中。當(dāng)ε>Mepμ(u，v)時(shí)，要么u是一個(gè)非核心節(jié)點(diǎn)，要么v不是u的ε-鄰居，在這兩種情況下，u都不可以將v聚類到自己所在的簇中。

如圖4（b）所示，Mep4(v3，v8)=min｛0.61，0.58｝=0.58：當(dāng)ε≤0.58 時(shí)，v3可以將v8聚類到自己所在簇中；當(dāng)ε>0.58 時(shí)，v3不能將v8聚類到自己所在簇中；當(dāng)ε=0.61 時(shí)，v8成為離群節(jié)點(diǎn)。

為了提高檢驗(yàn)節(jié)點(diǎn)之間構(gòu)建結(jié)構(gòu)可達(dá)路徑的效率，引入以下引理，只需要判斷核心節(jié)點(diǎn)之間結(jié)構(gòu)可達(dá)就可以滿足引理2 的需求。

引理4對(duì)于聚類結(jié)果C中的每個(gè)核心節(jié)點(diǎn)，如果核心節(jié)點(diǎn)之間相互結(jié)構(gòu)可達(dá)，C中節(jié)點(diǎn)就能夠構(gòu)成一個(gè)簇。

如圖1 所示，聚類結(jié)果中的簇C1中，核心節(jié)點(diǎn)v1，v2，v3，v4，v5，v6都是相互結(jié)構(gòu)可達(dá)的。

依據(jù)引理3 和定義6 可以減少節(jié)點(diǎn)之間結(jié)構(gòu)相似度的計(jì)算，依據(jù)引理4 可以減少節(jié)點(diǎn)之間構(gòu)建結(jié)構(gòu)可達(dá)路徑的檢驗(yàn)。改進(jìn)后算法的偽代碼如算法2 所示。

算法2 實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算的改進(jìn)算法（ImPART）。

首先通過輸入圖結(jié)構(gòu)D、實(shí)例簇Cs（第1）行）提取Cs及其周圍節(jié)點(diǎn)的子圖結(jié)構(gòu)。根據(jù)子圖結(jié)構(gòu)，可以得到密度約束μ的可能區(qū)間（第2）行），接下來對(duì)可能區(qū)間內(nèi)的最大μ進(jìn)行計(jì)算（第3）行）。首先劃分得到一部分非核心節(jié)點(diǎn)（第4）～6）行）。然后根據(jù)引理2，對(duì)每一個(gè)非核心節(jié)點(diǎn)，計(jì)算每一個(gè)鄰居的最大結(jié)構(gòu)可達(dá)相似度閾值，將最大結(jié)構(gòu)可達(dá)相似度閾值最大值鄰居劃分為核心節(jié)點(diǎn)（第7）～9）行）。如果當(dāng)前ε大于該核心節(jié)點(diǎn)的最大結(jié)構(gòu)可達(dá)相似度閾值，則更新ε為該核心節(jié)點(diǎn)的最大結(jié)構(gòu)可達(dá)相似度閾值（第10）～11）行）。接下來根據(jù)引理1 計(jì)算剩余未確定節(jié)點(diǎn)的核心節(jié)點(diǎn)最大相似度閾值（第14）～21）行），類似PART 算法劃分核心節(jié)點(diǎn)和非核心節(jié)點(diǎn)并更新ε，直到所有節(jié)點(diǎn)均被劃分為核心節(jié)點(diǎn)或非核心節(jié)點(diǎn)（第22）～33）行），接下來檢驗(yàn)當(dāng)前ε能否成功聚類為同一個(gè)簇（第25）～30）行），如果能夠成功聚類，則輸出當(dāng)前μ和ε；如果核心節(jié)點(diǎn)之間不能夠相互結(jié)構(gòu)可達(dá)或者核心節(jié)點(diǎn)和簇外節(jié)點(diǎn)結(jié)構(gòu)可達(dá)或者得到的ε為0，則降低μ，對(duì)更新后的μ重新計(jì)算ε（第3）～30）行）。最后輸出最優(yōu)聚類參數(shù)μopt，εopt（第31）行）或者空集。

5 實(shí)驗(yàn)及結(jié)果分析

在本章中，通過大量實(shí)驗(yàn)來評(píng)估實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算算法PART 和ImPART 的性能。

5.1 數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

數(shù)據(jù)集（http：//snap.stanford.edu/data/）的說明如下：

ego-Facebook：ego-Facebook 是一個(gè)來自Facebook 的用戶社交關(guān)系網(wǎng)絡(luò)數(shù)據(jù)。該數(shù)據(jù)集包含4 039 個(gè)節(jié)點(diǎn)和88 234 條邊，為相對(duì)稠密的圖。

p2p-Gnutella31：p2p-Gnutella31 是一個(gè)來自Gnutella 的從2002 年8 月開始收集的對(duì)等文件共享網(wǎng)絡(luò)數(shù)據(jù)。該數(shù)據(jù)集包含62 586 個(gè)節(jié)點(diǎn)和147 892 條邊，為稀疏圖。

Slashdot0902：Slashdot0902 是一個(gè)來自Slashdot 的用戶社交關(guān)系網(wǎng)絡(luò)數(shù)據(jù)。該數(shù)據(jù)集包含82 166 個(gè)節(jié)點(diǎn)和948 464條邊，為稀疏圖。

由于目前沒有基于實(shí)例簇對(duì)圖結(jié)構(gòu)聚類參數(shù)進(jìn)行計(jì)算的相關(guān)算法，且現(xiàn)有的基于實(shí)例對(duì)查詢參數(shù)進(jìn)行計(jì)算的算法都無法解決本文研究的問題。因此，在上述稠密圖和稀疏圖中只對(duì)本文所提出的PART 和ImPART 兩個(gè)算法的性能進(jìn)行了測(cè)試。為每一個(gè)數(shù)據(jù)集都設(shè)計(jì)了四組實(shí)例簇，四組實(shí)例簇的大小均在100～1 000 內(nèi)（同一量級(jí)），且相差不大。其中，實(shí)例簇C1～C4 屬于ego-Facebook 數(shù)據(jù)集，實(shí)例簇C5～C8 屬于p2p-Gnutella31 數(shù)據(jù)集，實(shí)例簇C9～C12 屬于Slashdot0902 數(shù)據(jù)集，每個(gè)實(shí)例簇中的節(jié)點(diǎn)個(gè)數(shù)如表1 所示。

表1 實(shí)驗(yàn)中使用的實(shí)例簇Tab.1 Instance clusters used in experiments

5.2 算法性能

首先，評(píng)估了在不同數(shù)據(jù)集下，針對(duì)不同實(shí)例簇，算法PART 和ImPART 的運(yùn)行時(shí)間。正如期望的那樣，如圖5 所示，對(duì)于同一實(shí)例簇，ImPART 的運(yùn)行時(shí)間明顯低于PART 的運(yùn)行時(shí)間，運(yùn)行時(shí)間縮短了20%以上，主要是因?yàn)镮mPART基于引理3 和引理4 剪枝掉了很多冗余計(jì)算，提高了計(jì)算效率。對(duì)于同一數(shù)據(jù)集的不同實(shí)例簇來說，雖然節(jié)點(diǎn)個(gè)數(shù)不同，但I(xiàn)mPART 的運(yùn)行時(shí)間卻相差不大，如圖5（b）中的C5～C8，主要原因就是ImPART 算法的運(yùn)行時(shí)間主要受到通過實(shí)例簇獲取的相關(guān)子圖的結(jié)構(gòu)的影響，而C5～C8 獲得的相關(guān)子圖的結(jié)構(gòu)相差不大，因此運(yùn)行時(shí)間相差不大，C10 和C12的運(yùn)行時(shí)間相差不大也是類似的原因。此外，對(duì)于不同數(shù)據(jù)集上實(shí)例簇節(jié)點(diǎn)個(gè)數(shù)相近的實(shí)例簇來說，算法的執(zhí)行時(shí)間相差還是比較大的，如圖5（b）和5（c）所示，實(shí)例簇C8 和C11 中的節(jié)點(diǎn)個(gè)數(shù)相近，但是為C11 計(jì)算最優(yōu)聚類參數(shù)的時(shí)間明顯高于為C8 計(jì)算最優(yōu)聚類參數(shù)的時(shí)間，主要原因是，這兩個(gè)實(shí)例簇所在的數(shù)據(jù)集不同，導(dǎo)致獲取的實(shí)例簇相關(guān)的子圖結(jié)構(gòu)差別比較大，子圖結(jié)構(gòu)越復(fù)雜，需要訪問的邊數(shù)越多，需要計(jì)算的結(jié)構(gòu)相似度也會(huì)更多，從而導(dǎo)致PART 和ImPART 的運(yùn)行時(shí)間就越長(zhǎng)。

圖5 不同實(shí)例簇下PART和ImPART的運(yùn)行時(shí)間Fig.5 Running times of PART and ImPART under different instance clusters

其次，評(píng)估了同一實(shí)例簇下數(shù)據(jù)集節(jié)點(diǎn)數(shù)對(duì)PART 和ImPART 運(yùn)行時(shí)間的影響，選擇C4、C7、C10 實(shí)例簇進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果如圖6 所示，當(dāng)數(shù)據(jù)集節(jié)點(diǎn)數(shù)增大時(shí)，PART 和ImPART 的運(yùn)行時(shí)間都在增加，但增加的不明顯。因?yàn)殡S著數(shù)據(jù)集中節(jié)點(diǎn)數(shù)的增加，在數(shù)據(jù)集中獲取與實(shí)例簇相關(guān)的子圖的時(shí)間就會(huì)增加，子圖的結(jié)構(gòu)也會(huì)變得更復(fù)雜，而算法的運(yùn)行時(shí)間會(huì)隨著圖結(jié)構(gòu)的復(fù)雜程度增大而增加。增加不明顯主要原因是數(shù)據(jù)集中增多的節(jié)點(diǎn)沒有對(duì)獲取的實(shí)例簇相關(guān)的子圖產(chǎn)生大的影響。

圖6 數(shù)據(jù)集大小不同時(shí)PART和ImPART的運(yùn)行時(shí)間Fig.6 Running times of PART and ImPART under different data sizes

再次，評(píng)估了同一實(shí)例簇下不同量級(jí)數(shù)據(jù)集節(jié)點(diǎn)數(shù)對(duì)ImPART 運(yùn)行時(shí)間的影響。設(shè)置數(shù)據(jù)集的節(jié)點(diǎn)數(shù)為5 000 和20 000，由于ego-Facebook 數(shù)據(jù)集的大小只有4 000，無法選擇不同量級(jí)數(shù)據(jù)集大小，所以只選擇p2p-Gnutella31 數(shù)據(jù)集和Slashdot0902 數(shù)據(jù)集進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果如圖7 所示，當(dāng)數(shù)據(jù)集節(jié)點(diǎn)數(shù)明顯增加時(shí)，ImPART 的運(yùn)行時(shí)間也在增加，但增加得不明顯。因?yàn)殡S著數(shù)據(jù)集中節(jié)點(diǎn)數(shù)的增加，在數(shù)據(jù)集中獲取相關(guān)子圖的時(shí)間會(huì)增加，子圖的復(fù)雜程度會(huì)增加，因此運(yùn)行時(shí)間會(huì)增加。增加的時(shí)間不明顯的原因是數(shù)據(jù)集中需要計(jì)算的結(jié)構(gòu)相似度的次數(shù)沒有明顯增加，增加的節(jié)點(diǎn)對(duì)實(shí)例簇相關(guān)的子圖沒有產(chǎn)生較大影響。此外，C5 和C6 運(yùn)行時(shí)間幾乎相同，這主要是因?yàn)镃5 和C6 獲得的相關(guān)子圖的結(jié)構(gòu)相差不大。

圖7 不同量級(jí)數(shù)據(jù)集上ImPART的運(yùn)行時(shí)間Fig.7 Running time of ImPART on datasets with different magnitudes

然后，為每個(gè)數(shù)據(jù)集設(shè)計(jì)了3 個(gè)節(jié)點(diǎn)數(shù)屬于不同量級(jí)的實(shí)例簇來評(píng)估算法PART 和ImPART 的性能。3 個(gè)實(shí)例簇的節(jié)點(diǎn)數(shù)選取區(qū)間分別為［10，100）、［100，1 000）、［1 000，5 000］。其中，實(shí)例簇C21～C23 屬于ego-Facebook 數(shù)據(jù)集，實(shí)例簇C24～C26 屬于p2p-Gnutella31 數(shù)據(jù)集，實(shí)例簇C27～C29屬于Slashdot0902 數(shù)據(jù)集，實(shí)例簇大小如表2 所示。如圖8 所示，對(duì)于同一個(gè)數(shù)據(jù)集的不同量級(jí)的實(shí)例簇來說，兩個(gè)算法的執(zhí)行時(shí)間會(huì)隨著實(shí)例簇節(jié)點(diǎn)個(gè)數(shù)量級(jí)的增大而明顯地增大。實(shí)例簇越大，ImPART 的效率提升越明顯，如圖8（a）所示，這是因?yàn)樗惴ǖ倪\(yùn)行時(shí)間主要集中在結(jié)構(gòu)相似度的計(jì)算和檢驗(yàn)?zāi)芊癯纱氐挠?jì)算，而ImPART可以減少大量冗余計(jì)算。

表2 不同量級(jí)的實(shí)例簇Tab.2 Instance clusters with different magnitudes

圖8 不同量級(jí)實(shí)例簇下PART和ImPART的執(zhí)行時(shí)間Fig.8 Running times of PART and ImPART under instance clusters with different magnitudes

最后，本文比較了不同實(shí)例簇所對(duì)應(yīng)的最優(yōu)聚類參數(shù)，不同實(shí)例簇對(duì)應(yīng)的最優(yōu)密度約束和最優(yōu)結(jié)構(gòu)相似度閾值分別如圖9 所示。

圖9 不同實(shí)例簇對(duì)應(yīng)的最優(yōu)聚類參數(shù)Fig.9 Optimal clustering parameters corresponding to different instance clusters

從圖9 中可以看出不同的實(shí)例簇所對(duì)應(yīng)的最優(yōu)聚類參數(shù)是不同的，主要原因就是最優(yōu)聚類參數(shù)會(huì)受到實(shí)例簇中節(jié)點(diǎn)數(shù)量、邊的數(shù)量以及實(shí)例簇相關(guān)子圖結(jié)構(gòu)的影響。

6 結(jié)語

本文提出了一種實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算算法，可以根據(jù)用戶提供的實(shí)例簇得到滿足當(dāng)前實(shí)例簇需求且不包含任何冗余節(jié)點(diǎn)的一組最優(yōu)聚類參數(shù)μopt和εopt。基于此提出了一個(gè)實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算的基本算法PART；然后對(duì)PART 算法進(jìn)行了改進(jìn)，提出了一個(gè)有效的實(shí)例簇驅(qū)動(dòng)的圖結(jié)構(gòu)聚類參數(shù)計(jì)算的改進(jìn)算法ImPART，提高了參數(shù)計(jì)算效率。實(shí)驗(yàn)結(jié)果表明，所提算法可以快速且準(zhǔn)確地找到滿足用戶提供的實(shí)例簇需求的最優(yōu)聚類參數(shù)。未來將探索更有效的參數(shù)計(jì)算算法，更快確定密度約束參數(shù)μ的有效可行區(qū)間，通過更有效地對(duì)實(shí)例簇中節(jié)點(diǎn)進(jìn)行劃分，更有效地獲得滿足實(shí)例簇需求的最優(yōu)聚類參數(shù)。