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

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

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

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