#🔒 Optimizing Python code to centroid data

65 messages · Page 1 of 1 (latest)

mellow sequoiaBOT
#

@south bear

Python help channel opened

Remember to:

  • Ask your Python question, not if you can ask or if there's an expert who can help.
  • Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
  • Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.
south bear
#

Hi all, I'm a physicist (and rather inexperienced Python programmer!) working on writing some code to "cluster" and then "centroid" some data from a detector. The TLDR of the problem is events that are close to one another in space and time need to be grouped into one "centroid". I'm using a KDTree to find clusters but I'm looking for advice on further optimizations I can make or other suggestions. The code will be run many times on large datasets.

https://pastebin.com/K8qm7SDS

Happy to provide any more context which would be helpful.

Pastebin
from scipy.spatial import KDTreeimport numpy as npimport pandas as ...

Pastebin.com is the number one paste tool since 2002. Pastebin is a website where you can store text online for a set period of time.

#

Main things I'm wondering about:

Is there a more efficient way to remove the duplicate list of indices than:
clusters = set(tuple(n) for n in neighbors)

Is there a better way to do what I'm trying to do in cluster_stats() and create_cluster_arr() in preparation to go into cluster_arr_to_cent() ? I'd like to try to go straight from generating clusters from KDTree into njit but the list of lists is giving me a hassle.

fringe mantle
#

oh i was just working on basically this a few hours ago, lemme get to my computer and i'll see if i have any info that could help

fringe mantle
#

also what order of magnitude are the sample sizes? if you're willing to play with specific parameters, there's a very useful table here with info for which clustering algorithm to use

scikit-learn
2.3. Clustering

Clustering of unlabeled data can be performed with the module sklearn.cluster. Each clustering algorithm comes in two variants: a class, that implements the fit method to learn the clusters on trai...

#

and one way to maximize speed is to do everything in numpy

#

converting between numpy arrays and lists/sets/tuples is slow for large datasets (>500k or so)

#

if you're able to share the dataset, i'd be happy to run a profiler over to look at some places that could use optimization

south bear
#

The detector writes partitions and I'd process many partitions in parallel. Input data (to build the KDTree) is around 1M events/partition but in principle could go be significantly larger (say 100M).

Yeah, I'd like to get it in numpy, however the number of events/cluster varies. The output of the KDTree query_ball_point is a list of lists that might look like:

[[0], [1], [2,3], [2,3], [4,5,6], [4,5,6], [4,5,6], ...]

#

I was thinking about doing DBSCAN too

fringe mantle
#

yeah i do hdbscan usually

#

but i've noticed HDBSCAN was super slow for me with <5 clusters and an input of shape 50k, 2

#

took like 8 seconds

#

i've been trying to switch to optics for a few hours now

fringe mantle
south bear
#

I have a large number of small clusters. 1M raw events might get grouped into 750k clusters where most clusters are size 1, some small numbers are 2, and trivial are 3, 4, 5

#

Not really. The server I'll run it on has 755GB of memory. I guess if I try to run many partitions in parallel it could be but I haven't run into that

fringe mantle
#

ah ok

#

seems like a powerful server, have you profiled the code yet to see which lines/functions are taking the most time?

#

i see the query_ball_point seems to only be using one cpu core

south bear
#

I'm OK with it only using one core, as I'll be running that whole bit on many different partitions in parallel

fringe mantle
#

ah ok

south bear
#

I should profile it more. I'm mainly just frustrated that I have to go through so many hoops to get the list of lists of indices into numpy or something I can play with nicely using njit, haha

fringe mantle
south bear
#

Well I have a list of lists that has duplicates right. I want to get it into a numpy array so I can use vectorized or numba computations on it. But first I have to convert the list of list to a set of tuples to kill duplicates (maybe not necessary if I can get it in numpy first then do .unique as you suggest), but then I also have to find the maximum length of clusters, and then iterate over every event in my (now set) to assign the values in the numpy array

#

Unless I'm missing something!

fringe mantle
#

to kill duplicates, i'd do clusters = np.unique(np.array(neighbors))

#

lemme think on the rest

south bear
#

` clusters = set(tuple(n) for n in neighbors)

num_clusters = len(clusters)
max_cluster = max(map(len, clusters))

cluster_arr = np.full(
    (num_clusters, max_cluster), -1, dtype=np.int64
)  # fill with -1; these will be passed later
for cluster_num, cluster in enumerate(clusters):
    for event_num, event in enumerate(cluster):
        cluster_arr[cluster_num, event_num] = event
return cluster_arr`
#

I can't do np.array(neighbors) :
ValueError: setting an array element with a sequence. The requested array has an inhomogeneous shape after 1 dimensions. The detected shape was (963189,) + inhomogeneous part.

fringe mantle
#

huh

south bear
#

I was looking to see if there was some way I could have it "fill" shorter rows with -1 (Which I ultimately want to do anyway)

fringe mantle
#

you could use dtype=object for np.array but i think that'd defeat the speed benefits

# 
import itertools
clusters = np.array(list(itertools.zip_longest(*neighbors, fillvalue=-1))).T
south bear
#

Hmmmm...there's a few interesting suggestions on this page

fringe mantle
#

then for max cluster i'd do something like:

new_clusters, counts = np.unique(clusters, return_counts=True)
max_cluster = clusters[np.argmax(counts)]
#

bonus that it also get the unique version of clusters

south bear
#

I only need to calculate max_cluster as I do in my code so that I can pre-allocate a numpy array of size (num_clusters, max_cluster_size). If I can find a better way to get the lists into numpy directly then maybe I don't need to

fringe mantle
#

ah ok

#

is the relationship between num_clusters and neighbors 1:1?

fringe mantle
fringe mantle
south bear
#

it varies depending on the dataset. neighbors is the length of the original raw data which I know. before removing duplicates yeah the num_clusters is equal to the original data length

fringe mantle
south bear
#

yeah after removing duplicates it gets reduced

#

oh i see, yeah an individual cluster maybe could go up to 10 or something but most are 1 or 2

fringe mantle
#

oh that wasn't the issue i was thinking of but that could be an issue if i overlooked something

south bear
#

the raw data is output from a detector with small (55x55 micron) pixels and occasionally you get charge sharing where a pixel leaks its charge into nearby pixels and then you gotta group those events together

fringe mantle
#

ic

#

also, sorry if this is slightly off-topic, but i'm an undergrad student studying physics with an interest in computational methods, and i havent decided what i want to do for my bachelor's thesis so i'm wondering what exactly you're measuring

#

profs havent been much help identifying topics

south bear
#

I don't want to share my credentials here but I'll DM you

fringe mantle
#

ah oki

fringe mantle
# south bear ` clusters = set(tuple(n) for n in neighbors) num_clusters = len(clusters...

overall, i'd turn this into

    import itertools
    clusters = np.array(list(itertools.zip_longest(*neighbors, fillvalue=-1))).T

    num_clusters = clusters.shape[0]

    cluster_arr = np.full(
        (num_clusters, clusters[np.argmax(np.unique(clusters, return_counts=True)[1])]), -1, dtype=np.int64
    )

    # since it's a numpy array they're all the same length
    cluster_length = clusters[0].shape[0]
    for cluster_num, cluster in enumerate(clusters):
        cluster_arr[cluster_num, :cluster_length] = cluster
    return cluster_arr
#

also if you can make do with int32 values, the smaller the dtype the faster the vectorized version tends to be

fringe mantle
#

wait a second

fringe mantle
# fringe mantle overall, i'd turn this into ```py import itertools clusters = np.array(...

i think this should be able to be turned into this

    import itertools
    clusters = np.array(list(itertools.zip_longest(*neighbors, fillvalue=-1))).T

    cluster_arr = np.full_like(
        clusters, -1, dtype=np.int64
    )
    # since it's a numpy array they're all the same length
    cluster_length = clusters.shape[1]
    for cluster_num, cluster in enumerate(clusters):
        cluster_arr[cluster_num, :cluster_length] = cluster
    return cluster_arr
#

using the property that numpy arrays of a given shape are always the given shape (idk how to explain this properly but like that a (400, 400, 3) array will always be of shape (400, 3) for any given row or column)

#

i gtg for now but if you need anything else feel free to ping me!

south bear
#

Will do! I'll try some of these now and let you know 🙂 Thanks for the help!

mellow sequoiaBOT
#
Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.