Data Mining and Knowledge Discovery

This paper addresses the problem of retrieving meaningful geometric information implied in image data. We outline a general algorithmic scheme to solve the problem in any geometric domain. The scheme, which depends on the domain, may lead to concrete algorithms when the domain is properly and formally specified. Taking plane Euclidean geometry $${\mathbb {E}}$$ as an example of the domain, we show how to formally specify $${\mathbb {E}}$$ and how to concretize the scheme to yield algorithms for the retrieval of meaningful geometric information in $${\mathbb {E}}$$ . For images of hand-drawn diagrams in $${\mathbb {E}}$$ , we present concrete algorithms to retrieve typical geometric objects and geometric relations, as well as their labels, and demonstrate the feasibility of our algorithms with experiments. An example is presented to illustrate how nontrivial geometric theorems can be generated from retrieved geometric objects and relations and thus how implied geometric knowledge may be discovered automatically from images.

Multi-view learning studies how several views, different feature representations, of the same objects could be best utilized in learning. In other words, multi-view learning is analysis of co-occurrence data, where the observations are co-occurrences of samples in the views. Standard multi-view learning such as joint density modeling cannot be done in the absence of co-occurrence, when the views are observed separately and the identities of objects are not known. As a practical example, joint analysis of mRNA and protein concentrations requires mapping between genes and proteins. We introduce a data-driven approach for learning the correspondence of the observations in the different views, in order to enable joint analysis also in the absence of known co-occurrence. The method finds a matching that maximizes statistical dependency between the views, which is particularly suitable for multi-view methods such as canonical correlation analysis which has the same objective. We apply the method to translational metabolomics, to identify differences and commonalities in metabolic processes in different species or tissues. The metabolite identities and roles in the different species are not generally known, and it is necessary to search for a matching. In this paper we show, using different metabolomics measurement batches as the views so that the ground truth is known, that the metabolite identities can be reliably matched by a consensus of several matching solutions.

Topic evolution modeling has received significant attentions in recent decades. Although various topic evolution models have been proposed, most studies focus on the single document corpus. However in practice, we can easily access data from multiple sources and also observe relationships between them. Then it is of great interest to recognize the relationship between multiple text corpora and further utilize this relationship to improve topic modeling. In this work, we focus on a special type of relationship between two text corpora, which we define as the “lead-lag relationship". This relationship characterizes the phenomenon that one text corpus would influence the topics to be discussed in the other text corpus in the future. To discover the lead-lag relationship, we propose a joint dynamic topic model and also develop an embedding extension to address the modeling problem of large-scale text corpus. With the recognized lead-lag relationship, the similarities of the two text corpora can be figured out and the quality of topic learning in both corpora can be improved. We numerically investigate the performance of the joint dynamic topic modeling approach using synthetic data. Finally, we apply the proposed model on two text corpora consisting of statistical papers and the graduation theses. Results show the proposed model can well recognize the lead-lag relationship between the two corpora, and the specific and shared topic patterns in the two corpora are also discovered.

The rise of sophisticated black-box machine learning models in Artificial Intelligence systems has prompted the need for explanation methods that reveal how these models work in an understandable way to users and decision makers. Unsurprisingly, the state-of-the-art exhibits currently a plethora of explainers providing many different types of explanations. With the aim of providing a compass for researchers and practitioners, this paper proposes a categorization of explanation methods from the perspective of the type of explanation they return, also considering the different input data formats. The paper accounts for the most representative explainers to date, also discussing similarities and discrepancies of returned explanations through their visual appearance. A companion website to the paper is provided as a continuous update to new explainers as they appear. Moreover, a subset of the most robust and widely adopted explainers, are benchmarked with respect to a repertoire of quantitative metrics.

Chúng tôi thảo luận về các khía cạnh hình học của phân tích cụm và chỉ ra rằng việc suy diễn cấu trúc hình học của một tập dữ liệu trước khi phân cụm có thể cải thiện đáng kể việc phát hiện cụm: chúng tôi chứng minh rằng việc phân cụm các vector nhúng đại diện cho cấu trúc tiềm ẩn của một tập dữ liệu thay vì các vector đặc trưng quan sát được sẽ mang lại nhiều lợi ích. Để minh chứng, chúng tôi kết hợp phương pháp học tạp UMAP để suy diễn cấu trúc hình học với phương pháp phân cụm dựa trên mật độ DBSCAN. Kết quả từ dữ liệu tổng hợp và thực tế cho thấy rằng điều này vừa đơn giản hóa vừa cải thiện phân cụm trong một loạt các bài toán có chiều thấp và cao, bao gồm các cụm có mật độ khác nhau và/hoặc hình dạng xoắn vào nhau. Cách tiếp cận của chúng tôi đơn giản hóa việc phân cụm vì việc xử lý trước theo hình học nhất quán làm giảm độ nhạy của các tham số của DBSCAN. Phân cụm các nhúng kết quả bằng DBSCAN thậm chí có thể vượt qua các phương pháp phức tạp như SPECTACL và ClusterGAN. Cuối cùng, cuộc điều tra của chúng tôi cho thấy rằng vấn đề quan trọng trong phân cụm không phải là số chiều danh nghĩa của dữ liệu hoặc có bao nhiêu đặc trưng không liên quan, mà đúng hơn là sự phân tách của các cụm trong không gian quan sát xung quanh mà chúng được nhúng, thường là không gian Euclid (có chiều cao) được xác định bởi các đặc trưng của dữ liệu. Cách tiếp cận thành công vì nó thực hiện phân tích cụm sau khi chiếu dữ liệu vào một không gian phù hợp hơn mà được tối ưu hóa cho sự phân tách, theo một nghĩa nào đó.

Social media has reshaped the way in which people interact with each other. The rapid development of participatory web and social networking sites like YouTube, Twitter, and Facebook, also brings about many data mining opportunities and novel challenges. In particular, we focus on classification tasks with user interaction information in a social network. Networks in social media are heterogeneous, consisting of various relations. Since the relation-type information may not be available in social media, most existing approaches treat these inhomogeneous connections homogeneously, leading to an unsatisfactory classification performance. In order to handle the network heterogeneity, we propose the concept of social dimension to represent actors’ latent affiliations, and develop a classification framework based on that. The proposed framework, SocioDim, first extracts social dimensions based on the network structure to accurately capture prominent interaction patterns between actors, then learns a discriminative classifier to select relevant social dimensions. SocioDim, by differentiating different types of network connections, outperforms existing representative methods of classification in social media, and offers a simple yet effective approach to integrating two types of seemingly orthogonal information: the network of actors and their attributes.

Trong những năm gần đây, sự phổ biến của chuỗi thời gian đã tăng vọt. Với việc sử dụng rộng rãi công nghệ thông tin hiện đại, một số lượng lớn chuỗi thời gian có thể được thu thập trong các hoạt động kinh doanh, y tế hoặc sinh học, chẳng hạn. Hệ quả là có sự gia tăng mạnh mẽ về mối quan tâm đến việc truy vấn và khai thác dữ liệu như vậy, điều này dẫn đến việc xuất hiện nhiều công trình giới thiệu các phương pháp mới cho việc lập chỉ mục, phân loại, phân cụm và xấp xỉ chuỗi thời gian. Cụ thể, nhiều thước đo khoảng cách mới giữa các chuỗi thời gian đã được giới thiệu. Trong bài báo này, chúng tôi đề xuất một hàm khoảng cách mới dựa trên đạo hàm. Trái ngược với các thước đo nổi tiếng từ tài liệu hiện có, phương pháp của chúng tôi xem xét hình dạng tổng quát của một chuỗi thời gian hơn là so sánh chức năng điểm đến điểm. Khoảng cách mới được sử dụng trong phân loại với quy tắc láng giềng gần nhất. Để cung cấp một so sánh toàn diện, chúng tôi đã tiến hành một loạt thí nghiệm, kiểm tra hiệu quả trên 20 tập dữ liệu chuỗi thời gian từ nhiều lĩnh vực ứng dụng khác nhau. Các thí nghiệm của chúng tôi cho thấy phương pháp của chúng tôi cung cấp chất lượng phân loại cao hơn trên hầu hết các tập dữ liệu đã được xem xét.

Real-world datasets are often characterised by outliers; data items that do not follow the same structure as the rest of the data. These outliers might negatively influence modelling of the data. In data analysis it is, therefore, important to consider methods that are robust to outliers. In this paper we develop a robust regression method that finds the largest subset of data items that can be approximated using a sparse linear model to a given precision. We show that this can yield the best possible robustness to outliers. However, this problem is NP-hard and to solve it we present an efficient approximation algorithm, termed SLISE. Our method extends existing state-of-the-art robust regression methods, especially in terms of speed on high-dimensional datasets. We demonstrate our method by applying it to both synthetic and real-world regression problems.

The effectiveness of classification methods relies largely on the correctness of instance labels. In real applications, however, the labels of instances are often not highly reliable due to the presence of label noise. Training effective classifiers in the presence of label noise is a challenging task that enjoys many real-world applications. In this paper, we propose a Markov chain sampling (MCS) framework that accurately identifies mislabeled instances and robustly learns effective classifiers. MCS builds a Markov chain where each state uniquely represents a set of randomly sampled instances. We show that the Markov chain has a unique stationary distribution, which puts much larger probability weights on the states dominated by correctly labeled instances than the states dominated by mislabeled instances. We propose a Markov Chain Monte Carlo sampling algorithm to approximate the stationary distribution, which is further used to compute the mislabeling probability for each instance, and train noise-resistant classifiers. The MCS framework is highly compatible with a wide spectrum of classifiers that produce probabilistic classification results. Extensive experiments on both real and synthetic data sets demonstrate the superior effectiveness and efficiency of the proposed MCS framework.