有限內(nèi)存下概念格二元關(guān)系消減維護(hù)算法研究.pdf

1、概念格（也叫形式概念分析）作為一種概念聚類(lèi)的方法，已被證明有利于機(jī)器學(xué)習(xí)、信息檢索和知識(shí)發(fā)現(xiàn)等。在實(shí)際應(yīng)用中，隨著時(shí)間的推移生成概念格的形式背景會(huì)產(chǎn)生大量冗余的對(duì)象、屬性或是對(duì)象與屬性之間的二元關(guān)系，這導(dǎo)致概念格中無(wú)效概念增多，而去除這些無(wú)效概念，有利于降低概念格的規(guī)模，從而有助于更快更準(zhǔn)確地獲取知識(shí)?，F(xiàn)階段大多數(shù)研究學(xué)者關(guān)注于對(duì)象或?qū)傩缘臐u減式維護(hù)工作，對(duì)于二元關(guān)系粒度的漸減式維護(hù)工作的研究卻很少。
　　為降低概念格的規(guī)模，提高

2、概念格的構(gòu)造效率，本文提出了基于二元關(guān)系消減的概念格維護(hù)方法。與傳統(tǒng)的基于新形式背景下重新構(gòu)造概念格不同，該方法通過(guò)調(diào)整原始概念格而得到新概念格，故節(jié)省了大量的構(gòu)格時(shí)間。文中首先分析了原始概念格和新概念格中概念節(jié)點(diǎn)之間的對(duì)應(yīng)關(guān)系以及概念節(jié)點(diǎn)之間邊的變化規(guī)律，在此理論基礎(chǔ)上提出了自底向上廣度優(yōu)先的概念格二元關(guān)系消減算法，該算法可以處理形式背景中任意位置二元關(guān)系消減的情況。實(shí)驗(yàn)表明在一定程度上與傳統(tǒng)算法相比能明顯提高概念格的構(gòu)造效率。

3、>　　以上概念格維護(hù)算法基于無(wú)限大內(nèi)存這一假設(shè)為前提條件運(yùn)行的。然而在有限內(nèi)存下，當(dāng)概念格的規(guī)模太大而無(wú)法全部載入內(nèi)存時(shí)，使得以上基于二元關(guān)系消減的概念格維護(hù)算法不再適用。因此為解決超出內(nèi)存容量的概念格的二元關(guān)系消減的維護(hù)問(wèn)題，本文進(jìn)一步提出了一種有限內(nèi)存空間下基于外存的概念格維護(hù)算法。該算法以概念簇為基本單位劃分概念格，同時(shí)利用最近最少使用調(diào)度策略釋放內(nèi)存中無(wú)用的概念節(jié)點(diǎn)，并從外存中調(diào)入所需的概念塊，從而有效地降低了內(nèi)存消耗，解決了內(nèi)