結(jié)合LSH的KNN數(shù)據(jù)填補(bǔ)算法

　　K近鄰（kNN）算法是缺失數(shù)據(jù)填補(bǔ)的常用算法，但由于需要逐個(gè)計(jì)算所有記錄對之間的相似度，因此其填補(bǔ)耗時(shí)較高。為提高算法效率，提出結(jié)合局部敏感哈希（ LSH）的kNN數(shù)據(jù)填補(bǔ)算法LSH-kNN。首先，對不存在缺失的完整記錄進(jìn)行局部敏感哈希，為之后查找近似最近鄰提供索引；其次，針對枚舉型、數(shù)值型以及混合型缺失數(shù)據(jù)分別提出對應(yīng)的局部敏感哈希方法，對每一條待填補(bǔ)的不完整記錄進(jìn)行局部敏感哈希，按得到的哈希值找到與其疑似相似的候選記錄；最后在候選記錄中通過逐個(gè)計(jì)算相似度來找到其中相似程度最高的七條記錄，并按照kNN算法對不完整記錄進(jìn)行填補(bǔ)。通過在4個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，結(jié)合局部敏感哈希的kNN填補(bǔ)算法LSH-kNN相對經(jīng)典的kNN算法能夠顯著提高填補(bǔ)效率，并且保持準(zhǔn)確性基本不變。