How to search for irregular signals: Fourier, DWT or k-means?

See my notebook here

I want to search for irregular time signals in a data set of ~3 500 000 time signals. By eyeballing I have found hundreds of flat and oscillating signals, but just a few that are irregular (see fig. 1). There are 1000-5000 data points/signal, although sometimes data points are missing or there is even a large gap.

My first plan for designing the search for irregular signals was:

1. Apply Fourier transformation (DFT, FFT o.s.) on all the signals $$f(t)$$ to get $$f(t)=A \cdot \Sigma_k^n e^{ikx} \hat{f}_k$$
2. Afterwards, approximate by setting the smallest contributions $$\hat{f}_k$$ to 0
3. Then, calculate PCA on the 3 500 000 sets of $$[\hat{f}_1, \hat{f}_2, ... \hat{f}_n]$$
4. there should be only "orthogonal" contributions left, on them I can perform K-means clustering
• or calculate the neighbours to the irregular signals $$f_i(t)$$ I have already found by the affinity $$|f_i(t)-f(t)|=[ (\hat{f}_{i1} - \hat{f}_{1})^2 + (\hat{f}_{i2} - \hat{f}_{2})^2 + ... + (\hat{f}_{in} - \hat{f}_{n})^2 ]^{1/n}$$

Steps 1. and 2. above gave really good results in python by using numpy.fft. Even when I set 98% of the smallest $$\hat{f}_k$$ to 0 (fig. 2 and 3) the back transformation of the irregular signal into the time domain was very well approximated (fig. 4). But I figured out, that K-means and $$|f_i(t)-f(t)|$$ might not help me in finding more irregular signals, because they might be not concentrated like the flat or oscillating ones (fig. 5). And I also just learned about DTW (Dynamic Time Warping), that in some cases helps to identify similarity of signals.

My questions are: Is using numpy.fft a legitimate method or will the gaps in the data compromise the results? Is there a better similarity measure than $$|f_i(t)-f(t)|$$ I presented above?

I am new to FFT, k-means and DWT, so explicit answers are appreciated!