相似矩阵稀疏化的稀疏计算算法。
sparsecomputation的Python项目详细描述
稀疏计算
sparsecomputation
是一个python包,用于构造成对相似性的稀疏矩阵(相似矩阵)。稀疏计算产生的稀疏相似矩阵为依赖成对相似矩阵/核矩阵的有监督机器学习算法(如k近邻、基于核的支持向量机和有监督规范化割)提供了显著的加速而不损失精度。
对于具有n
对象(观察)的数据集,相似矩阵具有O(n^2)
项。对于大型数据集,计算所有成对的相似性在计算上是困难的。稀疏计算通过识别空间中彼此靠近的所有对象对来克服这种计算负担。通过将对象投影到低维空间并使用低维空间中的贴近度作为原始空间中贴近度的代理来识别这些对。稀疏计算使用网格来确定低维空间中的有效闭合对象。
稀疏计算将二维numpy数组作为输入,其大小为n x d
。每一行代表一个具有d
功能的对象。spase计算返回一个包含两个元组的列表,其中每个元组是应该在其之间计算成对相似性的对象的索引。
安装
您可以使用pip
来安装包:
pip instal sparsecomputation
最小示例
要查找与稀疏计算相关的成对相似性,请使用以下代码:
# load sample datasetimportsklearn.datasetsdata,_=sklearn.datasets.load_iris(return_X_y=True)# load Sparse ComputationfromsparsecomputationimportApproximatePCA,SparseComputation# Project data to a low-dimensional space of dimension 3# with a fast, scalable version of PCA.apca=ApproximatePCA(dimLow=3)# Select pair if objects are closer than ~distance~ (1 / resolution).# Controls sparsity (small distance - highly sparse matrix)sc=SparseComputation(apca,distance=0.05)# Input: n x d matrix - data# Output: list of relevant pairs (undirected)pairs=sc.select_pairs(data)# Out: [(101, 142), (1, 9), (1, 34), (1, 37), ...]
相关论文
有关这些技术的更多细节,请阅读以下文章。如果您在学术工作中使用此实现,请引用这些作品:
- Dorit S.Hochbaum,Philipp Baumann(2016年)。大规模数据挖掘中的稀疏计算。ieee大数据事务,2(2),151-174。
- Philipp Baumann、Dorit S.Hochbaum和Quico Spaen(2017年)。大数据分析中稀疏计算的高性能几何算法。2017年ieee大数据国际会议,马萨诸塞州波士顿。
- Philipp Baumann、Dorit S.Hochbaum和Quico Spaen(2016年)。稀疏简化计算。第五届模式识别应用与方法国际会议论文集。
学分
Philipp Baumann的原始Matlab实现。Titouan Jehl和Quico Spaen的原始Python实现。由quico spaen和philipp baumann使用新的块移位算法更新实现。