實(shí)體關(guān)系高效發(fā)現(xiàn)課件

實(shí)體關(guān)系高效發(fā)現(xiàn)何靖劉源涂啟琛姚從磊邸楠2007.3實(shí)體關(guān)系高效發(fā)現(xiàn)何靖劉源涂啟琛姚從磊邸楠提綱—五個(gè)問(wèn)題任務(wù)是什么?--實(shí)體關(guān)系發(fā)現(xiàn)現(xiàn)有的方法是什么？--相關(guān)研究如何定義實(shí)體間具有關(guān)系？--指標(biāo)確定如何有效地發(fā)現(xiàn)實(shí)體？--算法和實(shí)現(xiàn)方法有效嗎？--驗(yàn)證和實(shí)驗(yàn)結(jié)論是什么？提綱—五個(gè)問(wèn)題任務(wù)是什么?--實(shí)體關(guān)系發(fā)現(xiàn)1.任務(wù)是什么背景：Webv.sreallife目標(biāo)：發(fā)現(xiàn)Web上的實(shí)體和他們的關(guān)系本文重點(diǎn)：提高發(fā)現(xiàn)實(shí)體之間關(guān)系的效率不關(guān)心實(shí)體間關(guān)系的具體類型1.任務(wù)是什么背景：Webv.sreallife2.已有的實(shí)體關(guān)系發(fā)現(xiàn)方法所有方法的思想實(shí)體共現(xiàn)實(shí)體關(guān)系幾個(gè)數(shù)量文檔集大小=N;感興趣實(shí)體集合大小=n方法一：O(N)掃描文檔集，獲得所有實(shí)體的關(guān)系方法二：O(n^2)對(duì)興趣實(shí)體集合，每對(duì)分別檢索方法三：O(n)對(duì)興趣實(shí)體集合，單個(gè)檢索，發(fā)現(xiàn)包含共現(xiàn)實(shí)體的文檔Drawback:難以通過(guò)searchengine獲得包含實(shí)體的所有網(wǎng)頁(yè)檢索出來(lái)的網(wǎng)頁(yè)依舊有很多是無(wú)用的—不包含感興趣實(shí)體如果只選取top網(wǎng)頁(yè)，表現(xiàn)出來(lái)的關(guān)系比應(yīng)有關(guān)系稀疏2.已有的實(shí)體關(guān)系發(fā)現(xiàn)方法所有方法的思想3.如何定義實(shí)體間具有關(guān)系？基本思路：采用共現(xiàn)衡量共現(xiàn)的一些指標(biāo)MutualInformationDiceCoefficientOverlapCoefficientJaccardCoefficientCosineCoefficient3.如何定義實(shí)體間具有關(guān)系？基本思路：采用共現(xiàn)3.如何定義實(shí)體間具有關(guān)系？測(cè)試共現(xiàn)有效性的實(shí)驗(yàn)Step1:根據(jù)指標(biāo)獲得兩兩實(shí)體的指標(biāo)量Step2:對(duì)每個(gè)實(shí)體，根據(jù)指標(biāo)量對(duì)相關(guān)實(shí)體進(jìn)行排序Step3:5個(gè)指標(biāo)選取topN結(jié)果進(jìn)入poolingStep4:人工判斷具有關(guān)系/不具有關(guān)系Step5:用兩個(gè)實(shí)驗(yàn)量：MAP,PR11測(cè)試共現(xiàn)有效性3.如何定義實(shí)體間具有關(guān)系？測(cè)試共現(xiàn)有效性的實(shí)驗(yàn)3.如何定義實(shí)體間具有關(guān)系？實(shí)驗(yàn)結(jié)果采用Cosine作為指標(biāo)3.如何定義實(shí)體間具有關(guān)系？實(shí)驗(yàn)結(jié)果4.有效地發(fā)現(xiàn)實(shí)體—基本思想基本思想利用聚類系數(shù)比較大這一特征聚類系數(shù)定義

4.有效地發(fā)現(xiàn)實(shí)體—基本思想基本思想4.有效地發(fā)現(xiàn)實(shí)體—基本思想驗(yàn)證以上直覺(jué)印象4.有效地發(fā)現(xiàn)實(shí)體—基本思想驗(yàn)證以上直覺(jué)印象4.有效地發(fā)現(xiàn)實(shí)體—算法一圖聚類算法：輸入：興趣實(shí)體集合初始化：檢索實(shí)體i,獲得topm網(wǎng)頁(yè)提取出現(xiàn)在這些網(wǎng)頁(yè)中的實(shí)體設(shè)置關(guān)系矩陣M[i][j]=實(shí)體j在實(shí)體i的topm中出現(xiàn)的次數(shù)/實(shí)體i的topm中出現(xiàn)的實(shí)體次數(shù)迭代聚類：反復(fù)以下以致變化程度小于閾值歸一：一行所有元素和為1游走：Me

增距：M[i][j]=M[i][j]λ

每個(gè)實(shí)體的topk作為候選實(shí)體，采用cosine驗(yàn)證4.有效地發(fā)現(xiàn)實(shí)體—算法一圖聚類算法：4.有效地發(fā)現(xiàn)實(shí)體—算法二算法一不能完全解決關(guān)系稀疏問(wèn)題算法二：概率算法順序加入實(shí)體e，初始化它和其他實(shí)體關(guān)系概率為平均關(guān)系密度迭代過(guò)程：以致和其他所有實(shí)體關(guān)系概率低于閾值測(cè)試e與已有集合中具有最高關(guān)系概率的實(shí)體的關(guān)系采用聚類系數(shù)、反聚類系數(shù)擴(kuò)散，更新與周圍實(shí)體的關(guān)系概率4.有效地發(fā)現(xiàn)實(shí)體—算法二算法一不能完全解決關(guān)系稀疏問(wèn)題5.方法有效嗎？5.方法有效嗎？5.方法有效嗎？5.方法有效嗎？6.結(jié)論Cosine是衡量