Es alguna app que instalaste. Trata de ubicar qué apps instalaste alrededor de la fecha en que te sale la publicidad. Una forma es desinstalar las apps que sospechas una a una hasta identificarla.
La otra, hay un par de apps para eliminar/bloquear publicidad, como airpush detector, adaway, adblock, luckypatcher, lbe security master, etc. Requieren dispositivo rooteado.