Try bending the mat bristle-side out a little bit at a time. With the "fanned" part of the rug facing downward, beat the back of the mat to let the debris fall toward the floor. Do this both for the width of the rug and its length. You could also roll the mat up and strike the ground for a similar result.
Fanning the bristles opens up the space between the bristles allowing loose bristles, dirt, fibres to work free.
A vacuum cleaner can also be used but it will not work any better due to the nature of natural bristle mats to resist a strong seal near the base.
Lastly, pluck tufts of lint and balled-up fibres with your fingers from the surface and you're good to go.
In winter, put the mat face down on freshly-fallen snow for a few minutes and walk on the bottom of it. Turn it face-up and sweep the snow off it and most of the dirt will be gone with the snow.