Public
Edited
Mar 24, 2023
function copyNestedArray(arr) {
let copy = arr.slice();
for (let i = 0; i < copy.length; i++) {
if (Array.isArray(copy[i])) {
copy[i] = copyNestedArray(copy[i]);
}
}
return copy;
}
function upgma(distanceMatrix) {
distanceMatrix = copyNestedArray(distanceMatrix);
const clusters = distanceMatrix.map((_, index) => [index]);
const result = [];
while (clusters.length > 1) {
const [minI, minJ] = findMinIndices(distanceMatrix);
const minDist = distanceMatrix[minI][minJ];
result.push([clusters[minI], clusters[minJ], minDist / 2]);
const newCluster = clusters[minI].concat(clusters[minJ]);
clusters[minI] = newCluster;
clusters.splice(minJ, 1);
updateDistanceMatrix(distanceMatrix, minI, minJ);
console.log(distanceMatrix);
}
return result;
}
function findMinIndices(matrix) {
let minI = 0;
let minJ = 1;
let minDist = matrix[minI][minJ];
for (let i = 0; i < matrix.length; i++) {
for (let j = i + 1; j < matrix[i].length; j++) {
if (matrix[i][j] < minDist) {
minDist = matrix[i][j];
minI = i;
minJ = j;
}
}
}
return [minI, minJ];
}
function createDistanceMatrix(matrix, metric, similarity) {
let distanceMatrix = [];
for (let i = 0; i < matrix.length; i++) {
let row = [];
for (let j = 0; j < matrix.length; j++) {
let distance;
if (similarity){
distance =
1 - metric(matrix[i], matrix[j]);
}else{
distance =
metric(matrix[i], matrix[j]);
}
row.push(distance);
}
distanceMatrix.push(row);
}
return distanceMatrix;
}
function updateDistanceMatrix(matrix, minI, minJ) {
for (let k = 0; k < matrix.length; k++) {
if (k === minI || k === minJ) continue;
const newDist =
(matrix[minI][k] * matrix[minI].length +
matrix[minJ][k] * matrix[minJ].length) /
(matrix[minI].length + matrix[minJ].length);
matrix[minI][k] = newDist;
matrix[k][minI] = newDist;
}
matrix.splice(minJ, 1);
matrix.forEach((row) => row.splice(minJ, 1));
}
function euclideanDistance(pointA, pointB) {
var sum = 0;
for (var i = 0; i < pointA.length; i++) {
var difference = pointA[i] - pointB[i];
sum += difference * difference;
}
return Math.sqrt(sum);
}
function doubleClustering(matrix, rowNames, colNames, metric = euclideanDistance) {
const distanceMatrix = createDistanceMatrix(matrix, metric, false);
let rowOrder = flatten(upgma(distanceMatrix).slice(-1)).slice(0, upgma(distanceMatrix).length+1)
const transposedMatrix = matrix[0].map((_, i) => matrix.map((row) => row[i]));
const distanceMatrixTransposed = createDistanceMatrix(transposedMatrix, metric, false);
let colOrder = flatten(upgma(distanceMatrixTransposed).slice(-1)).slice(0, upgma(distanceMatrixTransposed).length+1)
const sortedMatrix = rowOrder.map((i) => colOrder.map((j) => matrix[i][j]));
const sortedRowNames = rowOrder.map(i => rowNames[i]);
const sortedColNames = colOrder.map((i) => colNames[i]);
return {
matrix: sortedMatrix,
rowNames: sortedRowNames,
colNames: sortedColNames,
};
}
function flatten(array) {
return array.reduce(function(memo, el) {
var items = Array.isArray(el) ? flatten(el) : [el];
return memo.concat(items);
}, []);
}
Plotly = require("https://cdn.plot.ly/plotly-latest.min.js")
txt=` a b c d e
a 0 17 21 31 23
b 17 0 30 34 21
c 21 30 0 28 39
d 31 34 28 0 43
e 23 21 39 43 0`
fileType= '\t'
arr = txt.split('\n').map(r=>r.split(fileType).slice(1).map(d=>parseFloat(d))).slice(1)
rowNames = txt.split('\n').map(r=>r.split(fileType)[0]).slice(1)
colNames = txt.split('\n').map(r=>r.split(fileType))[0].slice(1)
// doubleClustering(arr, rowNames, colNames)
upgma(arr)
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
