On-line Partial Discharge (PD) monitoring is being increasingly adopted in an effort to improve asset management of the vast network of MV and HV power cables. This paper presents a novel method for autonomous recognition of PD patterns recorded under conditions in which a phase-reference voltage waveform from the HV conductors is not available, as is often the case in on-line PD based insulation condition monitoring. The paper begins with an analysis of two significant challenges for automatic PD pattern recognition. A methodology is then proposed for applying the K-Means method to the task of recognizing PD patterns without phase reference information. Results are presented to show that the proposed methodology is capable of recognising patterns of PD activity in on-line monitoring applications for both single-phase and three-phase cables and is also effective technique for rejecting interference signals.