đŸȘŽ Quartz 4.0

High-dimensional data analysis study group

Nov 22, 202417 min read

2024-11-22 Cybozu Labs Study Session

  • Previously: 2024-10-18 Public Opinion Map Study Group.
  • This ended up with 4403 rows x 84 columns of data
    • (We are in the process of converting it to open data and will write about it here when it is ready)
  • In this article, I will explain “analysis of high-dimensional data,” including the analysis of this data.
  • Rough Table of Contents
    • History of dimensionality reduction (from PCA to UMAP)
    • UMAP visualization experiment for the 2022 Upper House election
    • New projects (to be announced 11/22)
    • Extraction of dense masses
    • Relation to the KJ method

History of dimensionality reduction (from PCA to UMAP)

  • PCA (Principal Component Analysis) is a linear dimensionality reduction method

  • Mid-20th century: Limitations of PCA (reliance on linearity) begin to be pointed out and the need for methods to handle nonlinear structures increases.

  • 1960s: Multidimensional Scaling (MDS)

    • Mapping high-dimensional data to low-dimensional space based on a distance matrix.

    • Classical MDS is also called Principal Coordinate Analysis (PCoA), and is equivalent to Principal Component Analysis when Euclidean distance is used in Principal Coordinate Analysis. --- Multidimensional scaling - Wikipedia

    • There are linear and nonlinear versions, and nonlinear MDS can handle non-Euclidean distances.

  • 1982: Self-organizing map (SOM, Self-Organizing Maps)

    • Actually, my PhD research 20 years ago was one of the extensions of SOM, so when I told ChatGPT to write a history of nonlinear dimensionality reduction and this came up, I was like, “Whoa, a familiar face!
      • ChatGPT explains that it’s “based on a neuroscientific approach, mapping data onto a low-dimensional grid,” and well, in general, that’s not wrong, but it’s a “model inspired by the neural connections in the brain,” which is common at this time, and it’s so close that it no longer has much to do with the behavior in the brain. It doesn’t have much to do with the behavior in the brain.
        • Well, now neural nets are much less neural.
      • k-means method with adjacencies/distances between representative points
        • Pioneering role as an analysis method that takes into account the topological characteristics of data
      • As of 20 years ago, extensions to non-Euclidean distances were being made.

  • 1998: Kernel PCA (Kernel PCA)

  • Development of “analytical methods that take into account the topological properties of the data.

    • 2000: Isomap (Isometric Mapping)
      • Distance structure is approximated based on graphs, and dimensionality reduction preserving the manifold structure.
    • 2000: LLE (Locally Linear Embedding)
      • Dimensionality reduction is achieved by exploiting the local linearity of the data.

  • 2008: t-SNE (t-Distributed Stochastic Neighbor Embedding)

    • Probabilistic representation of local similarity in higher dimensional spaces and mapping to lower dimensions.
    • Widely used as a specialized method for visualization.

  • 2018: UMAP (Uniform Manifold Approximation and Projection)

    • Improvements to the shortcomings of t-SNE (computational load and collapse of local structure).
    • Mainstream modern visualization and dimensionality reduction methods.

  • I was going to explain the detailed algorithm of UMAP, but that alone would have taken up an hour, so I decided to save it for another time.

    • Summary of this section
      • PCA is a classical dimensionality reduction method from 1901
      • Nonlinear dimensionality reduction methods have been studied for many years because of the disadvantages of being linear
      • Right now it’s considered a good idea to use the 2018 UMAP.

  • Cases where PCA is not a good choice

    • image
      • antagonistic dimension
      • 1: A and B are in conflict
      • 2: (A+B) and C are in conflict
      • 3: ((A+B)+C) and D are in conflict
        • Here the number of dimensions is not enough so that A and B become identical in the 2-dimensional PCA.
        • Nonlinear dimensionality reduction (e.g., UMAP) divides

  • UMAP visibility for the 2022 Upper House election

  • My experience so far has been that Polis tends to become less and less divided into clusters as it progresses.

    • I didn’t want all the clusters to be separated at the end of this poll map.
    • So I was considering a version that uses non-linear UMAP instead of dimensionality reduction using the original Polis PCA.
    • In the experiment of the public opinion map, the “tendency for the clusters to become less divided as they progress” was not observed.
      • This phenomenon may not be due to an increase in the number of voting users, but rather to the fact that the opinion space is becoming more highly dimensioned as users contribute new opinions
      • Detailed discussion: Problem with two Polis clusters.

  • As a preliminary experiment, I visualized the 2022 Upper House election data (Joint research by Taniguchi Laboratory, University of Tokyo and Asahi Shimbun) analyzed by PCA using UMAP before the public opinion map data were available ( 592 respondents, 42 questions)

  • The UMAP analysis is very clearly divided into clusters compared to the PCA analysis, which is almost one cluster of ellipses.

    • image
    • Red boxes are manually added for detailed explanation
    • Some islands are dense, occupied by a particular political party, while others are a mixture of several parties
      • In other words, when there are parties A, B, and C, we tend to think that the division of opinion is between the parties, but in fact the division is between extremists and moderates within the parties.
      • image

  • I think this is a pretty interesting outcome.

  • UMAP of public opinion map image

  • I got the data for the poll map and immediately UMAP’d it.

  • Unlike the 2022 Upper House election data, there is no party data, so I used DBSCAN to cluster the data.

    • DBSCAN has nothing to do with database scanning at all, but Density-Based Spatial Clustering of Applications with Noise
    • Density-based clustering methods (I’ll talk more about them later, so that’s enough for now)

  • There are about 13 scattered clusters and a central [high-dimensional mud pie

  • What is the data volume ratio?

    • 3970 in all, with 655 smaller clusters around the perimeter.
    • 84% of users are in a central cluster with no clear separation

  • Perhaps in the case of politicians answering a questionnaire with a name, there is a “dynamics of opinion polarization” such as the relationship with the claims of the party they belong to, position talk of the opposition party to the ruling party, group polarization, etc. - The opinion vectors of anonymous citizens are not so clearly separated.

Struggle with high-dimensional mud dumplings

  • Can we analyze this part of the center a little better?

    • image
    • It looks like it has a meaningful internal structure, doesn’t it?

  • I was trying to analyze this part of the analysis (Should UMAP results be clustered?, I started thinking that it might be better not to cluster them).

    • image
    • Increasing parameter eps to reduce gray “outliers” causes clusters to be merged
    • imageimage
    • This is more of a problem with interpreting DBSCAN “outliers” as “data that is discarded because it is an outlier that is far away” and should be interpreted as “data that is between two clusters and hard to say which side it is on”.
      • image
      • We want to separate A from B, so where do we draw the line?”
        • Isn’t this question wrong in the first place? that this question is wrong in the first place, isn’t it?
        • Drawing a boundary line is putting in the assumption that it is divisible by a line of no thickness.
        • In reality, many things in the world do not have clear boundaries, but are divided across a wide “neither-here-nor-there” zone
    • (I understood later that this was reinventing the design concept of the DBSCAN/HDBSCAN system.)

  • I shared this story within the Yasuno team and they told me an interesting story: Careful clustering of tSNE results.

  • Attempted clustering directly on higher dimensional space rather than on post-UMAP data

    • image
    • I was shocked to see these results.
    • image
    • What I mean is.
      • Cluster-like dense masses” (blue and purple) after 2D visualization in UMAP
      • imageimage
      • That this is actually not dense at all in higher dimensional space.

  • What is happening?

  • UMAP of the data for and against issue

  • image

    • The greater the amount of data that is neither for nor against, the more reddened it is.
    • The “cluster-like dense clusters” were collections of data with few missing values, and the surrounding complex and meaningful shapes were data with many missing values.

  • Originally, this data was set to matrix.dropna(thresh=3) (only keep the data with 3 or more missing data), but when I changed this to matrix.dropna(thresh=8), the UMAP result was as follows

  • Maybe it’s like this:.

    • The process of filling in missing values with averages has created a very strong cluster of “people who hardly vote at all”.
    • Those who voted properly a lot are scattered in the higher dimensional space, forming a “thin, clear, boundaryless mass”.
    • UMAP estimates density using the distance to the k nearest neighbor points, which interferes with the characteristics of the opposite data where the data are discrete and overlap at the same coordinates, and is recognized as “clusters that are denser than they really are”, and UMAP attempts to isolate and visualize the characteristic clusters.

  • I have not been able to verify it thoroughly, but once I decided that the discrete value opposite vector is not suitable for UMAP, I put this line of thinking on hold.

    • I discarded all the people with missing values and UMAPed the data for only one map, not the 84 dimensions of the whole map, and I was able to get a better idea.

      • image

    • This also supports the hypothesis that “the lack of cluster separation is not a phenomenon caused by an increase in the number of voting users, but by the opinion space becoming more dimensional as users contribute new opinions” for the negative observation in Problem with two Polis clusters. Support.

New projects (to be announced 11/22)

  • This is an analysis for embedded vectors of natural language
  • I found the characteristics of the data distribution to be important, so I examined them with similar data. - distribution of text-embedded vectors - Argument 7574 extracted by Talk to the City extruction from the 18129 retrieved from X - Embedded in text-embedding-3-large, 3072 dimensions - A single mass of nearly uniform distance with some dark areas in places. - Conceptual drawing: One lump with small grains. - image
    • Clustering and Partitioning
    • The “where do we draw the line” question I mentioned earlier.
      • image
      • If you have a density distribution with nothing in between the density peaks like the one on the left, you don’t have to worry about clustering.
      • Real world data has no clear boundary because the data is also between density peaks, as shown on the right.
    • Traditional “clustering” such as K-means attempts to “split” the data set
      • That “division” (partition) is called a cluster.
      • image
      • Even data that are quite far from the peak of A, such as X, separated by a thin density zone, would be considered a “cluster of A”.
      • The DBSCAN authors saw this as a problem.
      • What is a “cluster” anyway?
    • The concept of “clusters” redefined by the authors of DBSCAN
      • A cluster is an area where data points are densely distributed.”

        • a cluster is defined to be a set of density-connected points which is maximal wrt. density-reachability.

      • image
        • The idea that a cluster is just a region of data points above a certain density, and X is noise that does not belong to any cluster.
      • To distinguish between these two ways of thinking about clustering, they refer to the former as “partitioning”
  • Clustering of opinion vectors using Talk to the City is “partitioning”

Extraction of dense masses

  • Now that I understand DBSCAN/HDBSCAN a little better, I decided to use that policy to tweak the Talk to the City algorithm.
  • Argument 7574 extracted by Talk to the City extruction from the 18129 retrieved from X
  • Embedded in text-embedding-3-large, 3072 dimensions
  • From here, we extracted the densely populated areas with HDBSCAN(min_cluster_size=5, max_cluster_size=30, min_samples=2) and obtained 79
    • This setting is intended to pick up a lot of fine clusters
    • Visually, it became, “It’s definitely dense content.”
  • 739 data used for the cluster, 9.8% coverage
    • Judgment that 90% is noise
    • Sometimes we call noise the outlier, but when we say outlier, you’d think it’s relatively small.
  • This approach has advantages and disadvantages compared to the current TTTC
  • The current TTTC, which shows the whole picture with scatter plots and forced clustering, is well suited to satisfy the desire Let’s start with the broad strokes
 I want to get the whole picture
.
    • During the gubernatorial campaign, it was like they’d shut up and show it to the people across the net OR the policy team would read it and refer to it.
      • Some policy team members suggested that another method Talk to the City Turbo was more in-depth and helpful (N=1).
      • Nittele NEWS x 2024 House of Representatives Election x Broad Listening needed to provide “commentary” for viewers
      • The process clarified the need to not only present the big picture, but also to “dig deeper into deep opinions.
        • In this process, the current TTTC can only show N=1 by “mouse hovering over a point”.
        • Also, there is a lack of support in that “finding an opinion to focus on” area.
          • You just look at a few at random and leave it up to luck.
          • You end up looking at all 7,000 cases.
      • The new method we have developed will improve this area.
        • Reduce the burden of “looking at 79 clusters with high concentration instead of looking at all 7,000 cases.”
        • Increased persuasiveness by being able to present as “N=5~30 opinions instead of N=1”.
  • We applied this algorithm to the data in TTTC: Public Comments on AI and Copyright, which can be made publicly available.
    • https://github.com/nishio/ai_kj/blob/main/dense_cluster_extruction.ipynb
    • 5957 cases 1536 dimensions
    • 48 clusters were extracted
    • We had GPT-4o score the cluster interesting, but that in itself did not yield very interesting results!
      • Well, this may be partly because we haven’t taught the AI what the purpose of research is and what kind of things are interesting.
    • It would be more interesting to include a prompt in the output list of clusters to “List clusters that introduce a unique perspective and what is original about them.
      • image
    • ChatGPT log

Relation to the KJ method

  • In the June Talk to the City Study Group, I also wrote about the connection with the KJ method in the appendix.
    • image

    • In his mind, he has a dogmatic principle of grouping, such as, “In my opinion, it is correct to divide this paper material into three major categories: market research, quality control, and labor management. They are simply applying this dogmatic classification scheme and sifting and fitting the paper materials into a ready-made framework. This is a mere sifting and fitting of paper materials into the ready-made wakku, which completely defeats the conceptual significance of the KJ method.

      • Jiro Kawakita criticized human beings for sieving, fitting into [* dogmatic classification wakugumi
    • As a way to deal with this problem, I proposed the KJ method, which is to look at each piece one by one and attach it to the related pieces.
    • This is Agglomerative Hierarchical Clustering in data science terms.
    • TTTC avoids “dogmatic human fitting” by having machines, rather than humans, perform the clustering.
  • This time, the relationship with the KJ method has become even clearer.
  • Clustering in the sense of “partitioning” has split the data set top-down.
  • Extracting clusters with high concentration using a method like DBSCAN is almost equal to “collecting related things to form a group” in the KJ method
  • Leaving things that don’t fit well in a cluster without putting them in a cluster is the same as the KJ method “leave monkey away”.
    • It is not KJ legal to say that 90% of the data will be away monkeys.
    • This phenomenon is caused by the fact that this method defines “proximity” as “distance in the embedded vector space.
    • When humans do the KJ method, they are asked to find connections between things that do not seem to be connected and group them together, and they “discover relationships” such as “This X and Y do not seem to be connected at first glance, but they are related on side A.
      • So this is finding another meaning of “nearness” by performing an additional operation on something that is “far” in the sense of “cosine distance in the embedded vector space”.
      • I think the reason why the KJ method causes the promotion of ideas as a “way of thinking” or “intellectual production technique” is because it forces people to do this “search for relationships.
    • How can a machine search for relationships that are not expressed in the distance of the embedding vector?
      • In my book “Natural Language Processing with word2vec, [Similarity of concepts is not distance.
      • In this case, it may be possible to deal with the problem by randomly collapsing axes, or by collapsing axes with low contribution rate by PCA, or by collapsing axes with the closest contribution rate by reversing the idea (future experiment).
      • If you’d rather get into the LLM context, you could let LLMs “discover relationships” just like humans.
        • I think it’s good to chop it down to an amount that will fit into the LLM context.
        • Because there is a limit to the number of labels that can fit in the human field of vision.
  • KJ legal never throws away one of the away monkeys.
    • In order to achieve this, we need to figure out how to merge the separate monkeys into a cluster.
    • Maybe on a mere distance basis it would “move, but not with good results”.
    • Need to experiment to see if I can prompt the LLM to do it.
  • The KJ method is a technique that requires a great deal of skill to begin with, and Jiro Kawakita, the world’s most experienced KJ methodner, says “50 KJ method assumes 10 hours” and has done only 129 KJ sheets in 5 years because it takes too much time. I felt that the time was approaching when AI would make it an easy method.

This page is auto-translated from /nishio/é«˜æŹĄć…ƒăƒ‡ăƒŒă‚żćˆ†æžć‹‰ćŒ·äŒš using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.

Graph View

Backlinks