We investigate the use of Minimax distances to extract in a nonparametric way the features that capture the unknown underlying patterns and structures in the data. We develop a general-purpose and computationally efficient framework to employ Minimax distances with many machine learning methods that perform on numerical data. We study both computing the pairwise Minimax distances for all pairs of objects and as well as computing the Minimax distances of all the objects to/from a fixed (test) object. We first efficiently compute the pairwise Minimax distances between the objects, using the equivalence of Minimax distances over a graph and over a minimum spanning tree constructed on that. Then, we perform an embedding of the pairwise Minimax distances into a new vector space, such that their squared Euclidean distances in the new space equal to the pairwise Minimax distances in the original space. We also study the case of having multiple pairwise Minimax matrices, instead of a single one. Thereby, we propose an embedding via first summing up the centered matrices and then performing an eigenvalue decomposition to obtain the relevant features. In the following, we study computing Minimax distances from a fixed (test) object which can be used for instance in K-nearest neighbor search. Similar to the case of all-pair pairwise Minimax distances, we develop an efficient and general-purpose algorithm that is applicable with any arbitrary base distance measure. Moreover, we investigate in detail the edges selected by the Minimax distances and thereby explore the ability of Minimax distances in detecting outlier objects. Finally, for each setting, we perform several experiments to demonstrate the effectiveness of our framework.

We propose unsupervised representation learning and feature extraction from dendrograms. The commonly used Minimax distance measures correspond to building a dendrogram with single linkage criterion, with defining specific forms of a level function and a distance function over that. Therefore, we extend this method to arbitrary dendrograms. We develop a generalized framework wherein different distance measures and representations can be inferred from different types of dendrograms, level functions and distance functions. Via an appropriate embedding, we compute a vector-based representation of the inferred distances, in order to enable many numerical machine learning algorithms to employ such distances. Then, to address the model selection problem, we study the aggregation of different dendrogram-based distances respectively in solution space and in representation space in the spirit of deep representations. In the first approach, for example for the clustering problem, we build a graph with positive and negative edge weights according to the consistency of the clustering labels of different objects among different solutions, in the context of ensemble methods. Then, we use an efficient variant of correlation clustering to produce the final clusters. In the second approach, we investigate the combination of different distances and features sequentially in the spirit of multi-layered architectures to obtain the final features. Finally, we demonstrate the effectiveness of our approach via several numerical studies.

Standard agglomerative clustering suggests establishing a new reliable linkage at every step. However, in order to provide adaptive, density-consistent and flexible solutions, we study extracting all the reliable linkages at each step, instead of the smallest one. Such a strategy can be applied with all common criteria for agglomerative hierarchical clustering. We also study that this strategy with the single linkage criterion yields a minimum spanning tree algorithm. We perform experiments on several real-world datasets to demonstrate the performance of this strategy compared to the standard alternative.

Several clustering methods (e.g., Normalized Cut and Ratio Cut) divide the Min Cut cost function by a cluster dependent factor (e.g., the size or the degree of the clusters), in order to yield a more balanced partitioning. We, instead, investigate adding such regularizations to the original cost function. We first consider the case where the regularization term is the sum of the squared size of the clusters, and then generalize it to adaptive regularization of the pairwise similarities. This leads to shifting (adaptively) the pairwise similarities which might make some of them negative. We then study the connection of this method to Correlation Clustering and then propose an efficient local search optimization algorithm with fast theoretical convergence rate to solve the new clustering problem. In the following, we investigate the shift of pairwise similarities on some common clustering methods, and finally, we demonstrate the superior performance of the method by extensive experiments on different datasets.

在过去十年中，图形内核引起了很多关注，并在结构化数据上发展成为一种快速发展的学习分支。在过去的20年中，该领域发生的相当大的研究活动导致开发数十个图形内核，每个图形内核都对焦于图形的特定结构性质。图形内核已成功地成功地在广泛的域中，从社交网络到生物信息学。本调查的目标是提供图形内核的文献的统一视图。特别是，我们概述了各种图形内核。此外，我们对公共数据集的几个内核进行了实验评估，并提供了比较研究。最后，我们讨论图形内核的关键应用，并概述了一些仍有待解决的挑战。

We review clustering as an analysis tool and the underlying concepts from an introductory perspective. What is clustering and how can clusterings be realised programmatically? How can data be represented and prepared for a clustering task? And how can clustering results be validated? Connectivity-based versus prototype-based approaches are reflected in the context of several popular methods: single-linkage, spectral embedding, k-means, and Gaussian mixtures are discussed as well as the density-based protocols (H)DBSCAN, Jarvis-Patrick, CommonNN, and density-peaks.

在机器学习中调用多种假设需要了解歧管的几何形状和维度，理论决定了需要多少样本。但是，在应用程序数据中，采样可能不均匀，歧管属性是未知的，并且（可能）非纯化；这意味着社区必须适应本地结构。我们介绍了一种用于推断相似性内核提供数据的自适应邻域的算法。从本地保守的邻域（Gabriel）图开始，我们根据加权对应物进行迭代率稀疏。在每个步骤中，线性程序在全球范围内产生最小的社区，并且体积统计数据揭示了邻居离群值可能违反了歧管几何形状。我们将自适应邻域应用于非线性维度降低，地球计算和维度估计。与标准算法的比较，例如使用K-Nearest邻居，证明了它们的实用性。

In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. On the first glance spectral clustering appears slightly mysterious, and it is not obvious to see why it works at all and what it really does. The goal of this tutorial is to give some intuition on those questions. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed.

The accuracy of k-nearest neighbor (kNN) classification depends significantly on the metric used to compute distances between different examples. In this paper, we show how to learn a Mahalanobis distance metric for kNN classification from labeled examples. The Mahalanobis metric can equivalently be viewed as a global linear transformation of the input space that precedes kNN classification using Euclidean distances. In our approach, the metric is trained with the goal that the k-nearest neighbors always belong to the same class while examples from different classes are separated by a large margin. As in support vector machines (SVMs), the margin criterion leads to a convex optimization based on the hinge loss. Unlike learning in SVMs, however, our approach requires no modification or extension for problems in multiway (as opposed to binary) classification. In our framework, the Mahalanobis distance metric is obtained as the solution to a semidefinite program. On several data sets of varying size and difficulty, we find that metrics trained in this way lead to significant improvements in kNN classification. Sometimes these results can be further improved by clustering the training examples and learning an individual metric within each cluster. We show how to learn and combine these local metrics in a globally integrated manner.

Graph clustering is a fundamental problem in unsupervised learning, with numerous applications in computer science and in analysing real-world data. In many real-world applications, we find that the clusters have a significant high-level structure. This is often overlooked in the design and analysis of graph clustering algorithms which make strong simplifying assumptions about the structure of the graph. This thesis addresses the natural question of whether the structure of clusters can be learned efficiently and describes four new algorithmic results for learning such structure in graphs and hypergraphs. All of the presented theoretical results are extensively evaluated on both synthetic and real-word datasets of different domains, including image classification and segmentation, migration networks, co-authorship networks, and natural language processing. These experimental results demonstrate that the newly developed algorithms are practical, effective, and immediately applicable for learning the structure of clusters in real-world data.

大多数维度降低方法采用频域表示，从基质对角线化获得，并且对于具有较高固有维度的大型数据集可能不会有效。为了应对这一挑战，相关的聚类和投影（CCP）提供了一种新的数据域策略，不需要解决任何矩阵。CCP将高维特征分配到相关的群集中，然后根据样本相关性将每个集群中的特征分为一个一维表示。引入了残留相似性（R-S）分数和索引，Riemannian歧管中的数据形状以及基于代数拓扑的持久性Laplacian进行可视化和分析。建议的方法通过与各种机器学习算法相关的基准数据集验证。

最近有一项激烈的活动在嵌入非常高维和非线性数据结构的嵌入中，其中大部分在数据科学和机器学习文献中。我们分四部分调查这项活动。在第一部分中，我们涵盖了非线性方法，例如主曲线，多维缩放，局部线性方法，ISOMAP，基于图形的方法和扩散映射，基于内核的方法和随机投影。第二部分与拓扑嵌入方法有关，特别是将拓扑特性映射到持久图和映射器算法中。具有巨大增长的另一种类型的数据集是非常高维网络数据。第三部分中考虑的任务是如何将此类数据嵌入中等维度的向量空间中，以使数据适合传统技术，例如群集和分类技术。可以说，这是算法机器学习方法与统计建模（所谓的随机块建模）之间的对比度。在论文中，我们讨论了两种方法的利弊。调查的最后一部分涉及嵌入$ \ mathbb {r}^ 2 $，即可视化中。提出了三种方法：基于第一部分，第二和第三部分中的方法，$ t $ -sne，UMAP和大节。在两个模拟数据集上进行了说明和比较。一个由嘈杂的ranunculoid曲线组成的三胞胎，另一个由随机块模型和两种类型的节点产生的复杂性的网络组成。

In this work we study statistical properties of graph-based algorithms for multi-manifold clustering (MMC). In MMC the goal is to retrieve the multi-manifold structure underlying a given Euclidean data set when this one is assumed to be obtained by sampling a distribution on a union of manifolds $\mathcal{M} = \mathcal{M}_1 \cup\dots \cup \mathcal{M}_N$ that may intersect with each other and that may have different dimensions. We investigate sufficient conditions that similarity graphs on data sets must satisfy in order for their corresponding graph Laplacians to capture the right geometric information to solve the MMC problem. Precisely, we provide high probability error bounds for the spectral approximation of a tensorized Laplacian on $\mathcal{M}$ with a suitable graph Laplacian built from the observations; the recovered tensorized Laplacian contains all geometric information of all the individual underlying manifolds. We provide an example of a family of similarity graphs, which we call annular proximity graphs with angle constraints, satisfying these sufficient conditions. We contrast our family of graphs with other constructions in the literature based on the alignment of tangent planes. Extensive numerical experiments expand the insights that our theory provides on the MMC problem.

应用分层聚类算法所需的时间最常由成对差异度量的计算数量主导。对于较大的数据集，这种约束使所有经典链接标准的使用都处于不利地位。但是，众所周知，单个连锁聚类算法对离群值非常敏感，产生高度偏斜的树状图，因此通常不会反映出真正的潜在数据结构 - 除非簇分离良好。为了克服其局限性，我们提出了一个名为Genie的新的分层聚类链接标准。也就是说，我们的算法将两个簇链接在一起，以至于选择的经济不平等度量（例如，gini-或bonferroni index）的群集大小不会大大增加超过给定阈值。提出的基准表明引入的方法具有很高的实际实用性：它通常优于病房或平均链接的聚类质量，同时保持单个连锁的速度。 Genie算法很容易平行，因此可以在多个线程上运行以进一步加快其执行。它的内存开销很小：无需预先计算完整的距离矩阵即可执行计算以获得所需的群集。它可以应用于配备有差异度量的任意空间，例如，在实际矢量，DNA或蛋白质序列，图像，排名，信息图数据等上。有关R。另请参见https://genieclust.gagolewski.com有关新的实施（GenieClust） - 可用于R和Python。

我们讨论集群分析的拓扑方面，并表明在聚类之前推断数据集的拓扑结构可以大大增强群集检测：理论论证和经验证据表明，聚类嵌入向量，代表数据歧管的结构，而不是观察到的特征矢量他们自己是非常有益的。为了证明，我们将流形学习方法与基于密度的聚类方法DBSCAN结合了歧管学习方法UMAP。合成和真实数据结果表明，这既简化和改善了多种低维问题，包括密度变化和/或纠缠形状的群集。我们的方法简化了聚类，因为拓扑预处理始终降低DBSCAN的参数灵敏度。然后，用dbscan聚类所得的嵌入可以超过诸如spectacl和clustergan之类的复杂方法。最后，我们的调查表明，聚类中的关键问题似乎不是数据的标称维度或其中包含多少不相关的功能，而是\ textIt {可分离}群集在环境观察空间中的\ textit {可分离}，它们嵌入了它们中。 ，通常是数据特征定义的（高维）欧几里得空间。我们的方法之所以成功，是因为我们将数据投影到更合适的空间后，从某种意义上说，我们执行了群集分析。

Data-driven neighborhood definitions and graph constructions are often used in machine learning and signal processing applications. k-nearest neighbor~(kNN) and $\epsilon$-neighborhood methods are among the most common methods used for neighborhood selection, due to their computational simplicity. However, the choice of parameters associated with these methods, such as k and $\epsilon$, is still ad hoc. We make two main contributions in this paper. First, we present an alternative view of neighborhood selection, where we show that neighborhood construction is equivalent to a sparse signal approximation problem. Second, we propose an algorithm, non-negative kernel regression~(NNK), for obtaining neighborhoods that lead to better sparse representation. NNK draws similarities to the orthogonal matching pursuit approach to signal representation and possesses desirable geometric and theoretical properties. Experiments demonstrate (i) the robustness of the NNK algorithm for neighborhood and graph construction, (ii) its ability to adapt the number of neighbors to the data properties, and (iii) its superior performance in local neighborhood and graph-based machine learning tasks.

即使机器学习算法已经在数据科学中发挥了重要作用，但许多当前方法对输入数据提出了不现实的假设。由于不兼容的数据格式，或数据集中的异质，分层或完全缺少的数据片段，因此很难应用此类方法。作为解决方案，我们提出了一个用于样本表示，模型定义和培训的多功能，统一的框架，称为“ Hmill”。我们深入审查框架构建和扩展的机器学习的多个范围范式。从理论上讲，为HMILL的关键组件的设计合理，我们将通用近似定理的扩展显示到框架中实现的模型所实现的所有功能的集合。本文还包含有关我们实施中技术和绩效改进的详细讨论，该讨论将在MIT许可下发布供下载。该框架的主要资产是其灵活性，它可以通过相同的工具对不同的现实世界数据源进行建模。除了单独观察到每个对象的一组属性的标准设置外，我们解释了如何在框架中实现表示整个对象系统的图表中的消息推断。为了支持我们的主张，我们使用框架解决了网络安全域的三个不同问题。第一种用例涉及来自原始网络观察结果的IoT设备识别。在第二个问题中，我们研究了如何使用以有向图表示的操作系统的快照可以对恶意二进制文件进行分类。最后提供的示例是通过网络中实体之间建模域黑名单扩展的任务。在所有三个问题中，基于建议的框架的解决方案可实现与专业方法相当的性能。

从一组给定对象中计算共识对象是机器学习和模式识别的核心问题。一种流行的方法是使用广义中位数将其作为优化问题。先前的方法（例如原型和距离嵌入方法）将对象转换为矢量空间，解决该空间中的广义中值问题，并反相转换回原始空间。这两种方法已成功地应用于广泛的对象域，其中广义的中值问题具有固有的高计算复杂性（通常为$ \ Mathcal {np} $ - 硬），因此需要近似解决方案。以前，在计算中使用了显式嵌入方法，这通常不反映对象之间的空间关系。在这项工作中，我们介绍了一个基于内核的广义中间框架，该框架适用于积极的确定和无限核。该框架计算对象与其在内核空间中的广义中位数之间的关系，而无需显式嵌入。我们表明，与使用易于计算的内核相比，对象之间的空间关系比在显式矢量空间中更准确地表示，并在三个不同域的数据集上展示了广义中值计算的出色性能。我们的工作产生的软件工具箱可公开使用，以鼓励其他研究人员探索广义的中位数计算和应用。

长序列中的子序列异常检测是在广泛域中应用的重要问题。但是，迄今为止文献中提出的方法具有严重的局限性：它们要么需要用于设计异常发现算法的先前领域知识，要么在与相同类型的复发异常情况下使用繁琐且昂贵。在这项工作中，我们解决了这些问题，并提出了一种适用于域的不可知论次序列异常检测的方法。我们的方法series2graph基于新型低维嵌入子序列的图表。 Series2Graph不需要标记的实例（例如监督技术）也不需要无异常的数据（例如零阳性学习技术），也不需要识别长度不同的异常。在迄今为止使用的最大合成和真实数据集的实验结果表明，所提出的方法正确地识别了单一和复发异常，而无需任何先验的特征，以优于多种差距的准确性，同时提高了几种竞争的方法，同时又表现出色更快的数量级。本文出现在VLDB 2020中。

Originally, tangles were invented as an abstract tool in mathematical graph theory to prove the famous graph minor theorem. In this paper, we showcase the practical potential of tangles in machine learning applications. Given a collection of cuts of any dataset, tangles aggregate these cuts to point in the direction of a dense structure. As a result, a cluster is softly characterized by a set of consistent pointers. This highly flexible approach can solve clustering problems in various setups, ranging from questionnaires over community detection in graphs to clustering points in metric spaces. The output of our proposed framework is hierarchical and induces the notion of a soft dendrogram, which can help explore the cluster structure of a dataset. The computational complexity of aggregating the cuts is linear in the number of data points. Thus the bottleneck of the tangle approach is to generate the cuts, for which simple and fast algorithms form a sufficient basis. In our paper we construct the algorithmic framework for clustering with tangles, prove theoretical guarantees in various settings, and provide extensive simulations and use cases. Python code is available on github.