一、基本信息

??題目：LSHiForest: A generic framework for fast tree isolation based ensemble anomaly analysis
??期刊/會(huì)議：IEEE ICDE
??發(fā)表時(shí)間：2017年
??引用次數(shù)：9

二、論文總結(jié)

2.1 研究方向

??將孤立森林和局部敏感哈希（LSH）結(jié)合起來(lái)，提出通用的框架LSHiForest

2.2 寫作動(dòng)機(jī)

??在大數(shù)據(jù)異常檢測(cè)領(lǐng)域，基于采樣的方法比較有優(yōu)勢(shì)，其中iForest最為出名。但是傳統(tǒng)的iForest算法和SCiForest的作者聲稱他們的算法不依賴于任何距離相似度，可以處理任意形狀分布的數(shù)據(jù)。但是本文作者提出LSHiForest框架后發(fā)現(xiàn)iForest和SCiForest是本框架的特例，而且iForest基于L1距離，SCIForest基于角度距離，因此iForest和SCiForest的使用情況有了限制。
??局部敏感哈希是一種適用于高維數(shù)據(jù)搜索的技術(shù)，它通過(guò)將相似的高維數(shù)據(jù)映射到同一個(gè)哈希桶里，達(dá)到減小搜索量以提升速度的目的。低維數(shù)據(jù)可以用KD樹。
??作者將孤立森林和LSH結(jié)合后，可以利用LSH領(lǐng)域的知識(shí)，提出基于L1距離、基于L2距離、基于角度距離、基于核函數(shù)等等孤立森林，以適應(yīng)不同的數(shù)據(jù)。

2.3 算法框架

??采樣，使用variable subsampling[1]
??計(jì)算樹的最高高度[2][3]
??遞歸構(gòu)建LSHiTree[4]
??計(jì)算路徑長(zhǎng)度，計(jì)算異常得分[2]
??里面涉及到很多公式，很多還沒有看明白，里面涉及到很多文獻(xiàn)，已在第三部分列出。

三、涉及的文獻(xiàn)

[1] Aggarwal C C, Sathe S. Theoretical foundations and algorithms for outlier ensembles[J]. ACM SIGKDD Explorations Newsletter, 2015, 17(1): 24-47.
[2] Bawa M, Condie T, Ganesan P. LSH forest: self-tuning indexes for similarity search[C]//Proceedings of the 14th international conference on World Wide Web. ACM, 2005: 651-660.
[3] Szpankowski W. On the analysis of the average height of a digital trie: Another approach[J]. 1986.
[4] Wang J, Shen H T, Song J, et al. Hashing for similarity search: A survey[J]. arXiv preprint arXiv:1408.2927, 2014.