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

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