一、基本信息
题目：LSHiForest: A generic framework for fast tree isolation based ensemble anomaly analysis
期刊/会议：IEEE ICDE
发表时间：2017年
引用次数：9
二、论文总结
2.1 研究方向
将孤立森林和局部敏感哈希（LSH）结合起来，提出通用的框架LSHiForest
2.2 写作动机
在大数据异常检测领域，基于采样的方法比较有优势，其中iForest最为出名。但是传统的iForest算法和SCiForest的作者声称他们的算法不依赖于任何距离相似度，可以处理任意形状分布的数据。但是本文作者提出LSHiForest框架后发现iForest和SCiForest是本框架的特例，而且iForest基于L1距离，SCIForest基于角度距离，因此iForest和SCiForest的使用情况有了限制。
局部敏感哈希是一种适用于高维数据搜索的技术，它通过将相似的高维数据映射到同一个哈希桶里，达到减小搜索量以提升速度的目的。低维数据可以用KD树。
作者将孤立森林和LSH结合后，可以利用LSH领域的知识，提出基于L1距离、基于L2距离、基于角度距离、基于核函数等等孤立森林，以适应不同的数据。
2.3 算法框架
采样，使用variable subsampling[1]
计算树的最高高度[2][3]
递归构建LSHiTree[4]
计算路径长度，计算异常得分[2]
里面涉及到很多公式，很多还没有看明白，里面涉及到很多文献，已在第三部分列出。
三、涉及的文献
[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.
