Barnes-Hut t-SNE:大规模数据的高效降维算法

本文涉及的产品
实时计算 Flink 版,1000CU*H 3个月
实时数仓Hologres,5000CU*H 100GB 3个月
智能开放搜索 OpenSearch行业算法版,1GB 20LCU 1个月
简介: Barnes-Hut t-SNE是一种针对大规模数据集的高效降维算法,它是t-SNE的变体,用于高维数据可视化。t-SNE通过保持概率分布相似性将数据从高维降至2D或3D。Barnes-Hut算法采用天体物理中的方法,将时间复杂度从O(N²)降低到O(NlogN),通过构建空间索引树和近似远距离交互来加速计算。在scikit-learn中可用,代码示例展示了如何使用该算法进行聚类可视化,成功分离出不同簇并获得高轮廓分数,证明其在大數據集上的有效性。

在数据科学和分析中,理解高维数据集中的底层模式是至关重要的。t-SNE已成为高维数据可视化的有力工具。它通过将数据投射到一个较低维度的空间,提供了对数据结构的详细洞察。但是随着数据集的增长,标准的t-SNE算法在计算有些困难,所以发展出了Barnes-Hut t-SNE这个改进算法,它提供了一个有效的近似,允许在不增加计算时间的情况下扩展到更大的数据集。

Barnes-Hut t-SNE 是一种高效的降维算法,适用于处理大规模数据集,是 t-SNE (t-Distributed Stochastic Neighbor Embedding) 的一个变体。这种算法主要被用来可视化高维数据,并帮助揭示数据中的内部结构。

基础概念

t-SNE 的基础是 SNE(Stochastic Neighbor Embedding),一种概率性降维技术,通过保持高维和低维空间中的概率分布相似来进行数据映射。而t-SNE 是由 Laurens van der Maaten 和 Geoffrey Hinton 于 2008 年提出的。它是一种非线性降维技术,非常适合于将高维数据降维到二维或三维空间中,用于数据可视化。

Barnes-Hut t-SNE 采用了在天体物理学中常用的 Barnes-Hut 算法来优化计算过程。这种算法最初是为了解决 N体问题,即计算多个物体之间相互作用的问题而设计的。

传统的 t-SNE 算法的时间复杂度约为 O(N2),而 Barnes-Hut 版本的 t-SNE 则将时间复杂度降低到 O(Nlog⁡N),这使得算法能够更加高效地处理大规模数据集。

工作原理

Barnes-Hut t-SNE改进了原来的t-SNE算法,加入了空间划分的数据结构,以降低点之间相互作用的复杂性。首先我们先简单介绍 t-SNE,因为理解 t-SNE 的基本工作原理对于理解 Barnes-Hut t-SNE 是必要的

t-SNE 的主要步骤包括:

  1. 相似度计算:在高维空间中,t-SNE 首先计算每对数据点之间的条件概率,这种概率反映了一个点选择另一个点作为其邻居的可能性。这种计算基于高斯分布,并且对于每个点会有不同的标准差(高斯分布的宽度),以保证每个点的有效邻居数大致相同。
  2. 低维映射:在低维空间(通常是 2D 或 3D)中,t-SNE 同样为数据点之间定义了一个概率分布,但这里使用的是 t 分布(自由度为1的学生 t-分布),这有助于在降维过程中避免“拥挤问题”(即多个高维点映射到相同的低维点)。
  3. 梯度下降:t-SNE 通过最小化高维和低维空间中概率分布的 Kullback-Leibler 散度来找到最佳的低维表示。这个过程通过梯度下降算法进行优化。

在处理大型数据集时,直接计算所有点对之间的相互作用非常耗时。Barnes-Hut 算法通过以下步骤优化这个过程:

  1. 构建空间索引树:在二维空间中构建四叉树,在三维空间中构建八叉树。每个节点表示一个数据点,而每个内部节点则表示它的子节点的质心(即子节点的平均位置)。
  2. 近似相互作用:在计算点之间的作用力(即梯度下降中的梯度)时,Barnes-Hut 算法不是计算每一对点之间的相互作用,而是使用树来估计远距离的影响。对于每个点,如果一个节点(或其包含的数据点的区域)距离足够远(根据预设的阈值,如节点的宽度与距离的比率),则该节点内的所有点可以被视为一个单一的质心,从而简化计算。
  3. 有效的梯度计算:通过这种近似,算法只需要计算与目标点近邻的实际点以及远处质心的影响,极大地减少了必须执行的计算量。

通过这种方法,Barnes-Hut t-SNE 将复杂度从 O(N2) 降低到 O(Nlog⁡N),使其能够有效地处理数万到数十万级别的数据点。但是这种效率的提升是以牺牲一定的精确度为代价的,因为远距离的相互作用是通过质心近似来实现的,而不是精确计算。

代码示例

Barnes-Hut t-SNE已经被集成到scikit-learn库种,所以我们直接可以拿来使用

首先我们生成一些简单的数据:

 importnumpyasnp
 importmatplotlib.pyplotasplt
 fromsklearn.manifoldimportTSNE
 fromsklearn.datasetsimportmake_blobs
 fromsklearn.model_selectionimporttrain_test_split
 fromsklearn.preprocessingimportStandardScaler
 fromsklearn.metricsimportsilhouette_score

 # Generate synthetic data
 X, y=make_blobs(n_samples=1000, centers=4, n_features=50, random_state=42)

生成4个簇,每个样本包含50个特征,总计1000个样本。

然后我们分割数据集,进行聚类

 # Split data into training and testing sets
 X_train, X_test, y_train, y_test=train_test_split(X, y, test_size=0.3, random_state=42)

 # Standardize features by removing the mean and scaling to unit variance
 scaler=StandardScaler()
 X_train_scaled=scaler.fit_transform(X_train)
 X_test_scaled=scaler.transform(X_test)

 # Hyperparameter tuning for t-SNE
 best_silhouette=-1
 best_params= {}
 perplexities= [5, 30, 50, 100]  # Different perplexity values to try
 learning_rates= [10, 100, 200, 500]  # Different learning rates to try

 forperplexityinperplexities:
     forlearning_rateinlearning_rates:
         # Apply Barnes-Hut t-SNE
         tsne=TSNE(n_components=2, method='barnes_hut', perplexity=perplexity,
                     learning_rate=learning_rate, random_state=42)
         X_train_tsne=tsne.fit_transform(X_train_scaled)

         # Calculate Silhouette score
         score=silhouette_score(X_train_tsne, y_train)

         # Check if we have a new best score
         ifscore>best_silhouette:
             best_silhouette=score
             best_params= {'perplexity': perplexity, 'learning_rate': learning_rate}
             best_embedding=X_train_tsne

 # Visualization of the best t-SNE embedding
 plt.figure(figsize=(8, 6))
 plt.scatter(best_embedding[:, 0], best_embedding[:, 1], c=y_train, cmap='viridis', edgecolor='k', s=50)
 plt.title(f'Barnes-Hut t-SNE Visualization\nPerplexity: {best_params["perplexity"]}, Learning Rate: {best_params["learning_rate"]}')
 plt.colorbar(label='Cluster Label')
 plt.xlabel('t-SNE Feature 1')
 plt.ylabel('t-SNE Feature 2')
 plt.grid(True)
 plt.show()

 # Interpretations and results
 print(f"Best Silhouette Score: {best_silhouette}")
 print("Best Parameters:", best_params)
 print("Barnes-Hut t-SNE provided a clear visualization of the clusters, indicating good separation among different groups.")

我们只要在sklearn的TSNE方法种传入参数method='barnes_hut'即可。上面代码运行结果如下:

 Best Silhouette Score: 0.9504804611206055
 Best Parameters: {'perplexity': 100, 'learning_rate': 500}
 Barnes-Hut t-SNE provided a clear visualization of the clusters, indicating good separation among different groups.

可以看到:

Barnes-Hut t-SNE算法已经有效地将高维数据分离成不同的簇。轮廓分数0.95说明聚类分离良好,几乎没有重叠,这个接近1的分数表明,平均而言,数据点离它们的集群中心比离最近的不同集群的中心要近得多。

通过观察可以看到到簇内的密度各不相同。例如图中底部的某个簇(蓝色的)看起来特别紧凑,表明其点之间的相似度很高。相反顶部的另一个簇(黄色的)看起来更为分散,意味着该组内的变异更大。

没有明显的异常值远离其各自的簇,这表明原始高维空间中的簇结构定义良好。

高轮廓分数和清晰的视觉分离,可以说明我们选择的超参数(perplexity:100,学习率:500)非常适合这个数据集。这也表明算法可能已经很好地收敛,找到了一个稳定的结构,强调了簇之间的差异。

总结

Barnes-Hut t-SNE 是一种高效的数据降维方法,特别适合于处理大型和复杂的数据集,它通过引入四叉树或八叉树的结构来近似远距离作用,从而大幅减少了计算量,同时保持了良好的数据可视化质量。Barnes-Hut t-SNE优化了原始 t-SNE 算法的计算效率,使其能够在实际应用中更为广泛地使用。

https://avoid.overfit.cn/post/ec11566be83d4f4fb7cf31d09197d8e4

目录
相关文章
|
7天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
13天前
|
机器学习/深度学习 算法 调度
14种智能算法优化BP神经网络(14种方法)实现数据预测分类研究(Matlab代码实现)
14种智能算法优化BP神经网络(14种方法)实现数据预测分类研究(Matlab代码实现)
|
2月前
|
机器学习/深度学习 Dragonfly 人工智能
基于蜻蜓算法优化支持向量机(DA-SVM)的数据多特征分类预测研究(Matlab代码实现)
基于蜻蜓算法优化支持向量机(DA-SVM)的数据多特征分类预测研究(Matlab代码实现)
|
21天前
|
算法 数据挖掘 定位技术
基于密度的聚类算法能够在含有噪声的数据集中识别出任意形状和大小的簇(Matlab代码实现)
基于密度的聚类算法能够在含有噪声的数据集中识别出任意形状和大小的簇(Matlab代码实现)
|
26天前
|
机器学习/深度学习 数据采集 运维
改进的遗传算法优化的BP神经网络用于电厂数据的异常检测和故障诊断
改进的遗传算法优化的BP神经网络用于电厂数据的异常检测和故障诊断
|
2月前
|
机器学习/深度学习 传感器 边缘计算
【轴承故障诊断】基于融合鱼鹰和柯西变异的麻雀优化算法OCSSA-VMD-CNN-BILSTM轴承诊断研究【西储大学数据】(Matlab代码实现)
【轴承故障诊断】基于融合鱼鹰和柯西变异的麻雀优化算法OCSSA-VMD-CNN-BILSTM轴承诊断研究【西储大学数据】(Matlab代码实现)
|
3月前
|
存储 监控 算法
基于 Python 跳表算法的局域网网络监控软件动态数据索引优化策略研究
局域网网络监控软件需高效处理终端行为数据,跳表作为一种基于概率平衡的动态数据结构,具备高效的插入、删除与查询性能(平均时间复杂度为O(log n)),适用于高频数据写入和随机查询场景。本文深入解析跳表原理,探讨其在局域网监控中的适配性,并提供基于Python的完整实现方案,优化终端会话管理,提升系统响应性能。
80 4
|
3月前
|
机器学习/深度学习 人工智能 算法
AP聚类算法实现三维数据点分类
AP聚类算法实现三维数据点分类
123 0
|
4月前
|
机器学习/深度学习 算法
基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法matlab仿真
本项目实现基于差分进化灰狼混合优化的SVM(DE-GWO-SVM)数据预测算法的MATLAB仿真,对比SVM和GWO-SVM性能。算法结合差分进化(DE)与灰狼优化(GWO),优化SVM参数以提升复杂高维数据预测能力。核心流程包括DE生成新种群、GWO更新位置,迭代直至满足终止条件,选出最优参数组合。适用于分类、回归等任务,显著提高模型效率与准确性,运行环境为MATLAB 2022A。
|
4月前
|
传感器 数据采集 人工智能
AI是如何收集体育数据的?从摄像头到算法,揭秘赛场背后的“数字间谍网“!
⚽ 你是否好奇:AI如何知道哈兰德每秒跑多快?教练的平板为何比裁判还清楚谁偷懒?本文揭秘AI收集体育数据的“黑科技”:视觉追踪、传感器网络、数据清洗与高阶分析。从高速摄像机捕捉梅西肌肉抖动,到GPS背心记录姆巴佩冲刺速度;从表情识别判断装伤,到量子计算模拟战术可能,AI正让体育更透明、精准。未来已来,2030年世界杯或将实现AI替代球探、裁判甚至教练!你认为AI数据收集算侵犯隐私吗?最想统计哪些奇葩指标?留言互动吧!