Jak nazywa się algorytm, który na podstawie dosłownie kilku do kilkunastu punktów jest w stanie wygenerować plamy statystycznej gęstości występowania punktów (kolory plam to już inna sprawa, to tylko dobór palety w zależności od prezentowanej wartości)?
Chodzi o coś takiego, jak na tym obrazku:
O ile pamiętam, nazwa pochodzi od nazwiska twórcy tego algorytmu i chyba nawet czytałem o nim, problem w tym, że całkowicie zapomniałem to nazwisko.
To mi wygląda na klastrowanie, ale jaki algorytm dokładnie to nie wiem. (https://towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68)
Pewnie dowolne klastrowanie, jakiś DBSCAN albo coś podobnego powinno dać ci zbliżony efekt.
Nie chodzi o algorytm zastosowany na tym konkretnym obrazku, tylko o to, jakiemu algorytmowi wystarczy tylko kilka-kilkanascie punktów, żeby wytworzyć takie plamy.
Jednak teraz już wiem, czego i jak szukać, jakby co.
Klastrowanie to chyba trochę coś innego (bardziej służy do zlewania punktów w figurę). To, co mnie interesuje nazywa się "heat map" lub "click map".
Postanowiłem popróbować wymyślony przez siebie prosty algorytm, który pobiera takie dane wejściowe:
Wynikiem jest bitmapa zawierająca plamy obrazujące gęstości.
Funkcja spełniająca warunki jest na przykład taka:
f(x) = 1 - x * 0.05 dla x<20
f(x) = 0 dla x=0
Dla każdego piksela mapy wykonuje się operacje:
Czy takie podejście się stosuje?
Czy funkcja odległość-jasność o podanym wzorze jest dobra, czy raczej powinienem zastosować inną funkcję i jaką?
Do testów napisałem prostą aplikację w HTML5/JS (testowana wyłącznie w Mozilla Firefox). Działa ona następująco:
Wyświetlane są dwa obrazy. Górny obraz reaguje na kliknięcia i po każdym kliknięciu na nowo przelicza i wyświetla mapę. Suwak pod mapą umożliwia skalowanie jasności punktów. Dolny obraz wyświetla wykres funkcji odległość-jasność. Funkcja odległość-jasność jest nazwana PointValue.
Dla jasności kodu, celowo pominąłem usprawnienia wydajnościowe, jak np. pomijanie punktów bardziej odległych niż stała c, tablicowanie funkcji odległość-jasność. Aby usunąć wszystkie punkty, należy najzwyczajniej w świecie zrestartować poprzez naciśniecie Ctrl+F5.
<!doctype html>
<html>
<head>
<title>Clickmap</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
<meta charset="utf-8">
</head>
<body>
<div style="border-style:solid;display:inline-block"><canvas style="display:block" id="ClickMap" width="500" height="500"></canvas></div>
<br />
<input type="range" min="0" max="200" value="100" style="width:500px" id="ColorScale" oninput="GenerateMap()">
<br />
<div style="border-style:solid;display:inline-block"><canvas style="display:block" id="DistFunc" width="500" height="101"></canvas></div>
<script>
// Obraz mapy klikniec
var ClickMap = document.getElementById("ClickMap");
var ClickMapW = ClickMap.width;
var ClickMapH = ClickMap.height;
var ClickMapC = ClickMap.getContext('2d')
var ClickMapD = ClickMapC.createImageData(ClickMapW, ClickMapH);
// Obraz wykresu funkcji jasnosci
var DistFunc = document.getElementById("DistFunc");
var DistFuncW = DistFunc.width;
var DistFuncH = DistFunc.height;
var DistFuncC = DistFunc.getContext('2d')
var DistFuncD = DistFuncC.createImageData(DistFuncW, DistFuncH);
// Lista punktow
var PointList = []
// Wstawianie punktu
function SetPoint(Evt)
{
var _ = ClickMap.getBoundingClientRect();
var X = Evt.clientX + window.scrollX - _.left;
var Y = Evt.clientY + window.scrollX - _.top;
//alert('punkt' + [X, Y]);
PointList.push([X, Y])
GenerateMap();
}
// Inicjalizacja aplikacji
function Init()
{
ClickMap.addEventListener('click', function(e) { SetPoint(e); });
GenerateMap();
}
// Generowanie obrazów
function GenerateMap()
{
var ColorScale = document.getElementById("ColorScale").value / 100.0;
// Generowanie obrazu
for (var Y = 0; Y < ClickMapH; Y++)
{
for (var X = 0; X < ClickMapW; X++)
{
var ColorVal = 0;
// Ostateczna jasnosc piksela to suma wartosci funkcji odleglosci dla wszystkich punktow
for (var I = 0; I < PointList.length; I++)
{
ColorVal += PointValue(X, Y, PointList[I][0], PointList[I][1]);
}
// Korekcja gamma w celu uzyskania jasności proporcjonalnej do wartości
// i skalowanie do zakresu od 0 do 255;
ColorVal = Math.pow(ColorVal * ColorScale, 1/2.2) * 255;
if (ColorVal > 255) { ColorVal = 255; }
// Generowanie piksela
var Offset = (Y * ClickMapW + X) << 2;
ClickMapD.data[Offset + 0] = ColorVal;
ClickMapD.data[Offset + 1] = ColorVal;
ClickMapD.data[Offset + 2] = ColorVal;
ClickMapD.data[Offset + 3] = 255;
}
}
ClickMapC.putImageData(ClickMapD, 0, 0);
// Generowanie wykresu funkcji odleglosci
for (var X = 0; X < DistFuncW; X++)
{
// Obliczanie funkcji odleglosci i skalowanie do zakresu od 0 do 100
var Val = 100 - Math.round(PointValue(X, 0, 0, 0) * 100);
for (var Y = 0; Y < DistFuncH; Y++)
{
var Offset = (Y * DistFuncW + X) << 2;
if (Y == Val)
{
DistFuncD.data[Offset + 0] = 255;
DistFuncD.data[Offset + 1] = 255;
DistFuncD.data[Offset + 2] = 255;
}
else
{
DistFuncD.data[Offset + 0] = 128;
DistFuncD.data[Offset + 1] = 128;
DistFuncD.data[Offset + 2] = 128;
}
DistFuncD.data[Offset + 3] = 255;
}
}
DistFuncC.putImageData(DistFuncD, 0, 0);
}
// Obliczanie jasnosci punktu w zaleznosci od odleglosci
function PointValue(X1, Y1, X2, Y2)
{
// Obliczanie odleglosci miedzy punktami (X1, Y1) a (X2, Y2)
var Dist = Math.sqrt(((X1 - X2) * (X1 - X2)) + ((Y1 - Y2) * (Y1 - Y2)));
// Obliczanie wartosci jasnosci
var Val = 1 - (Dist * 0.05);
// Ograniczanie wartosci funkcji do zakresu od 0 do 1
if (Val < 0) Val = 0;
if (Val > 1) Val = 1;
return Val;
}
Init();
</script>
</body>
</html>
Klastrowanie to chyba trochę coś innego (bardziej służy do zlewania punktów w figurę). To, co mnie interesuje nazywa się "heat map" lub "click map".
Ale sam spytałeś o grupowanie punktów i tworzenie "plam". Założyłem z góry ze wiesz że to co chcesz zrobić to heatmap a pytasz jak to osiągąć - np. właśnie klastrowaniem. Klastrowanie pozwala wyznaczyć "spójne grupy" które potem możesz pokolorować zgodnie z jakimiś zasadami.
Najbardziej trywialny pomysł to:
Na koniec możesz sklastrować żeby móc zaznaczyć granice obszarów i to "wygładzić".