Epilepsy is a common neurological disorder characterized by recurrent epileptic seizures. These seizures have different intensities and might lead to accidents or, in the worst case, to sudden death. Therefore, being able to predict epileptic seizures would allow patients to be prepared, reducing the risk of injury. This paper focuses on epileptic seizure prediction using EEG (Electroencephalogram) signals. In contrast to the standard approach where the preictal state is assumed to have a constant duration in all the seizures of a patient, we propose a new method that labels each seizure individually exploiting clustering. Our labeling approach, which was applicable for 38% of the selected seizures, results in substantial improvements compared to the standard one. In fact, it reduces noise in the labels and improves the performance of the binary classifier used to distinguish the interictal and preictal states. Hence, our results suggest that the preictal duration is seizure-specific, not only patient-specific. Finally, we show that our method is able to predict 17 out of 18 (94%) seizures between 15 and 85 minutes, before seizure onset.