B Caron Llacan
email: caron@vjf.cnrs.fr

Gùùs, aka Sigidi (Chadic, West-B, South-Bauchi): Grammatical notes and vocabulary

Keywords: Aor., aorist, C, consonant, conj., conjunction, Cont., continuous, det., determiner, Fut., future, Hab., habitual, id., ideophone, Imm., immediate, Ipl., plural imperative, Irr., irrealis, n., noun, n.col., collective (=non-count) noun, num., numeral, Perf., perfective, Pl., plural, prep., preposition, Rec., recent, Rem., remote, Spec, specific usage, Vn, verbal noun, VV, long vowel Jigi, Kufai, Tungri, lizard .  n. urine. , bilharzia , IPl: .  n. pumpkin IPl: .  , IPl: .  v. heavy pot, beer pot, water storage pot. Pl , IPl: .  2 v. measure. Vn: , IPl: .  n. bush, farm  v. twist, sharpen, whet .  n. lame. Pl:   n. arrow, sting, quill of insect. Pl: .  v. combine, glue gather, collect, reckon , shoot, kick

This paper was inspired by Jaggar (98) which convinced me of the interest of publishing descriptive material without waiting for a full phonological or comparative analysis. Let him be thanked for it. 1 Transcription system : Long vowels are indicated by double letters ; low (Lo=L) tone =  ; high (Hi=H) tone =  ; middle (Mid=M

Introduction

In his 1975 monograph entitled Boghom and Zaar : vocabulary and notes, Kiyoshi shimizu wrote :

In addition to the Zaar dialects, we may perhaps be able to include the language of the Sugudawa to Zaar, for my informant of Zaar from Kal says that his dialect and this 'language' are mutually intelligible. [...] the Kal forms seemed to have the original tone reconstructed for the Proto-Ɓarawa. In addition, the independant pronouns elicited for the Kal dialect seemed to preserve the older status of the language. (p.6) Gùùs, called Sigidi by Shimizu (78 : 13) belongs to the Southern Bauchi group of the West Chadic-B sub-branch of Chadic (Afroasiatic). It is part of the Zaar dialect continuum and apart from these mentions by Shimizu, remains undocumented. The following notes will confirm Shimizu's intuitions.

  is the ethnonym of a group of people living in 16 villages or so around Sigidi, in the southern part of Bauchi state, Nigeria 2 old, ancient. They refer to a human being as  (pl.) and to the language they speak as  (lit. the mouth of the Gùùs, or the ancient language).

Phonology

Consonant phonemes

                                                                                                                                                                                                   
As in Hausa, all Gùùs words begin with a consonant and vowel-initial words in the transcription are preceded by a glottal stop : , do =  Consonants are labialised in front of short / and /, some= [] ; but [], cola nut. , , m,  and  are palatalised in front of // and //.

Vowels

Gùùs has a six-vowel system, all of them occurring short and long, with no nasals.

short long

                    
Pending a deeper phonological analysis, we have chosen to account for diphthongs as a sequence vowel+glide : a(a)w ; a(a)j ; oj ; uj.

Tones

Gùùs has three levels of tone (Hi, Mid and Lo), plus a rising tone (Lo-Hi) and a falling tone (Hi-Lo).3

Verbal morphology

Monosyllabic verbs

Two thirds of the verbs are monosyllabic. They all have a Mid lexical tone.

Polysyllabic verbs

Apart from those borrowed from Hausa, all polysyllabic verbs are disyllabic, and have either M or MH tone schemes. The tones don't seem to be predictable : lick  try  be far  answer 

Verb plurals

Verbs have a plural Imperative, formed with a - ( suffix and HL(L)

Nouns

There is no morphological gender in Gùùs, but plurals are well developed.

Noun plurals

Two classes of plural can be distinguished :

Regular plurals (probably the more recent), use suffixes. The most common is  frequently combined with lengthening of a radical vowel, plus some other morphonological accidents (apophony, restitution of etymological consonants, etc.). The tone scheme of the singular is generally preserved in the plural. Finally, plural of terms of kinship are formed with the word  used before the singular : = grand-fathers ;  = grand-children ;  = uncles, etc.).

Possessive NP + NP constructions

Like in Hausa, possessive constructions in Gùùs use a genitive link : . The use of the genitive link is not limited to possession, but expresses a more abstract link between two notions. It is used also for adjectival constructions (, a red mango ; , sow = pig of female) and composition. (, beard = hair of chin ; , bilharziosis = urine of blood).

Adjectival nouns

In Gùùs, most qualities are expressed by verbs. The few adjectives comprise colour terms (black, white, red and yellow ; blue is borrowed from Hausa), terms referring to human states (male, female, young, drunk, lazy, insane) and a few other basic adjectives (long, big, new, round). (Cf. the lexicon at the end of the article.)

Derived nouns

Abstract nouns are derived from nouns and verbs with a - suffix.

Deictics

Indefinite determiner

The indefinite determiner is  [] for the singular, and  for the plural. It occurs on the right of the NP : , a boy is harvesting corn ;  some children are harvesting corn.

Definite determiner

The definite determiner is  : , child ; , the child ; , horse ; , the horse ; , goat ; , the goat.

Demonstratives

this that over there sg    pl    Demonstratives occur on the right of the NP, and the Lo tone of the last syllable of the noun lowers the Mid tone of the first syllable of the deictic : , these heads ; , these houses.

'here' and 'there' locative adverbs

here :  ; there : .

Existential predicator

The existential predicator "it is" (Hausa ) is ()... .  copies the preceding tone : , this is a man ;  , it's meat ; , it's a vulture.

Pronominal paradigms

Subject pronouns

Subjunctive

The Subjunctive markers are  for the singular and  for the plural. This is the only case where there is a distinction between singular and plural.



Perfective

The marker is . It is suffixed to the preceding word.

    child some+Perf. shoot bird

A child has shot a bird.

Imperfective

The marker is  followed by a floating Hi tone.

     child some Perf. shoot bird

A child is shooting a bird.

Aorist

The marker is . It is suffixed to the preceding word.

    child some+Aor. shoot bird

A child shot a bird.

Future

The marker is  followed by a floating Hi tone.

     child some

Fut. shoot bird A child will shoot a bird.

Habitual

The marker is . It is followed by a floating Hi tone.

    child some+Hab. beat dog

A child kept beating (the) dog.

Immediate past

The marker is . This tense is compatible with , this morning.

 

  child some+Imm.Past slaughter goat A child slaughtered a goat (this morning).

Recent past

The marker is , suffixed to the preceding word. It is followed by a floating Hi tone. This tense is compatible with , yesterday.

    child some+Rec.Past shoot bird

A child shot a bird (yesterday).

Remote past

The marker is , suffixed to the preceding word. This tense is compatible with , formerly.

    child some+Rem.Past shoot bird

A child shot a bird (formerly).

Irrealis

The marker is , suffixed to the preceding word. The mark appears both in the conditional and in the main clauses.



Syntax

Tone sandhi

Even in the little data we have, one can but notice the importance of tone sandhi in nominal and verbal phrases.

Nominal phrases

The Lo tone of the genitive link spreads rightward on to the next Mid tones : , the situation of the world (cf. Hausa 'zaman duniya' ; world = ; , bull (lit. cow of male ; male = ). When the genitive link is omitted, the Lo tone remains and spreads in the same way : , blacksmith (lit. man of forging ; forging = ). When followed by a Lo tone word, the genitive link raises the first tone : , wild animals (lit. meat of bush ; bush = ) ; , cobweb (lit. house of spider ; spider = ).

Verbal phrases

Rem : the Lo tone of plural pronouns spreads on to the following Mid tone of the verbs, except in the Imperfective, Future and Recent past where they are followed by a floating Hi tone. The singular object pronouns have a Mid tone which assimilates to any preceding Lo tone.

When a direct object begins with a Lo tone, it becomes Hi : , he hunted wild animals ( = wild animals) ;, he beat the dog (dog =).

Negatives

The same negative particle  appears at the end of all negative sentences.   he+Imm.Past jump+Neg.

He did not jump.

In the Perfective, an extra  is inserted between the subject pronoun and the verb :

     he+Perf. Neg. cut corn his+Neg.
He has not yet harvested his corn.

Question

Yes/no questions

Yes/No questions are expressed through intonation, without any syntactic change to the sentence. A  is suffixed to the last word of the sentence.



  tones.One verbal extension was identified, elicited with Hausa grade 5 'causative' verbs. It is not very productive. The form is  with a Mid-Hi tone scheme.  suffix and MH tone. They correspond to monosyllabic verbs in CVV, and a few monosyllabic verbs ending in  , ,  or .

			ask			
			hobble		
			protect		
			think	Verb   Plural Imperative
			unroll 		
	4. Numerals		knead 	
			chop	 
		1	lick  11 	 
	2 There are traces of a pluractional derivation through lengthening of the first vowel :  12  3  13 
		combine, glue  gather 4  20   bite  chew 5  21   tie  tie 6  30   see, look at  examine 7  40   answer  refuse 8  50   cease  9  100  stand, stop  10  10000 
	3.4 Verbal extensions
	original vb. Hausa		derived vb.	Hausa	
	come out	fita				get out	fitar (da)	
	enter	shiga			let in	shigar (da)	
	get up	tashi				make stand	tasar (da)	
	lie down	kwanta  lay down	kwantar (da) 
	come down sauka			take down	saukar (da)	
	3.5 Verbal nouns
			beg		
			knead 	
			boil		
			sleep	 
	(ii) -unroll 	
				dig			
				shoot	 
				throw		
				cut			
				spin		  	
	A few monosyllabic verbs in CVV take a (i) Vn
				lie down  
				grow		 
	(iii) verbal nouns of verbs borrowed from Hausa, keeping their original Hausa form, with L tones.

Three classes of verbal nouns can be identified :

(i) - suffix and L tones.

  Subject pronouns are pre-verbal. The Lo tone of plural pronouns spreads on to the following Mid tone of the verbs, except in the Imperfective, Future and Recent past where they are followed by a floating Hi tone. With a nominal subject, specific morphemes appear for each tense.

	Subjunctive Perfective Imperfective Aorist	Future Habitual 5
	1sg. 		+H		+H 
	2sg. 		+H		 +H 
	3sg. 		+H		+H 
	1pl 		+H		+H 
	2pl 		+H		+H 
	3pl 		+H		+H 
		Immediate past Recent Past Remote Past Irrealis
	1sg. 	+H		
	2sg. 	+H		
	3sg. 	+H		
	1pl		+H		
	2pl		+H	 	
	3pl		+H		
	Comments :

     child

		some+Irr. beat dog	3s.+Irr. die
	If a child had beaten the dog, it would have died
	Realis conditions are introduced by followed by the Aorist.
	 	  	
	if	you+Aor.	beat	dog	3s.+Fut. die
	If you beat the dog, it will die.
	7.2 Other pronouns
		Object pronouns Possessive pronouns	Independent pronouns
	1sg. 			
	2sg. 			
	3sg. 			
	1pl				
	2pl				
	3pl				
	The singular object pronouns have a Mid tone which assimilates to any preceding Lo tone. There is
	no specific marking of the Dative.

,see:.

   he+Aor. Come+Quest.Caron, Bernard. (2000). A propos de Kal et de Sigidi : problèmes de dialectologie zaar (tchadique sud-Bauchi). Communication au Troisième Congrès International de Linguistique Africaine (Lomé, 21-25 août 2000). Jaggar, Philip J. Guruntum () (West Chadic-B): Linguistic Notes and Wordlist. African Languages and Literatures, 1988, n° 2, vol. 1, p. 169-189. Schneeberg, Nan. Sayanci verb tonology. Journal of African Languages. Special Chadic Issue, 1971, n° 1, vol. 10, p. 87-100. Schneeberg, Nan. Sayanci Phonology. Ph.D. : Indiana University. 1974. Shimizu, Kiyoshi. Boghom and Zaar: Vocabulary and Notes. Kano :, 1975, 40 p. Coll. Centre for the Study of Nigerian Languages Monograph. Shimizu, Kiyoshi. (1978). The Southern Bauchi Group of Chadic Languages. A survey report, 50 p. Coll. Africana Marburgensia ; n° 2 (Special Issue ). .  n.col. vagina.  n. black ant. Pl: .  n. ridge. Pl: .  n. shrub producing red berries.  n. eagle.

	   			   	   
	blue colour	adj. . n. .	bridge cover (a pot) v. . n. .
	 you (sg.)+Aor. arrive when ?   When did you arrive ? 9. References boat n. . body n. . combine v. . come v. . English -Gùùs wordlist  bring v. . broom n. . cow gen. co-wife n. . e boil up v. . brother n. . come back v.i. . cowry n. .  n. liver. Pl: . bone n. . brother-in-law n. . come out v. . crab eagle n. . embroider n. . n. .  n. lungs. ; sunshine. book n. . bubble v. . compound n. . crawl v. (2). ear n. . end n. . a borrow v. . bucket n. ; cook v. (1). crested crane n. . earring n. . enemy -,see:.
	; honey. bottle n. . cooking pot n. . eat v. .  v. do. Vn: ; IPl: . ; travel. ; repeat. ; fight. ; ruminate, chew the cud. ; milk. above prep. . bottle gourd n. . copulate v. . ebony n. .  n. python.  n. crocodile. Pl: . ; sperm. abscess n. . bow n. . corn gen. n. (1). egg n. . ; green. abuse v. . bow down v. . corpse n. . egg-plant n. .  n. profit.  n. ram.  n. calf.  v. knead. Vn: ; IPl: .  n. market.  n. jealousy.  n. grandmother. Pl: .  n. tick.  n. centipede. ; pus. acacia albida n. ,see:. bracelet n. . correct n. . eight num. .  n. donkey. Pl: . acacia nilotica n. . brain -,see:. cotton n. . eighteen num. ;  n. tears. accuse v. . branch n. ; cough v. . num. .  n. world. acha n. . v. . council n. . eighty num. .  n. worm. Pl: . across prep. . break v. ; count v. . elbow n. . adder n. . v. . courage n. ,see:. elder brother -,see:. adze n. . breast (female) n. . court n. . elder sister n. . agree n. . ember agama lizard n. . breathe v. . eleven num. .	n. . crocodile n. . enter v.t/i. (1). ; wound. . ant hill -,see:. build v. . crooked v t/i. . entrance hut n. . antelope n. . bull -,see:. cross v. . equalize v. .  n. uncle (father's brother). Pl: . anus n. . bullet -,see:. crow n. . escape v. .  n. dove. Pl: .  n. fishing hook.  n. pigeon. Pl: .  n. caterpillar. anvil n. ,see:. bullrush millet n. . cry escort v. (2). v. . appear v. . bundle (corn, wood) n. (2). cup evening n. . n. . ; stallion. appropriate v. . burn v. . curse ewe -,see:. -,see:. ; mare. argue v. . bury -,see:. cut examine v. . v. (1); ; mantis. armpit n. . bush n. ; v.t. (1). exceed v. .  n. tortoise. Pl: . arrive v. . n. . excreta n. .  n. stomach. Pl: . arrow n. (1). bush cow -,see:. extinguish (fire) v. .  n. foam. ask (a question) v. . at prep. ; d   n. son, boy. Pl: . ash n. . butcher -,see:. eye n. .
					prep. ;
	dance	n. ;			prep. .
		v. .	aunt	n. ;
					n. .
	dig	v. ;
	female	v. . adj. ;
	Did he come ?  you (sg.)+Aor. see   me+Quest. Did you see me ? 8.3.2 Wh-questions dirt, filth n. (2). n. . dirty fence n. ; v. . disease n. . n. . dish fetish n. (1). n. . fever n. . disperse (intr.) v. . beat v. ; centipede n. . divide v. . few, little adv. . v. (1). chain n. . divinator n. . ficus gnaphalocarpa n. . bed n. . chameleon n. . diving n. . ficus thonningii n. . Questions words appear in situ. bed-bug n. . change v. . divorce v. (2). fifteen num. .	 n. shade. bite v. (2);  adv. last year. v. ;  n. night. v. .  n. yam. bitter v. .  n. neck. Pl: . black adj. . cloud n. . dwell v. .  n. ficus gnaphalocarpa. Pl: . black spitting snake sp. n. . club n. . dye v. (2).  v t/i. bend, crooked. Vn: . blacken v. . cobweb -,see:. dye-pit -,see:. blacksmith -,see:. cock n. . dysentery n. .
	bee charcoal do fifty	  n. . n. . v. . num. . 	blanket	n. .
		who	Aor. arrive+Det.
		Who came ?
			 
		he+Aor stay where ?
		Where did he stay ?
			Gùùs -English Wordlist English -Gùùs wordlist English -Gùùs wordlist English -Gùùs wordlist	13 22 23 24

  v. pray god. Vn: ; IPl: .  adj. white.  n. sun, god.  n. lamp.  n. acha, hungry rice.  n. gum tree sp. Pl: .  v. cover (a pot). Vn: ; IPl: .  n. thunder.  v. blow (with mouth), winnow. Vn: ; IPl: .  n. granary. Pl: .  v. beg for. Vn: ; IPl: .  n. baboon. Pl: ; .   v. put. Vn: ; IPl: .  v. let ferment.  n. bridge.  n. head, bundle (corn, wood). Pl: . ; roof.  n. drum hanging from the shoulder, beaten with a stick. Spec:  'smaller type of ganga';  'bigger type of ganga'. Pl: .  n. shield. Pl: .  n. crested crane.  n. woman, wife, female. Spec:  'mare';  'female rat'. Pl: . ; widow. Pl: . ; bride. Pl: . ; daughter in law. ; witch.  n. hiccup.  n. soot.  v. branch. Vn: ; IPl: .  v. send (so do sth), escort. Vn: ; IPl: . ; sing. ; curse.  n. cheek, jaw. Pl: .  n. chest. Pl: .  n. wing. Pl: .  n. bullrush millet.  n. grass.  n. palm tree.  n. African ebony tree.  v. laugh. Vn: ; IPl: .  n. acacia nilotica.  v. vomit. Vn: ; Vn2: ; IPl: .  v. get black, dirty, ripe (itili). Vn: ; IPl: .  adj. round.  n. dry season.  n. lid of granary. Pl: .  prep. in, at.  v. laugh. Vn: ; IPl: .  n. ash, ember. Pl: . ; gunpowder.  n. bed. Pl: .  det. some, other. Pl: .  n. cola nut.  n. dum-palm.  v. plough with the big hoe. Vn: ; IPl: ; Spec:  'farm'. ; bury.  n. poison.  n. fist. Pl: .  n. hammer.  n. kiln. Pl: .  n. seasonal river. Pl: .  n. ululation. Pl: .  n. bucket to draw water. Pl: .  n. drumstick. Pl: .  n. mumps.  n. cock. Pl: .  v. forge (blacksmith). Vn: ; IPl: .  n. clay for houses and pots.  n. bachelor, widower. Pl: .  n. celibacy.  v. old (ant. new). Vn: .  n. Gùùs (ethnonym).  n. rule.  v. sell, trade. Vn: ; IPl: .   v. drive away. Vn: ; IPl: .  n. flour.  n. red pepper, spice.  adj. lazy.  v. abuse. Vn: ; IPl: .  n. today.  n. war. Pl: .  n. tree.  v. be ripe (corn, maize). Vn: .  n. saliva.  n. co-wife. Pl: .  n. soil.  v. cough. Vn2: ; IPl: .  n. wind, spirit. Pl: .  v. harvest standing crop (e.g. corn). Vn: ; IPl: . ; harvest of corn.  n. corn gen., millet.  n. bird. ; hawk, falcon.  adv. when?  adj. yellow.  n. friend. Pl: .  n. thorn. Pl: .  n. acacia albida.  v. produce. Vn: ; IPl: ; Spec:  'urinate'; 'defecate'.  v. full. Vn: .  v. plant (e.g. tubers, tomato), sow (seeds in a hole). Vn: ; IPl: .  v. possess. Vn: ; IPl: .  v. sue, accuse. Vn: ; IPl: .  n. eye. Pl: .  n. excreta.  n. nose.  n. snake. Pl: ; .  n. smoke.  v. scratch. Vn: ; IPl: .   n. heal.  v. cold. Vn2: .    adv. behind.  n. papaw.  n. bark. Pl: .  n. bee wax.  n. bottle gourd. Pl: .  v. hear, feel, smell. Vn: ; IPl: .  n. coco-yam sp.  n. egg-plant.  n. garden egg, bitter tomato.  n. straw, stalks. Pl: . ; sugar cane.  n. crow, crab. Pl: .  n. water melon.  v. seize, take. Vn: ; IPl: .  prep. into.  v. stick, push into the ground. Vn: ; IPl: .  v. dig, farm (i.e. rice). Vn: .    Gùùs -English Wordlist 14  n. back. Pl: . ; nape of the neck.  n. gecko.  n. lip. Pl: .  v. increase. Vn: ; IPl: .  n. dog. Pl: . ; jackal. ; hippopotamus.  v. rub. Vn: ; IPl: .  n. jujube tree. Pl: .  n. rattle. ; ankle metal rattle.  n. uncle (mother's brother). Pl: .  n. small reed.  v. itch. Vn: .  n. catfish, mudfish. Pl: .  n. lightning.  n. ear. Pl: .  adv. in front.  v. cut (i.e. with a machete); bite (i.e. snake). Vn: ; IPl: .  v. hollow out. Vn: ; IPl: .  v. run, flow. Vn: ; IPl: .  v. cross. Vn: ; IPl: .  n. handle. Pl: .  n. antelope. Pl: .  n. shirt. Pl: . ; man's gown.  n. prostitute.  n. guitar.  n. work. Pl: .  n. winnow. Pl: .  n. tail.  v. roll. Vn: ; IPl: .  n. sand.  n. face. Pl: .  v. shame. Vn: ; IPl: .  v. learn. Vn: ; IPl: .  v. hunt. Vn: ; IPl: .  n. cup. Pl: .  n. penis sheath. Pl: .  n. open-ended hour glass drum beaten with hand. Pl: .  n. younger brother. Pl: .  n. brother-in-law. Pl:  n. servant. Pl: .  n. mortar. Pl: .  v.i. dry up, ripen. Vn: ; IPl: .  n. skin. Pl: .  n. shell, peel (i.e. groundnut).  n. deaf. Pl: .  n. rat. Pl: ; .  n. hunger.  n. tin.  n. testicle. Pl: .  n. room, hut. Pl: .  n. kidney. Pl: .  n. okra.  n. leopard, panther. Pl: .  n. small hoe. Pl: .  n. oil-palm.  n. black plum tree.  n. bottle.  n. slip.  v. look for, find. Vn: ; IPl: .  v. count, read. Vn: ; IPl: .  n. dish. Pl: .  v. wipe. Vn: ; IPl: .  n. fowl gen. Pl: .  n. pebble.  n. calabash. Pl: .  n. skull.   n. sickle.  n. cave. Pl: .  n. corpse. Pl: .  v. hard, strong. Vn: ; Vn2: .  v. go, disperse (intr.). Vn: ; IPl: .  n. garden. Pl: .   v. pull, crawl. Vn: ; IPl: .  n. water. ; fish. Pl: .  v. tame, teach. Vn: ; IPl:  v. show sth. Vn: ; IPl: .  n. owl. Pl: .  n. horse. Pl: .   v. sow (hungry rice). Vn: ; IPl: .  n. sling. Pl: . ; rainbow.  v. tear. Vn: ; IPl: .  v. doorway. Pl: .  n. branch. Pl: .  prep. across. Vn: .  v. chop wood. Vn: ; IPl: .  n. facial marking.  n. squirrel. Pl: .  n. guinea-fowl. Pl: .  v. breathe. Vn: ; IPl: .  v. fear. Vn: ; IPl: .  v. squeeze, wring out. Vn: ; IPl: .  v. snore. Vn: ; IPl: .  v. cease. Vn: ; IPl: .  v. stand, stop. Vn: ; Vn2: ; IPl: .  n. middle, trunk of tree. ; noon.  n. body. ; become fat.  n. bone. Pl: .  v. suck. Vn: ; IPl: .  v. keep quiet. Vn: ; IPl: .  n. marrow. Pl: . ; brain. v. . all adv. . allow v. . alone adv. . amulet n. . animal -,see:; n. . anklet n. . answer v. . ant n. . ant gen. n. . avoid v. . awnings n. . axe, fighting axe n. . b baboon n. . baby n. . bachelor n. . back n. . bad n. . bag n. . banana n. . bank (river -) -,see:. baobab tree n. . bark n. . barter v. . basket n. . bat n. . beans n. . beard -,see:. bee wax n. . bee-hive -,see:. bee-keeper -,see:. beer n. . beg for v. . begin v. . behind -,see:. bellows n. . belly n. . belt n. . bend v t/i. . beniseed n. . big, large adj. . bilharziosis -,see:. bird n. . blind n. . blood n. . blow (wind) v. . blow (with mouth) v. . brew -,see:. brick n. . bride -,see:. bridegroom n. . butter n. . butterfly n. . buy v. . c calabash n. . calf n. . call v. . camel n. . cap n. . car n. . carpentry v. ; v. . carry v. . cassava n. . castrated ram n. . cat n. . catapult n. . catch v. (1). catch up with v. . caterpillar n. . catfish n. . cattle n. . cave n. . cease v. . celebration n. . celibacy n. . charm n. . chase -,see:. cheek n. . chest n. . chew v. . chick n. . chicken pox n. . chief n. ; n. . chieftainship n. . child n. . childhood n. . chin n. . choose v. . chop (a tree down) v. (1). chop wood v. . circumcision n. . clan n. . claw; nail n. . clay n. . clay-pit -,see:. cleanness n. . cleverness v. . clitoris n. . clothes -,see:; n. (2). coco-yam n. ; n. . cola nut n. . cold v. . collect v. (1). n. . dassie n. . date palm n. . datura n. . daughter n. . daughter in law -,see:. dawn n. . deaf n. . debt n. . deceive v. (1). decrease v. . deep v. . defecate v. . defend oneself -,see: 2 . desert date tree n. . destroy v. . dew n. . die v. . difficult v. dog n. . domestic animal -,see:. donkey n. . door -,see:. doorway v. . doubt n. . dove n. . dowry n. . draw v.  2 (1). dream n. . drink v.  1 . drive away v. . drop v. . drum n. ; n. . drummer n. . drumstick n. . drunk adj. . drunkenness n.col. (2). dry v. . dry season n. . dry up v.i. . duck n. . dumb and deaf n. . dum-palm n. . dung n. . dung beetle n. . dusk n. . f fabric, cloth n. . face n. . facial marking n. . falcon -,see:.

fall v. (1). fallow land n. . family n. . fan v. . far v. . farm n. ; v. . farmer -,see:. fat -,see:; n. . father n. . fear v. . feather n.col. . feed -,see:. feel v. . fight -,see:; n. . fill v. . filter n. ; v. . find v. . finger n. . finger millet n. . finish v. . fire n. . fire-place n. . fish -,see:. fisherman -,see:. fishing hook n. . fishing net n. . fist n. . five num. . five hundred num. . flag n. . flail -,

see:. flame -,see:. flatten v. . flea -,see:.

	    		    	    
	formerly hobble pull up shake sun	adv. . v. . v. . v. . n. (1).	frog human being n. . n. . lion n. . put n. ; sneeze v. .
	forty four fowl gen. n. . num. . num. . francolin n. . hoe n. ; n. . hold v. (1). hold down v. (2). leatherworker n. . leave v. . leaves n. (1). left side n. . pumpkin n. . shame v. . name n. . id. . pus -,see:. push v. . share out v. . sharp v.  1 .	fruit fruit-bat fry full hundred hunger hungry rice n. . n. . n. . v. . v. . num. . n. . hunt n. ; lip n. . live v. . liver n. . lizard n. . v. . snore v. . n adv. . son, boy n. . next year python n. . soil n. . some det. . v
	freeze friend hole hollow leg lemon nape of the neck -,see:. n. . n. . n. . id. . n. . n. . narrow v. . sharpen, whet v. (2). vagina n.col. . shea-butter tree n. . veins n. .	funeral load locust night Nile monitor n. . n. . n. ; v. . n. . n. . n. . song n. . vomit v. . q son-in-law -,see:. vulture n. .
	hollow out v. . honey -,see:. horn n. ; let ferment v. ,see:. neck n. . v. . shield n. . quiet lend v. . leopard n. . navel n. . near n. . queen bee n. ,see:. sheep n. . shell n. . village n.col. . voice n. .	g hunter hurry husband ninety sorrel locust-bean tree n. . -,see:. n. . n. . num. . n. . v.  2 . loincloth n. (2); nine num. . nineteen num. . quiver n. . soot n. . sorcerer -,see:. t
	galloping n. . garden n. . gather v. (1). gazelle n. . gecko n. . get down v. . get lost v.t/i. . ghost n. . n.col. . hornbill (ground -) n. . horse n. . horse rider -,see:. hot v. ,see:. I pro. . iguana n. . in, at prep. . in front adv. . liar -,see:. lick v. . lid n. . n. . lie v. . lie down v. . life n. . lift v. . light -,see:. lightning n. . like v. . limp v. . one num. ; necklace n. . needle n. . nest -,see:. new adj. . oil n. . oil-palm n. . okra n. . old v. (1); v. . on prep. . shin n. . shine v. . tail n. . take v. ; rabbit n. . raffia-palm n. . rain n. . rainbow -,see:. ram n. . rat n. . rattle n. . read v. . reckon v. (2). shirt n. . shoe n. . shoot v. ; v. . shoulder n. . shout (= throw a cry) v. ,see:. show sth. v. . shrew n. . v. . tamarind n. . waist n. . tame v. . walk v. . tan v. . walking stick n. . tan-bark -,see:. wall of compound n. . tanner -,see:. wall of room n. . wart-hog warm v. . war n. . teach v. . want v. .	grandmother n. . grass n. . n. . grass hut n. . grasshopper n. . grave n. . green -,see:. greet -,see: 2 . grill v. . hut n. . hyena n. . hyrax n. . loincloth, woman's clothes (gen.) n. . long adj. . look at v. . look for v. . look like -(2),see: 2 . loosen v. (1). lorry -,see:. lose sth. v.t/i. . louse n. . love v. . lungs n. . overpower -,see:. m i noon -,see:. nose n. . o orange n. . ordeal n. . orphan n. . ostrich n. . other det. . outside adv. . soup n. . sour v.i. ,see:. tick n. . tie v. ; w r spirit n. . ripe p.p. ,see:; v. ; v. . ripen v. ; v.i. . river n. ; n. . road n. . sow v.pl. . -,see:; tin n. . where? adv. . v. ; tired v. . whip n. . v. (2). speak tobacco n. . whistling n. . -,see: 2 . spear today n. . white adj. . n. . tomato (bitter) n. ,see:. white egret n. . spend a long time v. (2). sperm spider spin spinning stick n. . v.  1 . n. . tongs -,see:. tomorrow n. . who? quest. .
		num. .	owl	n. .
	machete onion	n. . n. .	owner	n. . n. .
	mahogany n. . open v. .	millet	n. (2);
	maid opening of granary n. . -,see:.		n. .
	maize	n. .	millet sp. n. .
	malaria male sixty	n. . adj. . num. .	minstrel mirror p	-,see:. n. .
	hard harmattan n. . v. . harness n. ,see:. harvest -,see: 2 ; v. (2); v. ; v.t. (2). hat n. . lake n. . lame n. . lamp n. . man n. . mango n. . mantis -,see:. many adv. . mare -,see:. market n. . marriage n. . marrow n. . mason wasp n.col. . masquerade n. . mat n. . mate v. (2). measles n. . measure v.  2 . meat n. . medicine n. . meet v. . melt v. . menstruation n. (2). middle -,see:; n. (1). migrate v. . milk -,see: 2 ; plough v. . -,see:; palm of hand n. . palm oil n. . palm tree n. . skin n. ; n. (1); v. . panther n. . parrot n. . papaw n. . pay v. . pebble n. . peel n. ; v. . play n. . scratch penis n. . penis sheath n. . pepper n. . pestle n. . pick (banana, mango) v. . pig n. . pigeon n. ; n. . place n. . plait hair v. . plant n. ; v. . sacrifice n. (1). saddle -,see:; n. . saliva n. . salt n. . sand n. . saw n. . say v.  2 . scar n. . scatter v. (1). scorpion n. . scrape (clean) v. . slip n. . slippers n. . small adj. . smash v. . throat n. . smell n. ; throw v. . v. ; thunder n. . v. . smithy -,see:. smoke n. . smoke (tobacco) -,see: 1 . smooth v. . ugly n. . ululation n. .	flesh flour flow flower fly fly away foam fold follow food foot headpad heal heap hear heart heavy hedgehog n. . n. . n. . v. . n. . n.col. . v. . n. . v. . v. . -,see:. n. . n. . n. . n. . v. . n. . v. . heel n. . he-goat n. . help v. . herbalist n. . here adv. . hiccup n. . hide v.t/i. (2). know v. . kunu n. . last year adv. . laugh v. ; v. . sew v. . mix v. . molar n. . money n. . plum n. . poison n. . poor n. . mongoose n. . monkey porcupine n. . n. . moon possess v. . n. . possessor n. . moonshine -,see:. morning pot n. . n. . mortar n. . pot for fetching water n. . pot gen. n. . mosquito n.col. . mother potash n. . n. . mother goat n. ,see:. mountain n. . mouth n. . move, stir (int.) n. . much adv. . mucus n. . mudfish n. . mumps n. . murder n.col. (1). murderer -,see:. mushroom n. . musician seventy num. . -,see:. potter -,see:. pound v. . pour v. (1). pray god v. . pregnancy -,see:; n. . press v. (2). prick v. . priest n. . profit n. . prostitute n. . protect v. . see v. . seed n. . seize v. . sell v. . send (so do sth) v. (1). separate v. . servant strengthen v. . n. . sesame strike fire v. . n. . set a trap -,see:. set bones strip off v. . strong u l s v. . -,see:. seven num. . seventeen num. . struggle n. . suck v. .
	pluck out (leaves) v. .	forget shade	vx. . n. .
		English -Gùùs wordlist English -Gùùs wordlist English -Gùùs wordlist English -Gùùs wordlist English -Gùùs wordlist	26 27 30 31 32

footprint -,see:. forehead -,see:. forge v. . giraffe -,see:. girl n. . give v. . give back v. . give birth, deliver -(3),see:. glue v. . go v. . go up, mount v. (1). goat n. . god n. (2). gold n. . good n. ; v. . gown -,see:. granary n. . grandchildren n. . grandfather n. (1). grind v. . grinding stone -,see:; n. . ground n. . groundnut n. . grow v. . guest n. . guinea-fowl n. . guitar made of reed n. . guitar (metal) n. . gum tree sp. n. . gun n. . gunpowder -,see:. Gùùs n. . h habit v. . hair n.col. . hammer n. . hand, arm n. . handle n. . handle of pot -,see:. hang v.t/i. . hate v. . hawk -,see:. he pro. . head n. (1). high v. . hippopotamus -,see:. hit v. (1). increase v. . indigo n. . in-laws n. (2). insane adj. . insect n. . inside -,see:. intestines, guts n. . into prep. . iron n. . itch v. . itili n. . ivory -,see:. j jackal -,see:. jaw n. . jealousy n. . journey n. . judge -,see:. jujube tree n. . jump v.  1 . jumper n. . k kapok -,see:. kid n. . kidney n. . kill v. . kiln n. . kitchen n. . kite (black -) n. . knead v. . knee n. . kneel down v. . knife n. . land v. . language n. . large termite n. . lazy adj. . leak, drip v. . learn v. . leather n. (1). puff-adder n. . pull v. (1). pull out v.  2 (1). red adj. . reed n. . refuse v. . remain, become v. . remember vx. . remove v.  2 (1). repeat -,see:. rest v. . return v.i. . ribs n.col. . rice n. . rich -,see:. ridge n. . right n. . right side n. . ring n. . robe -,see:. roll v. . roof -,see:; n. . room n. . root n. . rope (gen.) n. . rot v. . round adj. . rub v. . rubbish heap n. . ruin n. . ruins n. . rule n. . run v. . v. . season n. . seat -,see:. shrub producing red berries n. . shut, close v. . sickle n. . silk cotton tree n. . silver n. . sing -,see:. singer -,see:. sister-in-law n. . sit down v. . six num. . sixteen num. . skink-lizard n. . skull n. ,see:. sky n. . slaughter v.t. (3). slave n.col. . slavery n. . sleep v. . sling n. . snail n. . snake n. . snap (a thread) v. . snare n. . spit -,see:. spoon n. . spread v. . sprout v. . squat v. . squeeze, wring out v. . squirrel n. . stab v. . stalks n. . stallion -,see:. stand v. . stand up v. . star n. . stick n. ; v. . sting v. . sting, quill of insect n. (2). stirring stick n. . stomach n. . stone n. . stop v. . stork n. . straight n. . straight on id. . straw n. . sue v. . suffer v. . sugar cane -,see:; n. . sunshine -,see:. swallow v. . swarm of bees -,see:. swear v. . sweat n. . sweep v. . sweet potato n. . swell v. . swimming n. . sword n. . tear v. . tears n. . tell v.  2 . ten num. . termite n. . termite hill -,see:. testicle n. . thank v. . theft n. . there adv. . they pro. . thick id. . thief n. . thigh n. . thin id. . thing n. . think v. . thirst n. . thirteen num. . thirty num. . this year adv. . thorn n. . thou pro. . thousand num. . thread n. . three num. . thresh v. (2). n. . tongue n. . tooth n. . tortoise n. . totem n. . touch v. . town n.col. . track n. . trade v. . trap n. . tree n. . tremble v. . trousers n. . trunk of tree n. (2). truth n. . try v. . turban n. . turkey n. . turn v. . turn round v. . tusk -,see:. tuwo n. . twelve num. . twenty num. . twenty-one num. . twins n.col. . twist v. (1). two num. . two hundred num. . uncle n. ; n. . under v. . unload v. . unroll v. . untie v. . urinate v. . urine n. . -,see:. wash v. ; v. . wasp n.col. . water n. . water melon n. . water place -,see:. we pro. . weapon n. ; n. . wear n. . weave v. ; v. . weaver -,see:. weed v. . well n. . wet v.t/i. . what? quest. . wheat n. . when? adv. . wide v. . widen v. . widow -,see:. widower n. . wife n. (1). wind n. . wing n. . winnow n. ; v. . wipe v. . witch -,see:. witchcraft n. . with conj. . woman n. (1). wood n. . work n. . world n. . worm n. . wound n. . wrap up v. . write v. . y yam n. . yellow adj. . yesterday n. . you (pl.) pro. . young adj. . younger sister n. .

This corresponds to a shallow phonological analysis corroborated by oppositions such as : , he is harvesting ; vs., they are harvesting.

 may be the causative of  (Vn ), unroll.

Cf. Hausa .

English -Gùùs wordlist


Hervé Cardot

Peggy Cénac

Jean-Marie Monnez

A fast and recursive algorithm for clustering large datasets with k-medians

Keywords: averaging, high dimensional data, k-medoids, online clustering, partitioning around medoids, recursive estimators, Robbins Monro, stochastic approximation, stochastic gradient

Clustering with fast algorithms large samples of high dimensional data is an important challenge in computational statistics. A new class of recursive stochastic gradient algorithms designed for the k-medians loss criterion is proposed. By their recursive nature, these algorithms are very fast and are well adapted to deal with large samples of data that are allowed to arrive sequentially. It is proved that the stochastic gradient algorithm converges almost surely to the set of stationary points of the underlying loss criterion. A particular attention is paid to the averaged versions which are known to have better performances. A data-driven procedure that permits a fully automatic selection of the value of the descent step is also proposed. The performance of the averaged sequential estimator is compared on a simulation study, both in terms of computation speed and accuracy of the estimations, with more classical partitioning techniques such as k-means, trimmed k-means and PAM (partitioning around medoids). Finally, this new online clustering technique is illustrated on determining television audience profiles with a sample of more than 5000 individual television audiences measured every minute over a period of 24 hours.

Introduction

Clustering with fast algorithms large samples of high dimensional data is an important challenge in computational statistics and machine learning, with applications in various domains such as image analysis, biology or computer vision. There is a vast literature on clustering techniques and recent discussions and reviews may be found in [START_REF] Jain | Data clustering: a review[END_REF] or [START_REF] Gan | Data Clustering: Theory, Algorithms, and Applications[END_REF]. Moreover, as argued in [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF], the development of fast algorithms is even more crucial when the computation time is limited and the sample is potentially very large, since fast procedures will be able to deal with a larger number of observations and will finally provide better estimates than slower ones. See also [START_REF] García-Treviño | Online wavelet-based density estimation for non-stationary streaming data[END_REF] for recent applications of recursive estimation procedures for streaming data.

We focus here on partitioning techniques which are able to deal with large samples of data, assuming the number k of clusters is fixed in advance. The most popular clustering methods are probably the non sequential [START_REF] Forgy | Cluster analysis of multivariate data: efficiency vs. interpretability of classifications[END_REF]) and the sequential [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF]) versions of the k-means algorithms. They are very fast and only require O(kn) operations, where n is the sample size. They aim at finding local minima of a quadratic criterion and the cluster centers are given by the barycenters of the elements belonging to each cluster. A major drawback of the k-means algorithms is that they are based on mean values and, consequently, are very sensitive to outliers.

Such atypical values, which may not be uncommon in large samples, can deteriorate significantly the performances of these algorithms, even if they only represent a small fraction of the data as explained in [START_REF] García-Escudero | A review of robust clustering methods[END_REF] or [START_REF] Croux | Machine learning and robust data mining[END_REF]. The k-medians approach is a first attempt to get more robust clustering algorithms; it was suggested by [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] and developed by [START_REF] Kaufman | Finding groups in data: an introduction to cluster analysis[END_REF]. It consists in considering criteria based on least norms instead of least squared norms, so that the cluster centers are the spatial medians, also called geometric or L 1 -medians (see [START_REF] Small | A survey of multidimensional medians[END_REF]), of the elements belonging to each cluster. Note that it has been proved in [START_REF] Laloë | l 1 -quantization and clustering in Banach spaces[END_REF] that under general assumptions, the minimum of the objective function is unique. Many algorithms have been proposed in the literature to find this minimum.

The most popular one is certainly the PAM (partitioning around medoids) algorithm which has been developed by [START_REF] Kaufman | Finding groups in data: an introduction to cluster analysis[END_REF] in order to search for local minima among the elements of the sample. Its computation time is O(kn 2 ) and as a consequence, it is not very well adapted for large sample sizes. Many strategies have been suggested in the literature to reduce the computation time of this algorithm. For example subsampling (see e.g the algorithm CLARA in [START_REF] Kaufman | Finding groups in data: an introduction to cluster analysis[END_REF] and the algorithm CLARANS in [START_REF] Ng | Clarans: a method for clustering objects for spatial data mining[END_REF]), local distances computation [START_REF] Zhang | A new and efficient k-medoid algorithm for spatial clustering[END_REF]) or the use of weighted distances during the iteration steps [START_REF] Park | A simple and fast algorithm for k-medoids clustering[END_REF]), allow one to reduce significantly the computation time without deteriorating the accuracy of the estimated partition.

Trimmed k-means (see [START_REF] García-Escudero | A general trimming approach to cluster analysis[END_REF], 2010) and references therein) is also a popular modification of the k-means algorithm that is more robust (see [START_REF] García-Escudero | Robustness properties of k-means and trimmed k-means[END_REF]) in the sense that it has a strictly positive breakdown point, which is not the case for the k-medians. Note however that the breakdown point is a pessimistic indicator of robustness since it is based on the worst possible scenario. For a small fraction of outliers whose distance is moderate to the cluster centers, k-medians remain still competitive compared to trimmed k-means as seen in the simulation study. Furthermore, from a computational point of view, performing trimmed k-means needs to sort the data and this step requires O(n 2 ) operations, in the worst cases, at each iteration so that its execution time can get large when one has to deal with large samples.

Borrowing ideas from [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] and [START_REF] Hartigan | Clustering algorithms[END_REF] who have first proposed sequential clustering algorithms and [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient approach[END_REF] who have studied the properties of stochastic gradient algorithms that can give efficient recursive estimators of the geometric median in high dimensional spaces, we propose in this paper a recursive strategy that is able to estimate the cluster centers by minimizing a k-medians type criterion. One of the main advantages of our approach, compared to previous ones, is that it can be computed in only O(kn) operations so that it can deal with very large datasets and is more robust than the k-means. Note also that by its recursive nature, another important feature is that it allows automatic update and does not need to store all the data.

A key tuning parameter in our algorithm is the descent step value. We found empirically that reasonable values are given by the empirical L 1 loss function. We thus also consider an automatic two steps procedure in which one first runs the sequential version of the k-means in order to approximate the value of the L 1 loss function and then run our stochastic k-medians with an appropriate descent step.

The paper is organized as follows. We first fix notations and present our algorithm. In the third Section, we state the almost sure consistency of the stochastic gradient k-medians to a stationary point of the underlying objective function. The proof heavily relies on [START_REF] Monnez | Almost sure convergence of stochastic gradient processes with matrix step sizes[END_REF]. In Section 4, we compare on simulations the performance of our technique with the sequential k-means, the PAM algorithm and the trimmed k-means when the data are contaminated by a small fraction of outliers.

We note that applying averaging techniques (see [START_REF] Polyak | Acceleration of stochastic approximation[END_REF]) to our estimator, with a small number of different initializations points, is a very competitive approach even for moderate sample sizes with computation times that are much smaller. In Section 5, we illustrate our new clustering algorithm on a large sample, of about 5000 individuals, in order to determine profiles of television audience. A major difference with PAM is that our algorithm searches for a solution in all the space whereas PAM, and its refinements CLARA and CLARANS, only look for a solution among the elements of the sample. Consequently, approaches such as PAM are not adapted to deal with temporal data presented in Section 5 since the data mainly consist of 0 and 1 indicating that the television is switched on or switched off during each minute of the day. Proofs are gathered in the Appendix.

2 The stochastic gradient k-medians algorithm

Context and definitions

Let (Ω, A, P) be a probability space. Suppose we have a sequence of independent copies Z 1 , . . . , Z n of a random vector Z taking values in R d . The aim is to partition Ω into a finite number k of clusters Ω 1 , . . . , Ω k . Each cluster Ω i is represented by its center, which is an element of R d denoted by θ i .

From a population point of view, the k-means and k-medians algorithms aim at finding local minima of the function g mapping R dk to R and defined as follows, for x = (x 1 , . . . , x k ) with for all i,

x i ∈ R d , g(x) def = E min r=1,...,k Φ( Z -x r ) , (1)
where Φ is a real, positive, continuous and non-decreasing function and the norm . in R d takes account of the dimension d of the data, for z ∈ R d , z 2 = d -1 d j=1 z 2 j . The particular case Φ(u) = u 2 , leads to the classical k-means algorithm, whereas φ(u) = |u| leads to the k-medians.

Before presenting our new recursive algorithm, let us introduce now some notations and recall the recursive k-means algorithm developed by [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF]. Let us denote by I r the indicator function,

I r (z; x) = k j=1 1 1 { z-x r ≤ z-x j } ,
which is equal to one when x r is the nearest point to z, among the set of points x i , i = 1, . . . , k.

The k-means recursive algorithm proposed by MacQueen (1967) starts with k arbitrary groups, each containing only one point, X 1 1 , . . . , X k 1 . Then, at each iteration, the cluster centers are updated as follows,

X r n+1 = X r n -a r n I r (Z n ; X n ) (X r n -Z n ) , (2)
where for n ≥ 2, a r n = (1 + n r ) -1 and n r = 1 + n-1 =1 I r (Z ; X ) is just the number of elements allocated to cluster r until iteration n -1. For n = 1, let a r 1 = 1 2 . This also means that X r n+1 is simply the barycenter of the elements allocated to cluster r until iteration n,

X r n+1 = 1 1 + n =1 I r (Z ; X ) X r 1 + n =1 I r (Z ; X )Z .
The interesting point is that this recursive algorithm is very fast and can be seen as a Robbins-Monro procedure.

Stochastic gradient k-medians algorithms

Assuming Z has an absolutely continuous distribution, we have

P( Z -x i = Z -x j ) = 0, for any i = j and x i = x j .
Then, the k-medians approach relies on looking for minima, that may be local, of the function g which can also be written as follows, for any x such that

x j = x i when i = j, g(x) = k r=1 E[I r (Z; x) Z -x r ]. (3)
In order to get an explicit Robbins-Monro algorithm representation, it remains to exhibit the gradient of g. Let us write g in integral form. Denoting by f the density of the random variable Z, we have,

g(x) = k r=1 R d \{x r } I r (z; x) z -x r f (z) dz.
For j = 1, . . . , d, it can be checked easily that

∂ ∂x r j ( z -x r ) = x r j -z j z -x r ,
and since

I r (z; x) x r j -z j z -x r f (z) ≤ f (z), for z = x r , the partial derivatives satisfy, ∂g ∂x r j (x) = R d \{x r } I r (z; x) x r j -z j z -x r f (z) dz. We define, for x ∈ R dk , ∇ r g(x) def = E I r (Z; x) x r -Z x r -Z . (4)
We can now present our stochastic gradient k-medians algorithm. Given a set of

k distinct initialization points in R d , X 1 1 , • • • , X k 1
, the set of k cluster centers is updated at each iteration as follows. For r = 1, . . . , k, and n ≥ 1,

X r n+1 = X r n -a r n I r (Z n ; X n ) X r n -Z n X r n -Z n (5) = X r n -a r n ∇ r g(X n ) -a r n V r n , with X n = (X 1 n , • • • , X k n ), and V r n def = I r (Z n ; X n ) X r n -Z n X r n -Z n -E I r (Z n ; X n ) X r n -Z n X r n -Z n F n , F n = σ(X 1 , Z 1 , . . . , Z n-1
). The steps a r n , also called gains, are supposed to be F n -measurable. We denote by ∇g(x) = (∇ 1 g(x), . . . , ∇ k g(x)) the gradient of g and define

V n def = (V 1 n , . . . V k n ) . Let A n be the diagonal matrix of size dk × dk, A n =                  a 1 n . . . a 1 n . . . a k n . . . a k n                  , each a r
n being repeated d times. Then, the k-medians algorithm can be written in a matrix way,

X n+1 = X n -A n ∇g(X n ) -A n V n , (6)
which is a classical stochastic gradient descent.

Tuning the stochastic gradient k-medians and its averaged version

The behavior of algorithm (5) depends on the sequence of steps a r n , r ∈ {1, . . . , k} and the vector of initialization X 1 . These two sets of tuning parameters play distinct roles and we mainly focus on the choice of the step values, noting that, as for the k-means, the estimation results must be compared for different sets of initialization points in order to get a better estimation of the cluster centers.

Assume we have a sample of n realizations Z 1 , . . . , Z n of Z and a set of initialization points of the algorithm, the selected estimate of the cluster centers is the one minimizing the following empirical risk,

R(X n ) = 1 n n i=1 k r=1 I r (Z i ; X n ) Z i -X r n (7)
Let us denote by n r = 1 + n-1 =1 I r (Z ; X ) the number of updating steps for cluster r, until iteration n -1, for r ∈ {1, . . . , k}. A classical form of the descent steps a r n can be given by

a r n =    a r n-1 if I r (Z n ; X n ) = 0, c γ (1 + c α n r ) α otherwise, (8)
where c γ , c α and 1/2 < α ≤ 1 control the gain.

Adopting an asymptotic point of view, one could believe that α should be set to α = 1 with suitable constants c α and c γ , which are unknown in practice, in order to attain the optimal parametric rates of convergence of Robbins Monro algorithms (see e.g. [START_REF] Duflo | Random iterative models[END_REF], Th. 2.2.12). Our experimental results on simulated data have shown that the convergence of algorithm (5) with descent steps defined in ( 8) is then very sensitive to the values of the parameters c γ and c α which have to be chosen very carefully. A simulation study performed in the particular case k = 1 by [START_REF] Cardot | Stochastic approximation to the multivariate and the functional median[END_REF] showed that the direct approach could lead to inaccurate results and is nearly always less effective than the averaged algorithm presented below, even for well chosen descent step values. From an asymptotic point of view, it has been proved in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient approach[END_REF] that the averaged stochastic gradient estimator of the geometric median, corresponding to k = 1, is asymptotically efficient under classical assumptions. Intuitively, when the algorithm is not too far from the solution, averaging allows to decrease substantially the variability of the initial algorithm which oscillates around the true solution and thus improves greatly its performances.

Consequently, we prefer to introduce an averaging step (see for instance [START_REF] Polyak | Acceleration of stochastic approximation[END_REF] or [START_REF] Pelletier | Asymptotic almost sure efficiency of averaged stochastic algorithms[END_REF]), which does not slow down the algorithm and provides an estimator which is much more effective. Our averaged estimator of the cluster centers, which remains recursive, is defined as follows, for r ∈ {1, . . . , k}, n ≥ 1, and for the value X r n+1 obtained by combining ( 5) and ( 8),

Xr n+1 =      Xr n if I r (Z n ; X n ) = 0, n r Xr n + X r n+1 n r + 1 otherwise, (9)
with starting points Xr 1 = X r 1 , r = 1, . . . , k. Then standard choices (see e.g. Bottou (2010) and references therein) for α and c α are α = 3/4 and c α = 1, so that one only needs to select values for c γ .

3 Almost sure convergence of the algorithm

A convergence theorem

The following theorem is the main theoretical result of this paper. It states that the recursive algorithm defined in (6) converges almost surely to the set of stationary points of the objective function defined in (3), under the following assumptions.

(H1) a) The random vector Z is absolutely continuous with respect to Lebesgue measure. b) Z is bounded:

∃K > 0: Z ≤ K a.s. c) ∃C: ∀x ∈ R d such that x ≤ K + 1, E 1 Z-x < C. (H2) a) ∀n ≥ 1, min r a r n > 0. b) max r sup n a r n < min( 1 2 , 1 8C ) a.s. c) ∞ n=1 max r a r n = ∞ a.s. d) sup n maxr a r n minr a r n < ∞ a.s. (H3) k r=1 ∞ n=1 (a r n ) 2 < ∞ a.s. (H3') k r=1 ∞ n=1 E (a r n ) 2 I r (Z n ; X n ) < ∞.
Theorem 1. Assume that X 1 is absolutely continuous and that X r 1 ≤ K, for r = 1, . . . , k. Then under Assumptions (H1a,c), (H2a,b), (H3) or (H3'), g(X n ) and

k r=1 ∞ n=1 a r n ∇ r g(X n ) 2
converge almost surely.

Moreover, if the hypotheses (H1b) and (H2c,d) are also fulfilled then ∇g(X n ) and the distance between X n and the set of stationary points of g converge almost surely to zero.

A direct consequence of Theorem 1 is that if the set of stationary points of g is finite, then the sequence (X n ) n necessarily converges almost surely towards one of these stationary points because X n+1 -X n converges almost surely towards zero. By Cesaro means arguments, the averaged sequence Xn also converges almost surely towards the same stationary point.

Comments on the hypotheses

Note first that if the data do not arrive online and X 1 is chosen randomly among the sample units then X 1 is absolutely continuous and X r 1 ≤ K, for r = 1, . . . , k under (H1a,b). Moreover, the absolute continuity of Z is a technical assumption that is required to get decomposition (3) of the L 1 error. Proving the convergence in the presence of atoms would require to decompose this error in order to take into account the points which could have a non-null probability to be at the same distance. Such a study is clearly beyond the scope of the paper. Note however that in the simple case k = 1, it has been established in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient approach[END_REF] that the stochastic algorithm for the functional median is convergent provided that the distribution, which can be a mixture of a continuous and a discrete distribution, does not charge the median.

Hypothesis (H1c) is a stronger version of a more classical hypothesis needed to get consistent estimators of the spatial median (see [START_REF] Chaudhuri | On a geometric notion of quantiles for multivariate data[END_REF]). As noted in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient approach[END_REF], it is

Simulation protocol

Simulation 1 : a simple experiment in R 2

We first consider a very simple case and draw independent realizations of variable Z,

Z = (1 -) (π 1 Z 1 + π 2 Z 2 + π 3 Z 3 ) + δ z , (10)
which is a mixture, with weights π 1 = π 2 = π 3 = 1/3, of three bivariate random Gaussian vectors Z 1 , Z 2 and Z 3 with mean vectors µ 1 = (-3, -3), µ 2 = (3, -3) and µ 3 = (4.5, -4.5) and covari-

ance matrices V ar(Z 1 ) =   2 1 1 3   , V ar(Z 2 ) =   3 1 1 2   and V ar(Z 3 ) =   2 -1 -1 3   .
Point z = (-14, 14) is an outlier and parameter controls the level of the contamination. A sample of n = 450 realizations of Z is drawn in Figure 1.

Simulation 2 : larger dimension with different correlation levels

We also performed a simulation experiment, with a mixture of three Gaussian random variables as in (10), but in higher dimension spaces with correlation levels that vary from one cluster to another. Now, Z 1 , Z 2 and Z 3 are independent multivariate normal distributions in R d , with means µ 1j = 2 sin(2πj/(d-1)), µ 2j = 2 sin(2π/3+2πj/(d-1)), and µ 3j = 2 sin(4π/3+2πj/(d-1)),

for j = 1, . . . , d. The covariance functions Cov(Z ij , Z i ) = 1.5ρ |j-| i
, for j, ∈ 1, . . . , d and i ∈ {1, 3} are controlled by a correlation parameter ρ, with ρ 1 = 0.1, ρ 2 = 0.5 and ρ 3 = 0.9. Note that this covariance structure corresponds to autoregressive processes of order one with autocorrelation ρ. As before, δ z = (4, . . . , 4) ∈ R d plays the role of an outlying point. A sample of n = 36 independent realizations of Z, without outliers, is drawn in Figure 2 for a dimension d = 50.

L 1 error and sensitivity to parameter c

As noted in [START_REF] Bryant | Asymptotic behaviour of classification maximum likelihood estimates[END_REF], comparing directly the distance of the estimates from the cluster centers µ 1 , µ 2 and µ 3 may not be appropriate to evaluate a clustering method. Our comparison is thus first made in terms of the value of the empirical L 1 error (7) which should be as small as possible. For all methods, we considered that there were k = 3 clusters. We first study the simple case of Simulation 1. The empirical mean L 1 error of the PAM algorithm, the k-means and the averaged k-medians, for 50 replications of samples with sizes n = 250 and a contamination level = 0.05 is presented in Figure 3. The number of initialization points equals 10 for both the k-means and the k-medians. When the descent parameter c equals 0, the initialization point is given by the estimated centers by the k-means, so that the empirical L 1 error corresponds in that case to the k-means error, which is sightly above 2.31. We first note that this L 1 error is always larger, even if the contamination level is small, than the PAM and the k-medians constant and is clearly smaller than the L 1 error of the PAM algorithm. This means that, even if the sample size is relatively small (n = 250), the recursive k-medians can perform well for values of c which are of the same order of the L 1 error. We now consider 50 replications of samples drawn from the distribution described in simulation 2, with n = 500, d = 50 and = 0.05. The number of initialization points for the k-means and the k-medians is now equal to 25 and the empirical mean L 1 error is presented in Figure 4. We first note that the performances of the PAM algorithm clearly decrease with the dimension. The k-means performs better even if there are 5% of outliers and if it is not designed to minimize an L 1 error criterion. This can be explained by the fact that PAM, as well as CLARA and CLARANS, look for a solution among the elements of the sample. Thus these approaches can hardly explore all the dimensions of the data when d is large and n is not large enough. On the other hand, the k-medians and the k-means look for a solution in all R d and are not restricted to the observed data and thus provide better results in terms of L 1 error. As before, we can also remark that the minimum error, which is around 1.36, is attained for c in the interval [0.5, 3]. As a first conclusion, it appears that for large dimensions the k-medians can give results which are much better than PAM in terms of empirical L 1 error. We can also note that the averaged recursive k-medians is not very sensitive to the choice of parameter c provided its value is not too far from the minimum value of the L 1 error. Thus we only consider, in the following subsection, the data-driven version of our averaged algorithm described in Section 2.3 in which the value of c is chosen automatically, its value being the empirical L 1 error of the recursive k-means. This data-driven k-medians algorithm can be summarized as follows 1. Run the k-means algorithm and get the estimated centers.

2. Set c as the value of the L 1 error of the k-means, evaluated with formula (7).

3. Run the averaged k-medians defined by ( 5), ( 8) and ( 9), with c computed in Step 2 and c α = 1.

Classification Error Rate

We now make comparisons in terms of classification error measured by the Classification Error Rate (CER) introduced by [START_REF] Chipman | Hybrid hierarchical clustering with applications to microarray data[END_REF] and defined as follows. For a given partition P of the sample, let 1 P (i,i ) be an indicator for whether partition P places observations i and i in the same group. Consider a partition Q with the true class labels, the CER for partition P is defined as

CER = 2 n(n -1) i>i 1 P (i,i ) -1 Q(i,i ) . (11)
The CER equals 0 if the partitions P and Q agree perfectly whereas a high value indicates disagreement. Since PAM, the k-means and our algorithm are not designed to detect outliers automatically, we only evaluate the CER on the non-outlying pairs of elements i and i of the sample.

We present in Figure 6, results for 500 replications of Simulation 1, with a sample size n = 500 and no outliers ( = 0). We note, in this small dimension context with no contamination, that the L 1 errors are comparable. Nevertheless, in terms of CER, the PAM, the k-means and the data-driven k-medians algorithms have approximately the same performances. For the trimmed k-means, the results are not as effective, since this algorithm automatically classifies 5% of the elements of the sample as outliers.

We then consider the same experiment as before, the only difference being that there is now a fraction of = 0.05 of outliers. The results are presented in Figure 7. The k-means algorithm is clearly affected by the presence of outliers and both its L 1 error and its CER are now much nel and when they watch television. Médiamétrie has a panel of about 9000 individuals equipped at home with sensors that are able to record and send the audience of the different television channels.

Among this panel, a sample of around 7000 people is drawn every day and the television consumption of the people belonging to this sample is sent to Médiamétrie at night, between 3 and 5 am.

Online clustering techniques are then interesting to determine automatically, the number of clusters being fixed in advance, the main profiles of viewers and then relate these profiles to socio-economic variables. In these samples, Médiamétrie has noted the presence of some atypical behaviors so that robust techniques may be helpful. We are interested in building profiles of the evolution along time of the total audience for people who watched television at least one minute on the 6th September 2010. About 1600 people, among the initial sample whose size is around 7000, did not watch television at all this day, so that we finally get a sample of n = 5422 individual audiences, aggregated along all television channels and measured every minute over a period of 24 hours. An observation Z i is a vector belonging to CLARA and CLARANS) are not really interesting in this context since they will return centers of the form of the profiles drawn in Figure 10 which are, in great majority, constituted of 0 and 1 and are consequently difficult to interpret. Furthermore, the dimension being very large, d = 1440, these algorithms which do not consider all the dimensions of the data, as seen in the simulation study, will lead to a minimum value of the empirical L 1 error (7) that will be substantially larger than for the k-means and our recursive k-medians. Indeed, at the optimum, the value of the L 1 empirical error is 0.2455 for the k-medians, 0.2471 for the k-means and 0.2692 for PAM.

The cluster centers, estimated with our averaged algorithm for k = 5, with a parameter value

≤ k r=1 B r -A r E [ ∇ r Z -C r -∇ r Z -A r ] ,
hence since

∇ r Z -C r -∇ r Z -A r = C r -Z C r -Z - A r -Z A r -Z ≤ 2 C r -A r A r -Z ,
one gets, with (H1c)

(1) ≤ 2 k r=1 B r -A r C r -A r E 1 Z -A r ≤ 2C k r=1 B r -A r 2 = 2C B -A 2 .
The definition of V r n implies that E[V r n |F n ] = 0 and hence E[V n |F n ] = 0.

Step 5: Proof of (A2b)

E A n V n 2 |F n = k r=1 E (a r n ) 2 V r n 2 |F n ≤ k r=1 (a r n ) 2 E I r (Z n ; X n ) X r n -Z n 2 X r n -Z n 2 F n ≤ k r=1 (a r n ) 2 .
Hence assuming (H3), one gets

E ∞ n=1 E A n V n 2 |F n < ∞.
In the case when (H3') holds instead of (H3), one has

E ∞ n=1 E A n V n 2 |F n ≤ ∞ n=1 k r=1 E (a r n ) 2 I r (Z n ; X n ) < ∞.
Consequently,

∞ n=1 E A n V n 2 |F n < ∞ a.s,
which concludes the proof.

Figure 1 :(Figure 2 :

 12 Figure 1: Simulation 1. A sample of n = 450 realizations of Z. An outlier is located at position (-14,14).

Figure 3 :

 3 Figure 3: Simulation 1 with = 0.05 and n = 250. Mean empirical L 1 error (over 50 replications) for the PAM algorithm (dashed line), the k-means (c = 0) and the stochastic k-medians (bold line), for c ∈]0, 10].

Figure 4 :

 4 Figure 4: Simulation 2 with n = 500, d = 50, and = 0.05. The mean empirical L 1 error (over 50 replications) is represented for the PAM algorithm (dashed line), the MacQueen version of the k-means (c = 0) and the recursive k-medians estimator (bold line), for c ∈]0, 7].

Figure 5 :

 5 Figure 5: Simulation 2 with n = 1000, d = 200, = 0.05, and Z multiplied by a factor 10. The mean L 1 loss function (over 50 replications) is represented for the PAM algorithm (dashed line), the MacQueen version of the k-means (c = 0) and our recursive k-medians estimator (bold line), for c ∈]0, 40].

Figure 6 :Figure 7 :Figure 8 :Figure 9 :

 6789 Figure6: Simulation 1 with = 0 and n = 500. On the left, the L 1 empirical error. On the right, CER for the k-means, PAM, the data-driven recursive k-medians algorithm (kmed) and the trimmed k-means (tkm) with a trimming level set to 0.05.

Figure 10 :

 10 Figure 10: A sample of 5 observations of individual audience profiles measured every minute over a period of 24 hours.

  d , with d = 1440, each component giving the fraction of time spent watching television during the corresponding minute of the day. A sample of 5 individual temporal profiles is drawn in Figure 10. Clustering techniques based on medoids and representative elements of the sample (e.g. PAM,

Figure 11 :B

 11 Figure 11: Cluster centers for temporal television audience profiles measured every minute over a period of 24 hours.

Acknowledgements. We thank the anonymous referees for their valuable suggestions. We also thank the Médiamétrie company for allowing us to illustrate our sequential clustering technique with their data.

closely related to small ball properties of Z and is fulfilled when

for a constant κ that does not depend on x and small enough. This implies in particular that hypothesis (H1c) can be satisfied only when the dimension d of the data satisfies d ≥ 2.

Hypotheses (H2) and (H3) or (H3') deal with the stepsizes. Considering the general form of gains a r n given in (8), they are fulfilled when the sizes n r of all the clusters grow to infinity at the same rate and α ∈]1/2, 1].

A simulation study

We first perform a simulation study to compare our recursive k-medians algorithm with the follow- Comparisons are first made according to the value of the empirical L 1 error (7) which must be as small as possible. We note that the results of our averaged recursive procedure defined by ( 5), ( 8) and ( 9) are very stable when the value of the tuning parameter c γ is not too far from the minimum value of the L 1 error, with α = 3/4 and c α = 1. This leads us to propose, in Section 4.2, an automatic clustering algorithm which consists in first approximating the L 1 error with a recursive k-means and then performing our recursive k-medians with the selected value of c γ , denoted by c in the following. We have no mathematical justification for such an automatic choice of the tuning parameter c but it always worked well on all our simulated experiments. This important point of our algorithm deserves further investigations that are beyond the scope of the paper. Note however that this intuitive approach will certainly be ineffective when the dispersion is very different from one group to another. It would then be possible to consider refinements of the previous algorithm which would consist in considering different values of tuning parameter c for the different clusters.

We only present here a few simulation experiments which highlight both the strengths and the drawbacks of our recursive k-medians algorithm.

Computation time

The codes of all the considered estimation procedures call C routines and provide the same output. Mean computation times, for 100 runs, various sample sizes and numbers of clusters are reported in Table 1. They are based on one initialization point. When the sample size or the dimension increases, the computation time is even more critical.

For instance, when d = 1440 and n = 5422 as in the example of Section 5, our data-driven recursive k-medians estimation procedure is at least 500 times faster than the trimmed k-means. It takes 5.5 seconds for the sequential k-means to converge and then about 3.0 seconds for the averaged kmedians, whereas it takes more than 5700 seconds for the trimmed k-means.

Determining television audience profiles with k-medians

The Médiamétrie company provides every day the official estimations of television audience in France. Television consumption can be measured both in terms of how long people watch each chan-

Appendix : Proof of Theorem 1

The proof of Theorem 1 relies on the following light version of the main theorem in [START_REF] Monnez | Almost sure convergence of stochastic gradient processes with matrix step sizes[END_REF], section 2.1. The proof of Theorem 1 consists in checking that all the conditions of the following theorem are satisfied.

Theorem 2 [START_REF] Monnez | Almost sure convergence of stochastic gradient processes with matrix step sizes[END_REF]). Assuming (A1a) g is a non negative function;

(A1b) There exists a constant L > 0 such that, for all n ≥ 1,

(A1c) The sequence (X n ) is almost surely bounded and ∇g is continuous almost everywhere on the compact set containing (X n );

(A2) There exists four sequences of random variables

to the sequence (F n ) such that a.s.:

then the distance of X n to the set of stationary points of g converges almost surely to zero.

Proof of Theorem 1.

Let us now check that all the conditions in Theorem 2 are fulfilled in our context.

Step 1: proof of (A1b)

Let A = X n and B = X n+1 . Since X n is absolutely continuous with respect to Lebesgue measure, k r=1 I r (Z; A) = 1 a.s. and one gets

Consequently, we have

Step 2: Proof of the assertion: ∀n ≥ 1, for all r = 1, ...k, X r n ≤ K + 2 sup n a r n Let us prove by induction on n that for all n ∈ N * , for all r = 1, . . . , k, X r n ≤ K + 2 sup n a r n . This inequality is trivial for the case n = 1: X

Now in the case when K + a r n < X r n ≤ K + 2 sup n a r n , one gets

and then

Since for I r (Z n ; X n ) = 0, X r n+1 = X r n , it remains to deal with the unique index r such that I r (Z n ; X n ) = 1. In that case,

.

By (H1b) and from the inequalities a r n / X r n -Z n < 1 and Z n ≤ K < X r n , we have,

which leads to X r n+1 ≤ K + 2 sup n a r n and concludes the proof by induction.

Step 3: Proof of (A1c)

From the integral form ∂g ∂x r j (x) = R d \{x r } I r (z; x) x r j -z j z -x r f (z)dz, it is easy to see that ∂g ∂x r j is a continuous function of x.

Step 4: Proof of (A2a)